6.5 LR-Parser per Hand entwerfen

Betrachten wir die kontextfreie Grammatik $G$ für arithmetische Ausdrücke mit den Variablen $x, y, z$ und strenger Klammerung über dem Alphabet $Σ = {x, y, z, (,), +, *}$ :

\begin{aligned} S & \to x | y | z \\ S & \to (S + S) \\ S & \to (S * S) \end{aligned}

Sie kann also $(x + (y * z))$ ableiten aber eben nicht $(x + y + z)$ . Wie können wir nun einen Parser für $G$ schreiben? Also einen Algorithmus, der ein Wort $w \in Σ^{*}$ nimmt und einen Ableitungsbaum konstruiert (falls $w \in L (G)$ )? Wenn wir uns an das LL-Paradigma halten und eine Linksableitung bauen wollen, dann stoßen wir schon ganz am Anfang auf ein Problem: wenn zum Beispiel

\begin{array}{r} w = ((((\dots \end{array}

dann wissen wir nicht, ob wir als ersten Schritt $S \to (S + S)$ oder $S \to (S * S)$ tätigen sollen. Das geht auch nicht, wenn wir $k$ Zeichen vorauslesen dürfen, weil der $(((\dots$ -Präfix ja länger als $k$ sein kann. Nein, wir müssen anders vorgehen. Wir könnten beispielsweise die Grammatik ändern:

\begin{aligned} S & \to x | y | z \\ S & \to (S O S) \\ O & \to + | * \end{aligned}

Das geht aber nicht immer:

Beispiel 6.5.1 Betrachten wir die recht einfache Sprache

\begin{array}{r} L_{2} := {a^{m + k} b^{m} c | m \geq 1, k \geq 0}, \end{array}

also beliebig viele $a$ 's, gefolgt von gleich vielen oder weniger $b$ 's (aber mindestens einem), abgeschlossen mit einem $c$ . Eine Grammatik ist schnell geschrieben:

\begin{aligned} (1) & S & \to a S \\ (2) & S & \to X c \\ (3) & X & \to a X b \\ (4) & X & \to a b \end{aligned}

Wenn wir jetzt die ersten $k$ Zeichen lesen: $a a a a \dots$ , dann gibt es keinen Weg, zu entscheiden, ob danach gleich viele oder weniger $b$ 's folgen werden, ob wir also $S \to s S$ oder $S \to X c$ anwenden sollen. Das lässt sich auch nicht durch Umschreiben der Grammatik lösen. Wir müssen lesen, bis wir ein $b$ sehen.

Das LR-Paradigma

Wir brauchen einen Paradigmenwechsel. Das LL-Paradigma war ja, mit $S$ zu starten und, geleitet von den nächsten $k$ Zeichen, zu entscheiden, welche Ableitungsregel als nächstes anzuwenden ist. Hierbei haben wir immer versucht, für das am weitesten links stehende Nichtterminal eine Regel zu finden. Wir beschreiben nun ein ganz anderes Vorgehen: wir lesen das Eingabewort $v$ von links nach rechts, unterhalten also einen Stack, auf dem ein Präfix $γ$ von $v$ liegt, bis wir am rechten Ende die rechte Seite einer Produktionsregel erkennen - bis also $γ = α β$ und es eine Produktion $X \to β$ gibt. Dann ersetzen wir $α β$ durch $α X$ . Unser Stack enthält nun keine Präfix von $v$ mehr, sondern eine Wortform $γ$ . Zusammen mit dem ungelesenen Teil $w$ des Eingabewortes ergibt das eine Wortform $γ w$ . Solange es eine Rechtsableitung $S \overset{}{⟸} γ w \overset{}{⟸} v$ gibt, sind wir auf dem richtigen Weg. Am Besten betrachten wir ein Beispiel für $L_{2} = {a^{m + k} b^{m} c | m \geq 1, k \geq 0}$ . Die Farbe grau bedeutet hier, dass wir das Eingabezeichen noch nicht gelesen haben.

Betrachten wir noch ein Beispiel, nun für die etwas nützlichere Grammatik der streng geklammerten arithmetischen Ausdrücke.

Wenn wir uns nun die Ableitung ansehen, die wir gefunden haben:

\begin{array}{r} S \overset{}{⟹} (S+S) \overset{}{⟹} (S+(S*S)) \overset{}{⟹} (S+(S*z)) \overset{}{⟹} (S+(y*z)) \overset{}{⟹} (x+(y*z)) \end{array}

dann sehen wir, dass es sich um eine Rechtsableitung handelt. Daher der Name LR-Parsing: wir beginnen links (daher das L) und suchen eine Rechtsableitung (daher das R), allerdings in umgekehrter Reihenfolge. Statt von $S$ ausgehend $w$ abzuleiten, also $S {\overset{}{⟹}}^{*} w$ , versuchen wir $w$ zu $S$ zu reduzieren, also $w {\overset{}{⟸}}^{*} S$ . Allerdings ist das nicht immer so einfach: manchmal ist nicht auf den ersten Blick erkennbar, welche Produktionsregel wir (rückwärts) anwenden sollen. Hier ein etwas konstruiertes Beispiel:

\begin{aligned} S & \to X Y z \\ X & \to a X a | b X b | c \\ Y & \to Y a | Y b | a | b \end{aligned}

Die erzeugte Sprache ist

\begin{array}{r} L (G) = {v c v^{R} w z | v, w \in {a, b}^{*}} \end{array}

Betrachten wir das Eingabewort $a c a b a$ . Wir schreiben nun immer den bis jetzt gelesenen / geparsten Teil des Wortes, gefolgt von dem ungelesen Teil in grau und dahinter in Klammern , was wir als nächstes tun, also das nächste Zeichen lesen oder eine Regel anwenden.

\begin{aligned} (lesen) & a c a b a z \\ (lesen) & a c a b a z \\ (reduzieren per X \to c) & a c a b a z \\ (lesen) & a X a b a z \\ (reduzieren per X \to a X a) & a X a b a z \\ (lesen) & X b a z \\ (reduzieren per Y \to b) & X b b a z \\ (lesen) & X Y a z \\ (reduzieren per Y \to Y a) & X Y a z \\ (lesen) & X Y z \\ (reduzieren per S \to X Y z) & X Y z \\ (fertig) & S \end{aligned}

Es stellen sich einige Fragen: woher wissen wir zum Beispiel bei $X Y a z$ , dass wir per $Y \to Y a$ reduzieren müssen und nicht per $Y \to a$ ? Wir könnten ja auch auf $X Y a \overset{}{⟸} X Y Y$ reduzieren. Oder in Schritt 2, bei $a c a b a z$ . Da könnten wir ja gleich $a \overset{}{⟸} Y$ reduzieren.

Beobachtung. 6.5.2 Die Reduktion $X Y a \overset{}{⟸} X Y Y$ kann nicht richtig sein, weil $X Y Y$ nie als Präfix in einer Rechtsableitung vorkommen kann. Genauer gesagt: es gibt kein $w \in Σ^{*}$ , so dass

\begin{array}{r} S {\overset{}{⟹}}^{*} X Y Y w \overset{}{⟹} X Y a w \end{array}

eine Rechtsableitung ist.

Wenn wir Glück haben, gibt es immer höchstens eine Reduktionsregel $α β w \overset{}{⟸} α X w$ , so dass $S {\overset{}{⟹}}^{*} α X w \overset{}{⟹} α β w$ in einer Rechtsableitung vorkommen kann. Das hängt von der Grammatik ab. Aber selbst dann brauchen wir einen Algorithmus, der uns sagen kann, ob $X Y a \overset{}{⟸} X Y Y$ ein korrekter Reduktionsschritt ist. Dies scheint komplexer, als $w \overset{?}{\in} L$ zu entscheiden, ist aber einfacher!

Ein zweites Problem ist, dass wir eben manchmal kein Glück haben und es mehrere plausible Reduktionsschritte geben kann. Ein Beispiel wäre die obere Grammatik, leicht abgewandelt:

\begin{aligned} (beachten Sie: oben hatten wir S \to X Y z) & S & \to X Y \\ X & \to a X a | b X b | c \\ Y & \to Y a | Y b | a | b \end{aligned}

Wenn wir jetzt als einfaches Beispiel $c a b$ ableiten wollen:

\begin{array}{r} (lesen) & c a b \\ (reduzieren per X \to c) & c a b \\ (lesen) & X a b \\ (reduzieren per Y \to a) & X a a b \\ (reduzieren per Y \to a) & X Y b \end{array}

Jetzt liegt die Wortform $X Y$ auf unserem Stack und wir haben zwei Möglichkeiten: wir könnten reduzieren, also $X Y \overset{}{⟸} S$ , oder das nächste Zeichen lesen. Ersteres wäre inkorrekt:

\begin{array}{r} X Y b \overset{}{⟸} S b, \end{array}

wobei $S b$ eben keine Wortform ist, die in einer Rechtsableitung vorkommen könnte. Das wissen wir aber erst, wenn wir $b$ gelesen haben. Wäre das Eingabewort nämlich nur $c a$ , dann wäre $X Y \overset{}{⟸} S$ tatsächlich die korrekte Reduktion. In der ersten Grammatik hatten wir als "Work-around" ein $z$ am Ende angehängt, um das Wortende zu erkennen. Im Allgemeinen ist es aber leichter, dem Parser zu erlauben, das nächste Zeichen zu lesen.

All diese Gedanken theoretisch rigoros zu formulieren ist einigermaßen herausvordernd. Daher werden wir erst einmal für eine Grammatik arithmetischer Ausdrücke einen Parser in Java implementieren.