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

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

<math>\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})</math> (DPDA = Deterministic Push-Down Automaton, PDA = Push-Down Automaton)

Formale Definition LR(k)-Grammatik

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

<math>\alpha\beta w</math>	<math>\Leftarrow_r \alpha A w</math>	<math>\Leftarrow_r^*</math>
			<math>S</math>
<math>\gamma\delta x</math>	<math>\Leftarrow_r \gamma B x</math>	<math>\Leftarrow_r^*</math>

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

<math>\alpha=\gamma</math>, <math>A = B</math> sowie <math>\beta=\delta</math>

Siehe auch

Weblinks

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