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{L}\mathrm{R}(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{L}\mathrm{R}(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{L}\mathrm{R}(1)$ nicht erreicht. Damit gibt es für alle $k\in \mathbb{N}$ kontextfreie Grammatiken, zu denen es keine äquivalente $\mathrm{L}\mathrm{R}(k)$-Grammatiken gibt, zum Beispiel eine inhärent mehrdeutige Sprache. Man nennt die durch $\mathrm{L}\mathrm{R}(k)$-Grammatiken definierte Sprachklasse auch deterministisch kontextfreie Sprachen.

$ℒ(\mathrm{L}\mathrm{R}(0))⊊ℒ(\mathrm{L}\mathrm{R}(1))=ℒ(\mathrm{L}\mathrm{R}(2))=\cdots =ℒ(\mathrm{D}\mathrm{P}\mathrm{D}\mathrm{A})⊊ℒ(\mathrm{P}\mathrm{D}\mathrm{A})$ (DPDA = Deterministic Push-Down Automaton, PDA = Push-Down Automaton)

Formale Definition LR(k)-Grammatik

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

$\alpha \beta w$	${\Leftarrow }_r\alpha Aw$	$\underset{r}{\overset{*}{\Leftarrow }}$
			$S$
$\gamma \delta x$	${\Leftarrow }_r\gamma Bx$	$\underset{r}{\overset{*}{\Leftarrow }}$

mit

$w,x\in {\mathrm{\Sigma }}^{*};\alpha ,\beta ,\gamma ,\delta \in (N\cup \mathrm{\Sigma }{)}^{*};A,B\in N$

und

$firs{t}_{|\alpha \beta |+k}(\alpha \beta w)=firs{t}_{|\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).