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

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

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

Wie können wir zum Beispiel die Grammatik zeigen?

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

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

EDIT (ybungalobill) : Ich habe keine zufriedenstellende Antwort auf den Unterschied zwischen LALR und LR erhalten. Die Tabellen von LALR sind also kleiner, können jedoch 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 tischgesteuert! Wie unterscheiden sie sich?

SLR-, LALR- und LR-Parser können alle mit genau denselben tischgesteuerten Maschinen implementiert werden.

Grundsätzlich sammelt der Parsing-Algorithmus das nächste Eingabetoken T und konsultiert den aktuellen Status S (und die zugehörigen Lookahead-, GOTO- und Reduktionstabellen), um zu entscheiden, was zu tun ist:

• SHIFT: Wenn die aktuelle Tabelle auf dem Token T SHIFT sagt, wird das Paar (S, T) auf den Analysestapel verschoben, und der Status wird entsprechend den Angaben in der GOTO-Tabelle für das aktuelle Token geändert (z. B. GOTO (T)). ) wird ein weiteres Eingabetoken T 'abgerufen und der Vorgang wiederholt
• REDUZIEREN: Jeder Zustand hat 0, 1 oder viele mögliche Reduzierungen, die im Zustand auftreten können. Wenn der Parser LR oder LALR ist, wird das Token anhand von Lookahead-Sets auf alle gültigen Reduzierungen für den Status überprüft. Wenn das Token mit einem Lookahead-Satz für eine Reduktion für die Grammatikregel G = R1 R2 übereinstimmt. Rn tritt eine Stapelreduktion und -verschiebung auf: Die semantische Aktion für G wird aufgerufen, der Stapel wird n (von Rn) mal gepoppt, das Paar ( S, G) wird auf den Stapel geschoben, der neue Zustand S 'wird auf GOTO (G) gesetzt und der Zyklus wird mit demselben Token T wiederholt. Wenn der Parser ein SLR-Parser ist, gibt es höchstens eine Reduktionsregel für die Zustand und so kann die Reduktionsaktion blind durchgeführt werden, ohne zu suchen, welche Reduktion gilt. Für einen SLR-Parser ist es hilfreich zu wissen, ob dies der Fall isteine Reduzierung oder nicht; Dies ist leicht zu erkennen, wenn jeder Zustand die Anzahl der damit verbundenen Reduzierungen explizit aufzeichnet und diese Anzahl in der Praxis ohnehin für die L (AL) R-Versionen erforderlich ist.
• FEHLER: Wenn weder SHIFT noch REDUCE möglich sind, wird ein Syntaxfehler deklariert.

Also, wenn sie alle die gleichen Maschinen benutzen, worum geht es dann?

Der angebliche Wert von SLR ist die einfache Implementierung. Sie müssen die möglichen Reduzierungen nicht durchsuchen, um Lookahead-Sets zu überprüfen, da es höchstens eine gibt. Dies ist die einzig praktikable Aktion, wenn keine SHIFT-Exits aus dem Status vorhanden sind. Welche Ermäßigung gilt, kann spezifisch an den Staat geknüpft werden, sodass die SLR-Parsing-Maschinerie nicht danach suchen muss. In der Praxis verarbeiten L (AL) R-Parser einen nützlich größeren Satz von Sprachen und sind so wenig zusätzliche Arbeit zu implementieren, dass niemand SLR implementiert, außer als akademische Übung.

Der Unterschied zwischen LALR und LR hat mit der Tabelle zu tun Generator. LR-Parser-Generatoren verfolgen alle möglichen Reduzierungen aus bestimmten Zuständen und deren genaue Lookahead-Einstellung. Sie erhalten Zustände, in denen jede Reduzierung mit dem genauen Lookahead-Satz aus dem linken Kontext verknüpft ist. Dies führt tendenziell zu ziemlich großen Mengen von Staaten. LALR-Parser-Generatoren sind bereit, Zustände zu kombinieren, wenn die GOTO-Tabellen und Lookhead-Sets für Reduzierungen kompatibel sind und keine Konflikte verursachen. Dies erzeugt eine erheblich geringere Anzahl von Zuständen, um bestimmte Symbolsequenzen, die LR unterscheiden kann, nicht unterscheiden zu können. LR-Parser können also einen größeren Satz von Sprachen analysieren als LALR-Parser, haben jedoch sehr viel größere Parsertabellen. In der Praxis kann man LALR-Grammatiken finden, die nahe genug an den Zielsprachen liegen, sodass die Größe der Zustandsmaschine optimiert werden sollte.

Also: Alle drei benutzen die gleiche Maschinerie. SLR ist "einfach" in dem Sinne, dass Sie ein kleines Stück der Maschine ignorieren können, aber es ist einfach nicht die Mühe wert. LR analysiert einen breiteren Satz von Sprachen, aber die Statustabellen sind in der Regel ziemlich groß. Damit bleibt LALR die praktische Wahl.

Nach alledem ist es wichtig zu wissen, dass GLR-Parser jede kontextfreie Sprache analysieren können, indem sie kompliziertere Maschinen verwenden, aber genau dieselben Tabellen (einschließlich der von LALR verwendeten kleineren Version). Dies bedeutet, dass GLR strikt leistungsfähiger ist als LR, LALR und SLR. Wenn Sie eine Standard-BNF-Grammatik schreiben können, analysiert GLR diese entsprechend. Der Unterschied in der Maschinerie besteht darin, dass GLR bereit ist, mehrere Analysen durchzuführen, wenn Konflikte zwischen der GOTO-Tabelle und / oder Lookahead-Sets bestehen. (Wie GLR dies effizient macht, ist einfach genial [nicht meins], passt aber nicht in diesen SO-Beitrag).

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 analysierten Ergebnis machen, und daher liegt der Fokus auf der Arbeit nach dem Parsen. Mit GLR kann ich relativ einfach funktionierende Grammatiken erstellen, verglichen mit dem Hacken einer Grammatik, um in eine LALR-verwendbare Form zu gelangen. Dies ist sehr wichtig, wenn Sie versuchen, sich mit nicht-akademischen Sprachen wie C ++ oder Fortran zu befassen, bei denen Sie buchstäblich Tausende von Regeln benötigen, um die gesamte Sprache gut zu handhaben, und Sie nicht Ihr Leben damit verbringen möchten, die Grammatikregeln zu hacken die Einschränkungen von LALR (oder sogar LR) erfüllen.

Als eine Art berühmtes Beispiel wird C ++ als extrem schwer zu analysieren angesehen ... von Leuten, die LALR-Analyse durchführen. C ++ lässt sich mit GLR-Maschinen ganz einfach anhand der Regeln analysieren, die im hinteren Teil des C ++ - Referenzhandbuchs angegeben sind. (Ich habe genau einen solchen Parser, der nicht nur Vanilla C ++, sondern auch eine Vielzahl von Hersteller-Dialekten verarbeitet. Dies ist nur in der Praxis möglich, da wir einen GLR-Parser verwenden, IMHO).

[EDIT November 2011: Wir haben unseren Parser auf C ++ 11 erweitert. GLR hat das viel einfacher gemacht. BEARBEITEN Aug 2014: Jetzt wird C ++ 17 vollständig verarbeitet. Nichts ist kaputt gegangen oder schlimmer geworden, GLR ist immer noch der Miau der Katze.]

LALR-Parser führen ähnliche Zustände innerhalb einer LR-Grammatik zusammen, um Parser-Statustabellen zu erstellen, die genau die gleiche Größe wie die entsprechende SLR-Grammatik haben und normalerweise eine Größenordnung kleiner sind als reine LR-Parsing-Tabellen. Bei LR-Grammatiken, die zu komplex sind, um LALR zu sein, führen diese zusammengeführten Zustände jedoch zu Parser-Konflikten oder erzeugen einen Parser, der die ursprüngliche LR-Grammatik nicht vollständig erkennt.

BTW, erwähne ich ein paar Dinge über das in meinem MLR (k) Parsingtabelle Algorithmus hier .

Nachtrag

Die kurze Antwort lautet, dass die LALR-Parsing-Tabellen kleiner sind, die Parser-Maschinerie jedoch dieselbe ist. Eine gegebene LALR-Grammatik erzeugt viel größere Analysetabellen, wenn alle LR-Zustände mit vielen redundanten (nahezu identischen) Zuständen erzeugt werden.

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

Der Nachteil ist, dass nicht alle LR-Grammatiken als LALR-Tabellen codiert werden können, da komplexere Grammatiken kompliziertere Lookaheads aufweisen, was zu zwei oder mehr Zuständen anstelle eines einzelnen zusammengeführten Zustands führt.

Der Hauptunterschied besteht darin, dass der Algorithmus zum Erzeugen von LR-Tabellen mehr Informationen zwischen den Übergängen von Zustand zu Zustand enthält, während der LALR-Algorithmus dies nicht tut. Der LALR-Algorithmus kann also nicht sagen, ob ein bestimmter zusammengeführter Zustand wirklich als zwei oder mehr separate Zustände belassen werden soll.

Noch eine Antwort (YAA).

Die Parsing-Algorithmen für SLR (1), LALR (1) und LR (1) sind identisch wie Ira Baxter sagte,
jedoch können die Parsertabellen aufgrund des Parser-Generierungsalgorithmus unterschiedlich sein.

Ein SLR-Parser-Generator erstellt eine LR (0) -Zustandsmaschine und berechnet die Vorausschau aus der Grammatik (FIRST- und FOLLOW-Sätze). Dies ist ein vereinfachter Ansatz und kann Konflikte melden, die in der LR (0) -Zustandsmaschine nicht wirklich vorhanden sind.

Ein LALR-Parsergenerator erstellt eine LR (0) -Zustandsmaschine und berechnet die Vorausschau von der LR (0) -Zustandsmaschine (ü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 Canonical LR-Parsergenerator berechnet eine LR (1) -Zustandsmaschine, und die Vorausschau ist bereits Teil der LR (1) -Zustandsmaschine. Diese Parsertabellen können sehr groß sein.

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

LRSTAR 10.0 kann LALR (1) -, LR (1) -, CLR (1) - oder LR (*) -Parser in C ++ generieren, unabhängig davon, was für Ihre Grammatik benötigt wird. Siehe dieses Diagramm, das den Unterschied zwischen LR-Parsern zeigt.

[Vollständige Offenlegung: LRSTAR ist mein Produkt]

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

Anhand Ihres Beispiels stößt es auf eine Zeichenfolge dc. Was macht es? Reduziert es es auf S, weil dceine gültige Zeichenfolge von dieser Grammatik erzeugt wird? ODER vielleicht haben wir versucht zu analysieren, bdcweil selbst das eine akzeptable Zeichenfolge ist?

Als Menschen wissen wir, dass die Antwort einfach ist. Wir müssen uns nur daran erinnern, ob wir gerade analysiert haben boder nicht. Aber Computer sind dumm :)

Da ein SLR (1) -Parser die zusätzliche Leistung über LR (0) hatte, um einen Lookahead durchzuführen, wissen wir, dass uns keine Mengen von Lookahead 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 und Weise, wie es sich an diesen Kontext erinnert, ist, dass es sich selbst diszipliniert, dass es, wenn es auf a stößt , als eine Möglichkeit bbeginnt, auf einem Weg zum Lesen bdczu gehen. Wenn es also ein sieht d, weiß es, ob es bereits einen Weg geht. Somit 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 kann dies zu Verwirrungsproblemen führen. Wir sind jedoch bereit, das Risiko auf Kosten der Größenreduzierung einzugehen.

Dies ist Ihr LALR (1) -Parser.

Nun, wie man es algorithmisch macht.

Wenn Sie die Konfigurationssätze für die oben genannte Sprache zeichnen, wird in zwei Zuständen ein Schichtreduzierungskonflikt angezeigt. Um sie zu entfernen, sollten Sie eine Spiegelreflexkamera (1) in Betracht ziehen, die Entscheidungen über eine Folge trifft, aber Sie würden feststellen, dass dies immer noch nicht möglich ist. Daher würden Sie die Konfigurationssätze erneut zeichnen, diesmal jedoch mit der Einschränkung, dass die hinzugefügten zusätzlichen Produktionen bei jeder Berechnung des Abschlusses strikt eingehalten werden müssen. Lesen Sie in jedem Lehrbuch nach, wie diese aussehen sollen.

Der grundlegende Unterschied zwischen den mit SLR und LR generierten Parsertabellen besteht darin, dass Reduzierungsaktionen auf den für SLR-Tabellen festgelegten Follows basieren. Dies kann zu restriktiv sein und letztendlich zu einem Schichtreduzierungskonflikt führen.

Ein LR-Parser hingegen reduziert Entscheidungen nur auf den Satz von Terminals, die tatsächlich dem reduzierten Nicht-Terminal folgen können. Dieser Satz von Terminals ist häufig eine geeignete Teilmenge des Follow-Satzes eines solchen Nicht-Terminals und hat daher eine geringere Wahrscheinlichkeit, mit Schichtaktionen in Konflikt zu geraten.

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

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

LALR-Parser sind etwas weniger leistungsfähig als LR-Parser, aber immer noch leistungsfähiger als SLR-Parser. YACC und andere solche Parser-Generatoren verwenden aus diesem Grund LALR.

PS Der Kürze halber bedeuten SLR, LALR und LR oben tatsächlich SLR (1), LALR (1) und LR (1), sodass ein Token-Lookahead impliziert ist.

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

Jeder dieser Zustände ist als Zustandsmaschine aufgebaut, wobei jeder Zustand einen Satz der Produktionsregeln der Grammatik (und die Position in jedem) darstellt, während die Eingabe analysiert wird.

Das Dragon Book- Beispiel für eine LALR (1) -Grammatik, die keine SLR ist, lautet:

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

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

S → L•= R
R → L•

Das •gibt die Position des Parsers in jeder der möglichen Produktionen an. Es weiß nicht, in welcher der Produktionen es sich tatsächlich befindet, bis es das Ende erreicht und versucht, es zu reduzieren.

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

Ein SLR-Parser (auch bekannt als LR (0)) würde bestimmen, ob er sich verringern könnte, indem er prüft, ob sich das nächste Eingabesymbol im Folgesatz von befindet R(dh im Satz aller Terminals in der Grammatik, die folgen können R). Da dies =auch in diesem Satz enthalten ist, stößt der SLR-Parser auf einen Shift-Reduction-Konflikt.

Ein LALR (1) -Parser würde jedoch die Menge aller Terminals verwenden, die dieser bestimmten Produktion von R folgen können , die nur $(dh das Ende der Eingabe) ist. Also kein Konflikt.

Wie frühere Kommentatoren festgestellt haben, haben LALR (1) -Parser die gleiche Anzahl von Zuständen wie SLR-Parser. Ein Lookahead-Ausbreitungsalgorithmus wird verwendet, um Lookaheads an SLR-Zustandsproduktionen aus entsprechenden LR (1) -Zuständen anzuheften. Der resultierende LALR (1) -Parser kann Reduktionsreduzierungskonflikte einführen, die im LR (1) -Parser nicht vorhanden sind, aber keine Schichtreduzierungskonflikte.

In Ihrem Beispiel verursacht der folgende LALR (1) -Zustand einen Schichtreduzierungskonflikt in einer SLR-Implementierung:

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

Das Symbol danach /ist der Folgesatz für jede Produktion im LALR (1) -Parser. In SLR enthält follow ( A) include a, das auch verschoben werden könnte.

Zusätzlich zu den obigen Antworten zeigt dieses Diagramm, wie verschiedene Parser zusammenhängen:

Eine einfache Antwort ist, dass alle LR (1) Grammatiken LALR (1) Grammatiken sind. Im Vergleich zu LALR (1) hat LR (1) mehr Zustände in der zugehörigen Finite-State-Maschine (mehr als doppelt so viele Zustände). Und das ist der Hauptgrund, warum LALR (1) -Grammatiken mehr Code benötigen, um Syntaxfehler zu erkennen als LR (1) -Grammatiken. Eine weitere wichtige Sache, die Sie in Bezug auf diese beiden Grammatiken wissen sollten, ist, dass wir in LR (1) -Grammatiken möglicherweise weniger Konflikte reduzieren / reduzieren. In LALR (1) gibt es jedoch mehr Möglichkeiten, Konflikte zu reduzieren / zu reduzieren.