Изменения

Пусть <tex>\Gamma' =\langle \Sigma', N', S', P' \rangle</tex> {{---}} пополненная грамматика для КС-грамматики <tex>\Gamma</tex>. Грамматика <tex>\Gamma</tex> явяется '''LR(k)-грамматикой''', если для любых двух [[Контекстно-свободные_грамматики,_вывод,_лево-_и_правосторонний_вывод,_дерево_разбора#Лево-_и_правосторонний_вывод_слова|правосторонних выводов]] вида:* <tex>S' \Rightarrow^* \alpha beta A w t z \Rightarrow \beta \alpha t z \beta Rightarrow^* w , </tex> если <tex>|t|=k</tex>или <tex>|t|<k,|z|=0 (z = \varepsilon)</tex>* <tex>S' \Rightarrow^* \gamma B x t z' \Rightarrow \alpha gamma \xi t z' \beta y Rightarrow^* w', </tex>,в которых если <tex> |t|<k \mathrm{FIRST}_k(w) Rightarrow z= \mathrm{FIRST}_k(y)varepsilon </tex> верно, должно быть что <tex>\alpha A y gamma \xi = \gamma B xbeta \alpha</tex>. Другими словами,  следует, что <tex>\alpha beta = \gamma, </tex> и <tex>A=B, y=x </tex>.

Говоря неформально, если согласно первому выводу <tex>\beta</tex> {{---}} основа, сворачиваемая Существенность использования пополненной грамматики в нетерминал <tex>A</tex>, то и во втором выводе <tex>\beta</tex> должна быть основой, сворачиваемой в нетерминал <tex>A</tex>.Из этого определения следует, что если имеется правовыводимая цепочка <tex>\alpha_i = \alpha \beta w</tex>, где <tex>\beta</tex> {{---}} основа, полученная из <tex>A</tex>, и если <tex>\alpha \beta = X_1 X_2 ... X_r</tex>, то* зная первые символы <tex>X_1 X_2 ... X_j</tex> цепочки <tex>\alpha \beta</tex> и не более, чем <tex>k</tex> следующих символов цепочки <tex>X_{j+1} X_{j+2} ... X_r w</tex>, мы можем быть уверены, что правый конец основы не будет достигнут до тех пор, пока <tex> j \ne r</tex>;* зная цепочку <tex>\alpha \beta = X_1 X_2 ... X_r</tex> и не более <tex>определении LR(k</tex> символов цепочки <tex>w</tex>, мы можем быть уверены, что именно <tex>\beta</tex> является основой, сворачиваемой в нетерминал <tex>A</tex>;* если <tex>\alpha_{i)-1} = S'</tex>, можно сигнализировать о выводимости исходной терминальной цепочки из <tex>S'</tex> и, следовательно, из <tex>S</tex>.грамматик продемонстрируем на следующем конкретном примере:

// --- TODO end---