LR(k)-Grammatik

In der theoretischen Informatik und dem Compilerbau bezeichnet LR(k)-Grammatik eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR-Parsers bildet.

Man nennt eine kontextfreie Grammatik $\mathrm {LR} (k)$-Grammatik, wenn jeder Reduktionsschritt eindeutig durch $k$ Symbole der Eingabe (sogenannter Lookahead) bestimmt ist. Das bedeutet, die Frage, zu welchem Nichtterminalsymbol mit welcher Regel als nächstes reduziert werden soll, kann eindeutig mit Hilfe der nächsten $k$ Symbole der Eingabe bestimmt werden.

Ein Unterschied der Sprachklasse, die mit $\mathrm {LR} (k)$-Grammatiken beschrieben werden kann, zeigt sich nur für die beiden Fälle $k=0$ und $k>0$. Die Ausdrucksstärke von kontextfreien Grammatiken wird von $\mathrm {LR} (1)$ nicht erreicht. Damit gibt es für alle $k\in \mathbb {N}$ kontextfreie Grammatiken, zu denen es keine äquivalente $\mathrm {LR} (k)$-Grammatiken gibt, zum Beispiel eine inhärent mehrdeutige Sprache. Man nennt die durch $\mathrm {LR} (k)$-Grammatiken definierte Sprachklasse auch deterministisch kontextfreie Sprachen.

${\mathcal {L}}(\mathrm {LR} (0))\subsetneq {\mathcal {L}}(\mathrm {LR} (1))={\mathcal {L}}(\mathrm {LR} (2))=\cdots ={\mathcal {L}}(\mathrm {DPDA} )\subsetneq {\mathcal {L}}(\mathrm {PDA} )$ (DPDA = Deterministic Push-Down Automaton, PDA = Push-Down Automaton)

Formale Definition LR(k)-Grammatik

Eine kontextfreie Grammatik $G=\left(N,\Sigma ,P,S\right)$ ist $\mathrm {LR} \left(k\right)$-Grammatik genau dann, wenn für alle Rechtsreduktionen der Form

$\alpha \beta w$	$\Leftarrow _{r}\alpha Aw$	$\Leftarrow _{r}^{*}$
			$S$
$\gamma \delta x$	$\Leftarrow _{r}\gamma Bx$	$\Leftarrow _{r}^{*}$

mit $w,x\in \Sigma ^{*};\alpha ,\beta ,\gamma ,\delta \in (N\cup \Sigma )^{*};A,B\in N$ und $first_{|\alpha \beta |+k}(\alpha \beta w)=first_{|\alpha \beta |+k}(\gamma \delta x)$ gilt:

$\alpha =\gamma$, $A=B$ sowie $\beta =\delta$

Siehe auch

• LL(k)-Grammatik
• LL-Parser

Weblinks

• LR(k)-Analyse für Pragmatiker, ausführliche Beschreibung der LR-Analyse und der Unterformen LR(0), SLR(1), LALR(1), LR(1).