297
правок
Изменения
→Определение
|id=def_LR_K
|definition=
Пусть <tex>\Gamma' =\langle \Sigma', N', E_0, P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> является '''LR(k)-грамматикой''', если из того, что для любых двух [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Лево-_и_правосторонний_вывод_слова|правосторонних выводов]]верно, что:
* <tex>E_0 \Rightarrow^* \beta A t z \Rightarrow \beta \alpha t z \Rightarrow^* w, </tex> если <tex>|t|=k</tex> или <tex>|t|<k, |z|=0 (z = \varepsilon)</tex>
* <tex>E_0 \Rightarrow^* \gamma B t z' \Rightarrow \gamma \xi t z' \Rightarrow^* w', </tex> если <tex>|t|=k</tex> или <tex>|t|<k, |z'|=0 (z' = \varepsilon)</tex>
}}
Говоря неформально, мы делаем правостороннюю свёртку нашей строки в стартовый нетерминал. Если по не более чем <tex>k</tex> символам неразобранной части строки мы можем однозначно определить, во что сворачивается хвост выведенного правила, то грамматика будет LR(k).
LR(k) означает, что
* входная цепочка обрабатывается слева направо (англ. ''left-to-right parse'');,* выполняется правый вывод (англ. ''rightmost derivation'');,
* не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
