Was ist der Unterschied zwischen LR-, SLR- und LALR-Parsern?

Question

Was ist der tatsächliche Unterschied zwischen LR-, SLR- und LALR-Parsern? Ich weiß, dass SLR und LALR sind Typen von LR-Parsern, aber was ist der tatsächliche Unterschied, was ihre Parsing-Tabellen angeht?

Und wie zeigt man, ob eine Grammatik LR, SLR oder LALR ist? Für eine LL-Grammatik müssen wir nur zeigen, dass keine Zelle der Parsingtabelle mehrere Produktionsregeln enthalten sollte. Gibt es ähnliche Regeln für LALR, SLR und LR?

Zum Beispiel: Wie können wir zeigen, dass die Grammatik

S --> Aa | bAc | dc | bda 
A --> d 

LALR (1) ist aber nicht SLR (1)?

---

EDIT (ybungalobill): ich keine befriedigende Antwort für das, was ist der Unterschied zwischen LALR und LR erhalten hat. Die Tabellen von LALR sind also kleiner, können aber nur eine Teilmenge der LR-Grammatiken erkennen. Kann jemand bitte mehr auf den Unterschied zwischen LALR und LR eingehen? LALR (1) und LR (1) reichen für eine Antwort aus. Beide verwenden 1 Token Look-Ahead und beide sind Tabellentreiber! Wie sind sie anders?

Answer 1

SLR-, LALR- und LR-Parser können alle mit derselben tabellengesteuerten Maschine implementiert werden.

Grundsätzlich sammelt der Parsing-Algorithmus, um die nächste Eingabe-Token T, und berät den aktuellen Zustand S (und die damit verbundene Look-Ahead, GOTO und Reduktion Tabellen) zu entscheiden, was zu tun ist:

• SHIFT: Wenn der Strom Die Tabelle sagt zu SHIFT auf dem Token T, das Paar (S, T) wird auf den Parse-Stapel geschoben, der Zustand wird entsprechend der GOTO-Tabelle für das aktuelle Token (z. B. GOTO (T)) geändert, ein weiteres Eingabetoken T 'wird abgerufen, und der Prozess wird wiederholt
• REDUZIEREN: Jeder Zustand hat 0, 1 oder viele mögliche Reduzierungen, die in diesem Zustand auftreten können. Wenn der Parser LR oder LALR ist, wird das Token mit Lookahead-Sätzen für alle gültigen Reduzierungen für den Status verglichen. Wenn das Token mit einem Lookahead-Set für eine Reduktion für die Grammatikregel G = R1 R2 .. Rn übereinstimmt, tritt eine Stapelreduktion und -verschiebung auf: die semantische Aktion für G wird aufgerufen, der Stapel wird n (von Rn) gepoppt, das Paar (S, G) wird auf den Stapel geschoben, der neue Zustand S 'wird auf GOTO (G) gesetzt, und der Zyklus wiederholt sich mit dem gleichen Token T. Wenn der Parser ein SLR - Parser ist, gibt es höchstens eine Reduktionsregel für den Zustand und so die Reduktion Aktion kann blind getan werden, ohne zu sehen, welche Reduktion gilt. Es ist nützlich für einen SLR-Parser zu wissen, ob eine Reduzierung ist oder nicht; Dies ist leicht zu sagen, wenn jeder Zustand die Anzahl der damit verbundenen Reduktionen explizit aufzeichnet, und diese Zählung wird für die L (AL) R-Versionen in der Praxis sowieso benötigt.
• FEHLER: Wenn weder SHIFT noch REDUCE möglich ist, wird ein Syntaxfehler gemeldet.

Also, wenn sie alle die gleiche Maschine verwenden, was ist der Punkt?

Der angebliche Wert in SLR ist seine Einfachheit in der Implementierung; Sie müssen nicht durch die möglichen Look-Ahead-Sets für die Reduktionsüberprüfung scannen, weil es höchstens eins gibt, und dies ist die einzige praktikable Aktion, wenn es keine SHIFT-Exits vom Status gibt. Welche Reduktion gilt, kann spezifisch an den Zustand angehängt werden, so dass die SLR-Parsing-Maschine nicht danach suchen muss. In der Praxis handhaben L (AL) R-Parser einen nützlichen größeren Satz von Sprachen, und es ist so wenig zusätzliche Arbeit zu implementieren, dass niemand SLR implementiert, außer als eine akademische Übung.

Der Unterschied zwischen LALR und LR hat mit der Tabelle Generator zu tun. LR-Parser-Generatoren verfolgen alle möglichen Reduktionen von bestimmten Zuständen und ihrer präzisen Lookahead-Menge; Sie enden mit Zuständen, in denen jede Verkleinerung mit ihrer genauen Lookahead-Menge aus ihrem linken Kontext verknüpft ist. Dies neigt dazu, ziemlich große Mengen von Zuständen zu bilden. LALR-Parsergeneratoren sind bereit, Zustände zu kombinieren, wenn die GOTO-Tabellen und Lookhead-Sets für Reduktionen kompatibel sind und nicht in Konflikt stehen; dies führt zu einer wesentlich geringeren Anzahl von Zuständen, zu dem Preis, dass bestimmte von LR zu unterscheidende Symbolsequenzen nicht unterschieden werden können. Also können LR-Parser eine größere Anzahl von Sprachen als LALR-Parser analysieren, haben aber sehr viel größere Parser-Tabellen. In der Praxis kann man LALR-Grammatiken finden, die nahe genug an den Zielsprachen liegen, dass die Größe der Zustandsmaschine optimiert werden muss; Die Stellen, an denen der LR-Parser besser wäre, werden durch Ad-hoc-Überprüfung außerhalb des Parsers behandelt.

Also: Alle drei benutzen die gleiche Maschine. SLR ist "einfach" in dem Sinne, dass Sie ein winziges bisschen der Maschinerie ignorieren können, aber es ist einfach nicht die Mühe wert. LR analysiert eine größere Anzahl von Sprachen, aber die Zustandstabellen sind in der Regel ziemlich groß. Damit bleibt LALR die praktische Wahl.

all dies gesagt ist, lohnt es sich zu wissen, dass GLR parsers freie Sprache jeden Kontext analysieren kann, kompliziertere Maschinen aber genau die gleichen Tabellen (einschließlich der kleineren Version von LALR verwendet wird) verwendet wird. Dies bedeutet, dass GLR strikter ist als LR, LALR und SLR; ziemlich viel, wenn Sie eine Standard-BNF-Grammatik schreiben können, wird GLR entsprechend analysieren. Der Unterschied in der Maschinerie ist, dass GLR bereit ist, mehrere Analysen zu versuchen, wenn es Konflikte zwischen der GOTO-Tabelle und den Lookahead-Sätzen gibt. (Wie GLR dies effizient ist, ist schier genial [nicht meins], aber passt nicht in diese SO Post).

Das ist für mich eine enorm nützliche Tatsache. Ich baue Programmanalysatoren und Codetransformatoren und Parser sind notwendig, aber "uninteressant"; Die interessante Arbeit ist, was Sie mit dem geparsten Ergebnis tun, und so liegt der Schwerpunkt auf der Post-Parsing-Arbeit. Die Verwendung von GLR bedeutet, dass ich relativ einfach Arbeitsgrammatiken erstellen kann, verglichen mit dem Hacken einer Grammatik, um in LALR verwendbare Form zu gelangen. Das ist sehr wichtig, wenn man versucht, nicht-akademische Sprachen wie C++ oder Fortran zu bearbeiten, wo man buchstäblich Tausende von Regeln braucht, um die gesamte Sprache gut zu handhaben, und man nicht sein Leben damit verbringen will, die Grammatikregeln zu hacken die Beschränkungen von LALR (oder sogar LR) erfüllen.

Als eine Art berühmtes Beispiel, C++ gilt als extrem schwierig zu parsen ... von Jungs tun LALR Parsing. C++ ist einfach zu analysieren mit GLR-Maschinen mit ziemlich genau die Regeln in der Rückseite des C++ Referenzhandbuchs zur Verfügung gestellt. (Ich habe genau einen solchen Parser, und er behandelt nicht nur Vanille C++, sondern auch eine Vielzahl von Herstellerdialekten. Dies ist nur in der Praxis möglich, weil wir einen GLR-Parser, IMHO, verwenden).

[EDIT November 2011: Wir haben unseren Parser erweitert, um alle C++ 11 zu behandeln. GLR hat das viel einfacher gemacht.]

Answer 2

LALR-Parser verschmelzen ähnliche Zustände innerhalb einer LR-Grammatik, um Parserzustandstabellen zu erzeugen, die genau die gleiche Größe wie die äquivalente SLR-Grammatik haben, die normalerweise eine Größenordnung kleiner als rein sind LR-Analysetabellen. Für LR-Grammatiken, die zu komplex sind, um LALR zu sein, führen diese verschmolzenen Zustände jedoch zu Parserkonflikten oder erzeugen einen Parser, der die ursprüngliche LR-Grammatik nicht vollständig erkennt.

BTW, ich erwähne ein paar Dinge in meinem MLR (k) Parsing-Tabelle Algorithmus here.

Nachtrag

Die kurze Antwort ist, dass die LALR Parsing-Tabellen sind kleiner, aber die Parser Maschinen sind das gleiche. Eine gegebene LALR-Grammatik wird wesentlich größere Parsingtabellen erzeugen, wenn alle LR-Zustände mit vielen redundanten (nahezu identischen) Zuständen erzeugt werden.

Die LALR-Tabellen sind kleiner, weil die ähnlichen (redundanten) Zustände zusammengeführt werden, wodurch die Kontext-/Lookahead-Informationen verworfen werden, die die einzelnen Zustände codieren. Der Vorteil ist, dass Sie viel kleinere Parsing-Tabellen für die gleiche Grammatik erhalten.

Der Nachteil ist, dass nicht alle LR-Grammatiken als LALR-Tabellen codiert werden können, da komplexere Grammatiken komplexere Lookaheads haben, was zu zwei oder mehr Zuständen anstatt zu einem einzigen zusammengeführten Zustand führt.

Der Hauptunterschied besteht darin, dass der Algorithmus zur Erzeugung von LR-Tabellen mehr Informationen zwischen den Übergängen von Zustand zu Zustand enthält, während der LALR-Algorithmus dies nicht tut. Daher kann der LALR-Algorithmus nicht feststellen, ob ein bestimmter zusammengeführter Zustand wirklich als zwei oder mehr separate Zustände übrig sein sollte.

Answer 3

Der grundlegende Unterschied zwischen den Parser-Tabellen, die mit SLR vs LR generiert werden, besteht darin, dass Reduzierungsaktionen auf den Folgen basieren, die für SLR-Tabellen festgelegt werden. Dies kann übermäßig restriktiv sein, was letztlich zu einem Shift-Reduce-Konflikt führt.

Ein LR-Parser auf der anderen Seite reduziert Entscheidungen nur auf der Menge der Terminals, die tatsächlich dem Nicht-Terminal folgen können, das reduziert wird. Dieser Satz von Endgeräten ist oft eine richtige Teilmenge des Folgensatzes eines solchen Nicht-Endgeräts und hat daher eine geringere Wahrscheinlichkeit, mit Verschiebeaktionen in Konflikt zu geraten.

LR-Parser sind aus diesem Grund leistungsfähiger. LR-Parsing-Tabellen können jedoch sehr groß sein.

Ein LALR-Parser beginnt mit der Idee, eine LR-Parsing-Tabelle zu erstellen, kombiniert jedoch generierte Zustände in einer Weise, die zu einer wesentlich geringeren Tabellengröße führt. Der Nachteil ist, dass eine kleine Wahrscheinlichkeit von Konflikten für einige Grammatiken eingeführt würde, die eine LR-Tabelle sonst vermieden hätte.

LALR-Parser sind etwas weniger leistungsfähig als LR-Parser, aber immer noch leistungsstärker als SLR-Parser. YACC und andere solche Parsergeneratoren neigen dazu, LALR aus diesem Grund zu verwenden.

P.S. Der Kürze halber bedeuten SLR, LALR und LR oberhalb von SLR (1), LALR (1) und LR (1), so dass ein Token-Lookahead impliziert wird.

Answer 4

Noch eine andere Antwort (YAA).

Die Parsing-Algorithmen für SLR (1), LALR (1) und LR (1) sind identisch wie Ira Baxter sagte
jedoch wegen der Parser-Erzeugungsalgorithmus die Parser Tabellen unterschiedlich sein können.

Ein SLR-Parser-Generator erstellt eine LR (0) State Machine und berechnet die Vorausschau aus der Grammatik (FIRST- und FOLLOW-Sets). Dies ist ein vereinfachter Ansatz und kann Konflikte melden, die in der Zustandsmaschine LR (0) nicht wirklich existieren.

Ein LALR-Parser-Generator erstellt eine LR (0) -Statusmaschine und berechnet die Vorausschau von der LR (0) -Statusmaschine (über die Terminalübergänge). Dies ist ein korrekter Ansatz, meldet jedoch gelegentlich Konflikte, die in einer LR (1) Zustandsmaschine nicht existieren würden.

Ein kanonischer LR-Parsergenerator berechnet eine LR (1) Zustandsmaschine und die Vorausschau ist bereits Teil der LR (1) Zustandsmaschine. Diese Parser-Tabellen können sehr groß sein.

Ein Minimal-LR-Parsergenerator berechnet eine LR (1) Zustandsmaschine, führt aber während des Prozesses kompatible Zustände zusammen und berechnet dann die Vorausschau von der minimalen LR (1) Zustandsmaschine. Diese Parsertabellen sind gleich groß oder etwas größer als LALR-Parsertabellen und bieten die beste Lösung.

LRSTAR 8.0 können LALR (1), Minimal LR (1) und LR (k) Parser in C++ generieren.

Answer 5

SLR-Parser erkennen eine richtige Teilmenge von Grammatiken, die durch LALR (1) -Parser erkannt werden, die ihrerseits eine richtige Teilmenge von Grammatiken erkennen, die von LR (1) -Parsern erkannt werden.

Jeder von diesen ist als eine Zustandsmaschine konstruiert, wobei jeder Zustand einen Satz von Grammatikproduktionsregeln (und Position in jedem) darstellt, während er die Eingabe analysiert.

Das Dragon Book Beispiel eines LALR (1) Grammatik, die nicht SLR ist, ist dies:

S → L = R | R 
L → * R | id 
R → L 

Hier ist einer der Zustände für diese Grammatik:

S → L•= R 
R → L• 

Die • zeigt die Position des Parsers in jeder der möglichen Produktionen. Es weiß nicht, welche der Produktionen es tatsächlich ist, bis es das Ende erreicht und versucht zu reduzieren.

Hier könnte der Parser entweder verschieben oder R → L reduzieren.

Ein SLR (aka LR (0)) Parser würden bestimmen, ob es durch Prüfen, ob das nächste Eingabesymbol in den ist folgen gesetzt von R (dh die Menge aller Terminals in der Grammatik reduzieren könnte, die folgen kann R). Da = ebenfalls in diesem Set enthalten ist, stößt der SLR-Parser auf einen Shift-Reduce-Konflikt.

jedoch ein LALR (1) Parser würden die Menge aller Endgeräte benutzen, die diese besondere Produktion von R folgen, was nur $ (dh, das Ende der Eingabe). Also, kein Konflikt.

Wie frühere Kommentatoren festgestellt haben, haben LALR (1) Parser die gleiche Anzahl von Zuständen wie SLR-Parser. Ein Lookahead-Propagationsalgorithmus wird verwendet, um Vorschauen auf SLR-Zustandsproduktionen von entsprechenden LR (1) -Zuständen zu verfolgen. Der resultierende LALR (1) -Parser kann Reduzieren-Reduzieren-Konflikte einführen, die nicht im LR (1) -Parser vorhanden sind, aber er kann keine Shift-Reduce-Konflikte einführen.

In Ihrem Beispiel verursacht die folgende LALR (1) Zustand einen shift-reduce Konflikt in einer SLR-Implementierung:

S → b d•a/$ 
A → d•/c 

Das Symbol nach / ist der Nachfolger Satz für jede Produktion in der LALR (1) Parser. In SLR, folgen (A) enthält a, die auch verschoben werden könnte.

Answer 6

Eine einfache Antwort ist, dass alle LR (0) Grammatiken LALR (1) Grammatiken sind. Im Vergleich zu LR (1) hat LALR (1) mehr Zustände im zugehörigen DFA (fast doppelte Zustände). Und das ist der Hauptgrund dafür, dass LALR (1) Grammatiken mehr Zeit benötigen, um Fehler anzuzeigen als LR (1) Grammatiken. Und noch eine wichtige Sache in Bezug auf diese beiden Grammatiken ist, dass wir in LR (1) Grammatiken keine shift/reduces finden oder Konflikte reduzieren/reduzieren. In LALR (1) gibt es jedoch die Möglichkeit Konflikte zu reduzieren/reduzieren.

Answer 7

Angenommen, ein Parser ohne Lookahead analysiert die Zeichenfolgen für Ihre Grammatik.

Mit Ihrem gegebenen Beispiel stößt es auf eine Zeichenfolge dc, was macht es? Reduziert es es auf S, weil dc eine gültige Zeichenfolge ist, die von dieser Grammatik erzeugt wird? ODER vielleicht haben wir versucht, bdc zu analysieren, weil auch das eine akzeptable Zeichenfolge ist?

Als Menschen wissen wir, die Antwort ist einfach, wir müssen nur daran denken, ob wir gerade b geparst haben oder nicht. Aber Computer sind dumm :)

Da ein SLR (1) Parser die zusätzliche Macht über LR (0) hatte, um ein Lookahead durchzuführen, wissen wir, dass irgendwelche Mengen von Lookahead uns nicht sagen können, was in diesem Fall zu tun ist; Stattdessen müssen wir in unsere Vergangenheit zurückblicken. So kommt der kanonische LR-Parser zur Rettung. Es erinnert sich an den vergangenen Kontext.

Die Art, wie es sich an diesen Kontext erinnert, ist, dass es sich selbst diszipliniert, dass, wann immer es auf b stößt, es als eine Möglichkeit beginnt, auf einen Pfad in Richtung bdc zu gehen. Also wenn es ein d sieht, weiß es, ob es bereits einen Pfad geht. So kann ein CLR (1) Parser Dinge tun, die ein SLR (1) Parser nicht kann!

Aber jetzt, da wir so viele Pfade definieren mussten, werden die Zustände der Maschine sehr groß!

Wir verschmelzen also gleich aussehende Pfade, aber wie erwartet könnte es zu Verwirrungsproblemen führen. Wir sind jedoch bereit, das Risiko auf Kosten der Größenreduzierung zu übernehmen.

Dies ist Ihr LALR (1) Parser.

---

Jetzt, wie man es algorithmisch tut.

Wenn Sie die Konfigurationssätze für die obige Sprache zeichnen, sehen Sie einen Shift-Reduce-Konflikt in zwei Zuständen. Um sie zu entfernen, sollten Sie eine Spiegelreflexkamera (1) in Betracht ziehen, die Entscheidungen trifft, wenn Sie eine Folge betrachten, aber Sie würden feststellen, dass dies immer noch nicht möglich ist. Sie würden also die Konfigurationssätze erneut zeichnen, aber dieses Mal mit der Einschränkung, dass bei jeder Berechnung des Abschlusses die hinzugefügten zusätzlichen Produktionen strikte Folge (n) haben müssen. Verweisen Sie auf irgendein Lehrbuch auf, was diese folgen sollten.