# LL(k)-Grammatik

Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus.
Eine LL(k)-Grammatik (im Gegensatz zu LF(k)-Grammatik auch schwache LL(k)-Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LL(k)-Parsers bildet.
Eine kontextfreie Grammatik heißt LL(k)-Grammatik für eine natürliche Zahl k, wenn jeder Ableitungsschritt eindeutig durch die nächsten k Symbole der Eingabe (Lookahead) bestimmt ist. Das bedeutet, die Frage, welches Nichtterminalsymbol mit welcher Regel als Nächstes expandiert werden soll, kann eindeutig mit Hilfe der nächsten k Symbole der Eingabe bestimmt werden.
Generell gilt, je größer k gewählt wird, umso mächtiger wird die Sprachklasse, wobei die Ausdrucksstärke von kontextfreien Grammatiken nie erreicht wird. Damit gibt es kontextfreie Sprachen, die für kein k von einer LL(k)-Grammatik erzeugt werden.
${\mathcal {L}}(\mathrm {LL} (1))\subsetneq {\mathcal {L}}(\mathrm {LL} (2))\subsetneq \dots \subsetneq {\mathcal {L}}(\mathrm {LL} (k))\subsetneq {\mathcal {L}}(\mathrm {LR} (1))={\mathcal {L}}(\mathrm {DPDA} )$
Dabei steht DPDA für die deterministischen Kellerautomaten. Diese können genau die deterministisch kontextfreien Sprachen erkennen.

## Formale Definition LL(k)-Grammatik

Eine kontextfreie Grammatik $G=(N,\Sigma ,P,S)$ ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form
    $S\Rightarrow _{l}^{*}wA\gamma \Rightarrow _{l}\left\{{\begin{array}{l}w\alpha \gamma \Rightarrow _{l}^{*}wx\\w\beta \gamma \Rightarrow _{l}^{*}wy\end{array}}\right.$
mit $\quad (w,x,y\in \Sigma ^{*};\alpha ,\beta ,\gamma \in (N\cup \Sigma )^{*};A\in N)$ und ${\mathit {first}}_{k}(x)={\mathit {first}}_{k}(y)^{\,}$ gilt: $\alpha =\beta ^{\,}$
Für die in der Definition benutzte Funktion zur Bestimmung der FIRST-Mengen gilt:
| $a\in \Sigma ^{*};|a|\leq k$ | ${\mathit {first}}_{k}\left(a\right)=\{a\}$ |
| $a\in \Sigma ^{*};|a|>k$ | ${\mathit {first}}_{k}(a)=\{v\in \Sigma ^{*}\mid a=vw;|v|=k\}$ |
| $A\in (N\cup \Sigma )^{*}\backslash \Sigma ^{*}$ | ${\mathit {first}}_{k}(A)=\{v\in \Sigma ^{*}\mid A\Rightarrow ^{*}w;w\in \Sigma ^{*};{\mathit {first}}_{k}(w)=\{v\}\}$ |

## Anwendung

Aktuelle LL-Parser benutzen meist nur einen Lookahead von 1. Daher kann in den folgenden Ausführungen $k=1$ gesetzt werden.
Bei der praktischen Anwendung ist nur mit großem Aufwand überprüfbar, ob die vorliegende Grammatik die Definition einer LL(k)-Grammatik erfüllt. Es wird stattdessen ein abgewandelter Ansatz benutzt.
Eine kontextfreie Grammatik ist genau dann eine LL(k)-Grammatik, wenn für alle Nichtterminalsymbole $A$, für alle Produktionen $A\to \beta$ und $A\to \gamma$ mit $\beta \neq \gamma$ und $S\Rightarrow _{l}^{*}wA\alpha$ gilt: $first_{k}(\beta \alpha )\cap first_{k}(\gamma \alpha )=\emptyset$. $(w\in \Sigma ^{*};\alpha ,\beta ,\gamma \in (N\cup \Sigma )^{*};A\in N)$
Erklärung: Das Startsymbol der kontextfreien Grammatik $S$ wurde (in eventuell mehreren Schritten) nach $wA^{\,}\alpha$ expandiert. Gemäß der Linksableitung wird das Nichtterminalsymbol $A$ als Nächstes ersetzt. Dazu gibt es in der kontextfreien Grammatik aber zwei verschiedene Regeln; $A\to \beta$ und $A\to \gamma$. Die Frage, mit welcher Regel $A$ expandiert wird, bestimmt sich aus der Berechnung von $first_{k}\left(\beta \alpha \right)$ und $first_{k}\left(\gamma \alpha \right)$. Um die Frage eindeutig beantworten zu können, müssen beide Mengen disjunkt sein.
Im Allgemeinen hängt $first_{k}\left(\beta \alpha \right)$ aber vom Rechtskontext $\alpha$ ab (wenn $\beta \Rightarrow ^{*}\epsilon$). Das Ziel ist die Bestimmung von $first_{k}\left(\beta \alpha \right)$ nur aus den Produktionen, d. h. aus $\beta$ und aus den Strings, die einem Vorkommen von $A$ folgen können. Für diesen Zweck wird die Funktion $follow_{k}\left(A\right)$ definiert, die die Menge aller $A$ folgenden Symbole berechnet.
$\forall \beta \in (N\cup \Sigma )^{*}:follow_{k}(\beta )=\{w\in \Sigma ^{*}\mid \exists \alpha ,\gamma \in (N\cup \Sigma )^{*}{\mbox{ mit }}S\Rightarrow _{l}^{*}\alpha \beta \gamma {\mbox{ und }}w\in first_{k}(\gamma )\}$
Damit kann die eingangs geforderte Bedingung umformuliert werden:
Eine reduzierte kontextfreie Grammatik ist genau dann eine LL(1)-Grammatik, wenn für alle Nichtterminalsymbole $A$ und für alle Produktionen $A\to \beta$ und $A\to \gamma$ mit $\beta \neq \gamma$ gilt: $first_{1}(\{\beta \}follow_{1}(A))\cap first_{1}(\{\gamma \}follow_{1}(A))=\emptyset .$
Achtung: Dieser Satz kann auf Fälle $k>1$ nicht angewandt werden.
Die zu einer Produktion $A\to \beta$ berechnete Menge $la(A,\beta )=first_{1}\left(\{\beta \}follow_{1}(A)\right)$ wird als Lookahead-Menge bezeichnet.

## Beispiel

Für die folgende Grammatik $G$ wird geprüft, ob sie eine LL(1)-Grammatik ist. Dazu müssen die Lookahead-Mengen aller Produktionen mit gleichen linken Regelseiten disjunkt sein.
    $G=\left(\{E,E',T,T',F\},\{a,(,),+,*\},P,E\right)$ und die Menge der Produktionen ist:
    $E\to TE'$
    $E'\to +TE'|\epsilon$
    $T\to FT'$
    $T'\to *FT'|\epsilon$
    $F\to (E)|a$
Zunächst werden die first- bzw. follow-Mengen der Nichtterminalsymbole bestimmt, da diese für die Berechnung der Lookahead-Mengen nötig sind.
| | E | E' | T | T' | F |
| $first_{1}$ | $\left\{(,a\right\}$ | $\left\{+,\epsilon \right\}$ | $\left\{(,a\right\}$ | $\left\{*,\epsilon \right\}$ | $\left\{(,a\right\}$ |
| $follow_{1}$ | $\left\{\$,)\right\}$ | $\left\{\$,)\right\}$ | $\left\{+,\$,)\right\}$ | $\left\{+,\$,)\right\}$ | $\left\{*,+,\$,)\right\}$ |
Es folgt der Vergleich der Lookahead-Mengen für alle Produktionen mit gleichen linken Regelseiten.
Als erstes für die beiden Produktionen $+TE'$ und $\epsilon$ von $E'\to +TE'|\epsilon$
    $first_{1}(\{+TE'\})\cap first_{1}(\{\epsilon \})=\{+\}\cap \{\epsilon \}=\emptyset$
    $first_{1}(\{+TE'\})\cap follow_{1}(E')=\{+\}\cap \{\$,)\}=\emptyset$
Als Nächstes für die beiden Produktionen $*FT'$ und $\epsilon$ von $T'\to *FT'|\epsilon$
    $first_{1}(\{*FT'\})\cap first_{1}(\{\epsilon \})=\{*\}\cap \{\epsilon \}=\emptyset$
    $first_{1}(\{*FT'\})\cap follow_{1}(T')=\{*\}\cap \{+,\$,)\}=\emptyset$
Als letztes für die beiden Produktionen $(E)$ und $a$ von $F\to (E)|a$
    $first_{1}(\{(E)\})\cap first_{1}(\{a\})=\{(\}\cap \{a\}=\emptyset$
Da alle betrachteten Schnittmengen leer sind, handelt es sich bei der Grammatik $G$ um eine LL(1)-Grammatik.