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 ${\displaystyle \mathrm {LR} (k)}$-Grammatik, wenn jeder Reduktionsschritt eindeutig durch ${\displaystyle 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 ${\displaystyle k}$ Symbole der Eingabe bestimmt werden.

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

${\displaystyle {\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 ${\displaystyle G=\left(N,\Sigma ,P,S\right)}$ ist ${\displaystyle \mathrm {LR} \left(k\right)}$-Grammatik genau dann, wenn für alle Rechtsreduktionen der Form

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

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

${\displaystyle \alpha =\gamma }$, ${\displaystyle A=B}$ sowie ${\displaystyle \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).