297
правок
Изменения
→LR(k)-грамматика
}}
Говоря неформально, мы делаем правостороннюю свёртку нашей строки в стартовый нетерминал. Если по не более чем <tex>k</tex> символам неразобранной строки мы можем однозначно определить, во что сворачивается хвост выведенного правила, то грамматика будет LR(k).
LR(k) означает, что
* выполняется правый вывод (англ. ''rightmost derivation'');
* не более <tex>k</tex> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
====Замечание о попролненной грамматике====
Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>S</tex> в правых частях правил, то свертка основы в <tex>S</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'</tex> нигде, кроме начальной сентенциальной формы, не встречается.
Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненая грамматика имеет следующие правила:
<tex>
S' \to S \\
S \to Sa \\
S \to a \\
</tex>
== LR-разборщик ==
