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.

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

Formale Definition LF(k)-Grammatik

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

	$wA\gamma {\Rightarrow }_{l}w\alpha \gamma \underset{l}{\overset{*}{\Rightarrow }}wx$
$S\underset{l}{\overset{*}{\Rightarrow }}$
	$w^{\prime }A{\gamma }^{\prime }{\Rightarrow }_l{w}^{\prime }\beta {\gamma }^{\prime }\underset{l}{\overset{*}{\Rightarrow }}{w}^{\prime }y$

mit $w,w^{\prime },x,y\in {\mathrm{\Sigma }}^{*};\alpha ,\beta ,\gamma ,{\gamma }^{\prime }\in (N\cup \mathrm{\Sigma }{)}^{*};A\in N$ und $firs{t}_k\left(x\right)=firs{t}_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\}\}$
$𝒜\in 2^{(N\cup \mathrm{\Sigma }{)}^{*}}$	${𝑓𝑖𝑟𝑠𝑡}_k(𝒜)=\{w\in firs{t}_k(\alpha )\mid \alpha \in 𝒜\}$

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: $firs{t}_k(\{\beta \}follo{w}_k(A))\cap firs{t}_k(\{\gamma \}follo{w}_k(A))=\mathrm{\varnothing }$.

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 $follo{w}_k\left(A\right)$ benötigt, die die Menge aller A folgenden Symbole berechnet.

$\mathrm{\forall }\beta \in (N\cup \mathrm{\Sigma }{)}^{*}gilt:follo{w}_k(\beta )=\{w\in {\mathrm{\Sigma }}^{*}\mid \mathrm{\exists }\alpha \gamma \in (N\cup \mathrm{\Sigma }{)}^{*}mitS\underset{l}{\overset{*}{\Rightarrow }}\alpha \beta \gamma undw\in firs{t}_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=(\{S,A\},\{\epsilon ,a,b\},P,S)$ und die Menge der Produktionen ist

$S\to aAaaS\to bAbaA\to \epsilon A\to b$

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

	$firs{t}_1$	$firs{t}_2$	$firs{t}_3$	$follo{w}_1$	$follo{w}_2$	$follo{w}_3$
$S$	$\{a,b\}$	$\{aa,ab,bb\}$	$\{aaa,aba,bba,bbb\}$	$\left\{\epsilon \right\}$	$\left\{\epsilon \right\}$	$\left\{\epsilon \right\}$
$A$	$\{\epsilon ,b\}$	$\{\epsilon ,b\}$	$\{\epsilon ,b\}$	$\{a,b\}$	$\{aa,ba\}$	$\{aa,ba\}$

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 \epsilon$ mit $A\to b$ verglichen.

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

	$k=1$	$k=2$	$k=3$
$firs{t}_k(\{\epsilon \}follo{w}_k(A))$	$\{a,b\}$	$\{aa,ba\}$	$\{aa,ba\}$
$firs{t}_k(\{b\}follo{w}_k\left(A\right))$	$\left\{b\right\}$	$\{ba,bb\}$	$\{baa,bba\}$

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)