297
правок
Изменения
→LR(k)-грамматика
Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора|контекстно-свободная]] грамматика. '''Пополненной грамматикой''' (англ. ''augmented grammar''), полученной из <tex>\Gamma</tex>, назовем грамматику <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex>, где <tex>\Sigma' = \Sigma; N' = N \cup \{S'\}; S' \notin N; P' = P \cup \{S' \to S\}</tex>
}}
Использование в определении LR(k)-грамматики пополненной грамматики существенно для однозначного определения конца анализа. Действительно, если грамматика использует <tex>S</tex> в правых частях правил, то свертка основы в <tex>S</tex> не может служить сигналом приема входной цепочки. Свертка же в <tex>S'</tex> в пополненной грамматике служит таким сигналом, поскольку <tex>S'</tex> нигде, кроме начальной сентенциальной формы, не встречается.
// TODO сделать пример, когда нам точно нужно пополнять грамматику
{{Определение
|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^* \alpha A w \Rightarrow \alpha \beta w </tex>,
* <tex>S' \Rightarrow^* \gamma B x \Rightarrow \alpha \beta y </tex>,
* зная цепочку <tex>\alpha \beta = X_1 X_2 ... X_r</tex> и не более <tex>k</tex> символов цепочки <tex>w</tex>, мы можем быть уверены, что именно <tex>\beta</tex> является основой, сворачиваемой в нетерминал <tex>A</tex>;
* если <tex>\alpha_{i-1} = S'</tex>, можно сигнализировать о выводимости исходной терминальной цепочки из <tex>S'</tex> и, следовательно, из <tex>S</tex>.
== LR(k)-Разбор ==
