SLL(k)-Grammatik

Eine SLL(k)-Grammatik (auch starke LL(k)-Grammatik) ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines SLL(k)-Parsers bildet. Sie ist eine besondere Form der LL(k)-Grammatik. Im Gegensatz zu dieser kann für eine aus der Grammatik ableitbare Terminalfolge allein durch die nächsten k-Symbole der Terminalfolge (Lookahead) – ohne Berücksichtigung der vorhergegangenen Zeichen – die nächste Produktion der Produktionsfolge, die die Terminalfolge erzeugt, eindeutig gewählt werden.

Formale Definition SLL(k)-Grammatik

Eine kontextfreie Grammatik $G=(N,\Sigma ,P,S)$ ist genau dann eine starke LL(k) Grammatik für festes k > 0, wenn für beliebige Ableitungen der Form

{\begin{aligned}&S\Rightarrow _{l}^{*}\mu A\chi \Rightarrow \omega \alpha \chi \Rightarrow ^{*}\omega \gamma \\&S\Rightarrow _{l}^{*}\mu 'A\chi '\Rightarrow \omega '\beta \chi '\Rightarrow ^{*}\omega '\gamma '\end{aligned}}

mit $\mu ,\mu ',\omega ,\omega ',\gamma ,\gamma '\in \Sigma ^{*},\alpha ,\beta ,\chi ,\chi '\in (\Sigma \cup N)^{*},A\in N$ und $k:\gamma =k:\gamma '$ gilt: $\alpha =\beta ^{\,}$

Dabei ist $k:\delta ={\begin{cases}\delta \#,&{\text{falls}}\;|\delta |<k\\\kappa ,&{\text{falls}}\;\delta =\kappa \eta \;{\text{und}}|\kappa |=k\end{cases}}$

mit Sentinel $\#$ .

Es lässt sich zeigen, dass jede LL(1)-Grammatik auch eine SLL(1)-Grammatik ist. Für allgemeine $k$ ist dies aber nicht der Fall.

Alternatives Kriterium

Der formale Nachweis der Gültigkeit obiger Definition für eine beliebige SLL(k)-Grammatik ist oft schwierig, weshalb hier ein alternatives Kriterium für eine SLL(k)-Grammatik vorgestellt wird.

Dafür seien zunächst

${\begin{aligned}{\text{first}}_{k}(\omega )&=\{\tau \,|\,\exists \nu \in \Sigma ^{*}\,{\text{mit}}\,\omega \Rightarrow ^{*}\nu ,\,\tau =k:\nu \}\\{\text{follow}}_{k}(\omega )&=\{\tau \,|\,\exists \nu \in (\Sigma \cup N)^{*}{\text{mit}}\,S\Rightarrow ^{*}\mu \omega \nu ,\tau \in {\text{first}}_{k}(\nu )\}\end{aligned}}$

die First- und Followmengen. Eine intuitive Erklärung für die Firstmenge ist, dass diese für die gegebene Zeichenfolge $\omega$ die ersten k Terminale, die sich aus $\omega$ ableiten lassen, enthält. Die Followmenge hingegen enthält diejenigen Terminale, die bei einer Produktionsfolge die $\omega$ ausgehend vom Startterminal erzeugt, nach $\omega$ folgen können.

Mit den First- und Followmengen lässt sich nun das Kriterium definieren:

Eine Grammatik ist genau dann eine SLL(k)-Grammatik, wenn paarweise für alle Produktionen der Form $A\rightarrow \alpha \,|\,\beta ,\quad \alpha \neq \beta$ gilt:

${\text{first}}_{k}(\alpha \,{\text{follow}}_{k}(A))\cap {\text{first}}_{k}(\beta \,{\text{follow}}_{k}(A))=\emptyset$

Dabei ist die Followmenge nur relevant, falls es sich bei der entsprechenden Ableitung um eine $\varepsilon$ -Ableitung handelt.

Auch hier findet sich eine intuitive Erklärung: Der Schnitt beider Mengen stellt gerade die Terminalsequenzen der Länge $k$ dar, die nach der Ableitung von $A$ aus beiden Produktionen erzeugt werden können. Wenn aber nun ein Parser den aktuellen Terminalstrom verarbeitet, muss sich dieser deterministisch für eine Produktion entscheiden. Dies kann er aber nicht wenn der gleiche Zeichenstrom aus mehreren Produktionen generiert werden kann. Genau diese Situation wird durch obige Definition verhindert: unabhängig vom vorhergegangenen Zeichen $\mu$ bzw. $\mu '$ ist die nächste Produktion eindeutig. Ein Parser braucht somit bereits gelesene Zeichen nicht nochmals zu betrachten.

Siehe auch

Literatur

Waite, W., & Goos, G. (1984). Compiler Construction. New York, USA: Springer-Verlag, ISBN 0-387-90821-8.