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.

$ℒ(\mathrm{L}\mathrm{L}(1))⊊ℒ(\mathrm{L}\mathrm{L}(2))⊊\dots ⊊ℒ(\mathrm{L}\mathrm{L}(k))⊊ℒ(\mathrm{L}\mathrm{R}(1))=ℒ(\mathrm{D}\mathrm{P}\mathrm{D}\mathrm{A})$

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,\mathrm{\Sigma },P,S)$ ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form

$S\underset{l}{\overset{*}{\Rightarrow }}wA\gamma {\Rightarrow }_l\{\begin{array}{c}w\alpha \gamma \underset{l}{\overset{*}{\Rightarrow }}wx\\ w\beta \gamma \underset{l}{\overset{*}{\Rightarrow }}wy\end{array}$

mit $(w,x,y\in {\mathrm{\Sigma }}^{*};\alpha ,\beta ,\gamma \in (N\cup \mathrm{\Sigma }{)}^{*};A\in N)$ und ${𝑓𝑖𝑟𝑠𝑡}_k(x)={𝑓𝑖𝑟𝑠𝑡}_k(y{)}^{}$ gilt: $\alpha ={\beta }^{}$

Für die in der Definition benutzte Funktion zur Bestimmung der FIRST-Mengen gilt:

$a\in {\mathrm{\Sigma }}^{*};|a|\le k$	${𝑓𝑖𝑟𝑠𝑡}_k\left(a\right)=\{a\}$
$a\in {\mathrm{\Sigma }}^{*};|a|>k$	${𝑓𝑖𝑟𝑠𝑡}_k(a)=\{v\in {\mathrm{\Sigma }}^{*}\mid a=vw;|v|=k\}$
$A\in (N\cup \mathrm{\Sigma }{)}^{*}\mathrm{\setminus }{\mathrm{\Sigma }}^{*}$	${𝑓𝑖𝑟𝑠𝑡}_k(A)=\{v\in {\mathrm{\Sigma }}^{*}\mid A{\Rightarrow }^{*}w;w\in {\mathrm{\Sigma }}^{*};{𝑓𝑖𝑟𝑠𝑡}_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\underset{l}{\overset{*}{\Rightarrow }}wA\alpha$ gilt: $firs{t}_k(\beta \alpha )\cap firs{t}_k(\gamma \alpha )=\mathrm{\varnothing }$. $(w\in {\mathrm{\Sigma }}^{*};\alpha ,\beta ,\gamma \in (N\cup \mathrm{\Sigma }{)}^{*};A\in N)$

Erklärung: Das Startsymbol der kontextfreien Grammatik $S$ wurde (in eventuell mehreren Schritten) nach $w{A}^{}\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 $firs{t}_k\left(\beta \alpha \right)$ und $firs{t}_k\left(\gamma \alpha \right)$. Um die Frage eindeutig beantworten zu können, müssen beide Mengen disjunkt sein.

Im Allgemeinen hängt $firs{t}_k\left(\beta \alpha \right)$ aber vom Rechtskontext $\alpha$ ab (wenn $\beta {\Rightarrow }^{*}ϵ$). Das Ziel ist die Bestimmung von $firs{t}_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 $follo{w}_k\left(A\right)$ definiert, die die Menge aller $A$ folgenden Symbole berechnet.

$\mathrm{\forall }\beta \in (N\cup \mathrm{\Sigma }{)}^{*}:follo{w}_k(\beta )=\{w\in {\mathrm{\Sigma }}^{*}\mid \mathrm{\exists }\alpha ,\gamma \in (N\cup \mathrm{\Sigma }{)}^{*}\text{ mit }S\underset{l}{\overset{*}{\Rightarrow }}\alpha \beta \gamma \text{ und }w\in firs{t}_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: $firs{t}_1(\{\beta \}follo{w}_1(A))\cap firs{t}_1(\{\gamma \}follo{w}_1(A))=\mathrm{\varnothing }.$

Achtung: Dieser Satz kann auf Fälle $k>1$ nicht angewandt werden.

Die zu einer Produktion $A\to \beta$ berechnete Menge $la(A,\beta )=firs{t}_1(\{\beta \}follo{w}_1(A))$ 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=(\{E,E^{\prime },T,T^{\prime },F\},\{a,(,),+,*\},P,E)$ und die Menge der Produktionen ist:

$E\to T{E}^{\prime }$

$E^{\prime }\to +T{E}^{\prime }|ϵ$

$T\to F{T}^{\prime }$

$T^{\prime }\to *F{T}^{\prime }|ϵ$

$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
$firs{t}_1$	$\{(,a\}$	$\{+,ϵ\}$	$\{(,a\}$	$\{*,ϵ\}$	$\{(,a\}$
$follo{w}_1$	$\{\mathrm{\$},)\}$	$\{\mathrm{\$},)\}$	$\{+,\mathrm{\$},)\}$	$\{+,\mathrm{\$},)\}$	$\{*,+,\mathrm{\$},)\}$

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

Als erstes für die beiden Produktionen $+T{E}^{\prime }$ und $ϵ$ von $E^{\prime }\to +T{E}^{\prime }|ϵ$

$firs{t}_1(\{+T{E}^{\prime }\})\cap firs{t}_1(\{ϵ\})=\{+\}\cap \{ϵ\}=\mathrm{\varnothing }$

$firs{t}_1(\{+T{E}^{\prime }\})\cap follo{w}_1(E^{\prime })=\{+\}\cap \{\mathrm{\$},)\}=\mathrm{\varnothing }$

Als Nächstes für die beiden Produktionen $*F{T}^{\prime }$ und $ϵ$ von $T^{\prime }\to *F{T}^{\prime }|ϵ$

$firs{t}_1(\{*F{T}^{\prime }\})\cap firs{t}_1(\{ϵ\})=\{*\}\cap \{ϵ\}=\mathrm{\varnothing }$

$firs{t}_1(\{*F{T}^{\prime }\})\cap follo{w}_1(T^{\prime })=\{*\}\cap \{+,\mathrm{\$},)\}=\mathrm{\varnothing }$

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

$firs{t}_1(\{(E)\})\cap firs{t}_1(\{a\})=\{(\}\cap \{a\}=\mathrm{\varnothing }$

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, Vorlage:ISSN, 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