5.5 LR-Grammatiken

Motivation und Intuition

Die LL-Parser, die wir in Kapitel 5.4 gesehen haben, versuchen, eine Linksableitung $S \Step{}^* w$ Schritt für Schritt zu konstruieren. Eine Hauptschwäche ist, dass Sie von einer Wortform \begin{align*} w A \alpha \end{align*} die nächste Ableitungsregel $A \rightarrow \beta$ bestimmen müssen, ohne das "Endergebnis" von $\beta$ überhaupt vollständig gelesen zu haben. Sie müssen also erkennen, dass der rote / mit "?" markierte Pfeil in der Ableitung \begin{align*} S \Step{}^* w A \alpha \textcolor{red}{\Step{?}} w \beta \alpha \Step{}^* w x \alpha \Step{}^* w x y \end{align*} die richtige Entscheidung ist, obwohl sie von dem aus $\beta$ abgeleiteten Wort $x$ nur die ersten $k$ Buchstaben sehen. Dem entgegen haben wir in den letzten zwei Teilkapiteln LR-Parser gesehen. Diese versuchen, von $w$ ausgehend eine Rechtsableitung $S \Step{}^* w$ zu finden, allerdings in zeitlich umgekehrter Reihenfolge, also

\begin{align*} w \Pets{} \alpha_1 \Pets{} \alpha_2 \Pets{} \dots \Pets{} \alpha_{t-1} \Pets{} S \end{align*}

Notation

Da aus der Sicht unseres neuen Parsers die Rückwärtsanwendung einer Produktion $X \rightarrow \beta$, also der Schritt $\alpha X \gamma \Leftarrow \alpha \beta \gamma$ einen Fortschritt darstellt und zeitlich auch nach vorne geht, verwende ich ab jetzt ein neues Pfeilsymbol, das von links nach rechts geht und daher dem in Europa üblichen Gefühlt, dass die Zeit von links nach rechts verläuft, mehr entgegen kommt: $\alpha \beta \gamma \rstep{} \alpha X \gamma $.

Definition (Reduktion und Linksreduktion) Seien $\alpha, \beta, \gamma \in (\Sigma \cup N)^*$ Wortformen und $X \rightarrow \beta$ eine Produktion. Dann schreiben wir \begin{align*} \alpha \beta \gamma \rstep{} \alpha X \gamma \ , \end{align*} und sagen $\alpha \beta \gamma$ reduziert zu $\alpha X \gamma$. Man nennt einen solchen Schritt auch einen Reduktionsschritt.

Wir nennen den Schritt einen Linksreduktionsschritt, wenn rechts von $\beta$ nur Terminale stehen. Wenn also $\gamma = w \in \Sigma^*$ und somit \begin{align*} \alpha \beta w \rstep{} \alpha X w \ . \end{align*}

Eine Folge von Linksreduktionsschritten nennen wir eine Linksreduktion. Links, weil wir uns von links nach rechts in den terminalen Teil hineinarbeiten. Wir werden im folgenden nur Linksreduktionsschritte betrachten und sagen daher manchmal auch einfach nur Reduktionsschritt.

Beobachtung: Wenn wir einen Linksreduktionsschritt $\alpha \beta w \rstep{} \alpha X w$ betrachten, also \begin{align*} \alpha X w \Step{} \alpha \beta w \ , \end{align*} so sehen wir, dass das am weitesten rechts stehende Nichtterminal ersetzt worden ist; Linksreduktionen entsprechen also einer Rechtsableitung.

In den vorherigen Kapiteln, insbesondere beim Implementieren eines Parsers, haben wir gesehen, dass nicht jeder Linksreduktionsschritt automatisch auch korrekt ist. Ein einfaches Beispiel war die "Zahlengrammatik"

\begin{align*} N & \rightarrow D \\ N & \rightarrow ND \\ D & \rightarrow 0 \ | \ 1 \ | \ 2\ | \ 3\ | \ 4\ | \ 5\ | \ 6\ | \ 7\ | \ 8\ | \ 9 \end{align*}

So ist folgende Linksreduktion korrekt:

\begin{align*} 14 \rstep{} D4\rstep{} N4 \rstep{} ND \rstep{} N \end{align*}

weil sie einer gültigen Rechtsableitung $N \Step{R}^* 14$ entspricht ($N$ ist das Startsymbol). Folgende Reduktionen sind allerdings inkorrekt:

\begin{align*} \textcolor{red}{14 \rstep{} D4 \rstep{} DD} \end{align*}

da zwar $DD \Step{R} D4$, allerdings es keine Rechtsableitung $N \Step{R}^* DD$ gibt. Auch

\begin{align*} \textcolor{red}{14 \rstep{} D4 \rstep{} N4 \rstep{} ND \rstep{} NN} \end{align*}

ist inkorrekt. In unserer Java-Implementierung haben wir dieses Problem händisch gelöst, indem wir der Regel $ND \rstep{} N$ den Vorzug vor $D \rstep{} N$ gegebene haben. Im allgemeinen müssen wir definieren, was ein korrekter Linksreduktionsschritt ist. Und dann überlegen, wie wir herausfinden, ob ein Linksreduktionsschritt korrekt ist. Diese Fragen werden uns für den Rest dieses und des nächsten Teilkapitels beschäftigen.

Definition (Gültige Wortform, korrekter Reduktionsschritt) Eine Wortform $\gamma \in (\Sigma \cup N)^*$ heißt gültig, wenn es eine Rechtsableitung \begin{align*} S \Step{R}^* \gamma \end{align*} gibt. Ein Linksreduktionsschritt \begin{align*} \alpha \beta w \rstep{} \alpha X w \end{align*} heißt korrekt, wenn $\alpha X w$ gültig ist. In diesem Fall ist natürlich $\alpha \beta w$ selbst gültig.

Den Präfix $\alpha\beta$ nennen wir eine Front der gültigen Wortform $\alpha \beta w$. Wenn die Grammatik eindeutig ist, dann hat jede gültige Wortform $\gamma$ genau eine Front, die wir mit $\front(\gamma)$ bezeichnen.

Wenn wir uns erinnern, wie wir in den letzten zwei Teilkapiteln informell LR-Parser entworfen und implementiert haben, dann sehen wir, dass in einem Linksreduktionsschritt $\alpha \beta w \rstep{} \alpha X w$ die Front $\alpha \beta$ der Stackinhalt ist und $w$ der bis jetzt ungelesene Teil des Eingabewortes. Wir wünschen wir uns folgendes:

Wunsch. Ob $\alpha \beta w \rstep{} \alpha X w$ gültig ist oder nicht, wollen wir allein auf Grund der Front $\alpha \beta$ entscheiden können, das heißt, ohne $w$ betrachten zu müssen.

Wir haben allerdings bereits gesehen, dass das nicht immer möglich ist. Bei der Implementierung von ArithmeticGrammar.java zum Beispiel haben wir manchmal das erste Zeichen von $w$ betrachten müssen. Allerdings behalten wir erst einmal obigen Wunsch als Idealziel. Um ihn zu formalisieren, fragen wir uns, wann es denn nicht möglich ist, ohne Betrachten von $w$ zu eintscheiden, ob $\alpha \beta w \rstep{} \alpha X w$ gültig ist.

Schlechter Fall 1: Es gibt für eine Wortform $\gamma$ zwei korrekte Linksreduktionsschritte: $\gamma \rstep{} \gamma'$ und $\gamma \rstep{} \gamma''$. In diesem Falle gäbe es zwei verschiedene Rechtsableitungen \begin{align*} S \Steps{R} \gamma' \Step{R} \gamma \Steps{R} w \in \Sigma^* \\ S \Steps{R} \gamma'' \Step{R} \gamma \Steps{R} w \in \Sigma^* \\ \end{align*}

(wir nehmen an, dass man aus jedem Nichtterminal mindestens ein Wort $u \in \Sigma^*$ ableiten kann; andernfalls kann man solche nutzlosen Nichtterminale eliminieren). Das Wort $w$ hat also zwei verschiedene Ableitungsbäume. Die Grammatik ist somit mehrdeutig. Mit uneindeutigen Grammatiken beschäftigen wir uns zunächst gar nicht; sie sind von einem praktischen Standpunkt aus auch unattraktiv: wenn z.B. eine Programmiersprache eine mehrdeutige Grammatik hätte, dann wäre ja für gewisse Programme nicht eindeutig festzustellen, was damit gemeint ist. Wir nehmen also an, dass die Grammatik $G$ eindeutig ist und somit dieser Fall nicht eintreten kann.

Schlechter Fall 2: Der Linksreduktionsschritt \begin{align*} \alpha \beta w \rstep{} \alpha X w \end{align*} ist korrekt, aber für ein anderes $w' \in \Sigma^*$ ist \begin{align*} \alpha \beta w' \rstep{} \alpha X w' \end{align*}

nicht korrekt, obwohl $\alpha\beta w'$ eine gültige Wortform ist. Dieser Fall ist schlecht, weil der Parser nur $\alpha \beta$ gelesen hat und somit nicht weiß, ob es sich bei der gesamten Wortform um $\alpha \beta w$ oder um $\alpha \beta w'$ handelt. Da beide gültig sind, können ja auch beide in einer Linksreduktion auftreten. Korrektheit hängt also davon ab, was weiter rechtskommt.

Beispiel Erinnern Sie sich: unsere obige Grammatik \begin{align*} S & \step{1} aS \\ S & \step{2} X \\ X & \step{3} a X b \\ X & \step{4} ab \ . \end{align*} ist eindeutig (das ist leicht zu sehen), allerdings tritt Schlechte Fall 2 ein: der Reduktionsschritt \begin{align*} aaX \rstep{} aaS \end{align*} ist korrekt (hier also $w = \epsilon)$, aber leider ist \begin{align*} aaXb \rstep{} aaSb \end{align*} nicht korrekt (hier $w' = b)$, da $aaXb$ gültig ist, $aaSb$ aber nicht. Die Entscheidung für eine Reduktionsregel kann also nicht ohne Wissen über das, was dahinter kommt, getroffen werden.

Wir definieren nun eine Klasse von Grammatiken, bei denen diese schlechten Fälle nicht auftreten.

Definition ($LR(0)$-Grammatiken) Eine kontextfreie Grammatik heißt $LR(0)$-Grammatik, wenn keiner der obigen schlechten Fälle eintritt. Formal, wenn (1) die Grammatik eindeutig ist und (2) wenn ein korrekter Linksreduktionsschritt \begin{align*} \alpha \beta w \rstep{} \alpha X w \end{align*} bedeutet, dass auch alle anderen Linksreduktionsschritte \begin{align*} \alpha \beta w' \rstep{} \alpha X w' \end{align*} korrekt sind, sofern $w' \in \Sigma^*$ ist und $\alpha \beta w'$ selbst eine gültige Wortform ist.

In Worten/Graustufen: wenn wir \begin{align*} \alpha \beta \textcolor{gray}{w} \rstep{} \alpha X \textcolor{gray}{w} \end{align*} guten Gewissens anwenden dürfen, ohne auch nur ein Zeichen von $w$ gelesen zu haben, sofern wir sicher sind, dass es irgendein $w$ gibt, das $\alpha \beta w$ zu einer gültigen Wortform macht.

Lemma (LR(0), äquivalente Formulierung). Eine Grammatik $G$ ist LR(0) genau dann, wenn für alle korrekten Linksreduktionsschritte $\alpha \beta w \rstep{} \alpha Xw$ und $\alpha' \beta' w' \rstep{} \alpha' X'w'$ gilt:

Falls $\alpha \beta = \alpha' \beta'$ dann auch $\beta = \beta'$ und $X= X'$; in Worten: wenn die Fronten identisch sind, dann auch die Reduktionsschritte.
Wenn $\alpha' \beta' = \alpha \beta \varphi$ und $|\varphi| \geq 1$, dann $\varphi \not \in \Sigma^*$; in Worten: wenn $\front(\gamma)$ ein echter Präfix von $\front(\gamma')$ ist, dann muss in dem überstehenden Teil von $\front(\gamma')$ mindestens ein Nichtterminal vorkommen.

Beweis. Der Beweis ist leider etwas mechanisch und repetitiv. Aber vielleicht ist es eine gute Übung, ihn genau durchzugehen, um die Definitionenen Linksreduktion, gültige Wortform etc. zu verinnerlichen. Ich bin auch immer noch auf der Suche nach einem knapperen, klareren Beweis, der nicht so viele Fallunterscheidungen enthält.

Wenn-Dann-Richtung. Wenn $G$ eine LR(0)-Grammatik ist, dann gelten die Schlussfolgerungen des Lemmas.

Beweis. Um Punkt 1 zu zeigen, nehmen wir an, dass $\alpha \beta = \alpha' \beta'$ gilt. Da $\alpha \beta w \rstep{} \alpha X w$ korrekt ist, $\alpha' \beta' w'$ eine gültige Wortform ist und $G$ eine LR(0)-Grammatik ist, so ist auch

\begin{align*} \alpha' \beta' w' = \alpha \beta w' \rstep{} \alpha X w' \end{align*}

ein korrekter Linksreduktionsschritt. Also sind $\alpha' \beta' w' \rstep{} \alpha X w'$ und $\alpha' \beta' w' \rstep{} \alpha' X' w'$ beides korrekte Linksreduktionsschritte. Da $G$ eindeutig ist, kann es nur eine Rechtsableitung geben, d.h. $\alpha X w' = \alpha' X' w'$, was $X = X'$ und somit $\beta = \beta'$ impliziert.

Um Punkt 2 zu zeigen, nehmen wir an, dass $\alpha' \beta' = \alpha \beta \varphi$ gilt. Falls - entgegen der Schlussfolgerung - nun $\varphi \in \Sigma^*$ gälte, wäre

\begin{align*} \alpha' \beta' w' = \alpha \beta \varphi w' \rstep{} \alpha X \varphi w' \end{align*}

ein korrekter Linksreduktionsschritt; nach Voraussetzung ist auch $\alpha' \beta' w' \rstep{} \alpha' X' w'$ korrekt. Es gäbe also zwei korrekte Linksreduktionsschritte und $G$ wäre nicht eindeutig. Wir folgern, dass $\varphi^* \not \in \Sigma^*$. Beachten Sie, dass es, wenn $\varphi$ Nichtterminale enthält, keinen Widerspruch gibt: dann ist nämlich $\alpha \beta \varphi w' \rstep{} \alpha X \varphi w'$ gar kein Linksreduktionsschritt, geschweige denn ein korrekter. $\square$

Nur-dann-Richtung. Wenn die Grammatik $G$ die Schlussfolgerungen des Lemmas erfüllt und müssen zeigen, dass sie auch LG(0).

Beweis. Als erstes zeigen wir, dass $G$ eindeutig ist; dass es also für jede gültige Wortform genau einen korrekten Linksreduktionsschritt gibt. Dafür nehmen wir dann, dass es von $\gamma$ aus die Linksreduktionsschritte

\begin{align*} \gamma = \alpha \beta w & \rstep{} \alpha X w \textnormal{ und} \\ \gamma = \alpha' \beta' w' & \rstep{} \alpha' X' w' \textnormal{ und} \\ \end{align*}

gibt und müssen zeigen, dass es sich in der Tat um denselben Schritt handelt. Ohne Beschränkung der Allgemeinheit ist $|\alpha\beta| \leq |\alpha' \beta'|$ und wir schreiben $\alpha' \beta' = \alpha \beta \varphi$. Da $\varphi$ ein Präfix von $w$ ist und $w \in \Sigma^*$, so gilt auch $\varphi \in \Sigma^*$. Nach Punkt 2 der Schlussfolgerung muss also $\varphi = \epsilon$ gelten. Es ist also $\alpha' \beta' = \alpha \beta$. Nach Punkt 1 der Schlussfolgerung gelten nun also auch $\alpha = \alpha'$, $\beta = \beta'$ und $X = X'$ und somit auch $w = w'$. Es handelt sich um ein und den selben Linksreduktionsschritt. Die Gramatik ist eindeutig.

Um den zweiten Punkt der LR(0)-Eigenschaft zu zeigen, nehmen wir an, dass

\begin{align*} \alpha \beta w \rstep{} \alpha X w \end{align*}

ein korrekter Linksreduktionsschritt ist und $\gamma' := \alpha \beta w''$ eine gültige Wortform ist mit $w'' \in \Sigma^*$. Wir müssen zeigen, dass $ \alpha X w''$ auch gültig ist. Da $G$ eindeutig ist, gibt es einen eindeutigen korrekten Linksreduktionsschritt

\begin{align*} \gamma' = \alpha' \beta' w' \rstep{} \alpha' X' w' \end{align*}

Da $\alpha \beta$ und $\alpha' \beta'$ beides Präfixe von $\gamma'$ sind, gibt es drei Fälle: (1) $\alpha\beta = \alpha' \beta'$; (2) $\alpha' \beta' = \alpha \beta \varphi$ mit $\varphi \ne \epsilon$; (3) $\alpha \beta = \alpha' \beta' \varphi$ mit $\varphi \ne \epsilon$.

(1) Wenn nun $\alpha \beta = \alpha' \beta'$ gilt, dann sind nach Punkt 1 der Schlussfolgerung $\alpha' = \alpha$ und $\beta' = \beta$ und $X = X'$; also ist $\gamma = \alpha' \beta' w' = \alpha \beta w'$ und auch $\gamma = \alpha \beta w''$ und somit $w'' = w'$. Somit ist $\alpha' X' w' = \alpha X w''$ und letztere ist eine gültige Wortform.

(2) Wir haben zwei korrekte Linksreduktionsschritte $\alpha \beta w \rstep{} \alpha X w$ und $\alpha' \beta' w' \rstep{} alpha' X' w'$. Nach Punkt 2 der Schlussfolgerung des Lemmas $\varphi$ mindestens ein Nichtterminal enthalten. Das kann aber nicht sein, da $\varphi$ ein Präfix von $w'$ ist. (3) kann aus dem gleichen Grund nicht gelten. $\square$

Wir haben nun beide Richtungen gezeigt und somit das Lemma bewiesen. $\square$

Übungsaufgabe Zeigen Sie, dass die folgende Grammatik $LR(0)$ ist: \begin{align*} S & \rightarrow aS \\ S & \rightarrow Bc \\ B & \rightarrow aBb \\ B & \rightarrow ab \end{align*} Als ersten Schritt sollten Sie sich überlegen, wie gültige Wortformen überhaupt aussehen können.

Übungsaufgabe Wir ändern die Grammatik etwas ab: \begin{align*} S & \rightarrow aS \\ S & \rightarrow B \\ B & \rightarrow aBb \\ B & \rightarrow ab \end{align*} Die erzeugte Sprache ist $\{ a^* a^m b^m \ | \ m \geq 1\}$. Zeigen Sie, dass die Grammatik nicht $LR(0)$ ist.

Übungsaufgabe Zeigen Sie, dass die folgende Grammatik $LR(0)$ ist: \begin{align*} S & \rightarrow aS \\ S & \rightarrow BC \\ B & \rightarrow aBb \\ B & \rightarrow ab \\ C & \rightarrow cC \\ C & \rightarrow cT \\ T & \rightarrow abC \\ T & \rightarrow ab \end{align*} Als ersten Schritt sollten Sie sich überlegen, wie gültige Wortformen überhaupt aussehen können.

Algorithmische Fragen

Es stellen sich unmittelbar zwei zentrale Fragen:

Wie können wir verifizieren, ob eine gegebene Grammatik die $LR(0)$-Bedingung erfüllt?
Falls sie es tut, wie können wir für eine gegebene gültige Wortform $\gamma$ den korrekten Reduktionsschritt \begin{align*} \gamma = \alpha \beta w \rstep{} \alpha X w \end{align*} finden? Insbesondere die Zerlegung in $\gamma = \alpha \beta w$?

Beide Aufgaben können mit Hilfe eines endlichen Automaten, des DK-Automaten erledigt werden (DK steht als Abkürzung für Donald Knuth, der als erstes diese Idee hatte).

Hinweis. Was nun folgt, ist mathematisch recht herausfordernd. Lesen Sie daher gerne auch das Kapitel 2.4 (Deterministic context free languages) im Lehrbuch Introduction to the Theory of Computing von Michael Sipser. Meine Darstellung des doch recht schwierigen Materials fußt auf diesem Kapitel, weicht aber doch stark genug von Sipser ab, so dass es womöglich hilfreich ist, beides zu lesen: dieses Vorlesungsskript und das Kapitel in Sipers Buch.