Grundlagen der lexikalischen Analyse und Automaten

Kontextsensitivität und Merkmale in LEX

• (): Dient der Gruppierung.
• {}: Gibt einen Wiederholungsbereich an.
• $: Das vorangehende Muster wird nur erkannt, wenn es am Zeilenende steht.
• ^: Außerhalb von Klammern zeigt dies an, dass das Muster nur am Zeilenanfang erkannt wird.

Funktionen und Variablen in PCLEX

• yylex(): Führt die lexikalische Analyse aus.
• yytext: Entspricht dem aktuellen Lexem.
• yyleng: Die Länge des aktuellen Lexems.
• yylval: Eine globale Variable für den semantischen Wert.
• yyerror(): Eine Funktion, die für die Ausgabe und Bearbeitung von Fehlern verantwortlich ist.

Nutzung und Aufgabe endlicher Automaten

Wozu dienen endliche Automaten?

Um Sprachen zu erkennen, die durch reguläre Ausdrücke beschrieben werden.

Andere Bezeichnungen

Endliche Automaten werden auch als Erkenner oder Akzeptoren bezeichnet.

Aufgabe eines endlichen Automaten

Er prüft, ob eine Zeichenkette den Regeln folgt, die durch einen regulären Ausdruck definiert wurden.

Arten und Darstellung von Automaten

Deterministische endliche Automaten (DFA)

Ein Automat, bei dem jeder Übergang von einem Zustand E aus ein eindeutiges Symbol erfordert; es gibt keine zwei Übergänge vom selben Zustand, die mit dem gleichen Symbol gekennzeichnet sind.

Darstellung eines AFN (NFA)

Die Darstellung erfolgt explizit durch eine Grafik der Übergänge mit den Parametern: Eingang (Zustand, Symbol) und Ausgang (Folgezustand).

Lexikalische Analyse und Implementierung

Bestandteile der Analyse zur Auswertung

Dazu gehören vorzeichenlose Integer-Konstanten, relationale Operatoren und individuelle Variablen.

Lexikalische Komponenten und Analysator

Die Umsetzung erfolgt mithilfe einer Übergangstabelle (TT).

Vor- und Nachteile endlicher Automaten

• Vorteile: Vielfältige Anwendungen, einfach zu programmieren (trivial).
• Nachteile: Hoher Speicherverbrauch.

Methoden der Umsetzung

• Erste Methode: Basiert auf Tabellen mit vielen identischen Spalten oder Zeilen.
• Zweite Methode: Besonders nützlich, wenn die Übergangsmatrix sehr dünn besetzt (sparse) ist.

Fehlerbehandlung und Definitionen

Häufige lexikalische Fehler

• Unerwartete Zeichen (meist zu Beginn eines Lexems).
• Überlauf von Variablen oder Konstanten.
• Zeilenende vor dem Schließen einer Zeichenfolge.
• Probleme beim Öffnen oder Schließen von Kommentaren.

Was ist eine lexikalische Analyse?

Sie ist für die Suche nach Wörtern oder lexikalischen Komponenten verantwortlich, aus denen ein Programm besteht.

Funktionsweise der Analyse

Sie verarbeitet eine Folge von Zeichen mithilfe einer vorgegebenen Grammatik.

Hauptfunktionen der lexikalischen Analyse

• Lesen der Eingabezeichen, um als Ausgabe eine Folge von Komponenten zu produzieren.
• Entfernen von Kommentaren und Leerzeichen.
• Erkennen von Benutzer-IDs.
• Verfolgung der gelesenen Zeilen.

Trennung von Lexikon und Syntaxanalyse

Dies geschieht, um spezialisierte und leistungsfähigere Prozessoren für die jeweiligen Phasen aufbauen zu können.

Struktur und Begriffe

Struktur des lexikalischen Prozessors

• (Regulärer Ausdruck 1) (Aktion 1)
• (Regulärer Ausdruck 2) (Aktion 2)
• (Regulärer Ausdruck 3) (Aktion 3)
• (Regulärer Ausdruck n) (Aktion n)

Definitionen: Muster, Lexem und Token

• Muster (Pattern): Ein regulärer Ausdruck.
• Lexem: Eine spezielle Zeichenfolge, die einem Muster entspricht.
• Token: Ein Terminalsymbol, das mit einem Muster verbunden ist.

Möglichkeiten zur Erstellung eines Lexers

Ad-hoc-Programmierung (manuell), Nutzung endlicher Automaten oder Verwendung eines Metacompilers.