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

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \quad (w,x,y\in \Sigma ^{*};\alpha ,\beta ,\gamma \in (N\cup \Sigma )^{*};A\in N)} und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle {\mathit {first}}_{k}(x)={\mathit {first}}_{k}(y)^{\,}} gilt: Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle S\Rightarrow _{l}^{*}wA\alpha } gilt: Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle first_{k}(\beta \alpha )\cap first_{k}(\gamma \alpha )=\emptyset } . Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle (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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle first_{k}\left(\beta \alpha \right)} und Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \beta } und aus den Strings, die einem Vorkommen von $A$ folgen können. Für diesen Zweck wird die Funktion Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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: Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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.

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle G=\left(\{E,E',T,T',F\},\{\epsilon ,a,(,),+,*\},P,E\right)} und die Menge der Produktionen ist:

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle E\to TE'}

$E'\to +TE'$

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle E'\to \epsilon }

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle T\to FT'}

$T'\to *FT'$

$T'\to \epsilon$

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle F\to (E)}

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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}$	Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \left\{(,a\right\}}	Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \left\{+,\epsilon \right\}}	$\left\{(,a\right\}$	Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \left\{*,\epsilon \right\}}	$\left\{(,a\right\}$
Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle follow_{1}}	$\left\{)\right\}$	Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \left\{\epsilon ,)\right\}}	Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \left\{+,\epsilon ,)\right\}}	$\left\{+,\epsilon ,)\right\}$	Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle \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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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$

Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle 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 Fehler beim Parsen (Konvertierungsfehler. Der Server („https://wikimedia.org/api/rest_“) hat berichtet: „Cannot get mml. Server problem.“): {\displaystyle F\to (E)} und Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle F \to a}

Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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 Fehler beim Parsen (MathML mit SVG- oder PNG-Rückgriff (empfohlen für moderne Browser und Barrierefreiheitswerkzeuge): Ungültige Antwort („Math extension cannot connect to Restbase.“) von Server „https://wikimedia.org/api/rest_v1/“:): {\displaystyle 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