~2025-38216-33: Link hat sich geaendert

2025-12-03T15:37:13Z

Link hat sich geaendert

Neue Seite

Im [[Compilerbau]] ist ein '''LR-Parser''' ein [[Bottom-up-Parser]] für [[LR(k)-Grammatik|LR-Grammatiken]]. Bei diesen [[Kontextfreie Grammatik|kontextfreien Grammatiken]] wird die Eingabe von '''l'''inks nach rechts abgearbeitet, um die [[Rechtsreduktion|'''R'''echtsreduktion]] zum Startsymbol zu berechnen.

== Allgemeines ==
Ein LR-Parser heißt ''LR(k)-Parser'', wenn er während des Parsens ''k'' [[Token (Compilerbau)|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 '''l'''inks nach rechts mit '''R'''echtsreduktionen, '''''k''''' Symbole Lookahead.

LR-Parser per Hand zu schreiben birgt ein großes Fehlerrisiko, weswegen hier meistens [[Parsergenerator]]en verwendet werden.

== Aufbau und Arbeitsweise eines LR-Parsers ==
Ein LR-Parser enthält einen [[Kellerspeicher]] (Stack), eine Aktionstabelle und eine Goto-Tabelle.
Das oberste Element im Keller gibt immer 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 [[Backus-Naur-Form|BNF]] mit Startsymbol E:

<pre>
E ::= E "*" B | E "+" B | B .
B ::= "0" | "1" .
</pre>

Diese Grammatik lässt sich in folgende einzelne Reduktionsregeln umwandeln:
# E * B ← E
# E + B ← E
# B ← E
# 0 ← B
# 1 ← B

Markiert man das Ende der Eingabe mit einem $-Zeichen (Regel E $ ← S; S ist neues Startsymbol), so sehen die Aktions- und Goto-Tabelle für einen LR(0)-Parser dazu folgendermaßen aus:

{| style="margin-left:1em" border="1" cellspacing="0" cellpadding="2"
!
!colspan="5"| Aktion
!colspan="2"| 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|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$
{| style="margin-left:3em" border="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$
{| style="margin-left:3em" border="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 <math>1\leftarrow B</math>
: Ausgabe: <math>1+1\$ \Leftarrow_r B+1\$</math>
{| style="margin-left:3em" border="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 <math>B\leftarrow E</math>
: Ausgabe: <math>1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$</math>
{| style="margin-left:3em" border="1"
|Keller:||0||3
|-
|Eingabe:|| ||E||+||1||$
|}

5. Jetzt kommt ein Shift. Wir wechseln in den Zustand 6.
: Aktion: Lege + in den Keller.
: Ausgabe: <math>1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$</math>
{| style="margin-left:3em" border="1"
|Keller:||0||3||6
|-
|Eingabe:|| ||E||+||1||$
|}

6. Shift, neuer Zustand: 2
: Aktion: Lege 1 in den Keller.
: Ausgabe: <math>1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$</math>
{| style="margin-left:3em" border="1"
|Keller:||0||3||6||2
|-
|Eingabe:|| ||E||+||1||$
|}

7. Reduktion mit Regel 5, neuer Zustand ist 8
: Aktion: Reduziere <math>1 \leftarrow B</math>.
: Ausgabe: <math>1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$\Leftarrow_r E+B\$</math>
{| style="margin-left:3em" border="1"
|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 <math>E + B \leftarrow E</math>.
: Ausgabe: <math>1+1\$ \Leftarrow_r B+1\$ \Leftarrow_r E+1\$\Leftarrow_r E+B\$ \Leftarrow_r E\$</math>
{| style="margin-left:3em" border="1"
|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 dessen Zustände und Übergänge werden 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]]

== Weblink ==
* [http://amor.cms.hu-berlin.de/~kunert/papers/lr-analyse/ LR(k)-Analyse für Pragmatiker], ausführliche Beschreibung der LR-Analyse und der entsprechenden Unterformen (LR(0), SLR(1), LALR(1), LR(1)).

[[Kategorie:Compilerbau|LRParser]]

LR-Parser - Versionsgeschichte

~2025-38216-33: Link hat sich geaendert