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.
Eine kontextfreie Grammatik
ist genau dann eine LF(k)-Grammatik, wenn für alle Linksableitungen der Form
|
|
|
|
|
mit
und
gilt
.
Für die in der Definition benutzte Funktion zur Bestimmung der first-Mengen gilt:
![{\displaystyle a\in \Sigma ^{*};|a|\leq k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/36da32ba1f04f971871477174686cfb5489bcac7) |
|
![{\displaystyle a\in \Sigma ^{*};|a|>k}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4048cc92b89492a9c0c4e8a39e2f1429071eebfa) |
|
![{\displaystyle A\in (N\cup \Sigma )^{*}\backslash \Sigma ^{*}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bc3b1d10cadfe39c92f68f7161e5e1f3f595e5f) |
|
![{\displaystyle {\mathcal {A}}\in 2^{(N\cup \Sigma )^{*}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5fa1c2519b94a0008e35a960da6bf9653fd017c4) |
|
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.
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
und
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
benötigt, die die Menge aller A folgenden Symbole berechnet.
![{\displaystyle \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 )\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/23809ef0c09e1b01050274426c19a478d44e5d7b)
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.
Die Grammatik
soll auf ihre LF(k)-Eigenschaft hin untersucht werden. Mit anderen Worten: Für welches k ist G eine LF(k)-Grammatik?
und die Menge der Produktionen ist
![{\displaystyle S\to aAaa\quad S\to bAba\quad A\to \varepsilon \quad A\to b}](https://wikimedia.org/api/rest_v1/media/math/render/svg/98c362107e7dfe3db5641cb0025e6599e41e6a4c)
Zunächst werden die first- bzw. follow-Mengen der Nichtterminalsymbole bestimmt.
|
![{\displaystyle first_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5e42aa90cd15cbcad1b657483d081801a72497f3) |
![{\displaystyle first_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9931136426f1929e4740110c165fef071912f1d6) |
![{\displaystyle first_{3}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/83e560b70d2400814a60ffe57ba4138898a1b151) |
![{\displaystyle follow_{1}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a2ba32a5455dc1d3ae087c930104c9747f715449) |
![{\displaystyle follow_{2}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e10e01be94666862ed55d59454210262f7240524) |
|
![{\displaystyle S}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4611d85173cd3b508e67077d4a1252c9c05abca2) |
![{\displaystyle \left\{a,b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7bac9672293209127a0494d74b2bcbcc547a630d) |
![{\displaystyle \left\{aa,ab,bb\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d1070d95fbf239c867e3455724a5dc045c222985) |
![{\displaystyle \left\{aaa,aba,bba,bbb\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d802e230763b70dce1d28d49087c23ae88de3e7) |
![{\displaystyle \left\{\varepsilon \right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e30ac972fd222442f77a1329b0c1042cdf09a445) |
![{\displaystyle \left\{\varepsilon \right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e30ac972fd222442f77a1329b0c1042cdf09a445) |
|
![{\displaystyle A}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7daff47fa58cdfd29dc333def748ff5fa4c923e3) |
![{\displaystyle \left\{\varepsilon ,b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7f7c10e45111d36bf1e58a6236a1e473a35168b) |
![{\displaystyle \left\{\varepsilon ,b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7f7c10e45111d36bf1e58a6236a1e473a35168b) |
![{\displaystyle \left\{\varepsilon ,b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e7f7c10e45111d36bf1e58a6236a1e473a35168b) |
![{\displaystyle \left\{a,b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7bac9672293209127a0494d74b2bcbcc547a630d) |
![{\displaystyle \left\{aa,ba\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df52ca9bda7a96ff499a6ac8a3dba87288fc2549) |
|
Es folgt der Vergleich der wie oben definierten Mengen für alle Produktionen mit gleichen linken Regelseiten. In diesem Beispiel werden somit die Regeln
mit
und
mit
verglichen.
Im Fall des Nichtterminalsymbols S sind schon für
die Mengen
und
disjunkt. Weitere Betrachtungen für größere k können entfallen.
|
![{\displaystyle k=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c035ffa69b5bca8bf2d16c3da3aaad79a8bcbfa) |
![{\displaystyle k=2}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0bd301789e1f25a3da4be297ff637754ebee5f5d) |
|
![{\displaystyle first_{k}(\{\varepsilon \}follow_{k}(A))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/94ca8a4a08a7d9bb9fc7f8e0384f370274d5e011) |
![{\displaystyle \left\{a,b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7bac9672293209127a0494d74b2bcbcc547a630d) |
![{\displaystyle \left\{aa,ba\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df52ca9bda7a96ff499a6ac8a3dba87288fc2549) |
|
![{\displaystyle first_{k}(\{b\}follow_{k}\left(A\right))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d497a8bac9cfce0d3e616c90f8bd58a76726109e) |
![{\displaystyle \left\{b\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/6c519fbf05a860943857bb267f73c2ef944302e7) |
![{\displaystyle \left\{ba,bb\right\}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/06bd4bbef8c38b82efe3f571ed39632ef8dd1e1a) |
|
Erst für
sind die zu vergleichenden Mengen disjunkt und damit die deterministische Regelauswahl gewährleistet. Die Beispielgrammatik G ist also eine LF(3)-Grammatik.