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

S$\displaystyle \to_{R}^{*}$uTv$\displaystyle \to_{R}^{}$uwv      
S$\displaystyle \to_{R}^{*}$u'T'v'$\displaystyle \to_{R}^{}$uwv',      

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



Johannes Waldmann 2008-01-24