LR(k)-Grammatik

(Weitergeleitet von LR(k))

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

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

     
 
     

mit   und   gilt:

 ,   sowie  

Siehe auch

Bearbeiten
Bearbeiten