LR(k)-Grammatik

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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 -Grammatik, wenn jeder Reduktionsschritt eindeutig durch 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 Symbole der Eingabe bestimmt werden.

Ein Unterschied der Sprachklasse, die mit -Grammatiken beschrieben werden kann, zeigt sich nur für die beiden Fälle und . Die Ausdrucksstärke von kontextfreien Grammatiken wird von nicht erreicht. Damit gibt es für alle kontextfreie Grammatiken, zu denen es keine äquivalente -Grammatiken gibt, zum Beispiel eine inhärent mehrdeutige Sprache. Man nennt die durch -Grammatiken definierte Sprachklasse auch deterministisch kontextfreie Sprachen.

(DPDA = Deterministic Push-Down Automaton, PDA = Push-Down Automaton)

Formale Definition LR(k)-Grammatik

[Bearbeiten | Quelltext bearbeiten]

Eine kontextfreie Grammatik ist -Grammatik genau dann, wenn für alle Rechtsreduktionen der Form

mit und gilt:

, sowie