5.5 LR-Grammatiken

Motivation und Intuition

Die LL-Parser, die wir im letzten Teilkapitel 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. Wäre es nicht besser, der Maxime zu folgen:

Maxime: Wende eine Regel $A \rightarrow \beta$ nur dann an, wenn Du im Eingabewort ein vollständiges Teilwort erkannt hast, das aus $\beta$ ableitbar ist.

Ich will diese Maxime an einem Beispiel demonstrieren. Betrachten wir die Grammatik $G$

\begin{align*} S & \step{1} aS \\ S & \step{2} X \\ X & \step{3} a X b \\ X & \step{4} ab \ . \end{align*}

Die von der Grammatik erzeugte Sprache ist \begin{align*} L(G) := \{a^{k+m} b^m \ | \ k \geq 0, m \geq 1\} \ , \end{align*} also: mindestens ein $b$ und mindestens so viele $a$s wie $b$s. Die Sprache ist nicht LL$(k)$: \begin{align*} S \Step{1} & aS \Step{1}^* a^k S \Step{2} a^k X \Step{4} a^k ab \\ S \Step{2} & X \Step{3}^* a^k X b^k \Step{4} a^k ab b^k \ . \end{align*} Die Ableitungen unterscheiden sich bereits in der ersten angewandten Produktion; trotzdem stimmen die Endergebnisse in den ersten $k$ (ja sogar $k+1$) Zeichen überein. Ich will nun aber zeigen, wie man eine Ableitung findet, wenn man die obige Maxime befolgt. Hierfür arbeiten wir uns von hinte nach vorne durch: statt mit $S$ anzufangen und zu $w$ hinzuarbeiten, fangen wir mit $w$ an und versuchen, und zu $S$ hin zurückzuarbeiten. In der folgenden Animation ist der Teil des Wortes, den unser Parser gelesen hat, schwarz markiert; der noch nicht gelesene Teil ist grau.

Wir erhalten eine Rechtsableitung, allerdings in verkehrter Reihenfolge, vom Zielwort hin zum Startsymbol. Daher schreiben wir in der obigen Animation auch $\Leftarrow$ statt $\Rightarrow$ geschrieben. Wenn Sie die Animation in verkehrter Reihenfolge anschauen (also immer auf

klicken), dann sehen Sie die Rechtsableitung $S \Step{}^* aaaabbb$ in der "üblichen" Reihenfolge.

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.

Vorsicht. Verfallen Sie nicht in verfrühte Euphorie. Das Prinzip der Linksreduktion ist immer noch nichtdeterministisch. Die folgende Abbildung illustriert, dass manchmal mehrere Reduktionen anwendbar sind:

Uns als Betrachter ist klar, dass nur die obere Alternative zum Erfolg führt; wie das der Parser aber im Allgemeinen entscheiden soll, ist uns zu diesem Zeitpunkt noch nicht klar und wird uns für den Rest dieses Kapitels 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{}^* \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.

Beobachtung: Das impliziert unmittelbar, dass die Wortform $\alpha \beta w $ auch gültig ist.

Überlegen wir nun, welche Situationen schlecht wären für unser Vorhaben, einen Parser ohne Sackgassen zu implementieren.

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 \Step{} ^* \gamma' \Step{} \gamma \Step{}^* w \in \Sigma^* \\ S \Step{} ^* \gamma'' \Step{} \gamma \Step{}^* 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 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 der Schritt \begin{align*} \alpha \beta w' \rstep{} \alpha X w' \end{align*} ist nicht korrekt, obwohl $\alpha\beta w'$ eine gültige Wortform ist. Dieser Fall ist schlecht, weil der Parser zum Zeitpunkt $\alpha \beta \textcolor{darkgray}{w}$, wenn er also $\alpha\beta$ gelesen hat, aber noch nicht $w$, sich nicht sicher sein kann, dass der Reduktionsschritt korrekt ist. Korrektheit hängt davon ab, was weiter rechts davon kommt.

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, $aX$ aber nicht. Die Entscheidung für eine Reduktionsregel kann also nicht ohne Wissen über das, was dahinter kommt, getroffen werden.

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 $\alpha \beta w'$ selbst überhaupt gültig 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.

Ü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 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.

Ü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.

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 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.

Gültige Wortformen und deren Ableitungsbäume

Zu jeder Ableitung $S \Step{}^* w \in \Sigma^*$ können wir eindeutig einen Ableitungsbaum zeichnen. Wenn die Grammatik eindeutig ist, so hängt auch der Baum nur vom Wort $w \in L(G)$ ab und nicht von der Ableitung $S \Step{}^* w$. Allerdings können wir für Zwischenformen $S \Step{}^* \gamma \Step{}^* w$ auch einen Ableitungsbaum zeichnen, und der unterscheidet sich stark, abhängig davon, ob $S \Step{}^* \gamma$ eine Rechtsableitung, Linksableitung oder sonst was ist. Ich zeige Ihnen jetzt ein Beispiel für eine Grammatik und eine Handvoll Ableitungen samt Ableitungsbaum. \begin{align*} G & : \\ S & \rightarrow AB \\ A & \rightarrow xBS \ | \ Bz \\ B & \rightarrow yAS \ | \ Az \ | \ x \ | \ y \ | \ z \end{align*} Es ist zu diesem Zeitpunkt irrelevant, ob $G$ eindeutig oder sogar $LR(0)$ ist. Ich interessiere mich gerade nur für Ableitungsbäume von Wortformen.

Fällt Ihnen etwas auf? Schauen Sie sich bitte noch ein weiteres Beispiel an für den Ableitungsbaum einer in einer gültigen Wortform, also von einer, die in einer Rechtsableitung vorkommen kann:

Warten Sie! Scrollen Sie erst weiter, wenn Sie den Baum oben lang genug angeschaut haben! Versuchen Sie selbst, die spezielle Form dieses Baumes möglichst formal zu beschreiben!

Auflösung. Hier sehen Sie noch einmal den gleichen Baum, nun aber gewisse Teile verschieden umrandet / eingefärbt.

Sie sehen: links vom Stamm gibt es nur Blätter. Rechts vom Stamm ist jedes Blatt ein Terminalsymbol. Wir erkennen auch, was der letzte Ableitungsschritt war, der zu diesem Baum geführt hat: die Blüte ist hinzugekommen, in diesem Fall also $A \rightarrow x B S$. Wir definieren nun eingeführten Begriffe formal:

Definition / Beobachtung (Stamm, linker Rand, Blüte, rechter Rest) Sei $S \Step{}^* \gamma$ eine Rechtsableitung, $\gamma$ also eine gültige Wortform, und $\mathcal{T}$ der Ableitungsbaum von $\gamma$. Stamm ist der Pfad von der Wurzel zu jenem inneren Knoten $u$, der von allen inneren Knoten, deren Kinder allesamt Blätter sind, am weistesten links steht. Die Kinder von $u$, per Definition alles Blätter, sind die Blüte. Die Menge der Knoten, die einen Stammknoten als rechtes Geschwister haben, heißt der linke Rand. Jeder Knoten $v$ im linken Rand muss ein Blatt sein, ansonsten stünde er ja weiter links als $u$; die Menge der rechten Geschwisterkinder von Stammknoten sowie deren Nachkommen heißt der rechte Rand. Im rechten Rest ist jedes Blatt ein Terminalsymbol, ansonsten wäre es keine Rechtsableitung.

Die Beschriftung der Knoten im linken Rand ergibt eine Wortform $\alpha$; die Blüte ergibt $\beta$. Die Blätter im rechten Rand sind ausschließlich mit Terminalen beschriftet und ergeben ein Wort $w \in \Sigma^*$. Der ganze Baum stellt also eine Rechtsableitung

\begin{align*} S \Step{}^* \alpha \beta w \end{align*} dar. Wir sagen auch, dass $\beta$ eine Blüte von $\gamma$ ist, ohne über den Ableitungsbaum $\mathcal{T}$ selbst zu reden. Hierbei ist zu beachten, dass in einer mehrdeutigen Grammatik eine gültige Wortform mehrere Ableitungsbäume und somit mehrere Blüten haben kann, die Unterteilung $\gamma = \alpha\beta w$ also nicht eindeutig ist. Für eindeutige Grammatiken ist die Unterteilung aber eindeutig.

Sei weiterhin $A$ die Beschriftung des Elternknoten der Blüte (notwenigerweise ein Nichtterminal; Terminale haben keine Kinder). Dann ist $A \rightarrow \beta$ eine Produktion in der Grammatik und $\alpha A w$ eine gültige Wortform; wir erhalten den Ableitungsbaum von $\alpha A w$, indem wir die Blüte von $\mathcal{T}$ entfernen. Wir schließen, dass \begin{align*} \alpha \beta w \rstep{} \alpha A w \end{align*} ein korrekter Linksreduktionsschritt ist.

Wir können also, ausgehend von der Wortform $\gamma$, eine Linksreduktion $\gamma \rstep{}^* S$ finden, indem wir den Ableitungsbaum von $\gamma$ zeichnen und immer wieder die Blüte abschneiden:

Um für eine Wortform $\gamma$ den korrekten Reduktionsschritt zu finden, reicht es also aus, linken Rand und Blüte zu bestimmen, also $\alpha$ und $\beta$, so dass $\gamma = \alpha\beta w$ und $\alpha \beta w \rstep \alpha A w$ korrekt ist ($A$ steht hier für das Nichtterminal, mit dem der Elternknoten der Blüte beschriftet ist). Linken Rand und Blüte zu finden scheint keine leichte Aufgabe zu sein: schließlich müssen wir dafür doch den Ableitungsbaum von $\gamma$ bilden, was selbst wieder eine Parsing-Aufgabe ist???

An dieser Stelle zeigt sich die Genialität des DK-Ansatzes: der Ableitungsbaum von $\gamma$ kann beliebig verschachtelt sein, aber Stamm, linker Rand und Blüte haben zusammen eine einfache, beinahe linear anmutende Struktur. Schematisch:

Die Aussage "Stamm, linker Rand und Blüte haben eine einfache Struktur" können wir formalisieren:

Lemma Für eine kontextfreie Grammatik $G$ definieren wir die Sprache $\textnormal{SLRB}(G) \subseteq (\Sigma \cup N)^*$: \begin{align*} \textnormal{SLRB}(G) := \{\alpha \beta \in (\Sigma\cup N)^*\ | \ \exists \ w \in \Sigma^*: \textnormal{ $\alpha\beta w$ ist gültig und $\beta$ eine Blüte von $\gamma$}\} \ , \end{align*} also die Menge aller Wortformen, die als Beschriftung des linken Randes und der Blüte in einem Ableitungsbaum einer gültigen Wortform vorkommen können.

Die Sprache SLRB ist regulär.

Insbesondere gibt es eine reguläre Grammatik $\hat{G}$ für SLRB, so dass die Blüte genau die im letzen Ableitungsschritt erzeugten Terminalsymbole sind.

Hier ist etwas Mentalgymnastik vonnöten: aus Sicht der Sprache SLRB sind $\Sigma \cup N$ Terminalsymbole. Sie können ja schließlich in den Wörtern der Sprache auftauchen. Die Grammatik $\hat{G}$ hat also die Terminalsymbole $\Sigma \cup N$. Darüberhinaus hat sie die Nichtterminale $\hat{N} := \{ \hat{X} \ | \ X \in N\}$, also für jedes Nichtterminal $X$ von $G$ ein Meta-Nichtterminal $\hat{X}$. Das $X \in N$ entspricht dem $\boxed{X}$ in den obigen Bäumen, wo also $N$ als Blatt vorkommt; das $\hat{X} \in \hat{N}$ entspricht dem , also wo $W$ als innerer Knoten vorkommt. Bevor ich $\hat{G}$ formal definiere, zeige ich den obigen Ableitungsbaum (ohne rechten Rand, weil der ja bei SLRB eh fehlt) und annotiere jeden Knoten auf dem Stamm mit der entsprechenden $\hat{G}$-Produktion.

Definition Sei $G = (\Sigma, N, S, P)$ eine kontextfreie Grammatik. Die SLRB-Grammatik oder DK-Grammatik von $G$ ist die reguläre Grammatik $\hat{G} = (\Sigma \cup N, \hat{N}, \hat{S}, \hat{P}$ mit $\hat{N} := \{\hat{X} \ | \ X \in N\}$, wobei $\hat{P}$ für jede $G$-Produktion \begin{align*} A \rightarrow w_0 A_1 w_1 A_2 w_2 \dots w_{k-1} A_k w_k \end{align*} mit $w_i \in \Sigma^*$ die Produktionen \begin{align*} \hat{A} & \rightarrow w_0 \hat{A}_1 \\ \hat{A} & \rightarrow w_0 A_1 w_1 \hat{A}_2 \\ & \vdots \\ \hat{A} & \rightarrow w_0 A_1 w_1 A_2 w_2 \dots A_{k-1} w_{k-1} \hat{A}_k \\ \hat{A} & \rightarrow w_0 A_1 w_1 A_2 w_2 \dots w_{k-1} A_k w_k \end{align*} besitzt.

Strenggenommen ist $G$ eine erweitert reguläre Grammatik, weil manche Regeln mehrere Terminale hintereinander haben.

Beobachtung $\hat{G}$ erzeugt die Sprache $\textnormal{SLRB}(G)$.

Beispiel Für unsere Grammatik $G$ oben ergeben sich folgende Produktionen $\hat{P}$ in $\hat{G}$: \begin{align*} \begin{array}{l|l} \textnormal{Produktion in $G$} & \textnormal{Produktion in $\hat{G}$} \\ & {\dk{S}} \rightarrow \dk{A}\\ S \rightarrow AB & {\dk{S}} \rightarrow \dkt{A} \dk{B}\\ & {\dk{S}} \rightarrow \dkt{AB} \\ \hline % & {\dk{A}} \rightarrow \dkt{x} \dk{B}\\ A \rightarrow xBS & {\dk{A}} \rightarrow \dkt{x B} \dk{S}\\ & {\dk{A}} \rightarrow \dkt{x B S}\\ \hline % A \rightarrow Bz & {\dk{A}} \rightarrow \dk{B}\\ & {\dk{A}} \rightarrow \dkt{Bz} \\ \hline % & \dk{B} \rightarrow \dkt{y} \dk{A}\\ B \rightarrow y A S & \dk{B} \rightarrow \dkt{y A} \dk{S} \\ & \dk{B} \rightarrow \dkt{y A S} \\ \hline % & \dk{B} \rightarrow \dk{A} \\ B \rightarrow Az & \dk{B} \rightarrow \dkt{Az} \\ \hline % B \rightarrow x & \dk{B} \rightarrow \dkt{x} \\ B \rightarrow y & \dk{B} \rightarrow \dkt{y} \\ B \rightarrow z & \dk{B} \rightarrow \dkt{z} \\ \end{array} \end{align*}

Nochmals: Produktionen wie $\dk{B} \rightarrow \dkt{y A} \dk{S}$ sind regulär (strenggenommen: erweitert regulär), weil $\dkt{yA}$ aus Sicht von $\hat{G}$ beides Terminalsymbole sind. Wir können nun unseren $LR(0)$-Parser beschreiben:

Algorithmus - Der $LR(0)$-Parser. Starte mit einem leerem Stack. Sei $\gamma$ der Inhalt des Stacks zu einem Zeitpunkt.

Wenn $\gamma \in \textnormal{SLRB}(G)$, dann betrachte die letzte angewandte $\hat{G}$-Produktion $\hat{A} \rightarrow \beta$ und schreibe $\gamma = \alpha\beta$. Wende die $G$-Produktion $A \rightarrow \beta$ rückwärts an, reduziere also \begin{align*} \alpha \beta \rstep{} \alpha A \end{align*} Konkret: lösche $\beta$ vom Stack und ersetze es durch $A$.
Falls $\gamma \not \in \textnormal{SLRB}(G)$, lies das nächste Eingabezeichen und lege es auf den Stack.

Der Parser endet, wenn weder Schritt 1 noch Schritt 2 möglich sind; wenn zu diesem Zeitpunkt nur noch $S$ auf dem Stack liegt, akzeptiert er, andernfalls lehnt er das Eingabewort ab.

Theorem Wenn der $LR(0)$-Parser akzeptiert, dann hat er eine Linksreduktion $w \rstep{}^* S$ und somit eine Rechtsableitung konstruiert; es gilt also $w \in L(G)$.

Wenn umgekehrt $w \in L(G)$ gilt und $G$ die $LR(0)$-Bedingung erfüllt, dann findet der Parser die Rechtsableitung $S \Step{}^* w$,

Beweis. Da $G$ eindeutig ist, hat jede gültige Wortform $\gamma$ eine eindeutige Rechtsableitung und einen dazugehörigen Ableitungsbaum $\mathcal{T}$ mit einem linken Rand $\alpha$, einer Blüte $\beta$ und einem rechten Rest. Wir nennen die Wortform $\alpha\beta$ den aktiven Teil von $\gamma$. Beachten Sie, dass rechts vom aktiven Teil nur Terminalsymbole folgen. Da $\mathcal{T}$ eindeutig ist, nennen wir $\alpha$ auch den linken Rand von $\gamma$ anstatt den linken Rand von $\mathcal{T}$. Betrachten wir einen Zeitpunkt während des Parsing-Prozesses. Sei $\gamma$ der Stackinhalt und $w$ der ungelesene Teil des Eingabewortes. Wir werden beweisen, dass zu jedem Zeitpunkt folgende Invariante gilt:

Behauptung. (i) $\gamma w$ ist eine gültige Wortform. (ii) $\gamma$ ist ein Präfix des aktiven Teils $\gamma w$.

Beweis. Die Behauptung gilt offensichtlich am Anfang, da $w\in L$ und somit eine gültige Wortform ist. Des weiteren ist der Stack leer, also $\gamma = \epsilon$, und daher sicherlich ein Präfix von $\alpha\beta$. Wir zeigen nun, dass, wenn die Invariante in Schritt $t$ gilt, sie auch im nächsten Schritt $t+1$ gilt. Es gibt nun zwei Möglichkeiten.

Der Parser wendet Schritt 1 an, also $\gamma \in \textnormal{SLRB}(G)$. Das heißt nach Definition von SLRB, dass es ein $w' \in \Sigma^*$ gibt, so dass $\gamma w'$ eine gültige Wortform ist und $\gamma$ der aktive Teil, also $\gamma = \alpha' \beta'$, und $\beta'$ ist die (eindeutige) Blüte von $\gamma w'$ . Sei $\hat{A} \rightarrow \beta'$ die letzte angewandte $\hat{G}$-Produktion. Dann ist \begin{align*} \alpha' \beta' w' \rstep{} \alpha' A w' \end{align*} ein korrekter Reduktionsschritt. Da $G$ nach Annahme eine $LR(0)$-Grammatik ist, ist nach Definition auch \begin{align*} \alpha' \beta' w \rstep{} \alpha' A w \end{align*} korrekt. Der Stackinhalt im nächsten Schritt ist somit $\alpha' A$; der ungelesene Teil ist nach wie vor $w$, und somit gilt Teil (i) der Invariante. Um zu sehen, dass (ii) gilt, beachten Sie, dass nun auf dem Stack oben ein Nichtterminal liegt: $A$; da rechts vom aktiven Teil nur Terminale stehen, muss $A$ im aktiven Teil von $\alpha' A w$ liegen; somit ist Worten: der Stackinhalt $\alpha' A$ ein Präfix des aktiven Teils.
Der Parser wendet Schritt 2 an, also $w = cw'$, er liest $c$ und legt es auf den Stack. Im nächsten Schritt ist der Stackinhalt $\gamma' := \gamma c$ und das ungelesene Wort ist $w'$. Teil (i) der Behauptung gilt offensichtlich, da $\gamma' w' = \gamma w$ und somit immer noch eine gültige Wortform ist. Um zu sehen, dass Teil (ii) gilt, beachten Sie, dass $\gamma \not \in \textnormal{SLRB}(G)$ ist. Das heißt also, dass der aktive Teil von $\gamma w$ länger ist als $\gamma$ (kürzer kann er laut Invariante nicht sein). Daher ist nun auch $\gamma c$ ein Präfix des aktiven Teils.

Wenn das Eingabewort gelesen ist, ist nun $w = \epsilon$ und Stackinhalt $\gamma$ ist selbst eine gültige Wortform, die allerdings nicht weiter reduziert werden kann. Also muss $\gamma = S$ gelten und der Parser akzeptiert.

$\square$