Lexikalische Analyse

Im Informatik, lexikalische Analyse, Lexing oder Tokenisierung ist der Prozess der Konvertierung einer Sequenz von Figuren (wie in a Computer Programm oder Website) in eine Sequenz von lexikalische Token (Saiten mit einer zugewiesenen und so identifizierten Bedeutung). Ein Programm, das eine lexikalische Analyse durchführt Lexer, Tokenizer,^[1] oder Scanner, obwohl Scanner ist auch ein Begriff für die erste Stufe eines Lexer. Ein Lexer wird im Allgemeinen mit a kombiniert Parser, die gemeinsam die analysieren Syntax von Programmiersprachen, Webseiten, und so weiter.

Anwendungen

Ein Lexer bildet die erste Phase von a Compiler Frontend in der modernen Verarbeitung. Die Analyse tritt im Allgemeinen in einem Pass auf.

In älteren Sprachen wie z. AlgolDie Anfangsphase war stattdessen Zeilenrekonstruktion, was funktionierte ununterbrochen und die Weißespace entfernt und Kommentare (und hatte scannerlose Parser, ohne separate Lexer). Diese Schritte werden jetzt als Teil des Lexer durchgeführt.

Lexer und Parser werden am häufigsten für Compiler verwendet, können jedoch für andere Computersprachen -Tools verwendet werden, wie z. PrettyPrinters oder Linter. Lexing kann in zwei Phasen unterteilt werden: die Scannen, die die Eingangszeichenfolge in syntaktische Einheiten unterteilt Lexeme und kategorisiert diese in Token -Klassen; und die Bewertung, was Lexeme in verarbeitete Werte umwandelt.

Lexer sind im Allgemeinen recht einfach, wobei der größte Teil der Komplexität auf den Parser oder der Parser verschoben wird oder Semantische Analyse Phasen und können oft von a generiert werden Lexergenerator, vor allem Lex oder Derivate. Lexer können jedoch manchmal eine gewisse Komplexität einbeziehen, wie z. Phrasenstruktur Verarbeitung, um Eingaben zu vereinfachen und den Parser zu vereinfachen, kann teilweise oder vollständig von Hand geschrieben werden, um mehr Funktionen oder für die Leistung zu unterstützen.

Die lexikalische Analyse ist ebenfalls eine wichtige frühe Stufe in Verarbeitung natürlicher Sprache, wo Text oder Schallwellen in Wörter und andere Einheiten unterteilt sind. Dies erfordert eine Vielzahl von Entscheidungen, die nicht vollständig standardisiert sind, und die Anzahl der produzierten Token -Systeme variiert für Zeichenfolgen wie "1/2", "Stuhl", "nicht", und/oder "," 1/1// 2010 "," 2x4 "," ..., "und viele andere. Dies steht im Gegensatz zur lexikalischen Analyse für die Programmierung und ähnliche Sprachen, in denen exakte Regeln allgemein definiert und bekannt sind.

Lexeme

A Lexeme ist eine Folge von Zeichen im Quellprogramm, das dem Muster für ein Token entspricht und vom lexikalischen Analysator als Instanz dieses Tokens identifiziert wird.^[2]

Einige Autoren bezeichnen dies als "Token" mit "Token" austauschbar, um die String zu repräsentieren, die tokenisiert ist Tokenisierung Prozess.^[3][4]

Das Wort Lexem in der Informatik ist anders definiert als Lexeme in der Sprachwissenschaft. Ein Lexem in der Informatik entspricht ungefähr a Wort in der Linguistik (nicht zu verwechseln mit a Wort in der Computerarchitektur), obwohl es in einigen Fällen ähnlicher ist wie a Morphem.

Zeichen

A lexikalisches Token oder einfach Zeichen ist ein Saite mit einer zugewiesenen und so identifizierten Bedeutung. Es ist als ein Paar strukturiert, das aus a besteht Token -Name und ein optionales Token -Wert. Der Token -Name ist eine Kategorie der lexikalischen Einheit.^[2] Gemeinsame Token -Namen sind

• Kennung: nennt der Programmierer;
• Stichwort: Namen bereits in der Programmiersprache;
• Separator (Auch als Punctuators bekannt): Zeichenzeichen und gepaarte Delimiter;
• Operator: Symbole, die auf Argumente arbeiten und Ergebnisse erzielen;
• wörtlich: numerische, logische, textuelle, Referenzliterale;
• Kommentar: Zeile, Block (hängt vom Compiler ab, wenn Compiler Kommentare als Token implementiert, da er sonst entzogen wird).

Beispiele für Token -Werte

Token -Name	Probe -Token -Werte
Kennung	x, color, UP
Stichwort	if, while, return
Separator	}, (, ;
Operator	+, <, =
wörtlich	true, 6.02e23, "music"
Kommentar	/* Retrieves user data */, // must be negative

Betrachten Sie diesen Ausdruck in der C Programmiersprache:

x = a + b * 2;

Die lexikalische Analyse dieses Ausdrucks liefert die folgende Sequenz von Token:

[(Identifier, x), (Operator, =), (Identifier, a), (Operator, +), (Identifikator, b), (Operator, *), (buchstäblich, 2), (Separator,;)]

Ein Token -Name ist das, was als a bezeichnet werden könnte Teil der Rede in der Sprachwissenschaft.

Lexikalische Grammatik

Die Spezifikation von a Programmiersprache häufig enthält eine Reihe von Regeln, die lexikalische Grammatik, was die lexikalische Syntax definiert. Die lexikalische Syntax ist normalerweise a Regelmäßige Sprache, mit den Grammatikregeln, die aus bestehen aus Reguläre Ausdrücke; Sie definieren die Menge möglicher Zeichensequenzen (Lexeme) eines Tokens. Ein Lexer erkennt Saiten, und für jede Art von Saite fand das lexikalische Programm eine Aktion, die am einfachsten ein Token produziert.

Zwei wichtige häufige lexikalische Kategorien sind weißer Raum und Kommentare. Diese werden auch in der Grammatik definiert und vom Lexer verarbeitet, können jedoch weggeworfen werden (ohne Token produzieren) und berücksichtigt werden nicht signifikant, höchstens zwei Token (wie in Wenn x Anstatt von Ifx). Es gibt zwei wichtige Ausnahmen davon. Erster Off-Side-Regel Sprachen, die eingrenzen Blöcke Bei Einrücken ist die anfängliche Weißespace signifikant, da sie die Blockstruktur bestimmt und im Allgemeinen auf Lexerebene behandelt wird. sehen Phrasenstruktur, unter. Zweitens müssen in einigen Verwendungen von Lexern, Kommentare und Whitespace erhalten bleiben - zum Beispiel a a Prettyprinter Außerdem muss die Kommentare ausgeben und einige Debugging -Tools können den Programmierer Nachrichten zur Verfügung stellen, die den ursprünglichen Quellcode anzeigen. In den 1960er Jahren, insbesondere für Algol, Whitespace und Kommentare wurden als Teil der beseitigt Zeilenrekonstruktion Phase (die Anfangsphase der Compiler Frontend), aber diese separate Phase wurde beseitigt und diese werden jetzt vom Lexer behandelt.

Tokenisierung

Tokenisierung ist der Prozess der Abgrenzung und Klassifizierung von Abschnitten einer Zeichenfolge von Eingabebestellen. Die resultierenden Token werden dann an eine andere Form der Verarbeitung weitergegeben. Der Prozess kann als Unteraufgabe von betrachtet werden Parsing Eingang.

Zum Beispiel im Text Saite:

The quick brown fox jumps over the lazy dog

Die Zeichenfolge ist nicht implizit auf Räumen segmentiert, als Natürliche Sprache Sprecher würde tun. Die rohe Eingabe, die 43 Zeichen, müssen explizit in die 9 -Token mit einem bestimmten Raumtrennzeichen aufgeteilt werden (d. H. Die Zeichenfolge entspricht dem String "" " oder regulären Ausdruck /\ s {1}/).

Wenn eine Token -Klasse mehr als ein mögliches Lexem repräsentiert, spart der Lexer häufig genügend Informationen, um das ursprüngliche Lexem zu reproduzieren, damit er in verwendet werden kann Semantische Analyse. Der Parser ruft diese Informationen normalerweise aus dem Lexer ab und speichert sie in der Zusammenfassung Syntaxbaum. Dies ist erforderlich, um einen Informationsverlust zu vermeiden, in dem die Zahlen auch gültige Kennungen sein können.

Token werden anhand der spezifischen Regeln des Lexer identifiziert. Einige Methoden zur Identifizierung von Token umfassen: Reguläre Ausdrücke, spezifische Sequenzen von Zeichen als a Flagge, spezifische trennende Zeichen genannt Grenzwerteund explizite Definition durch ein Wörterbuch. Sonderzeichen, einschließlich Zeichenzeichen, werden häufig von Lexern verwendet, um Token aufgrund ihrer natürlichen Verwendung in schriftlichen und Programmiersprachen zu identifizieren.

Token werden häufig nach Charakterinhalten oder nach Kontext innerhalb des Datenstroms kategorisiert. Kategorien werden durch die Regeln des Lexer definiert. Kategorien umfassen häufig Grammatikelemente der im Datenstrom verwendeten Sprache. Programmiersprachen kategorisieren Token häufig als Bezeichner, Operatoren, Gruppierungssymbole oder nach Datentyp. Geschriebene Sprachen kategorisieren normalerweise Token als Substantive, Verben, Adjektive oder Zeichensetzung. Kategorien werden für die Nachbearbeitung der Token entweder durch den Parser oder nach anderen Funktionen im Programm verwendet.

Ein lexikalischer Analysator tut im Allgemeinen nichts mit Kombinationen von Token, eine Aufgabe für a Parser. Zum Beispiel erkennt ein typischer lexikalischer Analysator Klammern als Token, aber nichts, um sicherzustellen, dass jeder "(" mit einem ")").

Wenn ein Lexer -Token zum Parser token, ist die verwendete Darstellung typischerweise eine aufgezählte Liste von Zahlendarstellungen. Zum Beispiel wird "Identifier" mit 0, "Zuweisungsoperator" mit 1, "Addition Operator" mit 2 usw. dargestellt.

Token werden oft definiert von Reguläre Ausdrücke, die von einem lexikalischen Analysatorgenerator verstanden werden, wie z. Lex. Der lexikalische Analysator (automatisch von einem Tool wie Lex oder handgefertigt) liest in einem Zeichenstrom von Zeichen, die identifiziert die Lexeme im Strom und kategorisiert sie in Token. Dies wird bezeichnet Token. Wenn der Lexer ein ungültiges Token findet, meldet er einen Fehler.

Nach dem Tokenisieren ist Parsing. Von dort aus können die interpretierten Daten in Datenstrukturen für allgemeine Verwendung, Interpretation oder in Datenstrukturen geladen werden Kompilieren.

Scanner

Die erste Stufe, die Scanner, basiert normalerweise auf einem Finite-State-Maschine (FSM). Es wurde in IT -Informationen über die möglichen Sequenzen von Zeichen codiert, die in einem der von ihm behandelten Token enthalten sind (einzelne Instanzen dieser Zeichensequenzen werden bezeichnet Lexeme). Zum Beispiel eine ganze Zahl Lexeme kann jede Sequenz von enthalten Numerische Ziffer Figuren. In vielen Fällen kann der erste Nicht-Whitespace-Charakter verwendet werden, um die Art von Token abzuleiten, die folgt, und nachfolgende Eingabebereiche werden dann einzeln verarbeitet, bis ein Charakter erreicht ist, das nicht in der Reihe von Zeichen ist, die für dieses Token akzeptabel sind (dies wird als bezeichnet Maximales Munch, oder längstes Match, Regel). In einigen Sprachen sind die Regeln der Lexeme -Schöpfung komplexer und können beinhalten Backtracking über zuvor gelesene Zeichen. Beispielsweise reicht in C in C nicht aus, um zwischen einer Kennung zu unterscheiden, die mit 'L' beginnt, und einem Weitcharakter-Streichliteral.

Bewerter

A LexemeEs ist jedoch nur eine Zeichenfolge von Zeichen, von denen bekannt ist, dass sie eine bestimmte Art (z. B. eine String -Literal, eine Folge von Buchstaben). Um ein Token zu konstruieren, benötigt der lexikalische Analysator eine zweite Stufe, die Bewerter, was über die Charaktere des Lexems geht, um a zu produzieren Wert. Der Typ des Lexems in Kombination mit seinem Wert ist das, was ordnungsgemäß ein Token ausmacht, das einem Parser gegeben werden kann. Einige Token wie Klammern haben nicht wirklich Werte, und daher kann die Evaluator -Funktion für diese nichts zurückgeben: Nur der Typ wird benötigt. In ähnlicher Weise können Evaluatoren manchmal ein Lexem vollständig unterdrücken und es vor dem Parser verbergen, was für Whitespace und Kommentare nützlich ist. Die Bewerter für Identifikatoren sind normalerweise einfach (buchstäblich die Kennung darstellen), können jedoch einige enthalten ununterbrochen. Die Bewerter für ganzzahlige Literale kann die Schnur über weitergeben (Bewertung in die semantische Analysephase verschieben) oder die Bewertung selbst durchführen, die für verschiedene Basen oder Schwimmpunktzahlen beteiligt sein kann. Für einen einfachen zitierten String -Literal muss der Bewerter nur die Zitate entfernen, aber der Bewerter für eine Flucht String Literal Enthält einen Lexer, der die Escape -Sequenzen entzündet.

Zum Beispiel im Quellcode eines Computerprogramms der Zeichenfolge

net_worth_future = (assets – liabilities);

könnte in den folgenden lexikalischen Token -Stream umgewandelt werden; Whitespace ist unterdrückt und Sonderzeichen haben keinen Wert:

Identifier net_worth_future gleich open_parenthesis identifier assoets minus identifier verbindlichkeiten close_parenthesis semicolon

Aufgrund von Lizenzbeschränkungen bestehender Parser kann es erforderlich sein, einen Lexer von Hand zu schreiben. Dies ist praktisch, wenn die Liste der Token klein ist, aber im Allgemeinen werden Lexer durch automatisierte Werkzeuge generiert. Diese Tools akzeptieren im Allgemeinen reguläre Ausdrücke, die die im Eingangsstrom zulässigen Token beschreiben. Jeder reguläre Ausdruck ist mit a verbunden Produktionsregel In der lexikalischen Grammatik der Programmiersprache, die die Lexemen bewertet, die dem regulären Ausdruck entsprechen. Diese Tools können Quellcode generieren, die kompiliert und ausgeführt werden können oder a konstruieren a Zustandsübergangstabelle Für ein Finite-State-Maschine (der an den Vorlagencode zum Kompilieren und Ausführen angeschlossen ist).

Reguläre Ausdrücke repräsentieren kompakte Muster, denen die Zeichen in Lexemen folgen könnten. Zum Beispiel für eine Englisch-Ein Identifikator -Token ist möglicherweise ein englischer alphabetischer Charakter oder ein Unterstrich, gefolgt von einer beliebigen Anzahl von ASCII -alphanumerischen Zeichen und/oder Unterstrichen. Dies könnte kompakt durch die Zeichenfolge dargestellt werden [a-zA-Z_][a-zA-Z_0-9]*. Dies bedeutet "ein Zeichen a-z, a-z oder _, gefolgt von 0 oder mehr von a-Z, a-z, _ oder 0-9".

Regelmäßige Ausdrücke und die von ihnen erzeugten Finite-State-Maschinen sind nicht leistungsstark genug, um rekursive Muster wie "wie z."n Eröffnung von Klammern, gefolgt von einer Erklärung, gefolgt von n Klammern schließen. "Sie können nicht zählen und dies überprüfen n ist auf beiden Seiten gleich, es sei denn, es gibt eine endliche Menge zulässiger Werte für n. Es braucht einen vollständigen Parser, um solche Muster in ihrer vollen Allgemeinheit zu erkennen. Ein Parser kann Klammern auf einen Stapel schieben und dann versuchen, sie abzuheben und zu sehen, ob der Stapel am Ende leer ist (siehe Beispiel^[5] in dem Struktur und Interpretation von Computerprogrammen Buchen).

Hindernis

Typischerweise tritt eine Tokenisierung auf der Wortebene auf. Es ist jedoch manchmal schwierig zu definieren, was mit einem "Wort" gemeint ist. Oft stützt sich ein Tokenizer beispielsweise auf einfache Heuristiken:

• Interpunktion und Whitespace können in die resultierende Liste der Token aufgenommen werden oder nicht.
• Alle zusammenhängenden Zeichenfolgen alphabetischer Zeichen sind Teil eines Tokens; Ebenso mit Zahlen.
• Token werden durch getrennt von Whitespace Charaktere wie Raum oder Zeilenumbruch oder durch Interpunktionszeichen.

In Sprachen, die Inter-Wort-Räume verwenden (wie die meisten, die das lateinische Alphabet verwenden, und die meisten Programmiersprachen), ist dieser Ansatz ziemlich einfach. Aber auch hier gibt es viele Randfälle wie z. Kontraktionen, beigebracht Wörter, Emoticons, und größere Konstrukte wie z. URIS (was für einige Zwecke als einzelne Token zählen kann). Ein klassisches Beispiel ist "New York), das ein naiver Tokenizer im Raum brechen kann, obwohl die bessere Bruch (wohl) beim Bindestrich ist.

Tokenisierung ist besonders schwierig für Sprachen, die in geschriebenen in geschriebenen Sprachen geschrieben sind scriptio continua die keine Wortgrenzen aufweisen, wie z. Altgriechisch, Chinesisch,^[6] oder Thai. Agglutinative Sprachenwie Koreanisch, machen auch Tokenisierung Aufgaben kompliziert.

Einige Möglichkeiten, um die schwierigeren Probleme anzugehen, sind die Entwicklung komplexerer Heuristiken, die Abfrage einer Tabelle mit gemeinsamen Spezialkasen oder die Anpassung der Token an a Sprachmodell Dies identifiziert Kollokationen in einem späteren Verarbeitungsschritt.

Lexergenerator

Lexer werden oft von a generiert Lexergenerator, analog zu Parser -Generatorenund solche Werkzeuge kommen oft zusammen. Das etablierteste ist Lex, gepaart mit dem yacc Parser -Generator oder vielmehr einige ihrer vielen Neuauflagen, wie biegen (oft gepaart mit Gnu Bison). Diese Generatoren sind eine Form von Domänenspezifische SpracheAufnahme einer lexikalischen Spezifikation - im Allgemeinen regelmäßige Ausdrücke mit etwas Aufschlag - und einen Lexer ausgeben.

Diese Tools ergeben eine sehr schnelle Entwicklung, was in der frühen Entwicklung sehr wichtig ist, um sowohl einen funktionierenden Lexer zu erhalten als auch weil sich eine Sprachspezifikation häufig ändern kann. Darüber hinaus bieten sie häufig erweiterte Funktionen, wie z. B. Vor- und Nach-Konditionen, die von Hand schwer zu programmieren sind. Ein automatisch generiertes Lexer kann jedoch keine Flexibilität haben und erfordern daher möglicherweise eine manuelle Änderung oder einen komplett geschriebenen Lexer.

Die Lexer -Leistung ist ein Problem, und die Optimierung lohnt sich, mehr in stabilen Sprachen, in denen der Lexer sehr oft ausgeführt wird (wie C oder HTML). Lex/Flex-generierte Lexer sind einigermaßen schnell, aber Verbesserungen von zwei- bis dreimal sind mit mehr abgestimmten Generatoren möglich. Manchmal werden handgeschriebene Lexer verwendet, aber moderne Lexergeneratoren produzieren schnellere Lexer als die meisten handcodierten. Die LEX/Flex-Generatorenfamilie verwendet einen tabelletriebenen Ansatz, der viel weniger effizient ist als der direkt codierte Ansatz.^{[zweifelhaft – diskutieren]} Mit dem letzteren Ansatz erzeugt der Generator einen Motor, der direkt über GOTO-Aussagen zu Follow-up-Zuständen springt. Werkzeuge wie Re2c^[7] haben sich erwiesen, um Motoren zwischen zwei und dreimal schneller zu produzieren als flex produzierte Motoren. Im Allgemeinen ist es schwierig, Analysatoren von Handschreibungen zu handeln, die besser abschneiden als Motoren, die von diesen letzteren Werkzeugen erzeugt werden.

Phrasenstruktur

Die lexikalische Analyse unterteilt hauptsächlich den Eingangsstrom von Zeichen in Token, gruppiert einfach die Zeichen in Stücke und kategorisiert sie. Das Lexing kann jedoch signifikant komplexer sein. Am einfachsten können Lexer Token weglassen oder hinzugefügte Token einfügen. Das Weglassen von Token, insbesondere Whitespace und Kommentaren, ist sehr häufig, wenn diese vom Compiler nicht benötigt werden. Weniger häufig können hinzugefügte Token eingefügt werden. Dies geschieht hauptsächlich, um Token zu gruppieren Aussagenoder Aussagen in Blöcke, um den Parser zu vereinfachen.

Liniendauer

Liniendauer ist ein Merkmal einiger Sprachen, in denen eine neue Linie normalerweise ein Anweisungs -Terminator ist. Meistens beenden eine Linie mit einem Backslash (unmittelbar gefolgt von a Neue Zeile) führt dazu, dass die Linie ist Fortsetzung - Die folgende Zeile ist trat bei in die vorherige Zeile. Dies geschieht im Allgemeinen im Lexer: Der Backslash und die Newline werden weggeworfen und nicht die neue Linie, die tokenisiert wird. Beispiele beinhalten verprügeln,^[8] Andere Shell -Skripte und Python.^[9]

Semikoloninsertion

Viele Sprachen verwenden das Semikolon als Erklärungsterminator. Meistens ist dies obligatorisch, aber in einigen Sprachen ist das Semikolon in vielen Kontexten optional. Dies erfolgt hauptsächlich auf Lexerebene, wo der Lexer ein Semikolon in den Token -Stream ausgibt, obwohl man im Eingangszeichen nicht vorhanden ist und als bezeichnet wird und bezeichnet wird Semikoloninsertion oder Automatische Semikoloninsertion. In diesen Fällen sind Semikolone Teil der formalen Phrase -Grammatik der Sprache, können jedoch nicht im Eingabetxt gefunden werden, da sie vom Lexer eingefügt werden können. Optionale Semikolons oder andere Terminatoren oder Separatoren werden manchmal auch auf Parserebene gehandhabt, insbesondere im Fall von Nachlaufkommando oder Semikolons.

Semikoloninsertion ist ein Merkmal von BCPL und sein entfernter Nachkomme gehen,^[10] Obwohl es in B oder C fehlt, fehlt es^[11] Semikolon -Insertion ist in vorhanden JavaScriptobwohl die Regeln etwas komplex und viel kritisiert sind; Um Fehler zu vermeiden, empfehlen einige immer, Semikolons zu verwenden, während andere erste Semikolons verwenden, die als bezeichnet werden Defensive Semikolonszu Beginn potenziell mehrdeutiger Aussagen.

Semikoloninsertion (in Sprachen mit Semikolon-terminierten Aussagen) und die Liniendauer (in Sprachen mit neu line-terminierten Aussagen) können als komplementär angesehen werden: Semikolon-Einfügung fügt ein Token hinzu, obwohl Newlines im Allgemeinen dies tun nicht Erzeugen Sie Token, während die Line -Fortsetzung ein Token daran hindert, generiert zu werden, obwohl Newlines im Allgemeinen tun Token erzeugen.

Off-Side-Regel

Das Off-Side-Regel (Blöcke, die durch Einrückung bestimmt werden) können im Lexer wie in implementiert werden Python, wobei die Erhöhung des Einklebers dazu führt, dass der Lexer einen Einrückungs -Token ausgibt und die Einklage verringert, führt dazu, dass der Lexer einen dedenten Token ausgibt.^[9] Diese Token entsprechen der Eröffnungsklammer { und schließende Klammer } In Sprachen, die Klammern für Blöcke verwenden und bedeutet, dass die Phrase -Grammatik nicht davon abhängt, ob Zahnspangen oder Einrücken verwendet werden. Dies erfordert, dass der Lexer -Hold -Status, nämlich das aktuelle Einklangstufe, und somit Änderungen bei der Einführung feststellen kann, wenn sich dies ändert, und damit die lexikalische Grammatik nicht kontextfrei: Eingeschwindiger Eingeschwindigkeit hängen von den kontextuellen Informationen der vorherigen Einrückungsstufe ab.

Kontextempfindlicher Lexing

Im Allgemeinen sind lexikalische Grammatiken kontextfrei oder fast so und erfordern somit keinen Rückblick oder Vorweg oder eine Rückverfolgung, was eine einfache, saubere und effiziente Implementierung ermöglicht. Dies ermöglicht auch eine einfache Einweg-Kommunikation von Lexer zu Parser, ohne dass Informationen zum Lexer zurückfließen.

Es gibt jedoch Ausnahmen. Einfache Beispiele sind: Semikolon -Einfügung in GO, das ein Token zurückblickt; Verkettung von aufeinanderfolgenden Streichliteralen in Python,^[9] Dies erfordert das Halten eines Tokens in einem Puffer, bevor Sie es emittieren (um festzustellen, ob das nächste Token ein weiterer Streichliteral ist); und die außerhalb der Seite in Python, die eine Anzahl der Einrückungsniveaus aufrechterhalten muss (in der Tat einen Stapel jedes Einrückungsniveaus). Diese Beispiele erfordern nur einen lexikalischen Kontext, und obwohl sie einen Lexer etwas komplizieren, sind sie für den Parser und späteren Phasen unsichtbar.

Ein komplexeres Beispiel ist Der Lexer -Hack in C, wo die Token -Klasse einer Abfolge von Zeichen erst in der semantischen Analysephase festgelegt werden kann, seitdem Typedef Namen und Variablennamen sind lexikalisch identisch, bilden jedoch unterschiedliche Token -Klassen. Somit ruft der Lexer im Hack den semantischen Analysator (z. B. Symboltabelle) auf und prüft, ob die Sequenz einen Typedef -Namen erfordert. In diesem Fall müssen Informationen nicht nur vom Parser zurückfließen, sondern vom semantischen Analysator zurück zum Lexer, was das Design kompliziert.

Siehe auch

• Liste der Parsergeneratoren

Verweise

Quellen

Externe Links

• Yang, W.; Tsay, Chey-woei; Chan, Jien-Tsai (2002). "Über die Anwendbarkeit der längsten Match-Regel in der lexikalischen Analyse". Computersprachen, Systeme und Strukturen. 28 (3): 273–288. doi:10.1016/s0096-0551 (02) 00014-0.NSC 86-2213-E-009-021 und NSC 86-2213-E-009-079.
• Trim, Craig (23. Januar 2013). "Die Kunst der Tokenisierung". Entwickler arbeitet. IBM. Archiviert von das Original Am 2019-05-30.
• Word -Erwähnungs -Segmentierungsaufgabe, eine Analyse