297
правок
Изменения
Нет описания правки
== LR(k)-грамматика ==
=== Определение ===
{{Определение
|id=def_augmented_grammar)
|id=def_LR_K
|definition=
Пусть <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> явяется является '''LR(k)-грамматикой''', если для любых двух [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Лево-_и_правосторонний_вывод_слова|правосторонних выводов]]:
* <tex>S' \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>S' \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> символов цепочки (англ. ''k-token lookahead'') используются для принятия решения.
====Замечание о попролненной пополненной грамматике====
Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>S</tex> в правых частях правил, то свертка основы в <tex>S</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'</tex> нигде, кроме начальной сентенциальной формы, не встречается.
Существенность использования пополненной грамматики в определении LR(k)-грамматик продемонстрируем на следующем конкретном примере. Пусть пополненая пополненная грамматика имеет следующие правила:
<tex>
Управляющая программа одинакова для всех LR-анализаторов, а таблица и автомат изменяются от одного анализатора к другому.
Для запоминания строки запись в стек имеет вид: <tex>s_0X_1s_1X_2...X_ms_m</tex>, где <tex>s_m</tex> {{---}} вершина стека. Каждый <tex>X_i</tex> {{---}} символ грамматики(терминал или нетерминал), а <tex>s_i</tex> {{---}} состояние автомата. Каждое состояние суммирует информацию, cодержащуюся в стеке перед ним. <tex>s_0</tex> {{---}} стартовае стартовое состояние автомата.
Обращение к таблице происходит слудующим следующим образом <tex>\mathtt{T[state, token]}</tex>, где
*<tex>\mathtt{state}</tex> {{---}} состояние автомата,
*<tex>\mathtt{token}</tex> {{---}} входной символ;
=== Алгоритм ===
# Программа читает символ из входной цепочки.
# Обращается к утравляющей управляющей таблице.
# Совершает соответствующее действие.
# Возвращается к первому пункту, пока входная цепочка не закончится.
<font size=2>
'''Result''' algorithmLR(w: '''string''')
curToken {{---}} указатель на перый первый символ в строке w
'''while''' haveToken()
curState = top()
