wake-up-neo.com

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 Typen von LR-Parsern sind, aber was ist der tatsächliche Unterschied in Bezug auf ihre Parsing-Tabellen?

Und wie zeigt man, ob eine Grammatik LR, SLR oder LALR ist? Für eine LL-Grammatik müssen wir nur zeigen, dass jede Zelle der Parsing-Tabelle nicht mehrere Produktionsregeln enthalten darf. Ä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 befriedigende Antwort auf den Unterschied zwischen LALR und LR erhalten. Daher sind die Tabellen von LALR kleiner, sie können jedoch nur eine Teilmenge von LR-Grammatiken erkennen. Kann jemand bitte näher auf den Unterschied zwischen LALR und LR eingehen? LALR (1) und LR (1) sind für eine Antwort ausreichend. Beide verwenden 1 Token-Look-Ahead und beide sind tabellengesteuert! Wie unterscheiden sie sich?

96
Prasoon Saurav

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

Grundsätzlich erfasst der Analysealgorithmus das nächste Eingabe-Token T und prüft den aktuellen Status S (und die zugehörigen Lookahead-, GOTO- und Reduktionstabellen), um zu entscheiden, was zu tun ist:

  • SHIFT: Wenn in der aktuellen Tabelle SHIFT für das Token T angegeben ist, wird das Paar (S, T) auf den Parser-Stack verschoben. Der Status wird entsprechend den Angaben der GOTO-Tabelle für das aktuelle Token geändert (z. B. GOTO (T) ) wird ein anderes Eingabe-Token T 'abgerufen und der Vorgang wiederholt sich
  • REDUCE: Jeder Staat hat 0, 1 oder viele mögliche Reduzierungen, die im Staat auftreten können. Wenn der Parser LR oder LALR ist, wird das Token mit den Vorgriffssätzen auf alle gültigen Reduzierungen für den Status geprüft. Wenn das Token mit einem Lookahead-Satz übereinstimmt, der für die Reduzierung der Grammatikregel G = R1 R2 .. Rn festgelegt ist, tritt eine Stapelreduzierung und -verschiebung auf: Die semantische Aktion für G wird aufgerufen, der Stack wird n (von Rn) mal geknackt, 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 den Zustand und so kann die Reduktionsaktion blind durchgeführt werden, ohne zu suchen, welche Reduktion gilt. Für einen SLR-Parser ist es nützlich zu wissen, ob eine Verringerung ist oder nicht; Dies ist leicht zu erkennen, ob jeder Zustand die Anzahl der damit verbundenen Reduzierungen explizit aufzeichnet, und dass diese Zählung für die L (AL) R-Versionen in der Praxis ohnehin erforderlich ist.
  • ERROR: Wenn weder SHIFT noch REDUCE möglich ist, wird ein Syntaxfehler deklariert.

Wenn also alle die gleiche Maschine benutzen, was ist der Sinn?

Der angebliche Wert in der Spiegelreflexkameras ist die Einfachheit bei der Implementierung. Sie müssen nicht die möglichen Reduktionen durchsehen, um Lookahead-Sets zu überprüfen, da es höchstens einen gibt. Dies ist die einzig mögliche Aktion, wenn keine SHIFT-Exits aus dem Status vorhanden sind. Welche Reduzierung gilt, kann spezifisch an den Staat gebunden werden, so dass die SLR-Analysemaschinen nicht danach suchen müssen. In der Praxis handhaben L (AL) R-Parser eine sinnvoll größere Anzahl 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 generator zu tun. LR-Parser-Generatoren überwachen alle möglichen Reduzierungen von bestimmten Zuständen und deren genaue Vorausschau. Sie erhalten schließlich Zustände, in denen jede Reduktion mit ihrem exakten Lookahead-Satz aus dem linken Kontext verknüpft ist. Dies führt dazu, dass ziemlich viele Zustände gebildet werden. LALR-Parser-Generatoren sind bereit, Zustände zu kombinieren, wenn die GOTO-Tabellen und Lookhead-Sets für Verringerungen kompatibel sind und keinen Konflikt verursachen. Dies führt zu einer wesentlich geringeren Anzahl von Zuständen, jedoch mit dem Preis, bestimmte Symbolsequenzen, die LR unterscheiden kann, nicht unterscheiden zu können. Daher können LR-Parser eine größere Anzahl von Sprachen als LALR-Parser parsen, haben jedoch sehr viel größere Parser-Tabellen. In der Praxis kann man LALR-Grammatiken finden, die nahe genug an den Zielsprachen liegen, so dass die Größe der Zustandsmaschine zu optimieren ist; Die Stellen, an denen der LR-Parser besser wäre, werden durch eine Ad-hoc-Überprüfung außerhalb des Parsers behandelt.

Also: Alle drei verwenden die gleichen Maschinen. Die Spiegelreflexkamera ist "einfach" in dem Sinne, dass Sie ein winziges Stück der Maschinen ignorieren können, aber es lohnt sich nicht. LR analysiert eine breitere Gruppe von Sprachen, aber die Statustabellen sind in der Regel ziemlich groß. Somit bleibt LALR die praktische Wahl.

Trotzdem ist es wissenswert zu wissen, dass GLR-Parser jede kontextfreie Sprache mit komplizierteren Maschinen analysieren können , aber genau dieselben Tabellen (einschließlich der kleineren von LALR verwendeten Version). Dies bedeutet, dass der GLR strikt stärker ist als LR, LALR und SLR. Wenn Sie eine Standard-BNF-Grammatik schreiben können, wird GLR entsprechend analysiert. Der Unterschied in der Maschinerie besteht darin, dass GLR bereit ist, mehrere Parses durchzuführen, wenn Konflikte zwischen der GOTO-Tabelle und den Lookahead-Sätzen auftreten. (Wie GLR dies effizient tut, ist schlichtes Genie [nicht meins], passt aber nicht in diesen SO Posten). 

Das ist für mich eine enorm nützliche Tatsache. Ich baue Programmanalysatoren und Code-Transformatoren und Parser sind notwendig, aber "uninteressant". Die interessante Arbeit ist das, was Sie mit dem geparsten Ergebnis tun, und daher liegt der Schwerpunkt auf der Nachbearbeitung. Mit GLR kann ich relativ leicht 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, wo Sie buchstäblich Tausende von Regeln benötigen, um die gesamte Sprache gut zu beherrschen, und Sie möchten Ihr Leben nicht damit verbringen, 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 nach den Regeln des C++ - Referenzhandbuchs analysieren. (Ich habe genau einen solchen Parser, der nicht nur Vanilla C++, sondern auch eine Vielzahl von Hersteller-Dialekten beherrscht. Dies ist nur in der Praxis möglich, da wir einen GLR-Parser (IMHO) verwenden).

[BEARBEITEN November 2011: Wir haben unseren Parser um C++ 11 erweitert. GLR machte das viel einfacher. EDIT Aug 2014: Behandelt jetzt ganz C++ 17. Nichts ist kaputt oder schlimmer geworden, GLR ist immer noch das Miauen der Katze.].

[EDIT November 2011: We've extended our parser to handle all of C++11. GLR made that a lot easier to do. EDIT Aug 2014: Now handling all of C++17. Nothing broke or got worse, GLR is still the cat's meow.]

51
Ira Baxter

LALR-Parser führen ähnliche Zustände innerhalb einer LR-Grammatik zusammen, um Parser-Statustabellen zu erzeugen, die genau die gleiche Größe wie die äquivalente 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 kombinierten Zustände zu Parserkonflikten oder zu einem Parser, der die ursprüngliche LR-Grammatik nicht vollständig erkennt.

Übrigens, ich erwähne dazu ein paar Dinge in meinem MLR (k) -Parsing-Tabellen-Algorithmus hier .

Nachtrag

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

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

Der Nachteil ist, dass nicht alle LR-Grammatiken als LALR-Tabellen codiert werden können, da komplexere Grammatiken kompliziertere Lookaheads haben, 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 trägt, während dies beim LALR-Algorithmus nicht der Fall ist. Der LALR-Algorithmus kann also nicht feststellen, ob ein bestimmter zusammengeführter Zustand wirklich als zwei oder mehr separate Zustände belassen werden soll.

18
David R Tribble

Noch eine Antwort (YAA). 

Die Analysealgorithmen für SLR (1), LALR (1) und LR (1) sind identisch mit Ira Baxter.
Die Parser-Tabellen können jedoch aufgrund des Parser-Generierungsalgorithmus unterschiedlich sein. 

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

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 einem LR (1) -Statuscomputer nicht vorhanden wären.

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

Ein Minimal-LR-Parser-Generator berechnet eine LR (1) -Statusmaschine, führt jedoch kompatible Zustände während des Prozesses zusammen und berechnet dann die Vorausschau von der Minimal LR (1) -Statusmaschine. Diese Parser-Tabellen haben die gleiche Größe oder sind etwas größer als LALR-Parser-Tabellen, was die beste Lösung darstellt.

LRSTAR 9.1 kann minimale LR (1) - und LR (*) - Parser in C++ generieren. Siehe dieses Diagramm, das den Unterschied zwischen LR-Parsern zeigt. 

[Vollständige Offenlegung: LRSTAR ist mein Produkt]

12
Paul B Mann

Angenommen, ein Parser ohne Lookahead analysiert glücklich Strings für Ihre Grammatik.

Anhand Ihres gegebenen Beispiels stößt es auf einen String dc. Was macht es? Reduziert es auf S, weil dc eine gültige Zeichenfolge ist, die von dieser Grammatik erzeugt wird? OR Vielleicht haben wir versucht, bdc zu analysieren, weil selbst das eine akzeptable Zeichenfolge ist. 

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

Da ein SLR (1) -Parser über LR (0) zusätzlich die Möglichkeit hatte, einen Lookahead auszuführen, wissen wir, dass die Beträge des Lookaheads uns nicht sagen können, was in diesem Fall zu tun ist. Stattdessen müssen wir in unsere Vergangenheit zurückblicken. Damit kommt der kanonische LR-Parser zur Rettung. Es erinnert sich an den Kontext der Vergangenheit.

Die Art und Weise, wie er sich an diesen Kontext erinnert, ist, dass er sich selbst diszipliniert, dass er, wann immer er auf eine b stößt, auf einen Weg zum Lesen von bdc geht, als eine Möglichkeit. Wenn er also eine d sieht, weiß er, ob er bereits einen Pfad durchläuft .__ Ein CLR (1) -Parser kann also 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 kombinieren also die gleichen aussehenden Pfade, aber wie erwartet, kann dies zu Verwirrungsproblemen führen. Wir sind jedoch bereit, das Risiko auf Kosten der Verkleinerung einzugehen. 

Dies ist Ihr LALR (1) -Parser.


Nun wie es algorithmisch geht.

Wenn Sie die Konfigurationssätze für die obige Sprache zeichnen, wird in zwei Zuständen ein Konflikt zur Verringerung der Verschiebung angezeigt. Wenn Sie sie entfernen möchten, sollten Sie eine Spiegelreflexkamera (1) in Betracht ziehen, bei der Entscheidungen getroffen werden müssen, aber Sie würden feststellen, dass dies immer noch nicht möglich ist. Daher würden Sie die Konfigurationssets erneut zeichnen, diesmal jedoch mit der Einschränkung, dass bei jeder Berechnung des Abschlusses die hinzugefügten zusätzlichen Produktionen strenge Folgen haben müssen. Verweisen Sie auf jedes Lehrbuch, was diese folgen sollen.

5
Kang

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

Jede davon ist als Zustandsmaschine aufgebaut, wobei jeder Zustand einen Satz der Produktionsregeln der Grammatik (und der Position in jeder) darstellt, wenn die Eingabe analysiert wird.

Das Dragon Book Beispiel einer LALR (1) -Grammatik, die keine SLR ist, lautet wie folgt:

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

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

S → L•= R
R → L•

Der 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 hat und versucht zu reduzieren.

Hier kann der Parser entweder einen = verschieben oder R → L reduzieren.

Ein SLR-Parser (auch bekannt als LR (0)) -Parser würde feststellen, ob er reduziert werden könnte, indem er prüft, ob das nächste Eingabesymbol im follow set von R (dh der Menge aller Terminals in der folgenden Grammatik) enthalten ist R). Da sich = auch in diesem Set befindet, stößt der SLR-Parser auf einen Konflikt mit reduzierter Verschiebung.

Ein LALR (1) -Parser würde jedoch die Menge aller Terminals verwenden, die auf diese bestimmte Produktionvon R folgen können, was nur $ (dh Ende der Eingabe) ist. Also kein Konflikt.

Wie bereits in früheren Kommentaren erwähnt, haben LALR (1) -Parser dieselbe Anzahl von Zuständen wie SLR-Parser. Ein Lookahead-Ausbreitungsalgorithmus wird verwendet, um Lookaheads aus den entsprechenden LR (1) -Zuständen an SLR-Status-Produktionen anzuheften. Der resultierende LALR (1) -Parser kann reduzierende Konflikte einführen, die nicht im LR (1) -Parser vorhanden sind, er kann jedoch keine reduzierenden Konflikte einführen.

In Ihrem Beispiel verursacht der folgende LALR (1) -Zustand einen Konflikt zur Verringerung der Verschiebung in einer SLR-Implementierung:

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

Das Symbol hinter / ist das Folgeset für jede Produktion im LALR (1) -Parser. In der SLR enthält follow (A)a, das auch verschoben werden kann.

4
Klaus

Der grundlegende Unterschied zwischen den mit SLR und LR generierten Parser-Tabellen besteht darin, dass die Reduzierungsaktionen auf den für SLR-Tabellen festgelegten Folgestufen basieren. Dies kann zu restriktiv sein und letztendlich zu einem Konflikt mit reduzierter Verschiebung führen. 

Ein LR-Parser dagegen reduziert Entscheidungen nur auf der Menge von Terminals, die tatsächlich dem Nicht-Terminal folgen können, das reduziert wird. Diese Menge von Terminals ist oftmals eine geeignete Teilmenge der Follows-Gruppe eines solchen Nicht-Terminals und hat daher weniger Chancen, mit Schichtaktionen in Konflikt zu geraten.

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

Ein LALR-Parser beginnt mit der Idee, eine LR-Parsing-Tabelle zu erstellen, kombiniert jedoch die generierten Zustände auf eine Weise, die zu einer wesentlich geringeren Tabellengröße führt. Der Nachteil ist, dass für einige Grammatiken, die eine LR-Tabelle andernfalls vermieden hätte, eine geringe Konfliktwahrscheinlichkeit eingeführt würde. 

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

P.S. Für die Kürze bedeuten SLR, LALR und LR über SLR (1), LALR (1) und LR (1), so dass ein Lookahead-Wert impliziert wird.

4
tgoneil

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 das Doppelte der Zustände). Und das ist der Hauptgrund, warum LALR (1) - Grammatiken mehr Code zum Erkennen von Syntaxfehlern benötigen als LR (1) - Grammatiken .. Und was noch wichtiger ist, zu wissen, was diese beiden Grammatiken angeht, ist, dass wir in LR (1) -Gramatiken möglicherweise haben weniger Konflikte reduzieren/reduzieren. In LALR (1) besteht jedoch die Möglichkeit, Konflikte zu reduzieren.

0
Anil Kumar

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

enter image description here

0