In der Informatik ist ein LL parser ein verfeinernder parser für eine Teilmenge der Grammatiken ohne Zusammenhänge. Es analysiert den Eingang vom Linken bis Recht grammatisch, und baut eine Abstammung von Leftmost des Satzes (folglich LL, im Vergleich zu LR parser). Die Klasse von Grammatiken, die parsable auf diese Weise sind, ist als die LL Grammatiken bekannt.

Der Rest dieses Artikels beschreibt die tabellenbasierte Art von parser, die Alternative, die ein rekursiver Abstieg parser ist, der gewöhnlich mit der Hand codiert wird (obwohl nicht immer; sieh z.B. ANTLR für einen LL (*) rekursiver Abstieg parser Generator).

Ein LL parser wird einen LL (k) parser genannt, wenn er k Jetons von lookahead verwendet, wenn er einen Satz grammatisch analysiert. Wenn solch ein parser für eine bestimmte Grammatik besteht und er Sätze dieser Grammatik grammatisch analysieren kann, ohne dann denselben Weg zurückzuverfolgen, wird es einen LL (k) Grammatik genannt. Eine Sprache, die einen LL (k) Grammatik hat, ist als ein LL (k) Sprache bekannt. Es gibt LL (k+n) Sprachen, die nicht LL (k) Sprachen sind. Eine Folgeerscheinung davon ist, dass nicht alle Sprachen ohne Zusammenhänge LL (k) Sprachen sind.

LL (1) sind Grammatiken sehr populär, weil der entsprechende LL parsers nur auf den folgenden Jeton schauen muss, um ihre Syntaxanalyse-Entscheidungen zu treffen. Wie man traditionell betrachtet hat, sind Sprachen, die auf Grammatiken mit einem hohen Wert von k gestützt sind, schwierig gewesen grammatisch zu analysieren, obwohl das jetzt gegeben die Verfügbarkeit und der weit verbreitete Gebrauch von parser Generatoren weniger wahr ist, die LL (k) Grammatiken für willkürlichen k unterstützen.

Ein LL parser wird einen LL (*) parser genannt, wenn er auf begrenzte k Jetons von lookahead nicht eingeschränkt wird, aber Syntaxanalyse-Entscheidungen durch das Erkennen treffen kann, ob die folgenden Jetons einer regelmäßigen Sprache (zum Beispiel durch den Gebrauch eines Deterministischen Begrenzten Automaten) gehören.

Allgemeiner Fall

Der parser arbeitet an Schnuren von einer besonderen Grammatik ohne Zusammenhänge.

Der parser besteht aus

• ein Eingangspuffer, die Eingangsschnur (gebaut von der Grammatik) haltend
• ein Stapel, auf dem man die Terminals und Nichtterminals von der Grammatik noch versorgt, um grammatisch analysiert zu werden
• ein Syntaxanalyse-Tisch, der es was (wenn irgendwelcher) Grammatik-Regel erzählt, gegeben die Symbole oben auf seinem Stapel und dem folgenden Eingangsjeton zu gelten

Der parser wendet die im Tisch gefundene Regel durch das Zusammenbringen des höchsten Symbols auf dem Stapel (Reihe) mit dem aktuellen Symbol im Eingangsstrom (Säule) an.

Wenn der parser anfängt, enthält der Stapel bereits zwei Symbole:

[S, $]

wo '$' ein spezielles Terminal ist, um den Boden des Stapels und das Ende des Eingangsstroms anzuzeigen, und 'S' das Anfang-Symbol der Grammatik ist. Der parser wird versuchen, den Inhalt dieses Stapels dazu umzuschreiben, was es auf dem Eingangsstrom sieht. Jedoch behält es nur den Stapel, was noch umgeschrieben werden muss.

Konkretes Beispiel

Sich niederlassen

Um seine Tätigkeit zu erklären, werden wir die folgende kleine Grammatik denken:

1. S  F
2. S  (S + F)
3. F  ein

und analysieren Sie den folgenden Eingang grammatisch:

:(+ a)

Der Syntaxanalyse-Tisch für diese Grammatik sieht wie folgt aus:

:

(Bemerken Sie, dass es auch eine Säule für das spezielle Terminal, vertreten hier als $ gibt, der verwendet wird, um das Ende des Eingangsstroms anzuzeigen.)

Syntaxanalyse des Verfahrens

In jedem Schritt liest der parser das nächst-verfügbare Symbol vom Eingangsstrom und das höchste Symbol vom Stapel. Wenn das Eingangssymbol und das mit dem Stapel oberste Symbol-Match, der parser sie beide verwirft, nur die unvergleichlichen Symbole im Eingangsstrom und auf dem Stapel verlassend.

So, in seinem ersten Schritt, liest der parser das Eingangssymbol (und das mit dem Stapel oberste Symbol 'S'. Die Syntaxanalyse-Tabelleninstruktion kommt aus der durch das Eingangssymbol angeführten Säule (und die Reihe, die durch das mit dem Stapel oberste Symbol 'S' angeführt ist; diese Zelle enthält '2', der den parser beauftragt, Regel (2) anzuwenden. Der parser muss 'S' zu (S + F) auf dem Stapel umschreiben und die Regel Nummer 2 der Produktion schreiben. Der Stapel wird dann:

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

Seit (vom Eingangsstrom hat das höchste Symbol, 'S' vom Stapel nicht verglichen, wurde es nicht entfernt, und bleibt das nächst-verfügbare Eingangssymbol für den folgenden Schritt.

Im zweiten Schritt zieht der parser um (von seinem Eingangsstrom und von seinem Stapel, da sie zusammenpassen. Der Stapel wird jetzt:

[S, +, F,), $]

Jetzt hat der parser auf seinem Eingangsstrom und 'S' als seine Stapel-Spitze. Der Syntaxanalyse-Tisch beauftragt es, Regel (1) von der Grammatik anzuwenden und die Regel Nummer 1 dem Produktionsstrom zu schreiben. Der Stapel wird:

[F, +, F,), $]

Der parser hat jetzt auf seinem Eingangsstrom und 'F' als seine Stapel-Spitze. Der Syntaxanalyse-Tisch beauftragt es, Regel (3) von der Grammatik anzuwenden und die Regel Nummer 3 dem Produktionsstrom zu schreiben. Der Stapel wird:

[a, +, F,), $]

In den folgenden zwei Schritten liest der parser den a und + vom Eingangsstrom und, da sie die folgenden zwei Sachen auf dem Stapel vergleichen, auch entfernt sie vom Stapel. Das läuft hinaus:

[F), $]

In den folgenden drei Schritten wird der parser F auf dem Stapel durch a ersetzen, die Regel Nummer 3 dem Produktionsstrom zu schreiben und den a und zu entfernen), sowohl vom Stapel als auch vom Eingangsstrom. Der parser endet so mit dem $ sowohl auf seinem Stapel als auch auf seinem Eingangsstrom.

In diesem Fall wird der parser berichten, dass er akzeptiert hat, dass der Eingang spannt und die folgende Liste von Regel-Zahlen zum Produktionsstrom schreibt:

: [2, 1, 3, 3]

Das ist tatsächlich eine Liste von Regeln für eine leftmost Abstammung der Eingangsschnur, die ist:

: S  (S + F)  (F + F)  (+ F)  (+)

Durchführung von Parser in C ++

Unten folgt einem C ++ Durchführung eines tabellenbasierten LL parser für die Beispiel-Sprache:

1. einschließen

einschließen einschließen

Enum-Symbole {\

//die Symbole:

//Endsymbole:

TS_L_PARENS, //(

TS_R_PARENS, //)

TS_A, //ein

TS_PLUS, //+

TS_EOS, //$, entspricht in diesem Fall '\0'

TS_INVALID, //ungültiger Jeton

//Nichtendsymbole:

NTS_S, //S

NTS_F

};

/*

Wandelt einen gültigen Jeton zum entsprechenden Endsymbol um

• /

Enum-Symbole lexer (Rotforelle c)

{\

Schalter (c)

{\

Fall' (': Geben Sie TS_L_PARENS zurück;

Fall')': Geben Sie TS_R_PARENS zurück;

umgeben Sie: Geben Sie TS_A zurück;

Fall '+': Geben Sie TS_PLUS zurück;

Fall '\0': Geben Sie TS_EOS zurück;//Ende des Stapels: das $-Endsymbol

Verzug: Geben Sie TS_INVALID zurück;

}\

}\

int Hauptsache (interne Nummer argc, Rotforelle ** argv)

{\

das Verwenden namespace std;

wenn (argc

Karte

Stapel

Rotforelle *p; //Eingangspuffer

//initialisieren Sie den Symbol-Stapel

ss.push (TS_EOS); //Terminal, $\

ss.push (NTS_S); //Nichtterminal, S

//initialisieren Sie den Symbol-Strom-Cursor

p = &argv [1] [0];

//Einstellung der Syntaxanalyse-Tisch

Tisch [NTS_S] [TS_L_PARENS] = 2; Tisch [NTS_S] [TS_A] = 1;

Tisch [NTS_F] [TS_A] = 3;

während (ss.size > 0)

{\

wenn (lexer (*p) == ss.top )

{\

cout

Bemerkungen

Wie vom Beispiel gesehen werden kann, führt der parser drei Typen von Schritten je nachdem durch, ob die Spitze des Stapels ein Nichtterminal, ein Terminal oder der spezielle Symbol-$ ist:

• Wenn die Spitze ein Nichtterminal dann ist, blickt sie im Syntaxanalyse-Tisch auf der Grundlage von diesem Nichtterminal und dem Symbol auf dem Eingangsstrom auf, welche Regel der Grammatik sie verwenden sollte, um es durch auf dem Stapel zu ersetzen. Die Zahl der Regel wird dem Produktionsstrom geschrieben. Wenn der Syntaxanalyse-Tisch anzeigt, dass es keine solche Regel dann gibt, gibt er einen Fehler und Halt aus.
• Wenn die Spitze ein Terminal dann ist, vergleicht sie es mit dem Symbol auf dem Eingangsstrom, und wenn sie gleich sind, werden sie beide entfernt. Wenn sie nicht sind, sind gleich der parser gibt einen Fehler und Halt aus.
• Wenn die Spitze $ ist und auf dem Eingangsstrom es auch einen $ dann gibt, berichtet der parser, dass es den Eingang erfolgreich grammatisch analysiert hat, sonst gibt es einen Fehler aus. In beiden Fällen wird der parser anhalten.

Diese Schritte werden wiederholt bis zum Parser-Halt, und dann wird es entweder den Eingang völlig grammatisch analysiert haben und eine leftmost Abstammung dem Produktionsstrom geschrieben haben, oder es wird einen Fehler ausgegeben haben.

Das Konstruieren eines LL (1) Syntaxanalyse-Tisch

Um den Syntaxanalyse-Tisch zu füllen, müssen wir das einsetzen, welche Grammatik-Regel der parser wählen sollte, wenn es ein Nichtterminal A auf der Spitze seines Stapels und eines Symbols auf seinem Eingangsstrom sieht. Es ist leicht zu sehen, dass solch eine Regel der Form Ein  w sein sollte, und dass die Sprache entsprechend w mindestens eine Schnur haben sollte, die mit a anfängt. Für diesen Zweck definieren wir den Zuerst gesetzten von w, geschrieben hier als Fi (w) als der Satz von Terminals, die am Anfang von einer Schnur in w plus ε gefunden werden können, wenn die leere Schnur auch w gehört. In Anbetracht einer Grammatik mit den Regeln Ein  w..., Ein  w, können wir Fi (w) und Fi (A) für jede Regel wie folgt schätzen:

1. initialisieren Sie jeden Fi (w) und Fi (A) mit dem leeren Satz
2. fügen Sie Fi (w) zu Fi (A) für jede Regel Ein  w hinzu, wo Fi wie folgt definiert wird:
3. * Fi (ein w') = für jedes Terminal ein
4. * Fi (Ein w') = Fi (A) für jedes Nichtterminal A mit ε nicht in Fi (Ein)
5. * Fi (Ein w') = Fi (A) \{ε}  Fi (w') für jedes Nichtterminal A mit ε in Fi (Ein)
6. * Fi (ε) = {ε }\
7. fügen Sie Fi (w) zu Fi (A) für jede Regel Ein  w hinzu
8. tun Sie Schritte 2 und 3, bis alle Sätze von Fi dasselbe bleiben.

Leider sind die Ersten Sätze nicht genügend, um den Syntaxanalyse-Tisch zu schätzen. Das ist, weil eine Rechte w einer Regel zur leeren Schnur schließlich umgeschrieben werden könnte. So sollte der parser auch die Regel Ein  w verwenden, wenn ε in Fi (w) ist und es auf dem Eingangsstrom ein Symbol sieht, das A folgen konnte. Deshalb brauchen wir auch den Folgen-Satz von A, schriftlich als Fo (A) hier, der als der Satz von solchen Terminals a definiert wird, dass es eine Reihe von Symbolen αAaβ gibt, der aus dem Anfang-Symbol abgeleitet werden kann. Die Computerwissenschaft der Folgen-Sätze für die Nichtterminals in einer Grammatik kann wie folgt getan werden:

1. initialisieren Sie jeden Fo (A) mit dem leeren Satz
2. wenn es eine Regel der Form Ein  wAw', dann gibt
3. *, wenn das Terminal a in Fi (w') dann ist, fügen Sie zu Fo (Einen) hinzu
4. *, wenn ε in Fi (w') dann ist, fügen Sie Fo (A) zu Fo (Ein) hinzu
5. wiederholen Sie Schritt 2, bis alle Sätze von Fo dasselbe bleiben.

Jetzt können wir genau definieren, welche Regeln wo im Syntaxanalyse-Tisch enthalten werden. Wenn T [A,] den Zugang im Tisch für das Nichtterminal A und Terminal a, dann anzeigt

: T [A,] enthält die Regel Ein  w wenn und nur wenn

:: in Fi (w) oder zu sein

:: ε ist in Fi (w) und in Fo (A) zu sein.

Wenn der Tisch höchstens eine Regel in jeder seiner Zellen enthält, dann wird der parser immer wissen, welche Regel es verwenden muss und deshalb Schnuren ohne das Zurückverfolgen grammatisch analysieren kann. Es ist in genau diesem Fall, dass die Grammatik einen LL (1) Grammatik genannt wird.

Das Konstruieren eines LL (k) Syntaxanalyse des Tisches

Bis zur Mitte der 1990er Jahre wurde es weit geglaubt, dass LL (k) grammatisch analysierend (für k> war 1) seit dem Syntaxanalyse-Tisch unpraktisch, Exponentialgröße in k im Grenzfall haben würde. Diese Wahrnehmung hat sich allmählich nach der Ausgabe des PCCTS 1992 geändert, als es demonstriert wurde, dass viele Programmiersprachen effizient durch einen LL (k) parser grammatisch analysiert werden können, ohne das Grenzfall-Verhalten des parser auszulösen. Außerdem in bestimmten Fällen ist LL Syntaxanalyse sogar mit unbegrenztem lookahead ausführbar. Im Vergleich verwenden traditionelle parser Generatoren wie yacc LALR (1) Syntaxanalyse-Tische, um einen eingeschränkten LR parser mit einem festen einem Jeton lookahead zu bauen.

Konflikte

Wie beschrieben, in der Einführung LL (1) erkennen parsers Sprachen an, die LL (1) Grammatiken haben, die ein spezieller Fall von Grammatiken ohne Zusammenhänge (CFG'S) sind; LL (1) parsers kann alle Sprachen ohne Zusammenhänge nicht anerkennen. Die LL (1) Sprachen sind genau diejenigen, die durch deterministische pushdown auf einen einzelnen Staat eingeschränkte Automaten anerkannt sind. In der Größenordnung von einem CFG, um ein LL (1) Grammatik zu sein, müssen bestimmte Konflikte nicht entstehen, den wir in dieser Abteilung beschreiben.

Fachsprache

Lassen Sie A ein Nichtterminal sein. ERST (A) ist (definiert, um zu sein), der Satz von Terminals, die in der ersten Position jeder Schnur erscheinen können, ist auf A zurückzuführen gewesen. FOLGEN SIE (A) ist die Vereinigung über den ERSTEN (B), wo B jedes Nichtterminal ist, das sofort in der rechten Seite einer Produktionsregel folgt.

LL (1) Konflikte

Es gibt 3 Typen von LL (1) Konflikte:

• DER ERSTE/ERSTE Konflikt

: Die ERSTEN Sätze von zwei verschiedenen Nichtterminals schneiden sich.

• DER ERSTE/FOLGEN Konflikt

: Die ERSTEN und FOLGEN Satz eines Grammatik-Regel-Übergreifens. Mit einem Epsilon im ERSTEN Satz ist es der Alternative unbekannt auszuwählen.

: Ein Beispiel eines LL (1) Konflikt:

S-> 'Ein' 'b'

A-> | Epsilon

: Der ERSTE Satz dessen ist jetzt {'ein' Epsilon} und der FOLGEN Satz.

• nach-links-recursion

: Verlassener recursion wird einen ERSTEN/ERSTEN Konflikt mit allen Alternativen verursachen.

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

Lösungen von LL (1) Konflikte

• Nach links Factoring

Ein allgemeiner nach links Faktor wird "ausgeklammert".

A-> X | X Y Z

wird

A-> X B

B-> Y Z | ε\

Kann angewandt werden, wenn zwei Alternativen mit demselben Symbol wie ein ERSTER/ERSTER Konflikt anfangen.

• Ersatz

Das Ersetzen einer Regel in eine andere Regel, die indirekten oder ERSTEN/FOLGEN Konflikte zu entfernen.

Bemerken Sie, dass das einen ERSTEN/ERSTEN Konflikt verursachen kann.

• Verlassene recursion Eliminierung

Ein einfaches Beispiel für die linke recursion Eliminierung:

Die folgende Produktionsregel hat recursion auf E übrig

E-> E '+' T

-> T

Diese Regel ist nichts als Liste von T hat sich durch '+ getrennt '. In einem regelmäßigen Ausdruck bilden T (' +' T) *.

So konnte die Regel als umgeschrieben werden

E-> T Z

Z-> '+' T Z

-> ε\

Jetzt dort ist nicht recursion und keine Konflikte auf jeder der Regeln verlassen.

Jedoch haben nicht alle CFGs einen gleichwertigen LL (k) - Grammatik z.B:

S-> | B

A-> Ein 'b' | ε\

B-> 'ein' B 'b' 'b' | ε\

Es kann gezeigt werden, dass dort kein LL (k) - Grammatik besteht, die die durch diese Grammatik erzeugte Sprache akzeptiert.

Siehe auch

• Vergleich von parser Generatoren
• Syntaxanalyse-Baum
• Verfeinernde Syntaxanalyse
• Von unten nach oben Syntaxanalyse

Außenverbindungen

• Ein Tutorenkurs beim Einführen von LL (1) parsers in

C# Wenn man

• Simulator grammatisch analysiert, wird Dieser Simulator verwendet, um Syntaxanalyse-Tische LL1 zu erzeugen und die Übungen des Buches aufzulösen.
• LL (1) DSL-HAKEN parser (Werkzeug-Fachwerk)

Zeichen