LALR steht für Lookahead-LR. Ein LALR-Parser ist eine Bottom-up-Syntaxanalyse, die die Mächtigkeit eines kanonischen LR(1)-Parsers anstrebt, aber mit der deutlich kleineren Zustandsmenge eines SLR-Parsers auskommt. Damit ist LALR(1) die mit Abstand am häufigsten verwendete Parser-Technik in echten Compilern.
Die Idee hinter LALR
Ein kanonischer LR(1)-Parser speichert für jeden Zustand exakte Lookahead-Informationen. Das macht ihn sehr mächtig, erzeugt aber oft zehn- bis hundertmal mehr Zustände als der einfache LR(0)-Automat. Ein LALR-Parser geht einen Mittelweg: Er verwendet die kompakten LR(0)-Zustände und ergänzt sie um propagierte Lookahead-Mengen. Das Ergebnis sind Parsing-Tabellen von SLR-Größe mit einer Mächtigkeit, die für fast alle praktischen Grammatiken ausreicht.
Wie LALR konstruiert wird
- LR(0)-Automaten: Zuerst entsteht wie beim LR-Parser die Zustandsmenge aus den LR(0)-Items.
- Lookahead-Propagation: Für jede Reduktion wird berechnet, welche Terminale als nächstes Eingabezeichen erlaubt sind. Diese Mengen werden von Zustand zu Zustand weitergereicht, bis ein Fixpunkt erreicht ist.
- Tabellen: Wie beim LR-Parser entstehen ACTION- und GOTO-Tabellen für Shift-, Reduce- und Accept-Schritte.
Eine alternative Sichtweise: Man baut den kanonischen LR(1)-Automaten und verschmilzt alle Zustände mit identischem Kern (den LR(0)-Items). Durch diese Verschmelzung können allerdings reduce/reduce-Konflikte entstehen, die im unverschmolzenen LR(1)-Automaten nicht existierten — ein bekanntes LALR-Phänomen, das beim Grammatik-Entwurf beachtet werden muss.
LALR in der Praxis
Parser-Generatoren wie Yacc, GNU Bison, PLY (Python) oder CUP (Java) erzeugen standardmäßig LALR(1)-Parser. Die Grammatiken von C, C++ und Java sind in diesen Werkzeugen als LALR(1)-Grammatiken formuliert. Treten Shift/Reduce-Konflikte auf, löst Yacc sie nach einer festen Regel auf: Shift gewinnt gegen Reduce. Reduce/Reduce-Konflikte gelten dagegen als echter Konstruktionsfehler und müssen durch Umschreiben der Grammatik behoben werden.
Abgrenzung zu anderen Parsern
- LL-Parser arbeiten top-down und sind in der Grammatikklasse schwächer; LALR ist bottom-up und mächtiger.
- SLR-Parser nutzen nur die grobe FOLLOW-Menge als Lookahead — LALR verfeinert das und akzeptiert deutlich mehr Grammatiken.
- Der kanonische LR(1)-Parser akzeptiert die größte Klasse, ist aber praktisch oft zu groß; LALR ist der übliche Kompromiss in Werkzeugen.
- Rekursiver Abstieg ist der handgeschriebene Konkurrent — viele moderne Compiler verzichten dort ganz auf Generatoren.