LR-Parser sind die klassischen Bottom-up-Parser: Sie lesen den Quelltext ebenfalls von links nach rechts, bauen den Syntaxbaum aber von den Blättern zur Wurzel auf. LR steht für „Left-to-right, Rightmost derivation in reverse“ — die Rechtsableitung der Grammatik wird in umgekehrter Reihenfolge nachvollzogen. LR-Parser erkennen deutlich mehr Grammatiken als LL-Parser und sind die Arbeitspferde generatorbasierter Parser wie Yacc und Bison.
Shift-Reduce-Prinzip
Ein LR-Parser arbeitet mit einem Keller und einer Aktions-/Goto-Tabelle:
- Shift: Das nächste Eingabezeichen wird auf den Keller geschoben, zusammen mit dem neuen Zustand des Parsers.
- Reduce: Stehen auf dem Kellertop die Symbole der rechten Seite einer Produktion, werden sie durch das linke Nichtterminal ersetzt — eine Reduktion.
- Accept: Ist die gesamte Eingabe reduziert und der Keller enthält nur noch das Startsymbol, ist der Parse erfolgreich.
Die Tabelle entsteht aus LR(0)-Items: Regeln mit einem Marker, der die aktuelle Parse-Position angibt (A → α · β). Mengen solcher Items bilden die Zustände eines deterministischen Automaten; Übergänge entstehen über Grammatiksymbole (Goto) und Eingabezeichen (Action).
Die Varianten SLR, LALR und LR(1)
Je nach Lookahead-Information unterscheidet man mehrere Stufen:
- LR(0): Kein Lookahead, nur Grundlage für die anderen Varianten; erkennt nur wenige Grammatiken konfliktfrei.
- SLR(1): Einfacher Lookahead über FOLLOW-Mengen, kompakt, aber immer noch konfliktanfällig.
- LALR(1): Lookahead wird zustandsweise zusammengefasst — gleiche Mächtigkeit wie LR(1) für die meisten praktischen Grammatiken bei deutlich kleineren Tabellen. Yacc, GNU Bison und viele andere Generator-Werkzeuge erzeugen LALR-Parser.
- LR(1) (kanonisch): Die stärkste Stufe mit vollem Lookahead, dafür sehr viele Zustände. Wird selten direkt eingesetzt, dient aber als Referenz.
Vor- und Nachteile
LR-Parser akzeptieren fast alle nicht-mehrdeutigen Grammatiken praktischer Programmiersprachen — auch solche mit Rechtsrekursion oder komplexen Konstrukten, an denen LL-Parser scheitern. Dafür sind die erzeugten Tabellen groß und kaum von Hand lesbar, und gute Fehlermeldungen sind schwerer zu produzieren. Wer einen Parser von Hand schreibt, nutzt deshalb meist den rekursiven Abstieg; wer eine mächtige Grammatik schnell und korrekt parsen will, greift zu einem LR-Generator.
Der LR-Parser ist ein Teil des Frontends eines Compilers: Nach der lexikalischen Analyse liefert er den Syntaxbaum, den die semantische Analyse prüft. Danach folgen Zwischendarstellung und Codegenerierung.