6.8 Linker Rand, Blüten und die DK-Grammatik

In diesem Teilkapitel werden wir sehen, wie wir für eine gültige Wortform $γ$ den korrekten Linksreduktionsschritt

\begin{array}{r} γ = α β w \overset{}{↣} α X w \end{array}

finden. Als erstes müssen wir uns überlegen, wie die Front $front (γ) = α β$ überhaupt aussehen kann. Wenn wir uns den Ableitungsbaum von $γ$ ansehen, wird das einigermaßen offensichtlich sein.

Zur Erinnerung: Zu jeder Ableitung $S {\overset{}{⟹}}^{*} w \in Σ^{*}$ 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 {\overset{}{⟹}}^{*} w$ . Allerdings können wir für Zwischenformen $S {\overset{}{⟹}}^{*} γ {\overset{}{⟹}}^{*} w$ auch einen Ableitungsbaum zeichnen, und der unterscheidet sich stark, abhängig davon, ob $S {\overset{}{⟹}}^{*} γ$ eine Rechtsableitung, Linksableitung oder sonst was ist. Ich zeige Ihnen jetzt ein Beispiel für eine Grammatik und eine Handvoll Ableitungen samt Ableitungsbaum.

\begin{aligned} G & : \\ S & \to A B \\ A & \to x B S | B z \\ B & \to y A S | A z | x | y | z \end{aligned}

Es ist zu diesem Zeitpunkt irrelevant, ob $G$ eindeutig oder sogar $L R (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 \to x B S$ . Wir definieren nun eingeführten Begriffe formal:

Definition / Beobachtung 6.8.1 (Stamm, linker Rand, Blüte, Front, rechter Rest) Sei

S {\overset{}{⟹}}^{*} γ

eine Rechtsableitung,

γ

also eine gültige Wortform, und

T

der Ableitungsbaum von

γ

. Der 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 $α$ ; die Blüte ergibt $β$ . Die Blätter im rechten Rand sind ausschließlich mit Terminalen beschriftet und ergeben ein Wort $w \in Σ^{*}$ . Der ganze Baum stellt also eine Rechtsableitung

\begin{array}{r} S {\overset{R}{⟹}}^{*} α β w \end{array}

dar. Die Wortform

α β

, also linker Rand plus Blüte, nennen wir die Front von

T

und schreiben sie als

front (T)

. Wir sagen auch, dass

β

eine Blüte von $γ$ und

α β

die Front von

γ

ist, ohne über den Ableitungsbaum

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

γ = α β 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 \to β$ eine Produktion in der Grammatik und $α A w$ eine gültige Wortform; wir erhalten den Ableitungsbaum von $α A w$ , indem wir die Blüte von $T$ entfernen. Wir schließen, dass $\begin{array}{r} α β w \overset{}{↣} α A w \end{array}$ ein korrekter Linksreduktionsschritt ist.

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

Um für eine Wortform $γ$ den korrekten Reduktionsschritt zu finden, reicht es also aus, linken Rand und Blüte zu bestimmen, also $α$ und $β$ , so dass $γ = α β w$ und $α β w \overset{}{↣} α 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 $γ$ bilden, was selbst wieder eine Parsing-Aufgabe ist???

An dieser Stelle zeigt sich die Genialität des DK-Ansatzes: der Ableitungsbaum von $γ$ 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.

Definition 6.8.2 Für eine kontextfreie Grammatik

G

definieren wir die Sprache

Front (G) \subseteq (Σ \cup N)^{*}

\begin{array}{r} Front (G) := {front (T) | T ist der Ableitungsbaum einer Rechtsableitung S {\overset{R}{⟹}}^{*} γ} \end{array}

alternativ

\begin{array}{r} Front (G) := {α β | S \overset{R}{⟹^{*}} α X w \overset{R}{⟹} α β w} \end{array}

also die Menge aller Wortformen, die Front einer gültigen Wortform sind.

Lemma 6.8.3 Die Sprache $Front (G)$ ist regulär. Insbesondere gibt es eine erweitert reguläre Grammatik $\hat{G}$ für $Front (G)$ , so dass die Blüte genau die im letzen Ableitungsschritt erzeugten Terminalsymbole sind.

Hier ist etwas Mentalgymnastik vonnöten: aus Sicht der Sprache $Front (G)$ sind $Σ \cup N$ Terminalsymbole. Sie können ja schließlich in den Wörtern der Sprache auftauchen. Die Grammatik $\hat{G}$ hat also die Terminalsymbole $Σ \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 $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 $front (G)$ eh fehlt) und annotiere jeden Knoten auf dem Stamm mit der entsprechenden $\hat{G}$ -Produktion.

Definition 6.8.4 Sei

G = (Σ, N, S, P)

eine kontextfreie Grammatik. Die Front-Grammatik oder DK-Grammatik von

G

ist die erweitert reguläre Grammatik

\hat{G} = (Σ \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{array}{r} A \to w_{0} A_{1} w_{1} A_{2} w_{2} \dots w_{k - 1} A_{k} w_{k} \end{array}

mit

w_{i} \in Σ^{*}

die Produktionen

\begin{aligned} \hat{A} & \to w_{0} {\hat{A}}_{1} \\ \hat{A} & \to w_{0} A_{1} w_{1} {\hat{A}}_{2} \\ ⋮ \\ \hat{A} & \to w_{0} A_{1} w_{1} A_{2} w_{2} \dots A_{k - 1} w_{k - 1} {\hat{A}}_{k} \\ \hat{A} & \to w_{0} A_{1} w_{1} A_{2} w_{2} \dots w_{k - 1} A_{k} w_{k} \end{aligned}

besitzt.

Beobachtung 6.8.5

\hat{G}

erzeugt die Sprache

Front (G)

Beispiel 6.8.6 Für unsere Grammatik

G

oben ergeben sich folgende Produktionen

\hat{P}

\hat{G}

\begin{array}{r} \begin{array}{ll} Produktion in G & Produktion in \hat{G} \\ \hat{S} \to \hat{A} \\ S \to A B & \hat{S} \to A \hat{B} \\ \hat{S} \to A B \\ \hat{A} \to x \hat{B} \\ A \to x B S & \hat{A} \to x B \hat{S} \\ \hat{A} \to x B S \\ A \to B z & \hat{A} \to \hat{B} \\ \hat{A} \to B z \\ \hat{B} \to y \hat{A} \\ B \to y A S & \hat{B} \to y A \hat{S} \\ \hat{B} \to y A S \\ \hat{B} \to \hat{A} \\ B \to A z & \hat{B} \to A z \\ B \to x & \hat{B} \to x \\ B \to y & \hat{B} \to y \\ B \to z & \hat{B} \to z \end{array} \end{array}

Nochmals: Produktionen wie $\hat{B} \to y A \hat{S}$ sind erweitert regulär weil $y$ und $A$ aus Sicht von $\hat{G}$ beides Terminalsymbole sind. Wir können nun unseren $L R (0)$ -Parser beschreiben:

Algorithmus 6.8.7 - Der $L R (0)$ -Parser. Starte mit einem leerem Stack. Sei

γ

der Inhalt des Stacks zu einem Zeitpunkt.

Wenn $γ \in Front (G)$ , dann betrachte die letzte angewandte $\hat{G}$ -Produktion $\hat{X} \to β$ und schreibe $γ = α β$ . Wende die $G$ -Produktion $X \to β$ rückwärts an, reduziere also $\begin{array}{r} α β \overset{}{↣} α X \end{array}$ Konkret: lösche $β$ vom Stack und ersetze es durch $A$ .
Falls $γ \notin Front (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 6.8.8 Wenn der

L R (0)

-Parser akzeptiert, dann hat er eine Linksreduktion

w {\overset{}{↣}}^{*} S

und somit eine Rechtsableitung konstruiert; es gilt also

w \in L (G)

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

Beweis. Der erste Teil der Bedeutung ist einfach zu sehen. Jeder Reduktionsschritt ist ein Linksreduktionsschritt, und wenn man Ende $S$ steht, waren es auch alles korrekte Linksreduktionsschritte.

Der zweite Teil ist schwieriger. Wir nehmen also an, dass $G$ eine LR(0)-Grammatik ist. Da $G$ eindeutig ist, hat jede gültige Wortform $γ$ eine eindeutige Rechtsableitung und einen dazugehörigen Ableitungsbaum $T$ ; somit ist $front (γ) := front (T)$ eindeutig bestimmt. Beachten Sie, dass rechts von $front (γ)$ nur Terminalsymbole folgen. Betrachten wir einen Zeitpunkt während des Parsing-Prozesses. Sei $γ$ der Stackinhalt und $w$ der ungelesene Teil des Eingabewortes. Wir werden beweisen, dass zu jedem Zeitpunkt folgende Invariante gilt:

Behauptung. (i) $γ w$ ist eine gültige Wortform. (ii) $γ$ ist ein Präfix von $front (γ w)$ .

Beweis. Die Behauptung gilt offensichtlich am Anfang, da $γ = ϵ$ und $w \in L$ ist und somit $γ w = w$ eine gültige Wortform ist. Des weiteren ist der Stack leer, also $γ = ϵ$ , und daher sicherlich ein Präfix von $front (w)$ . 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 $γ \in Front (G)$ . Das heißt nach Definition von $Front (G)$ , dass es ein $w^{'} \in Σ^{*}$ gibt, so dass $γ w^{'}$ eine gültige Wortform ist und $γ = front (γ w^{'})$ . Also $\begin{array}{r} S {\overset{R}{⟹}}^{*} α A w^{'} {\overset{R}{⟹}}^{*} α β w^{'} \end{array}$ mit $γ = α β$ . Es sind $α$ und $β$ also linker Rand und Blüte von $γ w^{'}$ . Somit ist $\begin{array}{r} (1) & α β w^{'} \overset{}{↣} α^{'} A w^{'} \end{array}$ ein korrekter Linksreduktionsschritt. Die letzte $\hat{G}$ -Produktion in der Ableitung von $\hat{S} {\overset{}{⟹}}^{*} γ$ war somit $\hat{A} \to β$ ; somit ersetzt der Parser das $β$ auf dem Stack durch $A$ ; führt also die Linksreduktion $\begin{array}{r} (2) & α β w \overset{}{↣} α A w \end{array}$ an. Da ( $1$ ) korrekt ist und $α β w$ nach Invariante eine gültige Wortform ist, ist nach LR(0)-Bedingung auch ( $2$ ) ein korrekter Schritt; $α A w$ ist also auch eine gültige Wortform; 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$ ein Präfix von $front (α A w)$ sein.
Der Parser wendet Schritt 2 an, also $w = c w^{'}$ , er liest $c$ und legt es auf den Stack. Im nächsten Schritt ist der Stackinhalt $γ^{'} := γ c$ und das ungelesene Wort ist $w^{'}$ . Teil (i) der Behauptung gilt offensichtlich, da $γ^{'} w^{'} = γ w$ und somit immer noch eine gültige Wortform ist. Um zu sehen, dass Teil (ii) gilt, beachten Sie erstens, dass Teil (ii) vor dem Schritt galt, also $γ$ ein Präfix von $front (γ w)$ ist; zweitens, dass $γ \notin Front (G)$ ist (sonst hätte der Parser Schritt 1 angewandt); somit ist $γ$ ein echter Präfix von $front (γ w)$ und somit ist $γ c$ immer noch ein Präfix von $front (γ w)$ .

Wenn das Eingabewort gelesen ist, ist nun

w = ϵ

und Stackinhalt

γ

ist selbst eine gültige Wortform, die allerdings nicht weiter reduziert werden kann. Also muss

γ = S

gelten und der Parser akzeptiert.

◻