LR(k)-Grammatik
aus Wikipedia, der freien Enzyklopädie
Dieser Artikel setzt Vorkenntnisse im Bereich Theoretische Informatik und Compilerbau voraus.
Eine LR(k)-Grammatik ist eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR(k)-Parsers bildet.
Man nennt eine kontextfreie Grammatik LR(k)-Grammatik, wenn jeder Reduktionsschritt eindeutig durch k Symbole der Eingabe (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 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 LR(1) nicht erreicht. Damit gibt es kontextfreie Grammatiken, die für kein k LR(k)-Grammatiken sind, zum Beispiel die inhärent mehrdeutigen Sprachen. Man nennt die durch LR(k)-Grammatiken definierte Sprachklasse auch deterministisch kontextfreie Sprachen.
(DPDA = Deterministic Push-Down Automaton, PDA = Push-Down Automaton)
[Bearbeiten] Formale Definition LR(k)-Grammatik
Eine kontextfreie Grammatik G = (N,Σ,P,S) ist LR(k)-Grammatik genau dann, wenn für alle Rechtsreduktionen der Form
| αβw |  |
 |
|
| S | |||
| γδx |  |
|
mit 
und first | αβ | + k(αβw) = first | αβ | + k(γδx) gilt:
[Bearbeiten] Siehe auch
[Bearbeiten] Literatur
- Donald E. Knuth: Syntactic Algorithms. Band 5 von The Art of Computer Programming.
