LR-Parser
Ein LR-Parser ist ein Bottom-Up Parser für LR-Grammatiken. Bei diesen kontextfreien Grammatiken wird die Eingabe von links nach rechts abgearbeitet, um die Rechtsreduktion zum Startsymbol zu berechnen.
Allgemeines
Ein LR-Parser heißt LR(k)-Parser, wenn er während des Parsens k Token vorausschauen kann. k wird dabei als lookahead bezeichnet.
LR(k) ist eine Abkürzung für Parsen von links nach rechts mit Rechtsreduktionen, k Symbole Lookahead.
LR-Parser per Hand zu schreiben ist recht fehleranfällig, weswegen hier meistens Parser-Generatoren verwendet werden.
Aufbau und Arbeitsweise eines LR-Parsers
Ein LR-Parser besteht aus einem Kellerspeicher, einer Aktions-Tabelle und einer GoTo-Tabelle. Das oberste Element auf dem Stapel gibt den aktuellen Status des Parsers an. Bei Programmstart liegt nur der Startzustand auf dem Stapel. In der Aktionstabelle wird vermerkt, was bei jeder Kombination aus Zustand und Eingabezeichen zu tun ist. Mögliche Aktionen sind:
- Shift(n): Bewege den Zeiger im Eingabestrom einen Schritt weiter und lege den aktuellen Zustand auf den Stapel. Wechsle dann in den Zustand n.
- Reduce(k): Wende die Regel k an. D.h. nimm soviele Elemente vom Stapel, wie die Regel Elemente auf der rechten Seite hat. Schaue anschließend in der Goto-Tabelle nach, welches der nächste Zustand ist und lege ihn auf den Stapel.
- Accept: Akzeptiere die Eingabe. D.h. die Eingabe ist gültig und der Parser terminiert.
Beispiel eines Parse-Vorgangs
Wir betrachten folgende Grammatik in BNF:
- E := ( E "*" B ) | ( E "+" B ) | B .
- B := "0" | "1" .
Diese Grammatik lässt sich in folgende, einzelne Produktionsregeln umwandeln:
- E := E "*" B .
- E := E "+" B .
- E := B .
- B := "0" .
- B := "1" .
Die Aktions- und GoTo-Tabelle für einen LR(1)-Parser dazu sieht folgendermaßen aus:
| Aktion | GoTo | ||||||
|---|---|---|---|---|---|---|---|
| Zustand | * | + | 0 | 1 | $ | E | B |
| 0 | s1 | s2 | 3 | 4 | |||
| 1 | r4 | r4 | r4 | r4 | r4 | ||
| 2 | r5 | r5 | r5 | r5 | r5 | ||
| 3 | s5 | s6 | acc | ||||
| 4 | r3 | r3 | r3 | r3 | r3 | ||
| 5 | s1 | s2 | 7 | ||||
| 6 | s1 | s2 | 8 | ||||
| 7 | r1 | r1 | r1 | r1 | r1 | ||
| 8 | r2 | r2 | r2 | r2 | r2 | ||
Wie man diese Tabellen aus der Grammatik erstellt wird im nächsten Abschnitt beschrieben.
Als Eingabe sei die Zeichenkette "1+1" gegeben. Das Ende der Eingabe markieren wir mit einem $-Zeichen.
- Der Startzustand ist hier 0, also startet der Parser nur mit einer 0 auf dem Stapel, und der Lesezeiger steht auf dem ersten Zeichen der Eingabe:
- Stapel: 0
- Eingabe: 1+1$
- Wir schauen nun in der Aktionstabelle was beim Zustand 0 und der Eingabe "1" zu tun ist: s2, d.h. wir legen den Zustand 2 auf den Stapel und lesen das nächste Zeichen.
- Stapel: 0 2
- Eingabe: 1+1$
- Mit der Eingabe "+" sollen wir im Zustand 2 Regel 5 anwenden.
Die Regel 5 hat ein Element auf der rechten Seite. Daher nehmen wir ein Element vom Stapel und sehen in der Goto-Tabelle den nächsten Zustand nach. Im Zustand 0 (die 1 haben wir ja gerade weggenommen) wird nach Anwendung einer Regel, die auf der linken Seite ein B stehen hat in den Zustand 4 gewechselt.- Stapel: 0 4
- Eingabe: B+1$
- Jetzt kommt erneut ein Reduce. Diesmal mit Regel 3. Wir wechseln in den Zustand 3.
- Stapel: 0 3
- Eingabe: E+1$
- Jetzt kommt ein Shift. Wir wechseln in den Zustand 6.
- Stapel: 0 3 6
- Eingabe: E+1$
- Shift, neuer Zustand: 2
- Stapel: 0 3 6 2
- Eingabe: E+B$
- Reduce mit Regel 5, neuer Zustand ist 8
- Stapel: 0 3 6 8
- Eingabe: E$
- Reduce mit Regel 2. Wir nehmen daher drei Elemente vom Stapel. Dann liegt die 0 ganz oben, und wir wechseln in den Zustand 3, da die Regel 2 ein E auf der linken Seite hat.
- Stapel: 0 3
- Eingabe: accept
- Accept. Die Eingabe gehört zur Grammatik und wir sind fertig.