LL(k)-Grammatik

Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus.

---

Eine LL(k)-Grammatik ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LL(k)-Parsers bildet.

Eine kontexfreie Grammatik heißt LL(k)-Grammatik, wenn jeder Ableitungsschritt eindeutig durch 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 ersten k Symbole der Eingabe bestimmt werden.

Generell gilt, je größer k gewählt wird, um so mächtiger wird die Sprachklasse, wobei die Ausdrucksstärke von kontextfreien Grammatiken nie erreicht wird. Damit gibt es kontextfreie Grammatiken, die für kein k LL(k)-Grammatiken sind.

$L(LL(1))\subsetneq L(LL(2))\subsetneq \ldots \subsetneq L(PDA)$

Formale Definition LL(k)-Grammatik

Eine kontextfreie Grammatik $G=(N,\Sigma ,P,S)$ ist LL(k)-Grammatik genau dann, wenn für alle Linksableitungen der Form

	$\Rightarrow _{l}w\alpha \gamma \Rightarrow _{l}^{*}wx$
$S\Rightarrow _{l}^{*}wA\gamma$.
	$\Rightarrow _{l}w\beta \gamma \Rightarrow _{l}^{*}wy$

mit $\quad (w,x,y\in \Sigma ^{*};\alpha ,\beta ,\gamma \in (N\cup \Sigma )^{*};A\in N)$ und $first_{k}(x)=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$	$first_{k}\left(a\right)=\{a\}$
$a\in \Sigma ^{*};|a|>k$	$first_{k}(a)=\{v\in \Sigma ^{*}\mid a=vw;|v|=k\}$
$A\in (N\cup \Sigma )^{*}\backslash \Sigma ^{*}$	$first_{k}(A)=\{v\in \Sigma ^{*}\mid A\Rightarrow ^{*}w;w\in \Sigma ^{*};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.

Die formale Definition einer LL(k)-Grammatik ist bezüglich praktischer Anwendung nur mit großem Aufwand realisierbar. Es wird stattdessen ein abgewandelter Ansatz benutzt.

Eine kontextfreie Grammatik ist LL(k)-Grammatik genau dann, 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 )^{*}~gilt:~follow_{k}(\beta )=\{w\in \Sigma ^{*}\mid \exists \alpha \gamma \in (N\cup \Sigma )^{*}~mit~S\Rightarrow _{l}^{*}\alpha \beta \gamma ~und~w\in first_{k}(\gamma )\}$

Damit kann die eingangs geforderte Bedingung umformuliert werden.

Eine reduzierte kontextfreie Grammatik ist LL(1)-Grammatik genau dann, 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 $first_{1}\left(\{\beta \}follow_{1}(A)\right)=la(A,\beta )$ wird als lookahead Menge bezeichnet.

Beispiel

Für die folgende Grammatik $G$ wird geprüft, ob sie 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\},\{\epsilon ,a,(,),+,*\},P,E\right)$ und die Menge der Produktionen ist

$E\to TE'\quad E'\to +TE'\quad E'\to \epsilon \quad T\to FT'\quad T'\to *FT'\quad T'\to \epsilon \quad F\to (E)\quad F\to 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\{\epsilon ,)\right\}$	$\left\{\epsilon ,)\right\}$	$\left\{+,\epsilon ,)\right\}$	$\left\{+,\epsilon ,)\right\}$	$\left\{*,+,\epsilon ,)\right\}$

Es folgt der Vergleich der Lookahead-Mengen für alle Produktionen mit gleichen linken Regelseiten.

Als erstes für die beiden Produktionen $E'\to +TE'$ und $E'\to \epsilon$

$la(E',+TE')\cap la(E',\epsilon )=first_{1}(\{+TE'\}follow_{1}(E'))\cap first_{1}(\{\epsilon \}follow_{1}(E'))=\{+\}\cap \{\epsilon ,)\}=\emptyset$

Als nächstes für die beiden Produktionen $T'\to *FT'$ und $T'\to \epsilon$

$la(T',*FT')\cap la(T',\epsilon )=first_{1}(\{*FT'\}follow_{1}(T'))\cap first_{1}(\{\epsilon \}follow_{1}(T'))=\{*\}\cap \{+,\epsilon ,)\}=\emptyset$

Als letztes für die beiden Produktionen $F\to (E)$ und $F\to a$

$la(F,(E))\cap la(F,a)=first_{1}(\{(E)\}follow_{1}(F'))\cap first_{1}(\{a\}follow_{1}(F'))=\{(\}\cap \{a\}=\emptyset$

Da alle betrachteten Schnittmengen leer sind, handelt es sich bei der Grammatik G um eine LL(1)-Grammatik.

Siehe auch

• LR(k)-Grammatik

Literatur

• Donald E. Knuth: Top-down syntax analysis. Acta Informatica 1 (1971), 79–110. Neuabdruck in Donald E. Knuth: Selected Papers on Computer Languages, Kapitel 14.