Endliche Automaten und lexikalische Analyse

Endliche Automaten und reguläre Ausdrücke

Ein endlicher Automat (auch bekannt als Finite State Machine) ist ein mathematisches Modell eines Systems. Dieses System nimmt eine Zeichenfolge, bestehend aus Symbolen eines Alphabets, und bestimmt, ob die Zeichenfolge zu der Sprache gehört, die der Automat erkennt.

Formal kann ein endlicher Automat als ein Quintupel (S, Σ, T, s, A) beschrieben werden, wobei:

• S: eine endliche Menge von Zuständen ist
• Σ: ein Alphabet ist
• T: die Übergangsfunktion ist
• s: der Startzustand ist
• A: die Menge der akzeptierenden Zustände ist

Darstellungsformen endlicher Automaten

Neben der Möglichkeit, einen endlichen Automaten durch seine formale Definition darzustellen, kann er auch durch andere, komfortablere und manchmal intuitivere Notationen repräsentiert werden. Die gebräuchlichsten sind Übergangstabellen, Übergangsdiagramme und reguläre Ausdrücke.

Lexikalische Analyse

Der lexikalische Analysator (auch Scanner oder Lexer genannt) hat die Hauptfunktion, eine Folge von Zeichen oder Symbolen des Alphabets der Sprache zu nehmen und sie in Kategorien, bekannt als lexikalische Einheiten, einzuteilen. Diese Einheiten werden vom Parser (auch Syntaxanalysator genannt) verwendet, um festzustellen, ob das, was im Quellprogramm geschrieben steht, grammatikalisch korrekt ist oder nicht. Einige der lexikalischen Einheiten werden nicht vom Parser verwendet, sondern herausgefiltert. Dies ist der Fall bei Kommentaren, die das Programm dokumentieren, aber keine grammatikalische Funktion haben, oder bei Leerzeichen, die der Übersichtlichkeit des Codes dienen.

In der Terminologie des Compilerbaus werden folgende Begriffe verwendet:

• Muster: Stellt die Regel dar, nach der eine Folge von Zeichen als eine bestimmte lexikalische Einheit gilt.
• Lexem: Ist der konkrete Wert eines Zeichensatzes, der einem Muster entspricht.
• Token: Ist der Wert, der einer lexikalischen Einheit zugeordnet ist und als Ganzzahl dargestellt wird.
• Alphabet: Die für eine Sprache gültigen Zeichen.
• Lexikalische Einheiten: Die Kategorien, in die die gültigen Zeichenfolgen einer Sprache eingeteilt werden.

Die Rolle des lexikalischen Analysators

Obwohl der lexikalische Analysator die erste Stufe des Kompilierungsprozesses ist, ist er nicht derjenige, der den Prozess startet. Vielmehr führt er seine Verarbeitung durch und sendet seine Ergebnisse an den Parser, der den Prozess tatsächlich startet, indem er ein Token vom lexikalischen Analysator anfordert.

Während dieser Phasen wird eine enge Kommunikation mit der Symboltabelle aufrechterhalten, die Informationen über die im Programm verwendeten Einheiten enthält.

Beschreibung der Muster

Es gibt drei Möglichkeiten, Muster zu beschreiben: die informelle Beschreibung, die die natürliche Sprache verwendet, um das Verhalten der lexikalischen Regel zu beschreiben, die Verwendung von regulären Ausdrücken und die Verwendung von endlichen Automaten in Form von Übergangsdiagrammen.

Übergangsdiagramme

Ein Übergangsdiagramm ist die grafische Darstellung einer Reihe von Zuständen. Es kann Start-, Zwischen- oder Endzustände geben und es kann auch einen oder mehrere Ausgänge zu anderen Zuständen geben.

Die Startzustände werden durch einen doppelten Kreis und eine Null, die Zwischenzustände durch einen Kreis und eine Zahl und die Endzustände durch einen doppelten Kreis und die letzte Zahl dargestellt. Zustände stehen miteinander in Beziehung durch einen Pfeil mit einem Namen, der das Zeichen oder die Zeichenfolge ist, die den Übergang von einem Zustand in einen anderen bewirkt.

Eigenschaften von Übergangsdiagrammen

• Jeder Zustand muss mit der gleichen Menge an Zeichen erreicht werden, jedes Mal, wenn es einen Übergang gibt.
• Jedes Muster hat einen Zeichenselektor, der eindeutig angewendet werden kann, um das Muster zu erkennen.
• Um einen akzeptierenden Zustand zu erreichen, muss es einen Übergang zu dem Zeichen geben, das das Muster der lexikalischen Einheit unterbricht.

Informelle Beschreibungen von lexikalischen Einheiten

• Bezeichner: Ein Buchstabe, gefolgt von weiteren Buchstaben, Ziffern oder Unterstrichen.
• Kommentare: Beginnen mit /* und enden mit */ und können innerhalb jedes beliebige Symbol außer dem Endsymbol enthalten.
• EOF: Zeigt das Ende der Datei an.
• Fehler: Jedes Symbol oder jede Zeichenfolge, die keinem der vorherigen Muster entspricht.