LF(k)-Grammatik

aus Wikipedia, der freien Enzyklopädie

Du hast neue Nachrichten (Unterschied zur vorletzten Version).

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, daß 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 ersten k Symbole der Eingabe beantwortet werden.

Generell gilt, je größer k gewählt wird, um so 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})$

[Bearbeiten] 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}\}$

[Bearbeiten] Anwendung

Die formale Definition einer LF(k)-Grammatik ist bezüglich praktischer Anwendung nur mit großem Aufwand realisierbar. Daher erfolgt die Prüfung auf LF(k)-Eigenschaft mithilfe eines abgewandelten Ansatzes.

Eine reduzierte kontextfreie Grammatik ist LF(k)-Grammatik genau dann, wenn für alle Nichtterminalsymbole A, 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.

[Bearbeiten] 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.

	$f i r s t 1$	$f i r s t 2$	$f i r s t 3$	$f o l l o w 1$	$f o l l o w 2$	$f o l l o w 3$
$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$
$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.