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.

<math>\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})</math>

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 <math>G=(N,\Sigma,P,S)</math> ist genau dann eine LL(k)-Grammatik, wenn für alle Linksableitungen der Form

<math>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.</math>

mit <math>\quad (w,x,y \in \Sigma^*; \alpha,\beta,\gamma \in (N \cup \Sigma)^*; A \in N)</math> und <math>\mathit{first}_k(x)=\mathit{first}_k(y)^{\,}</math> gilt: <math>\alpha=\beta^{\,}</math>

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

a\|\le k</math>	<math>\mathit{first}_k\left(a\right)=\{a\}</math>
a\|>k</math>	v\|=k\}</math>
<math>A \in (N\cup\Sigma)^* \backslash \Sigma^*</math>	<math>\mathit{first}_k(A)=\{v \in \Sigma^ * \mid A \Rightarrow^* w;w \in \Sigma^ *; \mathit{first}_k(w)=\{v\}\}</math>

Anwendung

Aktuelle LL-Parser benutzen meist nur einen Lookahead von 1. Daher kann in den folgenden Ausführungen <math>k=1</math> 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 <math>A</math>, für alle Produktionen <math>A \to \beta</math> und <math>A \to \gamma</math> mit <math>\beta \ne \gamma</math> und <math>S \Rightarrow^*_l wA\alpha</math> gilt: <math>first_k(\beta\alpha) \cap first_k(\gamma\alpha) = \emptyset</math>. <math> (w \in \Sigma^*; \alpha,\beta,\gamma \in (N \cup \Sigma)^*; A \in N)</math>

Erklärung: Das Startsymbol der kontextfreien Grammatik <math>S</math> wurde (in eventuell mehreren Schritten) nach <math>wA^{\,}\alpha</math> expandiert. Gemäß der Linksableitung wird das Nichtterminalsymbol <math>A</math> als Nächstes ersetzt. Dazu gibt es in der kontextfreien Grammatik aber zwei verschiedene Regeln; <math>A \to \beta</math> und <math>A \to \gamma</math>. Die Frage, mit welcher Regel <math>A</math> expandiert wird, bestimmt sich aus der Berechnung von <math>first_k\left(\beta\alpha\right)</math> und <math>first_k\left(\gamma\alpha\right)</math>. Um die Frage eindeutig beantworten zu können, müssen beide Mengen disjunkt sein.

Im Allgemeinen hängt <math>first_k\left(\beta\alpha\right)</math> aber vom Rechtskontext <math>\alpha</math> ab (wenn <math>\beta \Rightarrow^* \epsilon</math>). Das Ziel ist die Bestimmung von <math>first_k\left(\beta\alpha\right)</math> nur aus den Produktionen, d. h. aus <math>\beta</math> und aus den Strings, die einem Vorkommen von <math>A</math> folgen können. Für diesen Zweck wird die Funktion <math>follow_k\left(A\right)</math> definiert, die die Menge aller <math>A</math> folgenden Symbole berechnet.

<math>\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)\}</math>

Damit kann die eingangs geforderte Bedingung umformuliert werden:

Eine reduzierte kontextfreie Grammatik ist genau dann eine LL(1)-Grammatik, wenn für alle Nichtterminalsymbole <math>A</math> und für alle Produktionen <math>A \to \beta</math> und <math>A \to \gamma</math> mit <math>\beta \ne \gamma</math> gilt: <math>first_1(\{\beta\}follow_1(A)) \cap first_1(\{\gamma\}follow_1(A))=\emptyset.</math>

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

Die zu einer Produktion <math>A \to \beta</math> berechnete Menge <math>la(A,\beta)=first_1\left(\{\beta\}follow_1(A)\right)</math> wird als Lookahead-Menge bezeichnet.

Beispiel

Für die folgende Grammatik <math>G</math> wird geprüft, ob sie eine LL(1)-Grammatik ist. Dazu müssen die Lookahead-Mengen aller Produktionen mit gleichen linken Regelseiten disjunkt sein.

<math>G=\left(\{E,E',T,T',F\},\{a,(,),+,*\},P,E\right)</math> und die Menge der Produktionen ist:

<math>E' \to +TE' | \epsilon</math>

<math>T' \to *FT' | \epsilon</math>

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
<math>first_1</math>	<math>\left\{(,a\right\}</math>	<math>\left\{+,\epsilon\right\}</math>	<math>\left\{(,a\right\}</math>	<math>\left\{*,\epsilon\right\}</math>	<math>\left\{(,a\right\}</math>
<math>follow_1</math>	<math>\left\{$,)\right\}</math>	<math>\left\{$,)\right\}</math>	<math>\left\{+,$,)\right\}</math>	<math>\left\{+,$,)\right\}</math>	<math>\left\{*,+,$,)\right\}</math>

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

Als erstes für die beiden Produktionen <math>+TE'</math> und <math>\epsilon</math> von <math>E' \to +TE' | \epsilon</math>

<math>first_1(\{+TE'\}) \cap first_1(\{\epsilon\})=\{+\} \cap \{\epsilon\}=\emptyset</math>

<math>first_1(\{+TE'\}) \cap follow_1(E')=\{+\} \cap \{$,)\}=\emptyset</math>

Als Nächstes für die beiden Produktionen <math>*FT'</math> und <math>\epsilon</math> von <math>T' \to *FT' | \epsilon</math>

<math>first_1(\{*FT'\}) \cap first_1(\{\epsilon\})=\{*\} \cap \{\epsilon\}=\emptyset</math>

<math>first_1(\{*FT'\}) \cap follow_1(T')=\{*\} \cap \{+,$,)\}=\emptyset</math>

Als letztes für die beiden Produktionen <math>(E)</math> und <math>a</math> von <math>F \to (E) | a</math>

<math>first_1(\{(E)\}) \cap first_1(\{a\})=\{(\} \cap \{a\}=\emptyset</math>

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

Siehe auch

Literatur

Donald E. Knuth: Top-down syntax analysis. In: Acta Informatica 1, 1971, {{#invoke:URIutil|{{#ifeq:1|1|linkISSN|targetISSN}}|0001-5903|0}}{{#ifeq:1|0|[!]

}}{{#ifeq:0|1

        |{{#switch:00
                  |11= (print/online)
                  |10= (print)
                  |01= (online)
          }}

}}{{#ifeq:0|0

        |{{#ifeq:0|0
              |{{#if:{{#invoke:URIutil|isISSNvalid|1=0001-5903}}
                    |
                    |{{#invoke:TemplUtl|failure|ISSN ungültig}}}}}}

}}, 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