WikiDer > Lexikalische Analyse

Lexikalische Analyse ist ein Begriff aus dem Informatik das ermöglicht die Konvertierung einer Reihe Zeichen in einer serie Symbole bezeichnet ist. Programme, die diese Konvertierung durchführen, werden lexikalische Analysatoren, lexer oder Scanner erwähnt.

Für die Umwandlung einer Zeichenfolge in eine Zeichenfolge werden eine Reihe von Regeln formuliert, die angeben, welche aufeinanderfolgenden Zeichen ein (gültiges) Zeichen bilden. Diese Regeln werden in der Regel durch Reguläre Ausdrücke.

Wofür werden Lexer verwendet?

Lexer werden hauptsächlich verwendet in Compiler und Dolmetscher. Dort bilden sie die erste Phase beim Lesen und Interpretieren eines Programms. Nachdem ein Quellprogramm (bestehend aus einer Zeichenkette, meist in einer Datei) in eine Zeichenkette umgewandelt wurde, werden diese Symbole von a . weiterverarbeitet Parser.

Auch außerhalb ihrer Verwendung in Compilern und Interpretern werden Lexer häufig in Kombination mit Parsern verwendet. Dies ist jedoch nicht erforderlich. Ein Lexer ist beispielsweise auch in einem Programm nützlich, das HTMLEntfernen Sie Tags aus einem Text. Ein Parser ist unnötig.

Leistungen^[1][2]

Die Verwendung eines separaten Lexers, der die lexikalische Analyse durchführt, bevor ein Parser seine Arbeit aufnimmt, hat eine Reihe von Vorteilen. Parser sind im Vergleich zu Lexern komplex. Lexer sind einfach und schnell. Außerdem ist die Konstruktion von Lexern fast immer automatisiert (mit Hilfe eines sog Lexer-Generator).

• Jede vom Lexer ausgeführte Operation an einem Eingabetext muss nicht vom Parser ausgeführt werden. Da Parser im Gegensatz zu Lexern mehr menschliche Eingriffe erfordern, vereinfacht die Verwendung eines Lexers die Arbeit des Programmierers.
• Lexer sind schnell. Einige Probleme können sowohl durch einen Parser als auch durch einen Lexer gelöst werden (zB das Erkennen von Kommentarzeilen im Quellcode). Ein Lexer macht dies aufgrund seiner einfachen Implementierung viel schneller.
• Der relativ komplexe Parser (oder die Spezifikation für a Parser-Generator) muss keine Details wie Leerzeichen und Leerzeilen oder die Unterscheidung zwischen ganze Zahlen und Gleitkommazahlen.
• Ein Lexer arbeitet mit Eingabe und enthält daher oft systemabhängigen Code, zum Beispiel zum Lesen von Zeichen aus a Eingabepuffer. Die Trennung des Lexers vom Parser und anderen Teilen eines Compilers/Interpreters beschränkt den systemabhängigen Code auf einen kleinen Teil des gesamten Compilers, was die Portierung auf andere Systeme erleichtert.
• Die Grammatik verschiedener Programmiersprachen unterscheidet sich oft zu sehr, um die Wiederverwendung von Parsern zu ermöglichen. Die Unterschiede zwischen lexikalischen Strukturen von Programmiersprachen sind oft viel kleiner (zum Beispiel haben viele Sprachen die gleichen Regeln für Kennungen und ganze Zahlen), wodurch Lexer besser für die Wiederverwendung geeignet sind.

Symbole

Wenn es um lexikalische Analyse geht, a Symbol (Englisch: Zeichen) bezeichnet eine Kombination von Zeichen, die eine sinnvolle Einheit bilden. Wenn wir zum Beispiel über niederländische Sätze sprechen, sind die Buchstaben die Buchstaben und die Wörter sind Symbole: Nicht alle Kombinationen von Buchstaben ergeben ein Wort.

Nehmen wir zum Beispiel den folgenden Ausdruck C:

res = berechnen (3.5);

13 verschiedene Zeichen werden hier verwendet ('r', 'e', ​​​​s', '=', 'k', 'n', '3', '5', Leerzeichen, offene Klammer, geschlossene Klammer, Komma und Semikolon), um 9 Symbole zu bilden. Die folgende Tabelle listet die gebildeten Symbole, den Typ jedes Symbols und seinen Wert (falls zutreffend) auf:

Das Ergebnis in der Tabelle ist spezifisch für die lexen eines C-Programms. Beachten Sie, dass einige Symbole keinen Wert haben, z. B. eine Klammer oder ein =-Zeichen. Wenn ein Symbol einen Wert hat, ist es die Aufgabe des Lexers, ihn an das Programm zu übergeben, das den Lexer verwendet (normalerweise ein Parser).

Lexikalische Analyse in Compilern

Das lexikalischer Scan stellt die erste Analyse dar, die auf die Eingabe der Compiler. Dieser Eintrag ist eine Zeichenfolge aus a Alphabet, die ein Wort im Sinne von a . bilden können formelle Sprache.

Eine solche formale Sprache unterscheidet normalerweise in einem Wort zwei Kategorien von Unterzeilen (Symbolreihen, die als Teil einer längeren Eingabe auftreten können): die Zeilen, die innerhalb der formalen Sprache eine besondere Bedeutung haben (in Programmiersprachen oft languages Schlüsselwörter oder Schlüsselwörter genannt, oder auch Operatoren (mathematische Operatoren wie und *, zum Beispiel)) und die mehr oder weniger Freiformzeilen, die Namen innerhalb der Eingabe angeben (im Fall einer Programmiersprache kann man sich vorstellen Kennungen).

Die Aufgabe eines lexikalischen Scanners innerhalb des Compilers besteht darin, die Eingabe in kleinere Teile zu zerlegen, genannt Token und übergeben Sie diese Token der Reihe nach an den Parser. Ein Token ist dann ein Objekt, das vom Parser als Schlüsselwort innerhalb der formalen Sprache oder als Name erkannt und als solches behandelt werden kann.

Operation

Die Funktionsweise des lexikalischen Scanners basiert auf dem Berechnungsmodell von a endliche Automaten: jede Unterzeile der Eingabe hat eine endliche Länge und die Eingabe wird Symbol für Symbol gelesen – so ist nach jedem Symbol sofort ersichtlich, ob die Unterzeile, an der der Scanner arbeitet, noch ein Schlüsselwort sein kann oder ob es unmöglich ist und das die Untersequenz muss ein Name sein. Das Modell der Zeicheneingabe und Zustandsübergänge des endlichen Automaten ist die perfekte Unterstützung für diesen Prozess.

Neben dem Erkennen von Schlüsselwörtern und Namen ist der Lexikonscanner natürlich auch dafür ausgestattet, „leere“ Zeichen zu erkennen (die Zeichen, die das Ende einer Unterzeile innerhalb der Eingabe markieren – in Programmiersprachen wird dafür oft das Leerzeichen verwendet ) und in der Regel auch, um falsch gebildete Zeichen zu erkennen (z. B. weil sie Zeichen enthalten, die die Eingabesprache des Compilers in Namen nicht zulässt, oder bestimmte Zeichen an Stellen enthalten, an denen diese Zeichen nicht erlaubt sind). Damit ist der lexikalische Scanner nicht nur ein Werkzeug für den Parser, sondern auch gerüstet, die erste einer Reihe von Analysen durchzuführen, die feststellen, ob die Eingabe eines Compilers wirklich zur Eingabesprache gehört.

Wie bereits erwähnt, basiert der lexikalische Scanner als System auf dem endlichen Automaten. Dieser Automat ist verwandt mit dem regulären Ausdruck, die natürlich verwendet werden kann, um Token zu beschreiben (eine wörtliche Folge von Symbolen für Schlüsselwörter, eine allgemeinere Beschreibung für Namen, eine Kategorie für leere Zeichen usw.). Reguläre Ausdrücke können reguläre Sprache das alle möglichen Zeichen einer Sprache umfasst. Reguläre Ausdrücke können auch automatisch in endliche Automaten übersetzt werden. Und endliche Automaten können nach einem festen Zeitplan auf a Computer. Somit ist es möglich, vollautomatisch aus einer Sammlung von regulären Ausdrücken einen lexikalischen Scanner für die Verwendung in einem Compiler zu generieren.

Lexer-Generatoren

Obwohl es möglich ist, einen Lexer selbst zu programmieren, werden Lexer normalerweise mit a . generiert Lexer-Generator wie lex. In diesem Fall wird eine Anzahl von Zeilen angegeben, wobei jede Zeile aus a regulären Ausdruck und eine Aktion. Der reguläre Ausdruck definiert, welche Zeichenfolgen ein gültiges Symbol bilden. Die entsprechende Aktion wird ausgeführt, wenn ein solches Symbol gefunden wird.

Lexer-Generatoren übersetzen die angegebenen regulären Ausdrücke in a endliche Automaten (endliche Automaten). Diese endliche Zustandsmaschine wird mit sogenannten Nachschlagetabellen. Dies sind Tabellen, in denen für jede mögliche Kombination von Zustand und Eingabezeichen der nächste Zustand angezeigt wird.

Siehe auch

• lex
• Lexikalischer Scan