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,Σ,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 α = β.

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\}\}$
$\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 \ne \gamma$ gilt: $first_k(\{\beta\}follow_k(A)) \cap first_k(\{\gamma\}follow_k(A))=\emptyset$.

Erklärung: In Folge 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.

	first1	first2	first3	follow1	follow2	follow3
S	$\left\{a,b\right\}$	$\left\{aa,ab,bb\right\}$	$\left\{aaa,aba,bba\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
firstk({ε}followk(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)