In der Informatik ist ein LR parser ein parser, der Eingang vom Linken bis Recht liest (wie es, wenn visuell gezeigt, erscheinen würde) und eine Niedrigstwertige Abstammung erzeugt. Der Begriff LR (k) parser wird auch gebraucht; wo sich der k auf die Zahl von unverbrauchten bezieht, "schauen vorn" Eingangssymbole, die im Treffen von Syntaxanalyse-Entscheidungen verwendet werden. Gewöhnlich ist k 1, und der Begriff LR ist parser häufig beabsichtigt, um sich auf diesen Fall zu beziehen.

LR Syntaxanalyse kann eine größere Reihe von Sprachen behandeln als LL-Syntaxanalyse, und ist auch im Fehlerbericht besser, d. h. es entdeckt syntaktische Fehler, wenn sich der Eingang der Grammatik so bald wie möglich nicht anpasst. Das ist im Gegensatz zu einem LL (k) (oder noch schlechter, ein LL (*) parser), der Fehlerentdeckung zu einem verschiedenen Zweig der Grammatik wegen des Zurückverfolgens aufschieben kann, häufig Fehler härter machend, über Trennungen mit langen allgemeinen Präfixen zu lokalisieren.

LR parsers sind schwierig, mit der Hand zu erzeugen, und sie werden gewöhnlich durch einen parser Generator oder einen Bearbeiter-Bearbeiter gebaut. Je nachdem, wie der Syntaxanalyse-Tisch erzeugt wird, können diese parsers einfachen LR parsers (SLR) genannt werden, schauen Sie LR parsers (LALR) oder kanonischer LR parsers vorn. LALR parsers haben mehr Sprachanerkennungsmacht als SLR parsers. Kanonische LR parsers haben mehr Anerkennungsmacht als LALR parsers.

Theorie

LR Syntaxanalyse wurde von Donald Knuth 1965 in einer Zeitung, "Auf der Übersetzung von Sprachen vom Linken bis Recht erfunden".

In dieser Zeitung beweist Donald Knuth das

"LR (k) Grammatiken kann mit einer zur Länge der Schnur im Wesentlichen proportionalen Ausführungszeit", effizient grammatisch analysiert werden

und das "Eine Sprache kann durch einen LR (k) Grammatik erzeugt werden, wenn, und nur wenn es deterministisch ist, wenn, und nur wenn es durch einen LR (1) Grammatik erzeugt werden kann".

Eine deterministische Sprache ohne Zusammenhänge ist eine Sprache, für die ein LR (k) Grammatik besteht. Jeder LR (k) Grammatik für k> 1 kann in einen LR (1) Grammatik für dieselbe Sprache mechanisch umgestaltet werden, während ein LR (0) Grammatik für dieselbe Sprache nicht bestehen kann; die LR (0) Sprachen sind eine richtige Teilmenge der deterministischen.

LR Syntaxanalyse kann als willkürliche Sprachsyntaxanalyse ohne Zusammenhänge ohne eine Leistungsstrafe, sogar für LR (k) Grammatiken verallgemeinert werden. Bemerken Sie, dass die Syntaxanalyse von non-LR (k) Grammatiken ohne Zusammenhänge eine Größenordnung langsamer (kubisch statt des quadratischen in Bezug auf die Eingangslänge) ist.

Die Syntax von vielen Programmiersprachen wird durch eine Grammatik definiert, die LR (k) ist (wo k eine kleine Konstante, gewöhnlich 1 ist), oder in der Nähe davon zu sein, so, und aus diesem Grund LR werden parsers häufig durch Bearbeiter verwendet, um Syntax-Analyse des Quellcodes durchzuführen.

Ein LR parser kann von einer Grammatik ohne Zusammenhänge durch ein Programm genannt einen parser Generator oder von einem Programmierer geschriebene Hand geschaffen werden. Eine Grammatik ohne Zusammenhänge wird als LR (k) klassifiziert, wenn dort ein LR (k) parser dafür, wie bestimmt, durch den parser Generator besteht.

Wie man

sagt, führt ein LR parser von unten nach oben Syntaxanalyse durch, weil es versucht, die Spitzenniveau-Grammatik-Produktion durch das Aufbauen von den Blättern (a.k.a. Terminals) abzuleiten.

Ein LR parser basiert auf einem Algorithmus, der durch einen Syntaxanalyse-Tisch, eine Datenstruktur gesteuert wird, die die Syntax der Computersprache enthält, die grammatisch wird analysiert. So bezieht sich der Begriff LR parser wirklich auf eine Klasse von parser, der fast jede Programmiersprache bearbeiten kann, so lange der parser Tisch für eine Programmiersprache geliefert wird. Der parser Tisch wird durch ein Programm genannt einen parser Generator geschaffen.

Architektur von LR parsers

Begrifflich ist ein LR Parser ein rekursives Programm, das richtig durch die direkte Berechnung bewiesen werden kann, und effizienter (rechtzeitig) als ein rekursiver Aufstieg parser, eine Reihe gegenseitig rekursiver Funktionen für jede Grammatik, viel wie ein rekursiver Abstieg parser durchgeführt werden kann. Herkömmlich, jedoch, LR werden parsers präsentiert und als tabellenbasierte Stapel-Maschinen durchgeführt, in denen der Anruf-Stapel des zu Grunde liegenden rekursiven Programms ausführlich manipuliert wird.

Ein tabellengesteuerter von unten nach oben parser kann als in der Abbildung 1 schematisch präsentiert werden. Der folgende beschreibt eine niedrigstwertige Abstammung durch diesen parser.

Allgemeiner Fall

Der parser ist eine Zustandmaschine. Es besteht aus:

• ein Eingangspuffer
• ein Stapel, auf dem eine Liste von Staaten versorgt wird, die es in gewesen ist
• ein goto Tisch, der vorschreibt, zu dem neuem Staat er bewegen sollte
• ein Handlungstisch, der eine Grammatik-Regel gibt, gegeben der aktuelle Staat und das aktuelle Terminal im Eingangsstrom zu gelten
• eine Reihe von CFL herrscht

über

Seit dem LR liest parser Eingang vom linken bis Recht, aber muss eine niedrigstwertige Abstammung erzeugen, es verwendet die Verminderungen statt Abstammungen, um Eingang zu bearbeiten. D. h. der Algorithmus arbeitet durch das Schaffen "leftmost die Verminderung" des Eingangs. Das Endergebnis, wenn umgekehrt, wird eine niedrigstwertige Abstammung sein.

Der LR Syntaxanalyse des Algorithmus arbeitet wie folgt:

1. Der Stapel wird mit [0] initialisiert. Der aktuelle Staat wird immer der Staat sein, der an der Oberseite vom Stapel ist.
2. In Anbetracht des aktuellen Staates und des aktuellen Terminals auf dem Eingangsstrom wird eine Handlung im Handlungstisch nachgeschlagen. Es gibt vier Fälle:
3. * eine Verschiebung sn:
4. ** das aktuelle Terminal wird vom Eingangsstrom entfernt
5. ** der Staat n wird auf den Stapel gestoßen und wird der aktuelle Staat
6. * ein Reduzieren rm:
7. ** die Zahl M wird dem Produktionsstrom geschrieben
8. ** für jedes Symbol in der Rechte der Regel wird M ein Staat vom Stapel entfernt (d. h. wenn die Rechte der Regel M besteht aus 3 Symbolen, 3 Spitzenstaaten, vom Stapel entfernt wird)
9. ** in Anbetracht des Staates, der dann oben auf dem Stapel und der linken Seite der Regel ist, wird M ein neuer Staat im goto Tisch nachgeschlagen und der neue aktuelle Staat durch das Stoßen davon auf den Stapel gemacht
10. * ein Akzeptieren: Die Schnur wird akzeptiert
11. * keine Handlung: Ein Syntax-Fehler wird ausgegeben
12. Schritt 2 wird wiederholt bis wird entweder die Schnur akzeptiert oder ein Syntax-Fehler wird berichtet.

Konkretes Beispiel

Um seine Tätigkeit zu erklären, werden wir die folgende kleine Grammatik verwenden, deren Anfang-Symbol E ist:

: (1) E  E * B

: (2) E  E + B

: (3) E  B

: (4) B  0

: (5) B  1

und analysieren Sie den folgenden Eingang grammatisch:

: 1 + 1

Handlung und goto Tische

Die zwei LR (0) Syntaxanalyse-Tische für diese Grammatik sehen wie folgt aus:

Der Handlungstisch wird durch einen Staat des parser und eines Terminals mit einem Inhaltsverzeichnis versehen (einschließlich eines speziellen End-$, der das Ende des Eingangsstroms anzeigt) und drei Typen von Handlungen enthält:

• Verschiebung, die als 'sn&#39 geschrieben wird; und zeigt an, dass der folgende Staat n ist
• nehmen Sie ab, der als 'rm&#39 geschrieben wird; und zeigt an, dass die Verminderung mit der Grammatik-Regel M durchgeführt werden sollte
• akzeptieren Sie, der als 'acc' geschrieben wird und anzeigt, dass der parser die Schnur im Eingangsstrom akzeptiert.

Der goto Tisch wird durch einen Staat des parser und eines Nichtterminals mit einem Inhaltsverzeichnis versehen und zeigt einfach an, was der folgende Staat des parser sein wird, wenn es ein bestimmtes Nichtterminal anerkannt hat. Dieser Tisch ist wichtig, um den folgenden Staat nach jeder Verminderung herauszufinden. Nach der Verminderung wird der folgende Staat durch das Aufblicken des goto Tabellenzugangs für die Spitze des Stapels (d. h. aktueller Staat) und der LHS der reduzierten Regel (d. h. Nichtterminal) gefunden.

Syntaxanalyse des Verfahrens

Der Tisch illustriert unten jeden Schritt im Prozess. Hier bezieht sich der Staat auf das Element an der Oberseite vom Stapel (das niedrigstwertige Element), und die folgende Handlung wird durch das Verweisen auf den Handlungstisch oben bestimmt. Bemerken Sie auch, dass ein $ an der Eingangsschnur angehangen wird, um das Ende des Stroms anzuzeigen.

Walkthrough

Der parser bricht mit dem Stapel auf, der gerade den anfänglichen Staat ('0') enthält:

: [0]

Das erste Symbol von der Eingangsschnur, die der parser sieht, ist '1'. Um herauszufinden, was die folgende Handlung ist (Verschiebung, nehmen Sie ab, akzeptieren Sie oder Fehler), der Handlungstisch wird mit dem aktuellen Staat mit einem Inhaltsverzeichnis versehen (erinnern Sie sich, dass der "aktuelle Staat" gerade ist, was auch immer auf der Spitze des Stapels ist), der in diesem Fall 0, und das aktuelle Eingangssymbol ist, das '1' ist. Der Handlungstisch gibt an, dass eine Verschiebung, um 2 festzusetzen, und so 2 festzusetzen, auf den Stapel gestoßen wird (wieder, erinnern Sie sich, dass die ganze Zustandinformation im Stapel ist, so "ist die Verschiebung, um 2 festzusetzen", dasselbe Ding wie das Stoßen 2 auf den Stapel). Der resultierende Stapel ist

: [0 '1' 2]

wo die Spitze des Stapels 2 ist. Wegen der Erklärung zeigen wir auch das Symbol (z.B, '1', B), der den Übergang zum folgenden Staat verursacht hat, obwohl genau genommen es nicht ein Teil des Stapels ist.

In staatlichen 2 sagt der Handlungstisch, dass unabhängig davon, welches Terminal wir auf dem Eingangsstrom sehen, wir die Verminderung mit der Grammatik-Regel 5 tun sollten. Wenn der Tisch richtig ist, bedeutet das, dass der parser gerade die Rechte der Regel 5 anerkannt hat, die tatsächlich der Fall ist.

In diesem Fall schreiben wir 5 dem Produktionsstrom, lassen einen Staat vom Stapel knallen (da die Rechte der Regel ein Symbol hat), und gehen Sie der Stapel der Staat von der Zelle im goto Tisch für staatlichen 0 und B voran, d. h., setzen Sie 4 fest. Der resultierende Stapel ist:

: [0 B 4]

Jedoch in staatlichen 4 sagt der Handlungstisch, dass wir jetzt die Verminderung mit der Regel 3 tun sollten. So schreiben wir 3 dem Produktionsstrom, lassen einen Staat vom Stapel knallen, und finden den neuen Staat im goto Tisch für staatlichen 0 und E, der Staat 3 ist. Der resultierende Stapel:

: [0 E 3]

Das folgende Terminal, das der parser sieht, ist '+', und gemäß dem Handlungstisch sollte es dann gehen, um 6 festzusetzen:

: [0 E 3 '+' 6]

Bemerken Sie, dass der resultierende Stapel als die Geschichte eines Zustandsautomaten interpretiert werden kann, der gerade ein Nichtterminal E gelesen hat, das von einem Terminal '+' gefolgt ist. Der Übergang-Tisch dieses Automaten wird durch die Verschiebungshandlungen im Handlungstisch und die goto Handlungen im goto Tisch definiert.

Das folgende Terminal ist jetzt '1', und das bedeutet, dass wir eine Verschiebung durchführen und gehen, um 2 festzusetzen:

: [0 E 3 '+' 6 '1' 2]

Ebenso das vorherige '1' wird dieser auf B das Geben des folgenden Stapels reduziert:

: [0 E 3 '+' 6 B 8]

Bemerken Sie wieder, dass der Stapel einer Liste von Staaten eines begrenzten Automaten entspricht, der ein Nichtterminal E gelesen hat, das von '+' und dann ein Nichtterminal B gefolgt ist. In staatlichen 8 führen wir immer ein Reduzieren mit der Regel 2 durch. Bemerken Sie, dass die 3 ersten Staaten auf dem Stapel den 3 Symbolen in der Rechte der Regel 2 entsprechen.

: [0 E 3]

Schließlich lesen wir einen '$' vom Eingangsstrom, was bedeutet, dass gemäß dem Handlungstisch (ist der aktuelle Staat 3), der parser die Eingangsschnur akzeptiert.

Die Regel-Zahlen, die dann dem Produktionsstrom geschrieben worden sein werden, werden [5, 3, 5, 2] sein, der tatsächlich eine niedrigstwertige Abstammung der Schnur "1 + 1" rückwärts ist.

Einleitungsdurchführung

Der folgende Einleitungscode führt das obengenannte Beispiel durch:

Handlung (0,0, s (1)).

Handlung (0,1, s (2)).

Handlung (1, _, r (4)).

Handlung (2, _, r (5)).

Handlung (3,' * ', s (5)).

Handlung (3,' + ', s (6)).

Handlung (3,' $ 'akzeptieren).

Handlung (4, _, r (3)).

Handlung (5,0, s (1)).

Handlung (5,1, s (2)).

Handlung (6,0, s (1)).

Handlung (6,1, s (2)).

Handlung (7, _, r (1)).

Handlung (8, _, r (2)).

goto (0, e, 3).

goto (0, b, 4).

goto (5, b, 7).

goto (6, b, 8).

rhs (1,3).

rhs (2,3).

rhs (3,1).

rhs (4,1).

rhs (5,1).

lhs (1, e).

lhs (2, e).

lhs (3, e).

lhs (4, b).

lhs (5, b).

Syntaxanalyse (Stapel ([H1 | _]), Eingang ([H2 | _])):-Handlung (akzeptieren H1, H2,).

Syntaxanalyse (Stapel ([H1 | _]), Eingang ([])):-Handlung (H1,' $ 'akzeptieren).

Syntaxanalyse (Stapel ([H1|T1]), Eingang ([H2|T2])):-Handlung (H1, H2, s (N)), Syntaxanalyse (Stapel ([N, H1|T1]), Eingang (T2)).

Syntaxanalyse (Stapel ([H1|T1]), Eingang ([H2|T2])):-

Handlung (H1, H2, r (N)),

schreiben Sie (N),

schreiben Sie (''),

rhs (N, M),

rep_pop ([H1|T1], [H3|T3], M),

lhs (N, Colorado),

goto (H3, Colorado, Neu),

Syntaxanalyse (Stapel ([Neu, H3|T3]), Eingang ([H2|T2])).

Syntaxanalyse (Stapel ([H1|T1]), Eingang ([])):-

Handlung (H1,' $ ', r (N)),

schreiben Sie (N), schreiben Sie (''), rhs (N, M), rep_pop ([H1|T1], [H3|T3], M), lhs (N, Colorado), goto (H3, Colorado, Neu),

Syntaxanalyse (Stapel ([Neu, H3|T3]), Eingang ([])).

rep_pop ([_ |T], T, 1).

rep_pop ([_ | [_ |T]], T, 2).

rep_pop ([_ | [_ | [_ |T]]], T, 3).

</Quelle>

Erklärung des Gebrauches

Die Funktion nimmt in zwei Argumenten: Das erste Argument sollte functor mit einer Liste als sein einziges Argument sein, und das zweite Argument sollte functor mit einer Liste als sein einziges Argument sein. Beispiele:

? - Syntaxanalyse (Stapel ([0]), Eingang ([1,' + ', 1])).

5 3 5 2

wahr.

? - Syntaxanalyse (Stapel ([0]), Eingang ([0,' * ', 1,' + ', 0])).

4 3 5 1 4 2

wahr.

? - Syntaxanalyse (Stapel ([0]), Eingang ([0,' + ',' + ', 0])).

4 3

falsch.

</Quelle>

Das Symbol '$' braucht am Ende keiner Eingangsliste eingeschlossen zu werden: Das Programm erkennt eine leere Eingangsliste als entsprechend der '$'-Säule im Handlungstisch an.

Der Code kann leicht modifiziert werden, um anderen LR parsers (LR (0) oder LR (1)) durchzuführen: Ändern Sie sich gerade und Tatsachen, um die Handlung und goto Tische des gewünschten LR parser zu widerspiegeln. Ändern Sie sich und Tatsachen, um die CFG-Regeln zu widerspiegeln. Ihre ersten Argumente sind die Seriennummern der Regeln; das zweite Argument dessen ist die Länge des Griffs der CFG Regel; das zweite Argument dessen entspricht dem Kopf der CFG-Regel. Noch einige Tatsachen könnten am Boden (je nachdem die Länge der Griffe der CFG-Regeln) erforderlich sein.

Referenzen: Das angeführte Beispiel ist LR (0) einfach, weil, wann auch immer eine reduzieren Handlung innerhalb einer gegebenen Reihe des Handlungstisches erscheint, alle anderen Zellen auf dieser Reihe damit gefüllt werden, reduziert dasselbe Handlung. Wenn dieses Eigentum verletzt wurde (wegen, verschieden zu haben, reduzieren Handlungen auf einer gegebenen Reihe), dann würde der Handlungstisch für einen LR (1) parser sein.

Das Konstruieren von LR (0) Syntaxanalyse-Tische

Sachen

Der Aufbau dieser Syntaxanalyse-Tische basiert auf dem Begriff von LR (0) Sachen (einfach genannte Sachen hier), die Grammatik-Regeln mit einem speziellen Punkt hinzugefügt irgendwo in der Rechte sind. Zum Beispiel hat die Regel E  E + B die folgenden vier entsprechenden Sachen:

: E  · E + B

: E  E · + B

: E  E + · B

: E  E + B

·

Regeln der Form Ein  ε haben nur einen einzelnen Artikel Ein  ·. Der Artikel E  E · + zeigt B zum Beispiel an, dass der parser eine Schnur anerkannt hat, die mit E auf dem Eingangsstrom entsprechend ist, und jetzt annimmt, '+' gefolgt von einer anderen mit B entsprechenden Schnur zu lesen.

Artikel-Sätze

Es ist gewöhnlich nicht möglich, den Staat des parser mit einem einzelnen Artikel zu charakterisieren, weil es im Voraus nicht wissen kann, welche Regel es dabei ist, für die Verminderung zu verwenden. Zum Beispiel, wenn es auch eine Regel E  E * B dann die Sachen E  E gibt · + B und E  E · * wird B beide gelten, nachdem eine mit E entsprechende Schnur gelesen worden ist. Deshalb werden wir den Staat des parser durch eine Reihe von Sachen, in diesem Fall der Satz {E  E charakterisieren · + B, E  E · * B\.

Erweiterung des Artikel-Satzes durch die Vergrößerung von Nichtterminals

Ein Artikel mit einem Punkt vor einem Nichtterminal, wie E  E + · B, zeigt an, dass der parser annimmt, das Nichtterminal B als nächstes grammatisch zu analysieren. Den Artikel-Satz zu sichern, enthält alle möglichen Regeln, die der parser in der Mitte der Syntaxanalyse sein kann, muss es alle Sachen einschließen, die beschreiben, wie B selbst grammatisch analysiert wird. Das bedeutet, dass, wenn es Regeln wie B  1 und B  0 dann gibt, der Artikel-Satz auch die Sachen B  einschließen muss · 1 und B  · 0. Im Allgemeinen kann das wie folgt formuliert werden:

: Wenn es einen Artikel der Form Ein  v gibt · Bw in einem Artikel gehen unter, und in der Grammatik gibt es eine Regel der Form B  w' dann der Artikel B  · w' sollte auch im Artikel-Satz sein.

Verschluss von Artikel-Sätzen

So kann jeder Satz von Sachen durch das rekursive Hinzufügen aller passenden Sachen erweitert werden, bis alle durch Punkte vorangegangenen Nichtterminals verantwortlich gewesen werden. Die minimale Erweiterung wird den Verschluss eines Artikel-Satzes genannt und als clos (I) geschrieben, wo ich ein Artikel-Satz bin. Es sind diese geschlossenen Artikel-Sätze, die wir als die Staaten des parser nehmen werden, obwohl nur diejenigen, die vom beginnen Staat wirklich erreichbar sind, in die Tische eingeschlossen werden.

Vermehrte Grammatik

Bevor wir anfangen zu beschließen, dass die Übergänge zwischen den verschiedenen Staaten, die Grammatik immer mit einer Extraregel vermehrt wird

: (0) S  E

wo S ein neues Anfang-Symbol und E das alte Anfang-Symbol ist. Der parser wird diese Regel für die Verminderung genau verwenden, als es die Eingangsschnur akzeptiert hat.

Für unser Beispiel werden wir dieselbe Grammatik wie zuvor nehmen und es vermehren:

: (0) S  E

: (1) E  E * B

: (2) E  E + B

: (3) E  B

: (4) B  0

: (5) B  1

Es ist für diese vermehrte Grammatik, dass wir die Artikel-Sätze und die Übergänge zwischen ihnen bestimmen werden.

Tabellenaufbau

Die Entdeckung des erreichbaren Artikels geht unter und die Übergänge zwischen ihnen

Der erste Schritt, die Tische zu bauen, besteht daraus, die Übergänge zwischen den geschlossenen Artikel-Sätzen zu bestimmen. Diese Übergänge werden bestimmt, als ob wir einen begrenzten Automaten denken, der Terminals sowie Nichtterminals lesen kann. Der beginnen Staat dieses Automaten ist immer der Verschluss des ersten Artikels der zusätzlichen Regel: S  · E:

: Artikel hat 0 gesetzt

: S  · E

: + E  · E * B

: + E  · E + B

: + E  · B

: + B  · 0

: + B  · 1

Das fette "+" vor einem Artikel zeigt die Sachen an, die für den Verschluss hinzugefügt wurden (um mit dem mathematischen '+' Maschinenbediener nicht verwirrt zu sein, der ein Terminal ist). Die ursprünglichen Sachen ohne "+" werden den Kern des Artikel-Satzes genannt.

Das Starten am beginnen Staat (S0) wir werden jetzt alle Staaten bestimmen, die von diesem Staat erreicht werden können. Die möglichen Übergänge für einen Artikel-Satz können durch das Schauen auf die Symbole gefunden werden (Terminals und Nichtterminals) wir finden direkt nach den Punkten; im Fall vom Artikel-Satz sind 0 jene Symbole die Terminals '0' und '1' und die Nichtterminals E und B. Um den Artikel-Satz zu finden, zu dem jedes Symbol x führt, folgen wir dem folgenden Verfahren für jedes der Symbole:

1. Nehmen Sie die Teilmenge, S von allen Sachen im aktuellen Artikel-Satz, wo es einen Punkt vor dem Symbol von Interesse, x gibt.
2. Für jeden Artikel in S, bewegen Sie den Punkt rechts von x.
3. Schließen Sie den resultierenden Satz von Sachen.

Für das Terminal '0' (d. h. wo x = '0') läuft das hinaus:

: Artikel hat 1 gesetzt

: B  0

·

und für das Terminal '1' (d. h. wo x = '1') läuft das hinaus:

: Artikel hat 2 gesetzt

: B  1

·

und für das Nichtterminal E (d. h. wo x = E) läuft das hinaus:

: Artikel hat 3 gesetzt

: S  E

·

: E  E · * B

: E  E · + B

und für das Nichtterminal B (d. h. wo x = B) läuft das hinaus:

: Artikel hat 4 gesetzt

: E  B

·

Bemerken Sie, dass der Verschluss neue Sachen in allen Fällen - in den neuen Sätzen oben zum Beispiel nicht hinzufügt, gibt es keine Nichtterminals im Anschluss an den Punkt. Wir setzen diesen Prozess fort, bis keine neue Artikel-Sätze mehr gefunden werden. Weil der Artikel 1, 2 untergeht, und 4 es keine Übergänge geben wird, da der Punkt nicht vor jedem Symbol ist. Weil Artikel 3 untergegangen ist, sehen wir, dass der Punkt vor den Terminals '*' und '+' ist. Für '*' geht der Übergang zu:

: Artikel hat 5 gesetzt

: E  E * · B

: + B  · 0: + B  · 1

und für '+' geht der Übergang zu:

: Artikel hat 6 gesetzt

: E  E + · B: + B  · 0: + B  · 1

Weil Artikel 5 untergegangen ist, müssen wir die Terminals '0' und '1' und das Nichtterminal B denken. Für die Terminals sehen wir, dass die resultierenden geschlossenen Artikel-Sätze den bereits gefundenen Artikel-Sätzen 1 und 2, beziehungsweise gleich sind. Für das Nichtterminal B geht der Übergang zu:

: Artikel hat 7 gesetzt

: E  E * B

·

Weil Artikel 6 untergegangen ist, müssen wir auch das Terminal '0' und '1' und das Nichtterminal B denken. Wie zuvor sind die resultierenden Artikel-Sätze für die Terminals den bereits gefundenen Artikel-Sätzen 1 und 2 gleich. Für das Nichtterminal B geht der Übergang zu:

: Artikel hat 8 gesetzt

: E  E + B ·

Diese Endartikel-Sätze haben keine Symbole außer ihren Punkten, so werden keine neue Artikel-Sätze mehr hinzugefügt und wir beendet werden. Der begrenzte Automat, mit Artikel-Sätzen als seine Staaten wird unten gezeigt.

Der Übergang-Tisch für den Automaten sieht jetzt wie folgt aus:

Das Konstruieren der Handlung und goto Tische

Von diesem Tisch und die gefundenen Artikel-Sätze bauen wir die Handlung und den goto Tisch wie folgt:

1. Die Säulen für Nichtterminals werden zum goto Tisch kopiert.
2. Die Säulen für die Terminals werden zum Handlungstisch als Verschiebungshandlungen kopiert.
3. Eine Extrasäule für 'den $' (Ende des Eingangs) wird zum Handlungstisch hinzugefügt, der acc für jeden Artikel-Satz enthält, der S  E enthält ·.
4. Wenn ein Artikel i untergegangen ist, enthält einen Artikel der Form Ein  w · und Ein  w ist Regel M mit der M &gt; 0 dann wird die Reihe für den Staat i im Handlungstisch mit der reduzieren Handlung rm völlig gefüllt.

Der Leser kann nachprüfen, dass das tatsächlich in der Handlung und dem goto Tisch resultiert, die früher präsentiert wurden.

Ein Zeichen über LR (0) gegen SLR und LALR-Syntaxanalyse

Bemerken Sie, dass nur der Schritt 4 des obengenannten Verfahrens erzeugt, reduzieren Handlungen, und so nehmen alle ab, müssen Handlungen eine komplette Tabellenreihe besetzen, die Verminderung veranlassend, unabhängig vom folgenden Symbol im Eingangsstrom vorzukommen. Das ist, warum das LR (0) Syntaxanalyse-Tische ist: Sie tun keinen lookahead (d. h. sie schauen vorn Nullsymbole) vor dem Entscheiden der die Verminderung zu leisten. Eine Grammatik, die lookahead braucht, um die Verminderungen zu disambiguieren, würde verlangen, dass eine Syntaxanalyse-Tabellenreihe, die verschieden enthält, Handlungen in verschiedenen Säulen reduziert, und das obengenannte Verfahren dazu nicht fähig ist, solche Reihen zu schaffen.

Verbesserungen zum LR (0) ist Tabellenbauverfahren (wie SLR und LALR) zum Konstruieren fähig reduzieren Handlungen, die komplette Reihen nicht besetzen. Deshalb sind sie zur Syntaxanalyse von mehr Grammatiken fähig als LR (0) parsers.

Konflikte in den gebauten Tischen

Der Automat wird auf solche Art und Weise gebaut, dass, wie man versichert, er deterministisch ist. Jedoch, wenn abnehmen, werden Handlungen zum Handlungstisch hinzugefügt es kann geschehen, dass dieselbe Zelle mit einer reduzieren Handlung und einer Verschiebungshandlung gefüllt wird (ein Shift-Reduce-Konflikt) oder mit zwei verschiedenen Handlungen reduzieren (ein Reduzieren - reduzieren Konflikt). Jedoch kann es gezeigt werden, dass, wenn das geschieht, die Grammatik nicht ein LR (0) Grammatik ist.

Ein kleines Beispiel eines non-LR (0) Grammatik mit einem Shift-Reduce-Konflikt ist:

: (1) E  1 E

: (2) E  1

Einer der Artikel-Sätze, die wir dann finden, ist:

: Artikel hat 1 gesetzt

: E  1 · E

: E  1

·

: + E  · 1 E

: + E  · 1

Es gibt einen Shift-Reduce-Konflikt in diesem Artikel-Satz weil in der Zelle im Handlungstisch für diesen Artikel-Satz und das Terminal '1' dort wird sowohl eine Verschiebungshandlung sein, um 1 als auch eine reduzieren Handlung mit der Regel 2 festzusetzen.

Ein kleines Beispiel eines non-LR (0) nimmt die Grammatik mit einem Reduzieren - ab Konflikt ist:

: (1) E  EIN 1

: (2) E  B 2

: (3) Ein  1

: (4) B  1

In diesem Fall erhalten wir den folgenden Artikel-Satz:

: Artikel hat 1 gesetzt

: Ein  1

·: B  1 ·

Es gibt ein Reduzieren - reduzieren Konflikt in diesem Artikel-Satz weil in den Zellen im Handlungstisch für diesen Artikel-Satz es wird sowohl eine reduzieren Handlung für die Regel 3 als auch ein für die Regel 4 geben.

Beide Beispiele können oben gelöst werden, indem sie den parser den folgen Satz verwenden lässt (sieh LL parser) eines Nichtterminals A, um zu entscheiden, ob es dabei ist, einen Als Regeln für die Verminderung zu verwenden; es wird nur die Regel Ein  w für die Verminderung verwenden, wenn das folgende Symbol auf dem Eingangsstrom im folgen Satz von A ist. Diese Lösung läuft auf so genannten Einfachen LR parsers hinaus.

Siehe auch

• Kanonischer LR
• Deterministische Grammatik ohne Zusammenhänge
• Schauen Sie LR vorn
• Verallgemeinerter LR
• LL parser
• Einfacher LR

• Aho, Sethi, Ullman, Addison-Wesley, 1986. Internationale Standardbuchnummer 0-201-10088-6. Eine umfassende Diskussion der LR-Syntaxanalyse und der Hauptquelle für einige Abteilungen in diesem Artikel.
• dickgrune.com Techniken - Ein Praktischer Führer Grammatisch analysierend, schließt die 1. Webseite von Ed des Buches herunterladbaren pdf ein.
• Die Funktionelle Behandlung, (Boston Grammatisch zu analysieren: Kluwer Akademisch, 1993), R. Leermakers, internationale Standardbuchnummer 0-7923-9376-7
• Die Theorie der Syntaxanalyse, die Übersetzung, und das Kompilieren, Alfred V. Aho und Jeffrey D. Ullman, der von ACM.org verfügbar

ist

Weiterführende Literatur

• Hausierer, Nigel P., LR Syntaxanalyse: Theorie und Praxis, Universität von Cambridge Presse, 1987. Internationale Standardbuchnummer 0 521 30413 X
• Pager, D., Eine Praktische Allgemeine Methode, um LR (k) Parsers Zu bauen. Acta Informatica 7, 249 - 268 (1977)

Links

Wenn man

• Simulator grammatisch analysiert, wird Dieser Simulator verwendet, um Syntaxanalyse-Tische LR zu erzeugen und die Übungen des Buches aufzulösen
• Internals eines LALR (1) parser, der vom GNU-Bison - Durchführung erzeugt ist, gibt aus