In der Informatik ist ein LALR parser (oder Blick vorn LR parser) ein Typ von LR parser gestützt auf einem Zustandsautomaten-Konzept. Die Datenstruktur, die durch einen LALR parser verwendet ist, ist ein pushdown Automat (PDA). Ein deterministischer PDA ist ein deterministischer begrenzter Automat (DFA) mit der Hinzufügung eines Stapels für ein Gedächtnis, anzeigend, welche Staaten der parser durchgeführt hat, um den aktuellen Staat zu erreichen. Wegen des Stapels kann ein PDA Grammatiken anerkennen, die mit einem DFA unmöglich sein würden; zum Beispiel kann ein PDA bestimmen, ob ein Ausdruck irgendwelche unvergleichlichen Parenthesen hat, wohingegen ein Automat ohne Stapel eine unendliche Zahl von Staaten wegen des unbegrenzten Nistens von Parenthesen verlangen würde.

LALR parsers werden durch einen parser Tisch in einem Format der Zustandsmaschine (FSM) gesteuert. Ein FSM ist für Menschen langweilig genug, um mit der Hand zu bauen, dass es günstiger ist, ein Softwarewerkzeug genannt einen LALR parser Generator zu verwenden, um einen parser Tisch automatisch von einer Grammatik in der Backus-Naur-Form zu erzeugen, die die Syntax der Computersprache definiert, die der parser bearbeiten wird. Der parser Tisch wird häufig im Quellcodeformat auf einer Computersprache (wie C ++ oder Java) erzeugt. Wenn der parser (mit dem parser Tisch) kompiliert und/oder durchgeführt wird, wird es Dateien anerkennen, die auf der durch die BNF Grammatik definierten Sprache geschrieben sind.

LALR parsers werden von LALR Grammatiken erzeugt, die dazu fähig sind, eine größere Klasse von Sprachen zu definieren, als

SLR Grammatiken, aber nicht eine so große Klasse wie LR Grammatiken. Echte Computersprachen können häufig als LALR (1) Grammatiken, und in Fällen ausgedrückt werden, wo ein LALR (1) Grammatik, gewöhnlich ein LALR (2) ungenügend ist, ist Grammatik entsprechend. Wenn der parser Generator nur LALR (1) Grammatiken behandelt, dann wird der LALR parser mit einem handschriftlichen Code verbinden müssen, wenn es auf den speziellen LALR (2) Situation auf der Eingangssprache stößt.

Geschichte

LR Syntaxanalyse wurde von Donald Knuth 1965 in einer Zeitung, "Auf der Übersetzung von Sprachen vom Linken bis Recht erfunden". LR parsers haben das Potenzial, die höchste Syntaxanalyse-Geschwindigkeit aller Syntaxanalyse-Algorithmen zur Verfügung zu stellen. Jedoch LR wurden parsers einmal unpraktisch betrachtet, weil Algorithmen, um LR parsers der lenksamen Größe zu erzeugen, bis zur Mitte der 1970er Jahre nicht bekannt waren.

LALR Syntaxanalyse wurde von Frank DeRemer 1969 in einer Zeitung, "Praktischer LR (k) Übersetzer erfunden". LALR parsers bieten dieselbe hohe Leistung von LR parsers an, und erzeugen viel kleinere Tische als der frühe LR parser Generationsalgorithmen des Endes der 1960er Jahre. Deshalb ist der LALR Algorithmus populär geworden, und LALR sind parsers diejenigen, die meistenteils durch Bearbeiter-Bearbeiter wie yacc und GNU-Bison erzeugt sind.

(Bearbeiter-Bearbeiter wie Menhir und HYacc, die wahren LR parser Tische mit dem Algorithmus des Pagers erzeugen, sind in den letzten Jahren erschienen, aber haben weit verbreitete Adoption nicht gesehen — ihr Hauptvorteil besteht darin, dass sie unecht nicht schaffen, reduzieren Konflikte für eindeutige deterministische Grammatiken/reduzieren.)

Das Erzeugen LALR Parsers

Ähnlich einem SLR parser Generator baut ein LALR parser Generator den LR (0) Zustandmaschine zuerst und schätzt dann die Lookahead-Sätze für alle Regeln in der Grammatik, für die Zweideutigkeit überprüfend. Ein SLR parser Generator schätzt die Lookahead-Sätze durch das Überprüfen der BNF Grammatik (diese werden genannt folgen Sätzen). Jedoch schätzt ein LALR parser Generator die Lookahead-Sätze durch das Überprüfen des LR (0) Zustandmaschine (diese werden LALR lookahead Sätze genannt, die genauer und weniger wahrscheinlich sind, einen Konflikt/Zweideutigkeit zu veranlassen, durch den parser Generator berichtet zu werden).

Wie SLR ist LALR eine Verbesserung zur Technik, um LR (0) Syntaxanalyse-Tische zu bauen. Während SLR-Gebrauch folgt, reduzieren Sätze, um zu bauen, Handlungen, LALR verwendet Lookahead-Sätze, die spezifischer sind, weil sie mehr vom Syntaxanalyse-Zusammenhang in Betracht ziehen. Folgen Sie Sätze werden mit einem Symbol vereinigt, während Lookahead-Sätze zu einem LR (0) Artikel und ein Parser-Staat spezifisch sind.

Spezifisch der folgen Satz für einen gegebenen LR (0) enthält der Artikel in einem gegebenen Parser-Staat alle Symbole, denen durch die Grammatik erlaubt wird, danach 's Nichtterminal der linken Seite zu erscheinen. Im Gegensatz enthält der Lookahead-Satz für den Artikel im Staat nur jene Symbole, denen durch die Grammatik erlaubt wird zu erscheinen, nachdem 's rechte Seite grammatisch analysiert worden ist, vom Staat anfangend. folgen Sie ist effektiv die Vereinigung der Lookahead-Sätze für den ganzen LR (0) Sachen mit derselben linken Seite wie, unabhängig von Parser-Staaten oder rechten Seiten, deshalb die ganze Zusammenhang-Information verlierend. Weil der Lookahead-Satz zu einem besonderen Syntaxanalyse-Zusammenhang spezifisch ist, kann es auswählender sein, deshalb feinere Unterscheidungen erlaubend, als der folgen Satz.

Leider ist die Computerwissenschaft LALR lookahead Sätze viel mehr kompliziert als SLR. Frank DeRemer und Tom Pennello haben eine Zeitung darüber geschrieben, das in SIGPLAN-Benachrichtigungen 1979 und in TOPLAS 1982 veröffentlicht ist, genannt "Effiziente Berechnung Von LALR (1) Sätze des Blicks vorn".

Vorteile

1. Ein LALR parser kann von einer LALR Grammatik automatisch erzeugt werden.
2. Eine LALR Grammatik kann verwendet werden, um viele Computersprachen zu definieren.
3. Ein LALR parser ist klein.
4. Ein LALR parser ist schnell (wenn der Syntaxanalyse-Algorithmus ein Matrixparser-Tabellenformat verwendet).
5. Ein LALR parser ist in der Geschwindigkeit geradlinig (d. h. die Geschwindigkeit basiert auf der Größe der Eingangstextdatei nur und nicht gestützt auf der Größe der Sprache, die wird anerkennt).
6. Die LALR Grammatik stellt wertvolle Dokumentation der Sprache zur Verfügung, die wird anerkennt.
7. Fehlerwiederherstellung kann bereits zum parser eingebaut sein.
8. Verallgemeinerte Fehlermeldungen können bereits in den parser eingebaut werden.
9. Aufbau des abstrakten Syntax-Baums kann bereits in den parser eingebaut werden.
10. Die Anerkennung von mit dem Zusammenhang empfindlichen Sprachkonstruktionen kann bereits in den parser eingebaut werden.

Nachteile

1. Softwareingenieure sind erforderlich, einen LALR parser Generator zu verwenden, der kann oder nicht benutzerfreundlich sein kann und eine Lernzeit verlangen kann.
2. Das Einführen bedeutungsvoller Fehlermeldungen im parser kann sehr schwierig oder unmöglich sein.
3. Das Verstehen des Syntaxanalyse-Algorithmus ist häufig ziemlich schwierig.
4. Wenn ein Fehler vorkommt, kann es schwierig sein zu bestimmen, ob es in der Grammatik oder dem Parser-Code ist.
5. Wenn es einen Fehler im parser Generator gibt, kann das sehr schwierig sein zu befestigen.

Siehe auch

• LR parser
• Parser-Generator
• LALR parser Generator
• Vergleich von parser Generatoren
• Lookahead in der Syntaxanalyse
• LL parser