LL(k)-Grammatik

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

---

Eine LL(k)-Grammatik (im Kontrast 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,Σ,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|\le 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 \ne \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 α ab (wenn $\beta \Rightarrow^* \epsilon$). Das Ziel ist die Bestimmung von $first_k\left(\beta\alpha\right)$ nur aus den Produktionen, d. h. aus β 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 \ne \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\},\{\epsilon,a,(,),+,*\},P,E\right)$ und die Menge der Produktionen ist:

$E \to TE'$

$E' \to +TE'$

$E' \to \epsilon$

$T \to FT'$

$T' \to *FT'$

$T' \to \epsilon$

$F \to (E)$

$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
first1	$\left\{(,a\right\}$	$\left\{+,\epsilon\right\}$	$\left\{(,a\right\}$	$\left\{*,\epsilon\right\}$	$\left\{(,a\right\}$
follow1	$\left\{)\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
• LR-Parser

Literatur

• Donald E. Knuth: Top-down syntax analysis. In: Acta Informatica 1, 1971, ISSN 0001-5903, S. 79–110, (Neuabdruck einer erweiterten Fassung in: Donald E. Knuth: Selected Papers on Computer Languages. Center for the Study of Language and Information, Stanford CA 2003, ISBN 1-575-86381-2, (CSLI lecture notes 139), Kapitel 14).
• LR(k)-Analyse für Pragmatiker von Andreas Kunert