LR(k)-Grammatiken

Für k $\in$ $\mathbb {N}$:

LR(k) ist die Menge aller CFG G, bei denen im angegebenen Automaten durch Vorausschau um k Zeichen die auszuführende Regel (reduce) eindeutig bestimmt ist.

Definition:

Für alle Paare von Rechtsableitungen

$$\to_{R}^{*} \to_{R}^{}$$

$$\to_{R}^{*} \to_{R}^{}$$

bei denen v und v' bis zur Länge k übereinstimmen,
gilt u = u', T = T', v = v'