LL-Parser

In der Informatik ist ein LL-Parser ein Top-Down-Parser für eine eingeschränkte kontextfreie Sprache . Er analysiert die Eingabe von links nach rechts und führt die Ableitung des Satzes vom linken Ende aus durch.

Ein LL-Parser heißt LL( k )-Parser, wenn er beim Parsen eines Satzes k Lookahead - Token verwendet . Eine Grammatik heißt LL( k )-Grammatik, wenn sich daraus ein LL( k )-Parser konstruieren lässt. Eine formale Sprache heißt LL( k )-Sprache, wenn sie eine LL( k )-Grammatik besitzt. Die Menge der LL( k )-Sprachen ist für jedes k  ≥ 0 vollständig in der Menge der LL( k +1)-Sprachen enthalten . ^{[ 1 ]} Daraus folgt, dass nicht alle kontextfreien Sprachen von einem LL( k )-Parser erkannt werden können.

Ein LL-Parser heißt LL-regulär (LLR), wenn er eine LL-reguläre Sprache parst . ^{[ 2 ] [ 3 ] [ 4 ]} Die Klasse der LLR-Grammatiken umfasst jede LL( k )-Grammatik für jedes k . Zu jeder LLR-Grammatik existiert ein LLR-Parser, der die Grammatik in linearer Zeit parst.

Zwei Arten von Ausreißerparsern sind LL(*) und LL(finite). Ein Parser wird als LL(*)/LL(finite) bezeichnet, wenn er die LL(*)/LL(finite)-Parsingstrategie verwendet. ^{[ 5 ] [ 6 ]} LL(*)- und LL(finite)-Parser sind funktional näher an PEG- Parsern. Ein LL(finite)-Parser kann eine beliebige LL( k )-Grammatik hinsichtlich der Anzahl der Lookahead-Vorhersagen und Lookahead-Vergleiche optimal parsen. Die Klasse der mit der LL(*)-Strategie parsbaren Grammatiken umfasst aufgrund der Verwendung syntaktischer und semantischer Prädikate einige kontextsensitive Sprachen und ist noch nicht identifiziert. Es wurde vorgeschlagen, LL(*)-Parser besser als TDPL- Parser zu betrachten. ^{[ 7 ]} Entgegen der weit verbreiteten Annahme sind LL(*)-Parser im Allgemeinen nicht LLR-Parser und es ist konstruktionsbedingt garantiert, dass sie im Durchschnitt schlechter abschneiden (superlinear gegenüber linearer Zeit) und im schlimmsten Fall noch viel schlechter (exponentiell gegenüber linearer Zeit).

LL-Grammatiken, insbesondere LL(1)-Grammatiken, sind von großem praktischem Interesse, da Parser für diese Grammatiken leicht zu konstruieren sind und viele Programmiersprachen aus diesem Grund als LL(1)-Grammatiken konzipiert sind. ^{[ 8 ]} LL-Parser können tabellenbasiert sein, ^{[ 9 ]} d. h. ähnlich wie LR-Parser , aber LL-Grammatiken können auch durch rekursive Abstiegsparser analysiert werden . Laut Waite und Goos (1984) ^{[ 10 ]} wurden LL( k )-Grammatiken von Stearns und Lewis (1969) eingeführt. ^{[ 11 ]}

Für eine gegebene kontextfreie Grammatik versucht der Parser, die linke Ableitung zu finden . Gegeben sei eine Beispielgrammatik G :

1. ${\displaystyle S\to E}$
2. ${\displaystyle E\to (E+E)}$
3. ${\displaystyle E\to i}$

Die am weitesten links stehende Ableitung für lautet: ${\displaystyle w=((i+i)+i)}$

${\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(2)}{\Rightarrow }}\ (E+E)\ {\overset {(2)}{\Rightarrow }}\ ((E+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+E)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+E)\ {\overset {(3)}{\Rightarrow }}\ ((i+i)+i)}$

Im Allgemeinen gibt es mehrere Möglichkeiten bei der Auswahl einer Regel zur Expansion des am weitesten links stehenden Nichtterminals. In Schritt 2 des vorherigen Beispiels muss der Parser entscheiden, ob Regel 2 oder Regel 3 angewendet werden soll:

${\displaystyle S\ {\overset {(1)}{\Rightarrow }}\ E\ {\overset {(?)}{\Rightarrow }}\ ?}$

Um effizient zu sein, muss der Parser diese Wahl nach Möglichkeit deterministisch treffen können, ohne zurückzuverfolgen . Bei manchen Grammatiken kann er dies durch einen kurzen Blick auf die noch nicht gelesene Eingabe (ohne sie zu lesen) erreichen. In unserem Beispiel: Wenn der Parser weiß, dass das nächste noch nicht gelesene Symbol ( ist , ist die einzig korrekte Regel 2.

Im Allgemeinen kann ein LL( k )-Parser k Symbole voraussehen . Allerdings ist das Problem, ob für ein gegebenes k ein LL( k )-Parser existiert , der die Grammatik erkennt, unentscheidbar . Für jedes k gibt es eine Sprache, die von einem LL( k )-Parser nicht erkannt werden kann, wohl aber von einem LL( k +1) -Parser.

Mithilfe der obigen Analyse lässt sich folgende formale Definition angeben:

Sei G eine kontextfreie Grammatik und k ≥ 1. Wir sagen, dass G LL( k ) ist, wenn für je zwei Linksableitungen gilt:

1. ${\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\beta \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wu}$
2. ${\displaystyle S\ \Rightarrow \ \cdots \ \Rightarrow \ wA\alpha \ \Rightarrow \ \cdots \ \Rightarrow \ w\gamma \alpha \ \Rightarrow \ \cdots \ \Rightarrow \ wv}$

Die folgende Bedingung gilt: Wenn das Präfix der Zeichenkette der Länge k gleich dem Präfix der Zeichenkette der Länge k ist, dann folgt daraus . ${\displaystyle u}$${\displaystyle k}$${\displaystyle v}$${\displaystyle \beta =\gamma }$

In dieser Definition ist das Startsymbol und ein beliebiges Nichtterminalsymbol. Die bereits abgeleitete Eingabe und die noch ungelesenen Zeichenketten und sind Terminalzeichenketten. Die griechischen Buchstaben , und repräsentieren beliebige Zeichenketten aus Terminal- und Nichtterminalsymbolen (auch leer). Die Präfixlänge entspricht der Größe des Lookahead-Puffers. Laut Definition ist dieser Puffer ausreichend, um zwischen zwei beliebigen Ableitungen verschiedener Wörter zu unterscheiden. ${\displaystyle S}$${\displaystyle A}$${\displaystyle w}$${\displaystyle u}$${\displaystyle v}$${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle \gamma }$

Der LL( k )-Parser ist ein deterministischer Kellerautomat, der die nächsten k Eingabesymbole vorab einsehen kann, ohne sie einzulesen. Diese Vorab-Funktion lässt sich emulieren, indem der Inhalt des Lookahead-Puffers im endlichen Zustandsraum gespeichert wird, da sowohl der Puffer als auch das Eingabealphabet endlich groß sind. Dadurch wird der Automat zwar nicht leistungsfähiger, aber es handelt sich um eine praktische Abstraktion.

Das Stapelalphabet ist , wobei: ${\displaystyle \Gamma =N\cup \Sigma }$

• ${\displaystyle N}$ist die Menge der Nichtterminale;
• ${\displaystyle \Sigma }$die Menge der Terminalsymbole (Eingabesymbole) mit einem speziellen Eingabeende-Symbol (EOI) $ .

Der Parserstapel enthält anfänglich das Startsymbol oberhalb des EOI: [ S $ ] . Während der Ausführung ersetzt der Parser wiederholt das oberste Symbol auf dem Stapel: ${\displaystyle X}$

• mit einigen , wenn und es gibt eine Regel ;${\displaystyle \alpha }$${\displaystyle X\in N}$${\displaystyle X\to \alpha }$
• mit (in manchen Notationen ), d. h. wird vom Stapel entfernt, wenn . In diesem Fall wird ein Eingabesymbol gelesen, und wenn , weist der Parser die Eingabe zurück.${\displaystyle \epsilon }$${\displaystyle \lambda }$${\displaystyle X}$${\displaystyle X\in \Sigma }$${\displaystyle x}$${\displaystyle x\neq X}$

Wenn das letzte vom Stapel zu entfernende Symbol das EOI ist, ist die Analyse erfolgreich; der Automat akzeptiert über einen leeren Stapel.

Die Zustände und die Übergangsfunktion werden nicht explizit angegeben; sie werden stattdessen mithilfe einer praktischeren Syntaxtabelle spezifiziert (generiert) . Die Tabelle liefert die folgende Zuordnung:

• Zeile: Symbol für Stapelspitze${\displaystyle X}$
• Spalte: | w | ≤ k Lookahead-Pufferinhalt
• Zelle: Regelnummer für oder${\displaystyle X\to \alpha }$${\displaystyle \epsilon }$

Kann der Parser keinen gültigen Übergang durchführen, wird die Eingabe zurückgewiesen (leere Zellen). Um die Tabelle übersichtlicher zu gestalten, werden üblicherweise nur die Nicht-Terminalzeilen angezeigt, da die Vorgehensweise für Terminals identisch ist.

Um die Funktionsweise eines LL(1)-Parsers zu erklären, betrachten wir die folgende kleine LL(1)-Grammatik:

1. S → F
2. S → ( S + F )
3. F → a

und die folgende Eingabe analysieren:

( a + a )

Eine LL(1)-Parsertabelle für eine Grammatik hat eine Zeile für jedes der Nichtterminale und eine Spalte für jedes Terminal (einschließlich des speziellen Terminals, das hier als $ dargestellt wird und das Ende des Eingabestroms anzeigt).

Jede Zelle der Tabelle kann höchstens auf eine Grammatikregel (identifiziert durch ihre Nummer) verweisen. Beispielsweise verweist in der Parsing-Tabelle für die obige Grammatik die Zelle für das Nichtterminal 'S' und das Terminal ' ( ' auf die Regelnummer 2:

	(	)	A	+	$
S	2	—	1	—	—
F	—	—	3	—	—

Der Algorithmus zum Erstellen einer Syntaxtabelle wird in einem späteren Abschnitt beschrieben, aber zunächst wollen wir sehen, wie der Parser die Syntaxtabelle zur Verarbeitung seiner Eingabe verwendet.

In jedem Schritt liest der Parser das nächste verfügbare Symbol aus dem Eingabestrom und das oberste Symbol vom Stapel. Stimmen Eingabesymbol und oberstes Symbol überein, verwirft der Parser beide, indem er zum nächsten Eingabesymbol übergeht und das oberste Symbol vom Stapel entfernt. Dieser Vorgang wird wiederholt, bis Eingabesymbol und oberstes Symbol nicht mehr übereinstimmen.

Im ersten Schritt liest der Parser das Eingabesymbol ' ( ' und das oberste Symbol des Stacks 'S'. Die Anweisung für die Parsertabelle stammt aus der Spalte mit dem Eingabesymbol ' ( ' und der Zeile mit dem obersten Symbol des Stacks 'S'. Diese Zelle enthält '2', was den Parser anweist, Regel (2) anzuwenden. Der Parser muss 'S' auf dem Stack in ' ( S + F ) ' umschreiben, indem er 'S' vom Stack entfernt und ')', 'F', ' + ', 'S', ' ( ' auf den Stack legt. Dadurch wird Regel Nummer 2 in die Ausgabe geschrieben. Der Stack sieht dann wie folgt aus:

[ ( , S, + , F, ) , $ ] 

Im zweiten Schritt entfernt der Parser das ' ( ' aus seinem Eingabestream und aus seinem Stack, da sie nun übereinstimmen. Der Stack sieht nun folgendermaßen aus:

[ S, + , F, ) , $ ] 

Der Parser hat nun ein ' a' im Eingabestrom und ein 'S' als oberstes Element im Stack. Die Parsertabelle weist ihn an, Regel (1) der Grammatik anzuwenden und die Regelnummer 1 in den Ausgabestrom zu schreiben. Der Stack sieht dann wie folgt aus:

[ F, + , F, ) , $ ] 

Der Parser hat nun ein ' a' im Eingabestrom und ein 'F' als oberstes Element im Stack. Die Parsertabelle weist ihn an, Regel (3) der Grammatik anzuwenden und die Regel Nummer 3 in den Ausgabestrom zu schreiben. Der Stack sieht dann wie folgt aus:

[ a , + , F, ) , $ ] 

Der Parser hat nun ein ' a' im Eingabestream und ein ' a ' oben auf dem Stack. Da sie identisch sind, entfernt er es aus dem Eingabestream und vom Stack. Anschließend hat der Parser ein ' + ' im Eingabestream, und auch das ' + ' befindet sich oben auf dem Stack. Das bedeutet, dass es, wie beim 'a', vom Stack entfernt und aus dem Eingabestream gelöscht wird. Das Ergebnis ist:

[ F, ) , $ ] 

In den nächsten drei Schritten ersetzt der Parser das 'F' auf dem Stack durch ein ' a ', schreibt die Regel Nummer 3 in den Ausgabestream und entfernt das ' a ' und die ' ) ' sowohl vom Stack als auch vom Eingabestream. Der Parser endet somit mit einem ' $ ' auf dem Stack und im Eingabestream.

In diesem Fall meldet der Parser, dass er die Eingabezeichenfolge akzeptiert hat, und schreibt die folgende Liste von Regelnummern in den Ausgabestream:

[ 2, 1, 3, 3 ]

Dies ist in der Tat eine Liste von Regeln für eine Linksableitung der Eingabezeichenkette, die wie folgt lautet:

S → ( S + F ) → ( F + F ) → ( a + F ) → ( a + a )

Nachfolgend eine C++- Implementierung eines tabellenbasierten LL-Parsers für die Beispielsprache:

#include <iostream> #include <map> #include <stack>​​​enum Symbols { // die Symbole: // Terminalsymbole: TS_L_PARENS , // ( TS_R_PARENS , // ) TS_A , // a TS_PLUS , // + TS_EOS , // $, entspricht in diesem Fall '\0' TS_INVALID , // ungültiges Token// Nichtterminalsymbole: NTS_S , // S NTS_F // F };/* Konvertiert ein gültiges Token in das entsprechende Terminalsymbol */ Symbols lexer ( char c ) { switch ( c ) { case '(' : return TS_L_PARENS ; case ')' : return TS_R_PARENS ; case 'a' : return TS_A ; case '+' : return TS_PLUS ; case '\0' : return TS_EOS ; // Ende des Stacks: das Terminalsymbol $ default : return TS_INVALID ; } }int main ( int argc , char ** argv ) { using namespace std ;if ( argc < 2 ) { cout << "usage: \n\t ll '(a+a)'" << endl ; return 0 ; }// LL - Parsertabelle, ordnet < Nichtterminal, Terminal>-Paaren Aktionen zu map < Symbole , map < Symbole , int >> table ; stack <Symbole> ss ; // Symbolstapel char * p ; // Eingabepuffer// Initialisiere den Symbolstapel ss.push ( TS_EOS ); // Terminal, $ ss.push ( NTS_S ) ; // Nichtterminal, S// Initialisiere den Symbolstromcursor p = & argv [ 1 ][ 0 ];// Parsingtabelle einrichten table [ NTS_S ][ TS_L_PARENS ] = 2 ; table [ NTS_S ][ TS_A ] = 1 ; table [ NTS_F ][ TS_A ] = 3 ;while ( ss.size ( ) > 0 ) { if ( lexer ( * p ) == ss.top ( ) ) { cout << "Übereinstimmende Symbole: " << lexer ( * p ) << endl ; p ++ ; ss.pop ( ) ; } else { cout << " Regel " << table [ ss.top ( )][ lexer ( * p )] << endl ; switch ( table [ ss.top ( )][ lexer ( * p ) ]) { case 1 : // 1. S → F ss.pop ( ) ; ss.push ( NTS_F ) ; // F break ;Fall 2 : // 2. S → (S + F) ss.pop ( ) ; ss.push ( TS_R_PARENS ) ; // ) ss.push ( NTS_F ) ; // F ss.push ( TS_PLUS ) ; // + ss.push ( NTS_S ) ; // S ss.push ( TS_L_PARENS ) ; // ( break ;Fall 3 : // 3. F → a ss.pop ( ) ; ss.push ( TS_A ) ; // a break ;default : cout << "Tabellenanalyse abgeschlossen" << endl ; return 0 ; } } }cout << "Parsing abgeschlossen" << endl ;return 0 ; }

from enum import Enum from collections.abc import Generatorclass Term ( Enum ): passclass Rule ( Enum ): pass# Alle Konstanten sind ab 0 indiziert. Klasse Terminal ( Term ): LPAR = 0 RPAR = 1 A = 2 PLUS = 3 END = 4 INVALID = 5def __str__ ( self ): return f "T_ { self . name } "Klasse Nichtterminal ( Regel ): S = 0 F = 1def __str__ ( self ): return f "N_ { self . name } "# Tabelle parsen table = [[ 1 , - 1 , 0 , - 1 , - 1 , - 1 ], [ - 1 , - 1 , 2 , - 1 , - 1 , - 1 ]]REGELN = [ [ Nichtterminal . F ], [ Terminal . LPAR , Nichtterminal . S , Terminal . PLUS , Nichtterminal . F , Terminal . RPAR , ], [ Terminal . A ], ]stack = [ Terminal . END , NonTerminal . S ]def lexical_analysis ( input_string : str ) -> Generator [ Terminal ] : print ( " Lexikalische Analyse " ) for c in input_string : match c : case " a " : yield Terminal.A case " + " : yield Terminal.PLUS case " ( " : yield Terminal.LPAR case " ) " : yield Terminal.RPAR case _ : yield Terminal.INVALID yield Terminal.ENDdef syntactic_analysis ( tokens : list [ Terminal ]) -> None : print ( "Tokens:" , end = "" ) print ( * tokens , sep = " " , "" ) print ( "Syntaktische Analyse" ) position = 0 while stack : svalue = stack.pop ( ) token = tokens [ position ] if isinstance ( svalue , Term ): if svalue == token : position += 1 print ( "pop" , svalue ) if token == Terminal.END : print ( " Eingabe akzeptiert" ) else : raise ValueError ( "Ungültiger Term in der Eingabe:" , str ( token )) elif isinstance ( svalue , Rule ): print ( f " { svalue = ! s } , { token = !s } " ) rule = table [ svalue.value ] [ token . Wert ] print ( f " { Regel = } " ) for r in reversed ( RULES [ Regel ]): stack . append ( r ) print ( "Stapel:" , end = " " ) print ( * stack , sep = ", " )if __name__ == "__main__" : inputstring = "(a+a)" syntactic_analysis ( list ( lexical_analysis ( inputstring )))

Ausgaben:

Lexikalische Analyse Token: T_LPAR, T_A, T_PLUS, T_A, T_RPAR, T_END Syntaktische Analyse svalue = N_S, Token = T_LPAR Regel = 1 Stacks: T_END, T_RPAR, N_F, T_PLUS, N_S, T_LPAR pop T_LPAR Stacks: T_END, T_RPAR, N_F, T_PLUS, N_S svalue = N_S, Token = T_A Regel = 0 Stacks: T_END, T_RPAR, N_F, T_PLUS, N_F svalue = N_F, Token = T_A Regel = 2 Stacks: T_END, T_RPAR, N_F, T_PLUS, T_A pop T_A Stacks: T_END, T_RPAR, N_F, T_PLUS pop T_PLUS Stacks: T_END, T_RPAR, N_F svalue = N_F, Token = T_A Regel = 2 Stapel: T_END, T_RPAR, T_A T_A entfernen Stapel: T_END, T_RPAR T_RPAR entfernen Stapel: T_END T_END entfernen Eingabe akzeptiert Stapel:

Wie aus dem Beispiel ersichtlich, führt der Parser drei Arten von Schritten aus, je nachdem, ob das oberste Element des Stapels ein Nichtterminal, ein Terminal oder das Sondersymbol $ ist :

• Wenn das oberste Symbol ein Nichtterminalsymbol ist, sucht der Parser anhand dieses Nichtterminalsymbols und des Symbols im Eingabestrom in der Syntaxtabelle nach der Grammatikregel, die er verwenden soll, um das Nichtterminalsymbol auf dem Stapel zu ersetzen. Die Nummer der Regel wird in den Ausgabestrom geschrieben. Falls die Syntaxtabelle keine solche Regel anzeigt, meldet der Parser einen Fehler und beendet den Vorgang.
• Wenn das oberste Zeichen ein Terminalsymbol ist, vergleicht der Parser es mit dem Symbol im Eingabestrom. Stimmen sie überein, werden beide entfernt. Andernfalls meldet der Parser einen Fehler und beendet den Vorgang.
• Wenn das oberste Zeichen ein Dollarzeichen ($) ist und sich auch im Eingabestream ein Dollarzeichen befindet , meldet der Parser, dass die Eingabe erfolgreich analysiert wurde; andernfalls meldet er einen Fehler. In beiden Fällen wird der Parser beendet.

Diese Schritte werden so lange wiederholt, bis der Parser stoppt. Dann hat er entweder die Eingabe vollständig analysiert und eine Linksableitung in den Ausgabestream geschrieben oder er hat einen Fehler gemeldet.

Um die Parsertabelle zu füllen, müssen wir festlegen, welche Grammatikregel der Parser wählen soll, wenn er ein Nichtterminalsymbol A oben auf seinem Stack und ein Symbol a in seinem Eingabestrom findet. Es ist leicht einzusehen, dass eine solche Regel die Form A → w haben sollte und dass die zu w gehörige Sprache mindestens eine Zeichenkette enthalten muss, die mit a beginnt . Zu diesem Zweck definieren wir die erste Menge von w , hier als Fi ( w ) geschrieben, als die Menge der Terminalsymbole , die am Anfang einer Zeichenkette in w stehen können, zuzüglich ε _, falls die leere Zeichenkette ebenfalls zu w gehört . Gegeben eine Grammatik mit den Regeln A₁ → w₁ , _... , Aₙ _→ wₙ _{, können} wir Fi ( wᵢ ₎ und Fi ( Aᵢ ) für jede Regel wie folgt berechnen :

1. Initialisiere jedes Fi ( A _i ) mit der leeren Menge
2. Addiere Fi( w _i ) zu Fi ( A _i ) für jede Regel A _i → w _i ​​, wobei Fi wie folgt definiert ist:
   • Fi( aw ′ ) = { a } für jedes Terminal a
   • Fi( Aw ′ ) = Fi ( A ) für jedes Nichtterminalsymbol A mit ε nicht in Fi ( A )
   • Fi( Aw ′ ) = ( Fi ( A ) \ { ε }) ∪ Fi( w' ) für jedes Nichtterminalsymbol A mit ε in Fi ( A )
   • Fi(ε) = { ε }
3. Füge Fi( w _i ) zu Fi ( A _i ) für jede Regel A _i → w _{i ​​hinzu.}
4. Wiederholen Sie die Schritte 2 und 3 so lange, bis alle Fi- Einstellungen unverändert bleiben.

Das Ergebnis ist die Lösung mit dem kleinsten Fixpunkt für das folgende System:

• Fi ( A ) ⊇ Fi ( w ) für jede Regel A → w
• Fi ( a ) ⊇ { a }, für jedes Terminal a
• Fi ( w ₀ w ₁ ) ⊇ Fi ( w ₀ )· Fi ( w ₁ ), für alle Wörter w ₀ und w ₁
• Fi ( ε ) ⊇ { ε }

wobei für Wortmengen U und V das abgeschnittene Produkt durch definiert ist und w:1 das anfängliche Länge-1-Präfix von Wörtern w der Länge 2 oder mehr oder w selbst bezeichnet, wenn w die Länge 0 oder 1 hat. ${\displaystyle U\cdot V=\{(uv):1\mid u\in U,v\in V\}}$

Leider reichen die First-Sets nicht aus, um die Parsertabelle zu berechnen. Dies liegt daran, dass die rechte Seite w einer Regel letztendlich zu einer leeren Zeichenkette umgeschrieben werden kann. Daher sollte der Parser die Regel A → w auch dann anwenden , wenn ε in Fi ( w ) liegt und er im Eingabestrom ein Symbol findet, das auf A folgen könnte . Aus diesem Grund benötigen wir auch das Follow-Set von A , hier Fo ( A ) geschrieben . Dieses ist definiert als die Menge der Terminalsymbole a, sodass es eine Symbolkette αAaβ gibt , die vom Startsymbol abgeleitet werden kann. Wir verwenden $ als spezielles Terminalsymbol, das das Ende des Eingabestroms anzeigt, und S als Startsymbol.

Die Berechnung der Folgemengen für die Nichtterminale in einer Grammatik kann wie folgt erfolgen:

1. Initialisiere Fo ( S ) mit { $ } und jedes andere Fo ( Ai ) mit der leeren Menge _.
2. Wenn es eine Regel der Form A _j → wA _i w ′ gibt , dann
   • Wenn der Terminal a in Fi ( w ′ ) enthalten ist, dann addiere a zu Fo ( A _i )
   • Wenn ε in Fi ( w ′ ) liegt, dann addiere Fo ( A _j ) zu Fo ( A _i )
   • Wenn w' die Länge 0 hat, dann addiere Fo ( A _j ) zu Fo ( A _i )
3. Wiederholen Sie Schritt 2, bis alle Fo- Mengen gleich bleiben.

Dies liefert die Lösung mit dem kleinsten Fixpunkt für das folgende System:

• Fo ( S ) ⊇ { $ }
• Fo ( A ) ⊇ Fi ( w )· Fo ( B ) für jede Regel der Form ⁠ ⁠${\displaystyle B\to \dots Aw}$

Nun können wir genau definieren, welche Regeln wo in der Syntaxtabelle erscheinen. Wenn T [ A , a ] den Eintrag in der Tabelle für das Nichtterminalsymbol A und das Terminalsymbol a bezeichnet , dann

T [ A , a ] enthält die Regel A → w genau dann, wenn

a ist in Fi ( w ) oder

ε ist in Fi ( w ) und a ist in Fo ( A ).

Äquivalent dazu: T [ A , a ] enthält die Regel A → w für jedes a ∈ Fi ( w )· Fo ( A ).

Enthält die Tabelle in jeder ihrer Zellen höchstens eine Regel, so weiß der Parser stets, welche Regel er anwenden muss und kann daher Zeichenketten ohne Backtracking analysieren. Genau in diesem Fall wird die Grammatik als LL(1)-Grammatik bezeichnet .

Die Konstruktion für LL(1)-Parser kann mit folgenden Modifikationen an LL( k )-Parser für k > 1 angepasst werden:

• Das abgeschnittene Produkt ist definiert als , wobei w : k das anfängliche Länge- k- Präfix von Wörtern der Länge > k bezeichnet , oder w selbst, falls w die Länge k oder weniger hat .${\displaystyle U\cdot V=\{(uv):k\mid u\in U,v\in V\}}$
• Fo ( S ) = { $ ^k }
• Wenden Sie Fi ( αβ ) = Fi ( α ) ⋅ Fi ( β ) auch in Schritt 2 der für LL(1) angegebenen Fi- Konstruktion an.
• Im zweiten Schritt der Fo -Konstruktion wird für A _j → wA _i w ′ einfach Fi ( w ′ )· Fo ( A _j ) zu Fo ( A _i ) addiert.

Dabei wird ein Input mit k Endmarkierungen $ versehen , um den k-ten Lookahead-Kontext vollständig zu berücksichtigen. Dieser Ansatz eliminiert Sonderfälle für ε und ist gleichermaßen im LL(1)-Fall anwendbar.

Bis Mitte der 1990er-Jahre herrschte die weitverbreitete Ansicht vor, dass LL( k )-Parsing (für k > 1) unpraktisch sei ^{[ 12 ] : 263–265,} da die Parsertabelle im schlimmsten Fall exponentiell mit k wachsen würde . Diese Auffassung änderte sich allmählich nach der Veröffentlichung des Purdue Compiler Construction Tool Set um 1992, als gezeigt wurde, dass viele Programmiersprachen effizient mit einem LL( k )-Parser geparst werden können, ohne dass dessen Worst-Case-Verhalten auftritt. Darüber hinaus ist LL-Parsing in bestimmten Fällen sogar mit unbegrenztem Lookahead möglich. Im Gegensatz dazu verwenden traditionelle Parsergeneratoren wie yacc LALR(1) -Parsertabellen, um einen eingeschränkten LR-Parser mit einem festen Lookahead von einem Token zu konstruieren.

Wie in der Einleitung beschrieben, erkennen LL(1)-Parser Sprachen mit LL(1)-Grammatiken, die einen Spezialfall kontextfreier Grammatiken darstellen. LL(1)-Parser können jedoch nicht alle kontextfreien Sprachen erkennen. Die LL(1)-Sprachen bilden eine echte Teilmenge der LR(1)-Sprachen, welche wiederum eine echte Teilmenge aller kontextfreien Sprachen sind. Damit eine kontextfreie Grammatik eine LL(1)-Grammatik ist, dürfen bestimmte Konflikte nicht auftreten.

Sei A ein Nichtterminalsymbol. FIRST( A ) ist definiert als die Menge der Terminalsymbole, die an der ersten Position einer beliebigen von A abgeleiteten Zeichenkette vorkommen können . FOLLOW( A ) ist die Vereinigung über: ^{[ 13 ]}

1. FIRST( B ) wobei B ein beliebiges Nichtterminalsymbol ist, das unmittelbar auf A auf der rechten Seite einer Produktionsregel folgt .
2. FOLLOW( B ) wobei B ein beliebiger Kopf einer Regel der Form B → wA ist .

Es gibt zwei Haupttypen von LL(1)-Konflikten:

Die ersten Mengen zweier verschiedener Grammatikregeln für dasselbe Nichtterminalsymbol überschneiden sich. Ein Beispiel für einen LL(1) FIRST/FIRST-Konflikt:

S -> E | E 'a' E -> 'b' | ε 

FIRST( E ) = { b , ε} und FIRST( E a ) = { b , a }, sodass beim Zeichnen der Tabelle ein Konflikt unter Terminal b der Produktionsregel S auftritt .

Linksrekursion führt zu einem FIRST/FIRST-Konflikt mit allen Alternativen.

E -> E '+' Term | alt1 | alt2 

Die FIRST- und FOLLOW-Mengen einer Grammatikregel überschneiden sich. Befindet sich eine leere Zeichenkette (ε) in der FIRST-Menge, ist unbekannt, welche Alternative ausgewählt werden soll. Ein Beispiel für einen LL(1)-Konflikt:

S -> A 'a' 'b' A -> 'a' | ε 

Die ERSTE Menge von A ist { a , ε}, und die FOLGENDE Menge ist { a }.

Ein gemeinsamer linker Faktor wird "herausgeklammert".

A -> X | XYZ 

wird

A -> XB B -> YZ | ε 

Kann angewendet werden, wenn zwei Alternativen mit dem gleichen Symbol beginnen, wie bei einem FIRST/FIRST-Konflikt.

Ein weiteres (komplexeres) Beispiel, das auf dem obigen FIRST/FIRST-Konfliktbeispiel basiert:

S -> E | E 'a' E -> 'b' | ε 

wird (verschmelzt zu einem einzigen Nicht-Terminal)

S -> 'b' | ε | 'b' 'a' | 'a' 

dann durch Linksfaktorisierung wird

S -> 'b' E | E E -> 'a' | ε 

Durch Ersetzen einer Regel durch eine andere, um indirekte oder FIRST/FOLLOW-Konflikte zu beseitigen. Beachten Sie, dass dies einen FIRST/FIRST-Konflikt verursachen kann.

Siehe ^{[ 14 ]}

Eine allgemeine Methode finden Sie unter „Beseitigen von Linksrekursion“ . Ein einfaches Beispiel für das Beseitigen von Linksrekursion: Die folgende Produktionsregel enthält Linksrekursion auf E.

E -> E '+' T E -> T 

Diese Regel ist nichts anderes als eine Liste von Ts, getrennt durch '+'. In der Form eines regulären Ausdrucks : T ('+' T)*. Die Regel könnte also umgeschrieben werden als:

E -> TZ Z -> '+' TZ Z -> ε 

Nun gibt es keine Linksrekursion mehr und keine Konflikte mehr bezüglich der Regeln.

Allerdings besitzen nicht alle kontextfreien Grammatiken eine äquivalente LL(k)-Grammatik, z. B.:

S -> A | B A -> 'a' A 'b' | ε B -> 'a' B 'b' 'b' | ε 

Es lässt sich zeigen, dass es keine LL(k)-Grammatik gibt, die die von dieser Grammatik erzeugte Sprache akzeptiert.

• Vergleich von Parsergeneratoren
• Syntaxbaum
• Top-Down-Parsing
• Bottom-up-Parsing

• Ein Tutorial zur Implementierung von LL(1)-Parsern in C# (archiviert)
• Parsing-Simulator Dieser Simulator wird verwendet, um Parsing-Tabellen LL(1) zu generieren und die Übungen des Buches zu lösen.
• Sprachtheoretischer Vergleich von LL- und LR-Grammatiken