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.
<math>\mathcal L(\mathrm{LF}(1)) \subsetneq \mathcal L(\mathrm{LF}(2)) \subsetneq \dots \subsetneq \mathcal L(\mathrm{PDA}) </math>
Formale Definition LF(k)-Grammatik
Eine kontextfreie Grammatik <math> G = (N,\Sigma,P,S) </math> ist genau dann eine LF(k)-Grammatik, wenn für alle Linksableitungen der Form
| <math>wA\gamma \Rightarrow_l w\alpha\gamma \Rightarrow^*_l wx</math> | |
| <math>S \Rightarrow^*_l</math> | |
| <math>w'A\gamma' \Rightarrow_l w'\beta\gamma' \Rightarrow^*_l w'y</math> |
mit <math>w,w',x,y \in \Sigma^*; \alpha, \beta, \gamma, \gamma' \in (N \cup \Sigma)^*; A \in N</math> und <math> first_k\left(x\right) = first_k(y) </math> gilt <math> \alpha = \beta </math>.
Für die in der Definition benutzte Funktion zur Bestimmung der first-Mengen gilt:
| a|\le k</math> | <math>\mathit{first}_k\left(a\right)=\{a\}</math> |
| a|>k</math> | v|=k\}</math> |
| <math>A \in (N\cup\Sigma)^* \backslash \Sigma^*</math> | <math>\mathit{first}_k(A)=\{v \in \Sigma^ * \mid A \Rightarrow^* w;w \in \Sigma^ *; \mathit{first}_k(w)=\{v\}\}</math> |
| <math>\mathcal{A} \in 2^{(N \cup \Sigma)^*}</math> | <math>\mathit{first}_k(\mathcal{A})=\{w \in first_k(\alpha) \mid \alpha \in \mathcal{A}\}</math> |
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 <math>A</math> und für alle Produktionen <math>A \to \beta</math> und <math>A \to \gamma</math> mit <math>\beta \ne \gamma</math> gilt: <math>first_k(\{\beta\}follow_k(A)) \cap first_k(\{\gamma\}follow_k(A))=\emptyset</math>.
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 <math>A \to \beta</math> und <math>A \to \gamma</math> 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 <math>follow_k \left( A \right)</math> benötigt, die die Menge aller A folgenden Symbole berechnet.
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 <math>G</math> soll auf ihre LF(k)-Eigenschaft hin untersucht werden. Mit anderen Worten: Für welches k ist G eine LF(k)-Grammatik?
- <math> G=\left(\{S,A\},\{\varepsilon,a,b\},P,S\right) </math> und die Menge der Produktionen ist
- <math> S \to aAaa \quad S \to bAba \quad A \to \varepsilon \quad A \to b </math>
Zunächst werden die first- bzw. follow-Mengen der Nichtterminalsymbole bestimmt.
| <math> first_1 </math> | <math> first_2 </math> | <math> first_3 </math> | <math> follow_1 </math> | <math> follow_2 </math> | <math> follow_3 </math> | |
| <math>S</math> | <math>\left\{a,b\right\}</math> | <math>\left\{aa,ab,bb\right\}</math> | <math>\left\{aaa,aba,bba,bbb\right\}</math> | <math>\left\{\varepsilon\right\}</math> | <math>\left\{\varepsilon\right\}</math> | <math>\left\{\varepsilon\right\}</math> |
| <math>A</math> | <math>\left\{\varepsilon,b\right\}</math> | <math>\left\{\varepsilon,b\right\}</math> | <math>\left\{\varepsilon,b\right\}</math> | <math>\left\{a,b\right\}</math> | <math>\left\{aa,ba\right\}</math> | <math>\left\{aa,ba\right\}</math> |
Es folgt der Vergleich der wie oben definierten Mengen für alle Produktionen mit gleichen linken Regelseiten. In diesem Beispiel werden somit die Regeln <math>S \to aAaa</math> mit <math>S \to bAba</math> und <math>A \to \varepsilon</math> mit <math>A \to b</math> verglichen.
Im Fall des Nichtterminalsymbols S sind schon für <math>k=1</math> die Mengen <math>first_1(\left\{aAaa\right\}follow_1(S))=\{a\}</math> und <math>first_1(\left\{bAba\right\}follow_1(S))=\{b\}</math> disjunkt. Weitere Betrachtungen für größere k können entfallen.
| <math> k=1 </math> | <math> k=2 </math> | <math> k=3 </math> | |
| <math>first_k(\{\varepsilon\}follow_k(A))</math> | <math>\left\{a,b\right\}</math> | <math>\left\{aa,ba\right\}</math> | <math>\left\{aa,ba\right\}</math> |
| <math>first_k(\{b\}follow_k\left(A\right))</math> | <math>\left\{b\right\}</math> | <math>\left\{ba,bb\right\}</math> | <math>\left\{baa,bba\right\}</math> |
Erst für <math>k=3</math> 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)