Wikipedia · einfach zusammengefasst · Stand
LR(k)-Grammatik
In der theoretischen Informatik und dem Compilerbau bezeichnet LR(k)-Grammatik eine spezielle kontextfreie Grammatik, welche die Grundlage eines LR-Parsers …
Grundidee
Eine LR(k)-Grammatik ist in der theoretischen Informatik und im Compilerbau eine spezielle kontextfreie Grammatik. Sie bildet die Grundlage eines LR-Parsers, also eines Verfahrens, das Eingaben deterministisch von links nach rechts analysiert und dabei Rechtsableitungen in umgekehrter Richtung nachvollzieht.
Eine kontextfreie Grammatik heißt LR(k)-Grammatik, wenn jeder Reduktionsschritt eindeutig durch k Symbole der Eingabe bestimmt ist. Diese nächsten k Symbole heißen Lookahead. Gemeint ist: Mit Hilfe der nächsten k Eingabesymbole lässt sich eindeutig entscheiden, zu welchem Nichtterminalsymbol und mit welcher Regel als Nächstes reduziert werden soll.
Sprachklasse
Bei der durch LR(k)-Grammatiken beschreibbaren Sprachklasse gibt es nur einen wesentlichen Unterschied zwischen den Fällen k=0 und k>0. Für k>0 haben LR(k)-Grammatiken dieselbe Ausdrucksstärke wie LR(1)-Grammatiken.
Die Ausdrucksstärke aller kontextfreien Grammatiken wird durch LR(1) nicht erreicht. Daher gibt es für alle k ∈ ℕ kontextfreie Grammatiken, zu denen keine äquivalente LR(k)-Grammatik existiert. Als Beispiel nennt der Artikel eine inhärent mehrdeutige Sprache.
Die durch LR(k)-Grammatiken definierte Sprachklasse heißt deterministisch kontextfreie Sprachen.
Einordnung durch Automaten
Die Beziehungen der Sprachklassen werden im Artikel so angegeben:
𝓛(LR(0)) ⊊ 𝓛(LR(1)) = 𝓛(LR(2)) = ··· = 𝓛(DPDA) ⊊ 𝓛(PDA)
Dabei bedeutet DPDA „Deterministic Push-Down Automaton“, also deterministischer Kellerautomat. PDA bedeutet „Push-Down Automaton“, also Kellerautomat. Die Formel sagt: LR(0) beschreibt echt weniger Sprachen als LR(1); LR(1), LR(2) und alle weiteren LR(k) mit k>0 beschreiben dieselbe Sprachklasse wie deterministische Kellerautomaten; diese Klasse ist echt kleiner als die Klasse aller Sprachen, die von Kellerautomaten beschrieben werden.
Formale Definition
Eine kontextfreie Grammatik G = (N, Σ, P, S) ist genau dann eine LR(k)-Grammatik, wenn für alle Rechtsreduktionen der im Artikel angegebenen Form gilt: Stimmen die ersten |αβ| + k Symbole von αβw und γδx überein, also first_|αβ|+k(αβw) = first_|αβ|+k(γδx), dann müssen auch die Bestandteile der Reduktion gleich sein.
Formal gilt unter den Bedingungen w, x ∈ Σ*, α, β, γ, δ ∈ (N ∪ Σ)* und A, B ∈ N: Aus der Übereinstimmung first_|αβ|+k(αβw) = first_|αβ|+k(γδx) folgt α = γ, A = B sowie β = δ.
Diese Definition drückt die Eindeutigkeit aus: Wenn zwei mögliche Rechtsreduktionen bei gleichem bisherigem Kontext und gleichem Lookahead nicht unterscheidbar wären, müssen sie tatsächlich dieselbe Reduktion sein.
