LR(k)-Grammatik
# 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$

$\beta =\delta$

