LR-Parser

Im Compilerbau ist ein LR-Parser 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 Tokens für eine natürliche Zahl k 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 birgt ein großes Fehlerrisiko, weswegen hier meistens Parsergeneratoren 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 im Keller gibt den aktuellen Zustand des Parsers an. Bei Programmstart liegt nur der Startzustand im Keller. In der Aktionstabelle wird vermerkt, was bei jeder Kombination aus Zustand und Eingabezeichen zu tun ist. Mögliche Aktionen sind:

• Shift(z): Bewege den Zeiger im Eingabestrom einen Schritt weiter und lege den aktuellen Zustand in den Keller. Wechsle dann in den Zustand z.
• Reduce(n): Wende die Regel n an. D. h. nimm so viele Elemente aus dem Keller, wie die Regel Symbole auf der rechten Seite hat. Schaue anschließend in der Goto-Tabelle nach, welches der nächste Zustand ist, und lege diesen in den Keller.
• Accept: Akzeptiere die Eingabe. D. h. die Eingabe ist gültig und der Parser terminiert.
• Error: Ist eine Zustands-Eingabe-Konstellation in der Tabelle nicht beschrieben, dann wird die Eingabe abgelehnt und der Parser terminiert.

Beispiel eines Parsers

Wir betrachten folgende Grammatik in BNF:

E ::= E "*" B | E "+" B | B .
B ::= "0" | "1" .

Diese Grammatik lässt sich in folgende einzelne Reduktionsregeln umwandeln:

1. E * B ← E
2. E + B ← E
3. B ← E
4. 0 ← B
5. 1 ← B

Markiert man das Ende der Eingabe mit einem $-Zeichen (Regel E $ ← S), so sehen die Aktions- und GoTo-Tabelle für einen LR(0)-Parser dazu 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 Abschnitt Erstellen der Aktions- und Goto-Tabelle beschrieben.

Beispiel eines Parse-Vorgangs

Als Eingabe sei die Zeichenkette "1+1" gegeben.

1. Der Startzustand ist hier 0, also startet der Parser nur mit einer 0 im Keller, und der Lesezeiger steht auf dem ersten Zeichen der Eingabe.

Ausgabe: 1+1$

Keller:	0
Eingabe:		1	+	1	$

2. 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 in den Keller und lesen das nächste Zeichen.

Aktion: Lege 2 in den Keller

Ausgabe: 1+1$

Keller:	0	2
Eingabe:		1	+	1	$

3. 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 aus dem Keller und sehen in der Goto-Tabelle den nächsten Zustand nach. Im Zustand 0 (die 2 haben wir ja gerade weggenommen) wird nach Anwendung einer Regel, auf deren linker Seite ein B steht, in den Zustand 4 gewechselt.

Aktion: Reduziere $1\leftarrow B$

Ausgabe: $1+1\$ \Leftarrow_r B+1\$$

Keller:	0	4
Eingabe:		B	+	1	$

4. Jetzt kommt erneut eine Reduktion. Diesmal mit Regel 3. Wir wechseln in den Zustand 3.

Aktion: Reduziere $B\leftarrow E$

Ausgabe: $1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$$

Keller:	0	3
Eingabe:		E	+	1	$

5. Jetzt kommt ein Shift. Wir wechseln in den Zustand 6.

Aktion: Lege + in den Keller.

Ausgabe: $1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$$

Keller:	0	3	6
Eingabe:		E	+	1	$

6. Shift, neuer Zustand: 2

Aktion: Lege 1 in den Keller.

Ausgabe: $1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$$

Keller:	0	3	6	2
Eingabe:		E	+	1	$

7. Reduktion mit Regel 5, neuer Zustand ist 8

Aktion: Reduziere $1 \leftarrow B$.

Ausgabe: $1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$\Leftarrow_r E+B\$$

Keller:	0	3	6	8
Eingabe:		E	+	B	$

8. Reduktion mit Regel 2. Wir nehmen daher drei Elemente aus dem Keller. Dann liegt die 0 ganz oben, und wir wechseln in den Zustand 3, da die Regel 2 ein E auf der linken Seite hat.

Aktion: Reduziere $E + B \leftarrow E$.

Ausgabe: $1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$\Leftarrow_r E+B\$ \Leftarrow_r E\$$

Keller:	0	3
Eingabe:		E	$

9. Accept. Die Eingabe gehört zur Grammatik und wir sind fertig.

Erstellen der Aktions- und Goto-Tabelle

Um die Tabelle zu erhalten, wird aus der Grammatik ein deterministischer endlicher Automat (DEA) erstellt und aus diesem die Zustände und die Übergänge in die Tabelle geschrieben. Je nachdem, welche Art von LR-Parser konstruiert wird, gibt es leichte Änderungen des Konstruktionsablaufs. Ein solcher Ablauf wird zum Beispiel für SLR-Parser beschrieben.

Siehe auch

• LL-Parser
• LALR-Parser

Weblinks

• LR(k)-Analyse für Pragmatiker, ausführliche Beschreibung der LR-Analyse und der entsprechenden Unterformen (LR(0), SLR(1), LALR(1), LR(1)).