LF(k)-Grammatik
# 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.

