LF(k)-Grammatik

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

---

Eine LF(k)-Grammatik ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LF(k)-Parsers bildet. Auf Grund der sehr engen Verwandtschaft werden LF(k)-Grammatiken auch als starke LL(k)-Grammatiken bezeichnet.

Die Bezeichnung LF(k)-Grammatik bedeutet, dass jeder Ableitungsschritt eindeutig durch k Symbole der Eingabe (Lookahead) bestimmt ist. Damit kann die Frage, welches Nichtterminalsymbol mit welcher Regel als Nächstes expandiert werden soll, eindeutig mit Hilfe der nächsten k Symbole der Eingabe beantwortet 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 Grammatiken, die für kein k LF(k)-Grammatiken sind.

${\mathcal {L}}(\mathrm {LF} (1))\subsetneq {\mathcal {L}}(\mathrm {LF} (2))\subsetneq \dots \subsetneq {\mathcal {L}}(\mathrm {PDA} )$

Formale Definition LF(k)-Grammatik

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

	$wA\gamma \Rightarrow _{l}w\alpha \gamma \Rightarrow _{l}^{*}wx$
$S\Rightarrow _{l}^{*}$
	$w'A\gamma '\Rightarrow _{l}w'\beta \gamma '\Rightarrow _{l}^{*}w'y$

mit $w,w',x,y\in \Sigma ^{*};\alpha ,\beta ,\gamma ,\gamma '\in (N\cup \Sigma )^{*};A\in N$ und $first_{k}\left(x\right)=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$	${\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\}\}$
${\mathcal {A}}\in 2^{(N\cup \Sigma )^{*}}$	${\mathit {first}}_{k}({\mathcal {A}})=\{w\in first_{k}(\alpha )\mid \alpha \in {\mathcal {A}}\}$

Anwendung

Die formale Definition einer LF(k)-Grammatik ist bezüglich praktischer Anwendung nur mit großem Aufwand überprüfbar. Daher erfolgt die Prüfung auf LF(k)-Eigenschaft mithilfe eines abgewandelten Ansatzes.

Eine reduzierte kontextfreie Grammatik ist genau dann eine LF(k)-Grammatik, wenn für alle Nichtterminalsymbole $A$ und für alle Produktionen $A\to \beta$ und $A\to \gamma$ mit $\beta \neq \gamma$ gilt: $first_{k}(\{\beta \}follow_{k}(A))\cap first_{k}(\{\gamma \}follow_{k}(A))=\emptyset$.

Erklärung: Infolge einer Wortableitung wurde das Startsymbol der kontextfreien Grammatik (in eventuell mehreren Schritten) expandiert. Angenommen, im nächsten Schritt soll das Nichtterminalsymbol A ersetzt werden. Dazu stehen aber zwei verschiedene Regeln $A\to \beta$ und $A\to \gamma$ zur Verfügung. Ist die in der Gesetzmäßigkeit angegebene Schnittmenge leer, dann kann die Regelauswahl eindeutig getroffen werden.

Für diesen Zweck wird die Funktion $follow_{k}\left(A\right)$ benötigt, 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 )\}$

Die Prüfung auf LL(1)-Eigenschaft benutzt den gleichen Ansatzpunkt. Eine Verallgemeinerung auf beliebige k ist dabei jedoch nicht möglich. Dieser Unterschied grenzt beide Grammatikformen voneinander ab.

Beispiel

Die Grammatik $G$ soll auf ihre LF(k)-Eigenschaft hin untersucht werden. Mit anderen Worten: Für welches k ist G eine LF(k)-Grammatik?

$G=\left(\{S,A\},\{\varepsilon ,a,b\},P,S\right)$ und die Menge der Produktionen ist

$S\to aAaa\quad S\to bAba\quad A\to \varepsilon \quad A\to b$

Zunächst werden die first- bzw. follow-Mengen der Nichtterminalsymbole bestimmt.

	$first_{1}$	$first_{2}$	$first_{3}$	$follow_{1}$	$follow_{2}$	$follow_{3}$
$S$	$\left\{a,b\right\}$	$\left\{aa,ab,bb\right\}$	$\left\{aaa,aba,bba,bbb\right\}$	$\left\{\varepsilon \right\}$	$\left\{\varepsilon \right\}$	$\left\{\varepsilon \right\}$
$A$	$\left\{\varepsilon ,b\right\}$	$\left\{\varepsilon ,b\right\}$	$\left\{\varepsilon ,b\right\}$	$\left\{a,b\right\}$	$\left\{aa,ba\right\}$	$\left\{aa,ba\right\}$

Es folgt der Vergleich der wie oben definierten Mengen für alle Produktionen mit gleichen linken Regelseiten. In diesem Beispiel werden somit die Regeln $S\to aAaa$ mit $S\to bAba$ und $A\to \varepsilon$ mit $A\to b$ verglichen.

Im Fall des Nichtterminalsymbols S sind schon für $k=1$ die Mengen $first_{1}(\left\{aAaa\right\}follow_{1}(S))=\{a\}$ und $first_{1}(\left\{bAba\right\}follow_{1}(S))=\{b\}$ disjunkt. Weitere Betrachtungen für größere k können entfallen.

	$k=1$	$k=2$	$k=3$
$first_{k}(\{\varepsilon \}follow_{k}(A))$	$\left\{a,b\right\}$	$\left\{aa,ba\right\}$	$\left\{aa,ba\right\}$
$first_{k}(\{b\}follow_{k}\left(A\right))$	$\left\{b\right\}$	$\left\{ba,bb\right\}$	$\left\{baa,bba\right\}$

Erst für $k=3$ sind die zu vergleichenden Mengen disjunkt und damit die deterministische Regelauswahl gewährleistet. Die Beispielgrammatik G ist also eine LF(3)-Grammatik.

Literatur

• Daniel Scheibler, Michael Henke, Peter Bachmann: Skript zur Compilertechnik (Februar / März 2004, PDF; 487 kB)