5.4 LL($k$)-Grammatiken

DefinitionGrenzform Sei $G = (\Sigma, N, S, P)$ eine kontextfreie Grammatik. Eine Wortform $A \alpha$ - also eine Wortform, die mit einem Nichtterminal beginnt - heißt Grenzform, wenn es ein $w \in \Sigma^*$ gibt, so dass es eine Linksableitung \begin{align*} S \Step{}^* w A \alpha \end{align*} gibt. In anderen Worten: eine Grenzform ist das, was bei einem Kellerautomaten auf dem Stack liegt, wenn ein Nichtterminal ganz oben liegt.

Grenzformen sind also diejenigen Wortformen, bei denen der Kellerautomat eine Entscheidung treffen muss, weil er eventuell mehrere Produktionen $A \rightarrow \beta$ zur Auswahl hat. In diesem Teilkapitel wollen wir herausarbeiten, unter welchen Umständen wir die richtige Auswahl treffen können, auch wenn wir nur wenige weitere Zeichen unseres Inputwortes lesen dürfen.

Definition Für ein Wort $w \in \Sigma^*$ und eine natürliche Zahl $k \in \N$ sei $\first_k(w)$ wie folgt definiert: \begin{align*} \first_k(w) := \begin{cases} w & \textnormal{ wenn $|w| \lt k$} \\ u & \textnormal{ wenn $w = uv$ und $|u| = k$} \end{cases} \end{align*} In Worten: $\first_{k}(w)$ besteht aus den ersten $k$ Zeichen von $w$ (oder aus ganz $w$, falls es weniger als $k$ lang ist).

Definition LL($k$)-Grammatiken Eine kontextfreie Grammatik $G = (\Sigma, N, S, P)$ ist eine LL($k$)-Grammatik, wenn für jede Grenzform $A \alpha$ und für jedes Paar \begin{align*} A & \step{1} \beta \\ A & \step{2} \gamma \end{align*} verschiedener Produktionen (also $\beta \ne \gamma$) folgendes gilt: wenn \begin{align*} A\alpha & \Step{1} \beta \alpha \Step{}^* x \\ A\alpha & \Step{2} \gamma \alpha \Step{}^* y \\ \end{align*} dann müssen sich $x$ und $y$ in den ersten $k$ Zeichen unterscheiden, also \begin{align*} \first_k(x) \ne \first_k(y) \ . \end{align*}

Intuitiv gesprochen: wenn wir bereits eine ersten Teil $w$ unseres Zielwortes abgeleitet haben, dann können wir die nächste anzuwendende Produktion eindeutig bestimmen, indem wir die nächsten $k$ Zeichen des Zielwortes lesen.

Übungsaufgabe Negieren Sie die Definition, d.h., schreiben Sie eine Aussage der Form Wenn $G$ nicht LL($k$) ist, dann gibt es...

Beispiel Die Klammern-Grammatik \begin{align*} S & \step{1} \epsilon \\ S & \step{2} (S)S \end{align*} ist LL(1).

Beweis. Folgen wir der Definition von LL(1): für jedes Paar verschiedener Regeln muss etwas gelten. Wir haben hier keine Auswahl, denn es gibt ja nur ein Paar. Also müssen wir zeigen, dass, falls \begin{align*} S \Step{}^* wS\alpha & \Step{1} w \alpha \Step{}^* w x \\ S \Step{}^* wS\alpha & \Step{2} w \texttt{(}S\texttt{)}S \alpha \Step{}^* w y \\ \end{align*} gilt, dann auch $\first_1(x) \ne \first_2(y)$ gilt. Offensichtlich ist $\first_2(y) = $ "$\texttt{(}$". Was kann $\first_k(x)$ sein?

Behauptung. Wenn $S \rightarrow \delta \in (\Sigma \cup N)^*$, dann steht jedes $S$ in $\delta$ entweder am Ende von $\delta$ oder unmittelbar vor einem "$\texttt{)}$".

Das folgt per Induktion über die Länge der Ableitung. Wenn es also für $\delta$ gilt und wir die Produktion $S \rightarrow (S)S$ auf $\delta$ anwenden, dann gilt es für jedes "alte" $S$ und auch für die beiden neu erzeugten; wenn wir $S \rightarrow \epsilon$ anwenden, dann verschwindet ein $S$, die Behauptung gilt aber nach wie vor für alle anderen $S$ in $\delta$. $\square$

Wir folgern also, dass für das $\alpha$ den beiden obigne Herleitungen $\first_k(\alpha) \in \{\epsilon, \texttt{)}\}$ gilt. Keines davon ist ein Nichtterminal, und so muss auch $\first_k(\alpha) = \first_k(x)$ gelten. Zusammenfassend gesagt: \begin{align*} \first_k(x) & \in \{\epsilon, \texttt{)}\} \\ \first_y(y) & = \texttt{(} \ , \end{align*} und somit sind sie verschieden. Wir folgern, dass $G$ eine LL(1)-Grammatik ist.

Sehen Sie, dass die LL($k$)-Bedingung der Aussage "der Backtrack-Baum hat keine langen Sackgassen" ähnelt (aber nicht völlig äquivalent dazu ist). Wenn $G$ eine LL($k$)-Grammatik ist und wir den Backtrack-Baum für ein Wort bauen, dann gilt: sobald wir in einer Sackgasse $k$ neue Terminalsymbole am "Terminalpräfix" der Wortform hergeleitet haben, merken wir, dass wir in einer Sackgasse sind. Mit Terminalpräfix meine ich den längsten Präfix einer Wortform, der ausschließlich aus Terminalen besteht. Allerdings muss nicht jeder Ableitungsschritt den Terminalpräfix wachsen lassen (Regeln wie $X \rightarrow YbZ$ zum Beispiel ersetzen einfach das erste Nichtterminal), aber "moralisch" geschieht etwas ähnliches).

Wenn umgekehrt eine Grammatik nicht LL($k$) ist, dann muss der Backtrack-Baum beiden Ableitungen \begin{align*} w A \alpha & \Rightarrow w \beta \alpha \\ w A \alpha & \Rightarrow w \gamma \alpha \\ \end{align*} mindestens so lange weiterverfolgen, bis der Terminalpräfix $k$ weitere Zeichen dazugewonnen hat. Der Baum bekommt also dementsprechend lange Sackgassen.

Übungsaufgabe (Beispiel 5.3 aus The Theory of Parsing, Translation, and Compiling von Alfred V. Aho und Jeffrey D. Ullman). Betrachten wir die Grammatik \begin{align*} S & \step{1} \epsilon \\ S & \step{2} ab A \\ A & \step{3} Saa \\ A & \step{4} b \end{align*} Zeigen Sie, dass diese Grammatik LL(2) ist, aber nicht LL(1).

Tip. Leiten Sie erst einmal ein Dutzend verschiedene Wörter ab und finden dann eine "normalsprachliche" Beschreibung dieser Sprache. Beschreiben Sie dann alle möglichen Wortformen $\alpha$ mit $S \Step{}^* \alpha$.

Übungsaufgabe Schreiben Sie eine äquivalente Grammatik zu der vorherigen Sprache, die LL(1) ist. (Warnung: Ich weiß nicht, ob das überhaupt geht).

Übungsaufgabe Betrachten wir die Grammatik $G$: \begin{align*} S & \step{1} a S b \\ S & \step{2} a S \\ S & \step{3} \epsilon \end{align*} Sie erzeugt die Sprache \begin{align*} L(G) := \{ a^{m+k} b^m \ | \ m, k \in \N \} \ , \end{align*} also Wörter, wo auf beliebig viele $a$'s eine Folge von höchstens so vielen $b$'s folgt.

Geben Sie diese Grammatik in den Parser-Simulator ein und finden Wörter mit langen Sackgassen.

Zeigen Sie, dass diese Grammatik nicht LL$(k)$ ist, für kein $k \in \N$.

Übungsaufgabe Sei $t \in \N$ eine feste, im Voraus bekannte Zahl. Betrachten wir die Sprache \begin{align*} L_t := \{a^{m + l} b^m \ | \ m \geq 0, l \leq t\} \ , \end{align*} also die Wörter der Form $a^m b^n$ mit $n \leq m \leq n+t$.

Schreiben Sie für $L_3$ eine Grammatik, geben Sie diese im Parser-Simulator ein und schauen, wie lang die Sackgassen werden können.

Zeigen Sie, dass $L_3$ eine LL$(k)$-Grammatik ist. Für welchen Wert von $k$? Ist $L_t$ (für im Voraus bekanntes $t$) eine LL$(k)$-Grammatik? Für welchen Wert von $k$?

LL$(k)$-Grammatiken parsen

Wir wollen nun erarbeiten, wie wir für eine LL$(k)$-Grammatik einen Parser, also im Prinzip einen deterministischen Pushdown-Automaten schreiben können. Wir tasten uns langsam voran. Wir beginnen mit einer Verallgemeinerung von $\first_k$ von Wörtern auf Wortformen (die also Nichtterminale beinhalten können).

Definition Sei eine kontextfreie Grammatik $G = (\Sigma, N, S, P)$ und eine Wortform $\alpha \in (\Sigma \cup N)^*$ gegeben. Wir definieren \begin{align*} \First_k(\alpha) := \{ \first_k(w) \ | \ w \in \Sigma^*, \alpha \Step{}^* w\} \end{align*}

Wir können nun die LL$(k)$-Bedingung äquivalent formulieren:

Definition/Beobachtung Eine Grammatik $G$ ist LL$(k)$ genau dann, wenn für alle Grenzformen $A \alpha$ und alle Produktionen mit $A$ auf der linken Seite, also \begin{align*} A & \rightarrow \beta_1 \\ A & \rightarrow \beta_2 \\ & \vdots\\ A & \rightarrow \beta_l \end{align*} die Mengen $\First(\beta_i \alpha)$ paarweise disjunkt sind (wenn also keine zwei dieser Mengen ein gemeinsames Element enthalten).

Nehmen wir eine Momentaufnahme unseres Kellerautomaten. Er hat den Präfix $x$ des Eingabewortes $xy$ gelesen und eine Linksableitung \begin{align*} S \Rightarrow^*{} x \alpha \end{align*} durchgeführt. Die Wortform $\alpha$ ist genau das, was im Moment auf dem Stack des Automaten liegt (um ganz genau zu sein: $\alpha\texttt{\$}$ liegt auf dem Stack). Wenn $\alpha$ mit einem Terminalsymbol $c$ beginnt, so ist klar, was wir machen müssen: wir schauen, ob $y$ mit $c$ beginnt. Wenn ja, lesen wir $c$ und poppen es vom Stack. Der schwierige Fall ist, wenn $\alpha$ mit einem Nichtterminal beginnt.

Nochmal von vorn: im schwierigen Fall liegt auf dem Stack (oberhalb vom $\$$) eine Wortform, die mit einem Nichtterminal beginnt, also $A \alpha$. Das bedeutet, dass der Automat per Linksableitung bis jetzt \begin{align*} S \Step{}^* x A \alpha \end{align*} hergeleitet hat. Der Automat muss sich nun zwischen allen Regeln für $A$ entscheiden: \begin{align*} A & \rightarrow \beta_1 \\ A & \rightarrow \beta_2 \\ & \vdots\\ A & \rightarrow \beta_l \ . \end{align*} Der Automat betrachtet nun die nächsten $k$ Eingabesymbole, also $\first_k(y)$ (wir gehen mal davon aus, dass er das kann; programmieren könnten wir das auf jeden Fall; ob man es im strengen Framework des Kellerautomaten hinkriegt, werden wir später sehen). Wenn $G$ eine LL$(k)$-Grammatik ist, dann gibt es höchstens eine Regel $A \rightarrow \beta_i$ mit \begin{align*} \first_k(y) \in \first_k(\beta_i \alpha) \end{align*} da ja nach obiger Beobachtung diese Mengen disjunkt sind. Wenn $\first_k(y)$ in keiner dieser Mengen enthalten ist, so kann die Ableitung offensichtlich nicht vervollständigt werden, und wir schließen, dass $xy \not \in L(G)$ ist. Wenn es genau ein $\beta_i$ gibt mit $\first_k(y) \in \first_k(\beta_i \alpha)$, dann ist $A \rightarrow \beta_i$ die "richtige" Produktion. Wir wenden sie an, ersetzen also $A$ auf dem Stack durch $\beta_i$. Falls es zwei oder mehr Produktionen $A \rightarrow \beta_i$ gibt mit $\first_k(y) \in \first_k(\beta_i \alpha)$, dann ist die Grammatik nicht LL$(k)$; wir beenden den Parsing-Prozess mit einer Laufzeitfehlermeldung. Hier ist ein Entwurf eines allgemeinen Algorithmus für LL$(k)$-Grammatiken:

Generischer Algorithmus zum Parsen von LL$(k)$-Gramatiken

Lege $S\texttt{\$}$ auf den Stack.
while Stack nicht leer

Sei $y$ das Resteingabewort.
Wenn das oberste Symbol auf dem Stack ein Terminalsymbol $c$ ist:
- Lies das nächste Eingabesymbol $c'$.
- Wenn $c = c'$, poppe $c$ vom Stack;
- ansonsten Reject.
Wenn das oberste Symbol auf dem Stack ein Nichtterminalsymbol $A$ ist:
1. Schreibe den Stack als $A \alpha$
2. Seien $A \rightarrow \beta_1, \dots, A \rightarrow \beta_l$ alle Produktionen mit $A$ auf der linken Seite.
3. Berechne $\First_k(\beta_i\alpha)$ für alle $\beta_i$ und schaue, welches $\first_k(y)$ enthält
  - Wenn es genau eine solche Produktion $A \rightarrow \beta_i$ gibt: wende Sie an; es ist die richtige Produktion.
  - Wenn es keine gibt: Reject. Das Wort kann nicht abgeleitet werden.
  - Wenn es mehrere gibt: ende mit einem Laufzeitfehler; die Grammatik ist nicht LL$(k)$.
Wenn das oberste Symbol $\texttt{\$}$ ist: wenn Eingabewort zu Ende Accept ansonsten Reject

Die rot und fett gedruckte Zeile ist das "Herz" dieses Algorithmus. Um den Algorithmus implementieren zu können, müssen wir es schaffen, die Menge $\First_k(\beta_i\alpha)$ zu berechnen.

$\First_k(A)$ und $\First_k(\alpha)$ berechnen.

Definition Seien $K, L \subseteq \Sigma^*$ zwei Mengen. Mit $K \circ L$ bezeichnen wir die Menge \begin{align*} K \circ L := \{xy \ | \ x \in K, y \in L\} \ . \end{align*} (Diese Definition haben Sie schon im Kapitel über reguläre Sprachen kennengelernt). Für eine natürliche Zahl $k$ definieren wir \begin{align*} \First_k(L) := \{\first_k(x) \ | \ x \in L\} \ . \end{align*} Weiterhin bezeichnen wir mit $K \circ_k L$ die Menge \begin{align*} K \circ_k L & := \First(K \circ L) \\ & = \{\first_k(xy) \ | \ x \in K, y \in L\} \ . \end{align*}

Im Allgemeinen gilt $\First_k(S_1 \circ \dots \circ S_l) = S_1 \circ_k S_2 \circ_k \dots \circ_k S_l$. In Worten: der $\circ_k$-Operator bildet alle möglichen Kombinationen von Wörtern und nimmt von jedem die ersten $k$ Zeichen.

Beispiel Sei \begin{align*} K & := \{\epsilon, a, ab, aba\} \\ L & := \{c, bb, b\} \end{align*} Dann ist \begin{align*} K \circ L = \{c, bb, b, ac, abb, ab, abc, abbb, abb, abac, ababb, abab\} \end{align*} und somit \begin{align*} K \circ_2 L & = \{c, bb, b, ac, ab, ab, ab, ab, ab, ab, ab, ab\} \\ & =\{c, bb, b, ac, ab\} \end{align*}

Beobachtung - Wie man $\First_k(\alpha)$ berechnet. Sei eine Wortform $\alpha$ gegeben, also $\alpha \in (\Sigma \cup N)^*$. Wir berechnen $\First_k(\alpha)$, indem wir als erstes $\alpha$ aussschreiben als \begin{align*} \alpha = (\sigma_1 \sigma_2 \sigma_3 \dots \sigma_n) \end{align*} wobei jedes $\sigma_i$ ein Terminalsymbol oder ein Nichtterminalsymbol ist, und berechnen dann $\First_k(\alpha)$ wie folgt: \begin{align} \First_k(\alpha) = \First_k(\sigma_1) \circ_k \First_k(\sigma_2) \circ_k \dots \circ_k \First_k (\sigma_n) \ . \label{first-k-wortform} \end{align}

Wir können dies schön der Reihe nach tun:

Initialisiere $K := \{\epsilon\}$
for $i=n$ down to 1 do:
- $K := \First_k(\sigma_i) \circ_k K $ // $K$ ist jetzt $\First_k(\sigma_i) \circ_k \dots \circ_k \First_k(\sigma_n)$
return $K$

Wir müssen nur noch herausfinden, wie wir $\First_k(\sigma)$ für einzelne Zeichen $\sigma$ berechnen.

Für ein Terminalsymbol $c$ ist es trivial, $\First_k(c)$ zu berechnen: es ist $\{c\}$, da sich aus $c$ natürlich nur das Wort $c$ ableiten lässt. Für Nichtterminale müssen wir uns anstrengen. Die erste Idee ist, dass wir für $\First_k(X)$ eine Gleichung schreiben können, die $(\ref{first-k-wortform})$ verwendet.

Beobachtung Sei $X$ ein Nichtterminal und \begin{align*} X & \rightarrow \alpha_1 \\ X & \rightarrow \alpha_2 \\ & \vdots \\ X & \rightarrow \alpha_k \end{align*} die Produktionen der Grammatik mit $X$ auf der linken Seite. Dann gilt \begin{align} \First_k(X) = \bigcup_{i=1}^k \First_k(\alpha_i) \label{first-k-nonterminal} \end{align} Was ja eigentlich offensichtlich ist: wenn sich ein Wort $X \Step{}^* w$ aus $X$ ableiten lässt, dann muss dies mittels einer der obigen Produktionen geschehen: $X \Step{} \alpha_i \Step{}^* w$, und somit gilt $\first_k(w)\in \First_k(\alpha_i)$.

Die Gleichungen $(\ref{first-k-wortform})$ und $(\ref{first-k-nonterminal})$ leuchten zwar ein, scheinen aber erstmal nicht hilfreich, diese Mengen auch tatsächlich zu berechnen. Denn eventuell taucht $X$ selbst wieder auf einer rechten Seite auf, sagen wir $\alpha_1$. Um $\First_k(X)$ zu berechnen, müssen wir also laut $(\ref{first-k-nonterminal})$ die Menge $\First_k(\alpha_1)$ kennen; um diese zu berechnen, brauchen wir laut $(\ref{first-k-wortform})$ allerdings zuerst unter Anderem die Menge $\First_k(X)$. Wo sollen wir also anfangen?

In solchen Situationen, wo sich "die Katze in den Schwanz beißt", hilft es oft, die Definition vorerst komplexere un genauer zu machen. Wir führen nun, zusätzlich zu $\First_k(X)$ und $\First_k(\alpha)$, noch eine feinere Unterteilung an:

Definition Sei $\sigma$ ein Symbol und $d \in \N$. Dann ist \begin{align*} \First_k^{(d)}(\sigma) := \{\first_k(w) \ | \ \textnormal{ es gibt einen Ableitungsbaum für $\sigma \Step{}^* w$ der Höhe höchstens $d$}\} \end{align*}

Beispiel Sei unsere Grammatik \begin{align*} S & \rightarrow Xa \\ X & \rightarrow Sb \ | c \end{align*} Dann ist beispielsweise

ein Ableitungsbaum der Höhe 2 von $S \Step{}^* ca$, und somit gilt \begin{align*} c \in \First_1^{(d)} (S) \ . \end{align*} Ein Baum der Höhe 1, der mit $S$ beginnt, könnte ja nur $Xa$ ableiten und somit gar kein Wort. Es gilt also \begin{align*} \First_1^{(1)} (S) = \emptyset \ . \end{align*} Für eine Wortform $\alpha = \sigma_1 \sigma_2 \dots \sigma_n \in (\Sigma \cup N)^*$ definieren wir \begin{align*} \First_k^{(d)}(\alpha) = \First_k^{(d)}(\sigma_1) \circ_k \First_k^{(d)}(\sigma_2) \circ_k \dots \circ_k \First_k^{(d)} \end{align*} Eine Ableitung $\alpha \Step{}^* w$ der Höhe maximal $d$ entspricht also einer Folge von $n$ Ableitungsbäumen, von denen jeder Höhe maximal $d$ hat.

Mit dieser Definition können wir nun Gleichungen für $\First_k^{(d)}(X)$ und $\First_k^{(d)}(\alpha)$ angeben. Seien $X \rightarrow \alpha_1 \ | \ \dots \ | \ \alpha_k$ die Produktionen mit $X$ auf der linken Seite. Dann gilt für $k \geq 1$:

Lemma. Für $d \geq 1$ gilt \begin{align*} \First_k^{(d)}(X) & = \bigcup_{i=1}^k \First_k^{(d-1)} (\alpha_i) \\ \First_k^{(d)}(\alpha) & = \First_k^{(d)}(\sigma_1) \circ_k \First_k^{(d)}(\sigma_2) \circ_k \dots \circ_k \First_k^{(d)} \end{align*} Für $d = 0$ gilt \begin{align*} \First_k^{(0)}(X) & := \emptyset \tag{für jedes Nichtterminal} \end{align*} und schließlich \begin{align*} \First_k^{(d)}(a) & := \{a\} \tag{für jedes Terminalsymbol und jedes $d \in \N$} \end{align*}

Die Gleichungen sagen, dass wir, falls wir $\First_{k}^{(d-1)}(X)$ für alle Nichtterminale kennen, dann auch $\First_{k}^{(d)}(X)$ berechnen können. Daraus folgt auch: wenn $\First_{k}^{(d-1)}(X)=\First_{k}^{(d)}(X)$ für alle $X \in N$, dann auch $\First_{k}^{(d)}(X)=\First_{k}^{(d+1)}(X)$ für alle $X \in N$, und somit werden die Mengen $\First_{k}^{(d)}(X)$ für alle $d$ von nun an gleich bleiben.

Beobachtung Falls $\First_{k}^{(d-1)}(X)=\First_{k}^{(d)}(X)$ für alle $X \in N$, dann gilt \begin{align*} \First_k (X) = \First_k^{(d)}(X) \end{align*} für alle $X \in N$.

Demo. - Berechnung der Menge $\First_k(A)$ für die Nichtterminale einer Sprache. Wir betrachten die Grammatik \begin{align*} S & \rightarrow Xa \ | \ \epsilon \\ X & \rightarrow b \ | \ Sc \ | \ SX \end{align*}

5.4 LL(\(k\))-Grammatiken

LL\((k)\)-Grammatiken parsen

\(\First_k(A)\) und \(\First_k(\alpha)\) berechnen.