Parser

Parsing, Syntaxanalyse oder syntaktische Analyse ist der Prozess der Analyse einer Zeichenfolge, entweder in natürlicher Sprache, in Computersprachen oder in Datenstrukturen, entsprechend den Regeln einer formalen Grammatik. Der Begriff Parsing kommt aus dem Lateinischen pars (orationis) und bedeutet Teil (der Rede). ⓘ

Der Begriff hat in verschiedenen Zweigen der Linguistik und Informatik leicht unterschiedliche Bedeutungen. Das traditionelle Satzparsing wird häufig als Methode zum Verständnis der genauen Bedeutung eines Satzes oder Wortes durchgeführt, manchmal mit Hilfe von Hilfsmitteln wie Satzdiagrammen. Dabei wird in der Regel die Bedeutung grammatischer Unterteilungen wie Subjekt und Prädikat betont. ⓘ

In der Computerlinguistik wird der Begriff verwendet, um die formale Analyse eines Satzes oder einer anderen Wortfolge in ihre Bestandteile durch einen Computer zu bezeichnen, was zu einem Parse-Baum führt, der ihre syntaktische Beziehung zueinander zeigt und auch semantische und andere Informationen (p-Werte) enthalten kann. Einige Parsing-Algorithmen können einen Parse-Wald oder eine Liste von Parse-Bäumen für eine syntaktisch mehrdeutige Eingabe erzeugen. ⓘ

Der Begriff wird auch in der Psycholinguistik zur Beschreibung des Sprachverständnisses verwendet. In diesem Zusammenhang bezieht sich Parsing auf die Art und Weise, wie Menschen einen Satz oder eine Phrase (in gesprochener Sprache oder Text) "in Bezug auf grammatikalische Konstituenten, die Identifizierung der Wortarten, syntaktische Beziehungen usw." analysieren. Dieser Begriff ist besonders gebräuchlich, wenn es darum geht, welche sprachlichen Hinweise den Sprechern helfen, Sätze zu interpretieren, die auf dem Gartenweg liegen. ⓘ

In der Informatik wird der Begriff bei der Analyse von Computersprachen verwendet und bezieht sich auf die syntaktische Analyse des Eingabecodes in seine Bestandteile, um das Schreiben von Compilern und Interpretern zu erleichtern. Der Begriff kann auch verwendet werden, um eine Aufspaltung oder Trennung zu beschreiben. ⓘ

Ein Parser [ˈpɑːʁzɐ] (engl. to parse, „analysieren“, bzw. lateinisch pars, „Teil“; im Deutschen gelegentlich auch Zerteiler) ist ein Computerprogramm, das in der Informatik für die Zerlegung und Umwandlung einer Eingabe in ein für die Weiterverarbeitung geeigneteres Format zuständig ist. Häufig werden Parser eingesetzt, um im Anschluss an den Analysevorgang die Semantik der Eingabe zu erschließen und daraufhin Aktionen durchzuführen. ⓘ

Im Vergleich zu einem Recognizer, der die Eingabe analysiert und ausgibt, ob diese im Sinne der Vorgaben richtig oder falsch ist, gibt der Parser die Analyse einer Eingabe in einer gewünschten Form aus und erzeugt zusätzlich Strukturbeschreibungen. ⓘ

Menschliche Sprachen

Traditionelle Methoden

Die traditionelle grammatikalische Übung des Parsens, manchmal auch als Klauselanalyse bezeichnet, beinhaltet die Zerlegung eines Textes in seine sprachlichen Bestandteile mit einer Erklärung der Form, Funktion und syntaktischen Beziehung jedes Teils. Dies wird größtenteils durch das Studium der Konjugationen und Deklinationen der Sprache bestimmt, was bei stark flektierten Sprachen recht kompliziert sein kann. Um einen Satz wie "Mann beißt Hund" zu analysieren, muss man feststellen, dass das Substantiv "Mann" das Subjekt des Satzes ist, das Verb "beißen" ist die dritte Person Singular des Präsens des Verbs "beißen" und das Substantiv "Hund" ist das Objekt des Satzes. Manchmal werden Techniken wie Satzdiagramme verwendet, um die Beziehungen zwischen den Elementen des Satzes aufzuzeigen. ⓘ

Das Parsing stand früher im Mittelpunkt des Grammatikunterrichts in der gesamten englischsprachigen Welt und wurde allgemein als grundlegend für die Verwendung und das Verständnis der Schriftsprache angesehen. Die allgemeine Vermittlung solcher Techniken ist jedoch nicht mehr zeitgemäß. ⓘ

Computergestützte Methoden

In einigen Systemen zur maschinellen Übersetzung und zur Verarbeitung natürlicher Sprache werden geschriebene Texte in menschlichen Sprachen von Computerprogrammen geparst. Menschliche Sätze lassen sich nicht ohne weiteres von Programmen analysieren, da die Struktur der menschlichen Sprache sehr mehrdeutig ist und ihre Verwendung darin besteht, eine Bedeutung (oder Semantik) aus einem potenziell unbegrenzten Spektrum von Möglichkeiten zu vermitteln, von denen jedoch nur einige für den jeweiligen Fall relevant sind. So ist eine Äußerung "Mann beißt Hund" im Gegensatz zu "Hund beißt Mann" in einem Detail eindeutig, könnte aber in einer anderen Sprache als "Mann beißt Hund" erscheinen, wobei man sich auf den größeren Kontext verlassen muss, um zwischen diesen beiden Möglichkeiten zu unterscheiden, wenn dieser Unterschied tatsächlich von Bedeutung ist. Es ist schwierig, formale Regeln aufzustellen, um informelles Verhalten zu beschreiben, auch wenn klar ist, dass einige Regeln befolgt werden. ⓘ

Um Daten in natürlicher Sprache zu analysieren, müssen sich die Forscher zunächst auf die zu verwendende Grammatik einigen. Die Wahl der Syntax wird sowohl von linguistischen als auch von rechnerischen Erwägungen beeinflusst; so verwenden einige Parsing-Systeme lexikalische funktionale Grammatiken, aber im Allgemeinen ist das Parsing für Grammatiken dieses Typs bekanntermaßen NP-komplett. Die kopfgesteuerte Phrasenstrukturgrammatik ist ein weiterer linguistischer Formalismus, der sich in der Parsing-Gemeinschaft großer Beliebtheit erfreut, aber andere Forschungsbemühungen haben sich auf weniger komplexe Formalismen konzentriert, wie z. B. den, der in der Penn Treebank verwendet wird. Shallow Parsing zielt darauf ab, nur die Grenzen der wichtigsten Konstituenten wie Substantivphrasen zu finden. Eine weitere beliebte Strategie zur Vermeidung linguistischer Kontroversen ist das Parsen von Abhängigkeitsgrammatiken. ⓘ

Die meisten modernen Parser sind zumindest teilweise statistisch, d. h. sie stützen sich auf einen Korpus von Trainingsdaten, die bereits annotiert (von Hand geparst) wurden. Dieser Ansatz ermöglicht es dem System, Informationen über die Häufigkeit des Auftretens verschiedener Konstruktionen in bestimmten Kontexten zu sammeln. (Siehe Maschinelles Lernen.) Zu den verwendeten Ansätzen gehören einfache PCFGs (probabilistische kontextfreie Grammatiken), maximale Entropie und neuronale Netze. Die meisten der erfolgreicheren Systeme verwenden lexikalische Statistiken (d. h. sie berücksichtigen die Identität der beteiligten Wörter sowie deren Wortart). Solche Systeme sind jedoch anfällig für eine Überanpassung und benötigen eine Art von Glättung, um effektiv zu sein. ⓘ

Parsing-Algorithmen für natürliche Sprache können sich nicht darauf verlassen, dass die Grammatik "schöne" Eigenschaften hat, wie dies bei manuell entworfenen Grammatiken für Programmiersprachen der Fall ist. Wie bereits erwähnt, sind einige Grammatikformalismen sehr schwer rechnerisch zu parsen; im Allgemeinen wird, selbst wenn die gewünschte Struktur nicht kontextfrei ist, eine Art kontextfreie Annäherung an die Grammatik verwendet, um einen ersten Durchgang durchzuführen. Algorithmen, die kontextfreie Grammatiken verwenden, stützen sich oft auf eine Variante des CYK-Algorithmus, in der Regel mit einer Heuristik, die unwahrscheinliche Analysen ausschließt, um Zeit zu sparen. (Siehe Chart-Parsing.) Einige Systeme tauschen jedoch Geschwindigkeit gegen Genauigkeit, indem sie z. B. Versionen des Shift-Reduce-Algorithmus mit linearer Zeit verwenden. Eine etwas neuere Entwicklung ist das Parse-Reranking, bei dem der Parser eine große Anzahl von Analysen vorschlägt und ein komplexeres System die beste Option auswählt. In Anwendungen zum Verstehen natürlicher Sprache wandeln semantische Parser den Text in eine Darstellung seiner Bedeutung um. ⓘ

Psycholinguistik

In der Psycholinguistik geht es beim Parsen nicht nur um die Zuordnung von Wörtern zu Kategorien (Bildung ontologischer Erkenntnisse), sondern auch um die Bewertung der Bedeutung eines Satzes nach den Regeln der Syntax, die durch Rückschlüsse aus den einzelnen Wörtern des Satzes gezogen werden (sog. Konnotation). Dies geschieht normalerweise während des Hörens oder Lesens von Wörtern. Folglich sind psycholinguistische Modelle des Parsens notwendigerweise inkrementell, d. h. sie bauen eine Interpretation auf, während der Satz verarbeitet wird, die normalerweise in Form einer partiellen syntaktischen Struktur ausgedrückt wird. Bei der Interpretation von Garden-Path-Sätzen kommt es zur Bildung von zunächst falschen Strukturen. ⓘ

Diskursanalyse

Die Diskursanalyse befasst sich mit der Analyse von Sprachgebrauch und semiotischen Ereignissen. Persuasive Sprache kann als Rhetorik bezeichnet werden. ⓘ

Computersprachen

Parser werden häufig eingesetzt, um aus einer Aneinanderreihung von Symbolen eine Baumstruktur zu machen. Ein typisches Beispiel dafür sind mathematische Ausdrücke wie

2+(2+2)-\sin(\pi )

.

Dieser Ausdruck, so wie er hier steht, besteht erstmal nur aus einer Reihe von Symbolen. Es ist die Aufgabe eines Tokenizers als Teil eines Parsers, diese Symbole (zum Beispiel in Leserichtung von links nach rechts) zu identifizieren und einzuordnen. Das Ergebnis ist eine Liste, die im Folgenden als Tabelle dargestellt wird und Zeile für Zeile zu lesen ist:

Symbol	Kategorie	Erläuterung ⓘ
2	Zahl
+	Rechenzeichen
(	Klammer auf
2	Zahl
+	Rechenzeichen
2	Zahl
)	Klammer zu
-	Rechenzeichen
sin	Symbolname	(hier: die Sinus-Funktion)
(	Klammer auf
π	Symbolname	(hier: die Kreiszahl π)
)	Klammer zu

Die (weitere) Aufgabe des Parsers ist nun, die zugrundeliegende Struktur dieser Symbolfolge zu erkennen. Häufig geschieht das in Form eines Parsebaums (abstrakter Syntaxbaum), der in diesem Fall so aussehen kann:

Dies ist die Ausgabe eines einfachen Parsers. Diese Ausgabe kann nun durch weitere Programme analysiert werden. ⓘ

Parser

Ein Parser ist eine Softwarekomponente, die Eingabedaten (häufig Text) entgegennimmt und eine Datenstruktur aufbaut - oft eine Art Parse-Baum, abstrakter Syntaxbaum oder eine andere hierarchische Struktur, die eine strukturelle Darstellung der Eingabe liefert und gleichzeitig die korrekte Syntax überprüft. Dem Parsing können andere Schritte vorausgehen oder folgen, oder diese können zu einem einzigen Schritt zusammengefasst werden. Dem Parser geht häufig ein separater lexikalischer Analysator voraus, der aus der Folge der Eingabezeichen Token erzeugt; alternativ können diese Schritte beim scannerlosen Parsen kombiniert werden. Parser können von Hand programmiert oder von einem Parsergenerator automatisch oder halbautomatisch erzeugt werden. Parsing ist eine Ergänzung zum Templating, das eine formatierte Ausgabe erzeugt. Sie können auf verschiedene Bereiche angewendet werden, treten aber oft zusammen auf, wie z. B. das scanf/printf-Paar oder die Eingabe- (Front-End-Parsing) und die Ausgabephase (Back-End-Code-Generierung) eines Compilers. ⓘ

Die Eingabe für einen Parser ist oft Text in einer Computersprache, kann aber auch Text in einer natürlichen Sprache oder weniger strukturierte Textdaten sein, wobei in diesem Fall in der Regel nur bestimmte Teile des Textes extrahiert werden, anstatt einen Parse-Baum zu erstellen. Parser reichen von sehr einfachen Funktionen wie scanf bis hin zu komplexen Programmen wie dem Frontend eines C++-Compilers oder dem HTML-Parser eines Webbrowsers. Eine wichtige Klasse des einfachen Parsings wird mit regulären Ausdrücken durchgeführt, wobei eine Gruppe regulärer Ausdrücke eine reguläre Sprache definiert und eine Engine für reguläre Ausdrücke automatisch einen Parser für diese Sprache erzeugt, der den Mustervergleich und die Extraktion von Text ermöglicht. In anderen Kontexten werden reguläre Ausdrücke stattdessen vor dem Parsen verwendet, als Lexing-Schritt, dessen Ausgabe dann vom Parser verwendet wird. ⓘ

Die Verwendung von Parsern variiert je nach Eingabe. Bei Datensprachen findet man einen Parser häufig als Dateilesefunktion eines Programms, z. B. beim Einlesen von HTML- oder XML-Text; diese Beispiele sind Auszeichnungssprachen. Bei Programmiersprachen ist ein Parser eine Komponente eines Compilers oder Interpreters, der den Quellcode einer Programmiersprache analysiert, um eine Art interner Repräsentation zu erstellen; der Parser ist ein wichtiger Schritt im Frontend des Compilers. Programmiersprachen werden in der Regel in Form einer deterministischen kontextfreien Grammatik spezifiziert, da für sie schnelle und effiziente Parser geschrieben werden können. Bei Compilern kann das Parsen selbst in einem oder mehreren Durchgängen erfolgen - siehe One-Pass-Compiler und Multi-Pass-Compiler. ⓘ

Die Nachteile eines One-Pass-Compilers können weitgehend durch das Hinzufügen von Korrekturen überwunden werden, wobei während des Vorwärtsdurchlaufs eine Codeverlagerung vorgesehen ist und die Korrekturen rückwärts angewendet werden, wenn das aktuelle Programmsegment als abgeschlossen erkannt wurde. Ein Beispiel, bei dem ein solcher Korrekturmechanismus nützlich wäre, wäre eine Vorwärts-GOTO-Anweisung, bei der das Ziel des GOTO unbekannt ist, bis das Programmsegment abgeschlossen ist. In diesem Fall würde die Anwendung der Korrektur so lange verzögert, bis das Ziel des GOTOs erkannt wurde. Umgekehrt ist bei einem rückwärtsgerichteten GOTO keine Korrektur erforderlich, da der Ort bereits bekannt ist. ⓘ

Kontextfreie Grammatiken können nur begrenzt alle Anforderungen einer Sprache ausdrücken. Der Grund dafür ist, dass der Speicher einer solchen Sprache begrenzt ist. Die Grammatik kann sich das Vorhandensein eines Konstrukts nicht über eine beliebig lange Eingabe hinweg merken; dies ist für eine Sprache notwendig, in der beispielsweise ein Name deklariert werden muss, bevor er referenziert werden kann. Mächtigere Grammatiken, die diese Einschränkung ausdrücken können, können jedoch nicht effizient geparst werden. Daher ist es eine gängige Strategie, einen entspannten Parser für eine kontextfreie Grammatik zu erstellen, der eine Obermenge der gewünschten Sprachkonstrukte akzeptiert (d. h. er akzeptiert einige ungültige Konstrukte); später können die unerwünschten Konstrukte im Schritt der semantischen Analyse (Kontextanalyse) herausgefiltert werden. ⓘ

In Python ist zum Beispiel der folgende Code syntaktisch gültig:

x = 1
print(x)

Der folgende Code ist jedoch syntaktisch gültig im Sinne der kontextfreien Grammatik und ergibt einen Syntaxbaum mit der gleichen Struktur wie der vorherige, verstößt aber gegen die semantische Regel, die verlangt, dass Variablen vor der Verwendung initialisiert werden müssen:

x = 1
print(y) <span title="Aus: Englische Wikipedia, Abschnitt &quot;Parser&quot;" class="plainlinks">[https://en.wikipedia.org/wiki/Parsing#Parser <span style="color:#dddddd">ⓘ</span>]</span>

Im Allgemeinen wird ein Parser dazu verwendet, einen Text in eine neue Struktur zu übersetzen, z. B. in einen Syntaxbaum, welcher die Hierarchie zwischen den Elementen ausdrückt. ⓘ

Überblick über den Prozess

Das folgende Beispiel zeigt den üblichen Fall des Parsens einer Computersprache mit zwei Grammatikstufen: lexikalisch und syntaktisch. ⓘ

Die erste Stufe ist die Tokengenerierung oder lexikalische Analyse, bei der der Eingabezeichenstrom in sinnvolle Symbole zerlegt wird, die durch eine Grammatik regulärer Ausdrücke definiert sind. Ein Taschenrechnerprogramm würde beispielsweise eine Eingabe wie "12 * (3 + 4)^2" in die Token 12, *, (, 3, +, 4, ), ^, 2 zerlegen, von denen jedes ein sinnvolles Symbol im Zusammenhang mit einem arithmetischen Ausdruck ist. Der Lexer würde Regeln enthalten, die ihm sagen, dass die Zeichen *, +, ^, ( und ) den Beginn eines neuen Tokens markieren, so dass bedeutungslose Token wie "12*" oder "(3" nicht erzeugt werden. ⓘ

Der nächste Schritt ist das Parsen oder die syntaktische Analyse, bei der geprüft wird, ob die Token einen zulässigen Ausdruck bilden. Dies geschieht in der Regel unter Bezugnahme auf eine kontextfreie Grammatik, die rekursiv die Komponenten definiert, aus denen ein Ausdruck bestehen kann, und die Reihenfolge, in der sie erscheinen müssen. Allerdings können nicht alle Regeln, die Programmiersprachen definieren, allein durch kontextfreie Grammatiken ausgedrückt werden, z. B. die Gültigkeit von Typen und die korrekte Deklaration von Bezeichnern. Diese Regeln können mit Attributgrammatiken formell ausgedrückt werden. ⓘ

Die letzte Phase ist das semantische Parsing oder die Analyse, bei der die Implikationen des soeben validierten Ausdrucks herausgearbeitet und die entsprechenden Maßnahmen ergriffen werden. Im Falle eines Rechners oder Interpreters besteht die Aktion darin, den Ausdruck oder das Programm auszuwerten; ein Compiler hingegen würde eine Art von Code erzeugen. Auch Attributgrammatiken können verwendet werden, um diese Aktionen zu definieren. ⓘ

Arten von Parsern

Die Aufgabe des Parsers besteht im Wesentlichen darin, festzustellen, ob und wie die Eingabe aus dem Startsymbol der Grammatik abgeleitet werden kann. Dies kann im Wesentlichen auf zwei Arten geschehen:

Top-Down-Parsing - Top-Down-Parsing kann als ein Versuch angesehen werden, Ableitungen von der linken Seite eines Eingabestroms zu finden, indem nach Parse-Bäumen unter Verwendung einer Top-Down-Expansion der gegebenen formalen Grammatikregeln gesucht wird. Die Token werden von links nach rechts konsumiert. Inclusive Choice wird verwendet, um Mehrdeutigkeit zu berücksichtigen, indem alle alternativen rechten Seiten von Grammatikregeln expandiert werden. Dieser Ansatz wird als "Ursuppe" (primordial soup) bezeichnet. Ähnlich wie bei der Satzdiagrammerstellung werden bei der Primordial Soup die Satzbestandteile zerlegt.
Bottom-up-Parsing - Ein Parser kann mit der Eingabe beginnen und versuchen, sie in das Startsymbol umzuschreiben. Intuitiv versucht der Parser, die grundlegendsten Elemente zu finden, dann die Elemente, die diese enthalten, und so weiter. LR-Parser sind Beispiele für Bottom-up-Parser. Ein anderer Begriff für diese Art von Parser ist Shift-Reduce-Parsing. ⓘ

LL-Parser und Recursive-Descent-Parser sind Beispiele für Top-Down-Parser, die keine linksrekursiven Produktionsregeln zulassen. Obwohl angenommen wurde, dass einfache Implementierungen von Top-Down-Parsern direkte und indirekte Linksrekursion nicht berücksichtigen können und beim Parsen von mehrdeutigen kontextfreien Grammatiken exponentielle Zeit- und Raumkomplexität benötigen, wurden von Frost, Hafiz und Callaghan ausgefeiltere Algorithmen für Top-Down-Parser entwickelt, die Mehrdeutigkeit und Linksrekursion in polynomialer Zeit berücksichtigen und polynomiale Darstellungen der potenziell exponentiellen Anzahl von Parse-Bäumen erzeugen. Ihr Algorithmus ist in der Lage, sowohl linke als auch rechte Ableitungen einer Eingabe in Bezug auf eine gegebene kontextfreie Grammatik zu erzeugen. ⓘ

Eine wichtige Unterscheidung bei Parsern ist, ob ein Parser eine ganz linke Ableitung oder eine ganz rechte Ableitung erzeugt (siehe kontextfreie Grammatik). LL-Parser erzeugen eine ganz linke Ableitung und LR-Parser eine ganz rechte Ableitung (allerdings meist in umgekehrter Reihenfolge). ⓘ

Einige grafische Parsing-Algorithmen wurden für visuelle Programmiersprachen entwickelt. Parser für visuelle Sprachen basieren manchmal auf Graphgrammatiken. ⓘ

Adaptive Parsing-Algorithmen wurden verwendet, um "sich selbst erweiternde" Benutzeroberflächen für natürliche Sprachen zu konstruieren. ⓘ

Man unterscheidet verschiedene Parse-Verfahren. Dabei wird nach genereller Vorgehensweise, also der Unterscheidung nach der Reihenfolge, in der die Knoten des Ableitungsbaums erstellt werden (top-down, auch theoriegetriebenes Parsing oder bottom-up, auch eingabegetriebenes Parsing, sowie left corner), spezifischer Vorgehensweise (LL, LR, SLR, LALR, LC, …) und Implementierungstechnik (rekursiv absteigend, rekursiv aufsteigend oder tabellengesteuert) unterschieden. Weiter wird auch nach Grammatikart unterschieden. ⓘ

Implementierung

Die einfachsten Parser-APIs lesen die gesamte Eingabedatei, führen einige Zwischenberechnungen durch und schreiben dann die gesamte Ausgabedatei. (Wie z. B. In-Memory-Multi-Pass-Compiler). ⓘ

Diese einfachen Parser funktionieren nicht, wenn nicht genügend Speicher vorhanden ist, um die gesamte Eingabedatei oder die gesamte Ausgabedatei zu speichern. Sie eignen sich auch nicht für unendliche Datenströme aus der realen Welt. ⓘ

Einige alternative API-Ansätze für das Parsen solcher Daten:

Push-Parser, die die registrierten Handler (Callbacks) aufrufen, sobald der Parser relevante Token im Eingabestrom entdeckt (wie Expat)
Pull-Parser
inkrementelle Parser (z. B. inkrementelle Diagrammparser), die bei der Bearbeitung des Textes der Datei durch den Benutzer nicht die gesamte Datei neu parsen müssen.
Aktive gegenüber passiven Parsern ⓘ

Parser für kontextsensitive Grammatiken

Packrat Parser (Parsing Expression Grammars) ⓘ

Das Parsen wohldefinierter künstlicher Sprachen (siehe formale Sprachen, Programmiersprachen) ist weniger komplex als das Parsen frei gewachsener natürlicher Sprachen wie Englisch oder Deutsch, die durch eine Vielzahl von Mehrdeutigkeiten, Irregularitäten und Inkonsistenzen geprägt sind. Siehe hierzu auch Computerlinguistik. ⓘ

Hinweis: Der Begriff parsen sollte nicht mit dem Begriff kompilieren verwechselt werden. Letzteres erzeugt einen Zielcode aus einem Quellcode, dabei wird unter anderem auch geparst, darüber hinaus finden aber weitere Aktionen statt. ⓘ

Software zur Entwicklung von Parsern

Einige der bekanntesten Parser-Entwicklungswerkzeuge sind die folgenden:

ANTLR
Bison
Coco/R
Grammatik der definiten Klauseln
GOLD
JavaCC
Zitrone
Lex
LuZc
Parboiled
Parsec
Ragel
Spirit Parser Framework
Formalismus der Syntaxdefinition
SYNTAX
XPL
Yacc
PackCC ⓘ

Lookahead

C-Programm, das mit weniger als 2 Token Lookahead nicht geparst werden kann. Oben: Ausschnitt aus der C-Grammatik. Unten: ein Parser hat die Token verdaut "int v;main(){" verdaut und ist dabei, eine Regel zur Ableitung von Stmt auszuwählen. Er betrachtet nur das erste Vorausschau-Token "v"sieht, kann er nicht entscheiden, welche der beiden Alternativen für Stmt zu wählen ist; für die letztere ist ein Blick auf das zweite Token erforderlich. ⓘ

Lookahead legt die maximale Anzahl eingehender Token fest, die ein Parser verwenden kann, um zu entscheiden, welche Regel er verwenden soll. Lookahead ist besonders für LL-, LR- und LALR-Parser relevant, wo er oft explizit angegeben wird, indem der Lookahead in Klammern an den Namen des Algorithmus angehängt wird, wie z. B. LALR(1). ⓘ

Die meisten Programmiersprachen, das primäre Ziel von Parsern, sind sorgfältig so definiert, dass ein Parser mit begrenztem Lookahead, typischerweise einer, sie parsen kann, weil Parser mit begrenztem Lookahead oft effizienter sind. Eine wichtige Änderung dieses Trends trat 1990 ein, als Terence Parr im Rahmen seiner Doktorarbeit ANTLR entwickelte, einen Parsergenerator für effiziente LL(k)-Parser, wobei k ein beliebiger fester Wert ist. ⓘ

LR-Parser haben typischerweise nur ein paar Aktionen, nachdem sie jedes Token gesehen haben. Diese sind Shift (Hinzufügen dieses Tokens zum Stapel für eine spätere Reduktion), Reduce (Token vom Stapel nehmen und ein syntaktisches Konstrukt bilden), End, Error (keine bekannte Regel trifft zu) oder Conflict (weiß nicht, ob Shift oder Reduce). ⓘ

Lookahead hat zwei Vorteile.

Er hilft dem Parser, im Falle von Konflikten die richtige Maßnahme zu ergreifen. Zum Beispiel beim Parsen der if-Anweisung im Falle einer else-Klausel.
Er eliminiert viele doppelte Zustände und erleichtert die Last eines zusätzlichen Stacks. Ein C-Sprachparser ohne Lookahead hat etwa 10.000 Zustände. Ein Lookahead-Parser hat etwa 300 Zustände. ⓘ

Beispiel: Parsen des Ausdrucks 1 + 2 * 3 ⓘ

Der Satz von Regeln für die Analyse von Ausdrücken (Grammatik genannt) lautet wie folgt ⓘ
Regel1:	E → E + E	Der Ausdruck ist die Summe von zwei Ausdrücken.
Regel2:	E → E * E	Der Ausdruck ist das Produkt zweier Ausdrücke.
Regel3:	E → Zahl	Ausdruck ist eine einfache Zahl
Regel4:	+ hat weniger Vorrang als *

Die meisten Programmiersprachen (mit Ausnahme einiger weniger wie APL und Smalltalk) und algebraischen Formeln geben der Multiplikation einen höheren Vorrang als der Addition. In diesem Fall ist die korrekte Interpretation des obigen Beispiels 1 + (2 * 3). Beachten Sie, dass die obige Regel4 eine semantische Regel ist. Es ist möglich, die Grammatik umzuschreiben, um sie in die Syntax zu integrieren. Allerdings können nicht alle Regeln dieser Art in die Syntax übersetzt werden. ⓘ

Einfache Nicht-Lookahead-Parser-Aktionen

Anfänglich Eingabe = [1, +, 2, *, 3]

Verschiebung der "1" von der Eingabe auf den Stapel (in Erwartung von Regel3). Eingabe = [+, 2, *, 3] Stapel = [1]
Reduziert "1" auf den Ausdruck "E" auf der Grundlage von Regel3. Stapel = [E]
Schiebt "+" von der Eingabe auf den Stapel (in Erwartung von Regel1). Eingabe = [2, *, 3] Stapel = [E, +]
Schiebe "2" von der Eingabe auf den Stapel (in Erwartung von Regel3). Eingabe = [*, 3] Stapel = [E, +, 2]
Reduziere das Stackelement "2" auf den Ausdruck "E" basierend auf Regel3. Stapel = [E, +, E]
Reduziere die Stack-Elemente [E, +, E] und die neue Eingabe "E" auf der Grundlage von Regel1 zu "E". Stapel = [E]
Schiebe "*" von der Eingabe auf den Stapel (in Erwartung von Regel2). Eingabe = [3] Stapel = [E,*]
Schiebt "3" von der Eingabe auf den Stapel (in Erwartung von Regel3). Eingabe = [] (leer) Stapel = [E, *, 3]
Reduziere das Stackelement "3" auf den Ausdruck "E" auf der Grundlage von Regel3. Stapel = [E, *, E]
Reduziere die Stackelemente [E, *, E] und die neue Eingabe "E" auf der Grundlage von Regel2 zu "E". Stack = [E] ⓘ

Der Parse-Baum und der sich daraus ergebende Code sind gemäß der Sprachsemantik nicht korrekt. ⓘ

Um ohne Vorausschau korrekt zu parsen, gibt es drei Lösungen:

Der Benutzer muss Ausdrücke in Klammern einschließen. Dies ist oft keine praktikable Lösung.
Der Parser muss über mehr Logik verfügen, um zurückverfolgen und erneut versuchen zu können, wenn eine Regel verletzt wird oder nicht vollständig ist. Eine ähnliche Methode wird bei LL-Parsern angewandt.
Alternativ dazu muss der Parser oder die Grammatik über eine zusätzliche Logik verfügen, um die Reduktion zu verzögern und nur dann zu reduzieren, wenn er sich absolut sicher ist, welche Regel zuerst zu reduzieren ist. Diese Methode wird in LR-Parsern verwendet. Damit wird der Ausdruck korrekt geparst, allerdings mit viel mehr Zuständen und einer größeren Stapeltiefe. ⓘ

Lookahead-Parser-Aktionen

Verschiebung von 1 auf den Stapel von Eingabe 1 in Erwartung von Regel3. Es wird nicht sofort abgebaut.
Reduziere Stack-Element 1 zu einem einfachen Ausdruck bei Eingabe + auf der Grundlage von Regel3. Der Lookahead ist +, also sind wir auf dem Weg zu E +, so dass wir den Stapel auf E reduzieren können.
Verschiebe + auf den Stapel am Eingang + in Erwartung von Regel1.
Schiebe 2 auf den Stapel am Eingang 2 in Erwartung von Regel3.
Reduziere Stack-Element 2 auf Expression am Eingang * basierend auf Regel3. Der Lookahead * erwartet nur E vor ihm.
Jetzt hat der Stapel E + E und die Eingabe ist immer noch *. Er hat nun zwei Möglichkeiten, entweder die Verschiebung aufgrund von Regel2 oder die Reduzierung aufgrund von Regel1. Da * einen höheren Vorrang hat als + nach Regel4, schieben wir * in Erwartung von Regel2 auf den Stapel.
Verschieben Sie 3 auf den Stapel am Eingang 3 in Erwartung von Regel3.
Reduziere Stapelposition 3 zu Expression, nachdem du das Ende der Eingabe gesehen hast, basierend auf Regel3.
Reduziere die Stapelpositionen E * E zu E basierend auf Regel2.
Reduziere die Stack-Elemente E + E zu E basierend auf Regel1.

Der erzeugte Parse-Baum ist korrekt und einfach effizienter als Parser ohne Vorausschau. Dies ist die Strategie, die in LALR-Parsern verfolgt wird. ⓘ