Изменения

Каждое состояние автомата будет состоять из LR(k0)-ситуаций.

|id=def_LRk_itemdef_LR0_item)

Пусть <tex>\Gamma =\langle \Sigma, N, S, P \rangle</tex> {{---}} КС-грамматика и <tex>A \to w_1 w_2 \in P</tex>. Композицию <tex>[A \to w_1 \cdot w_2, u] </tex>, где <tex>u \in \Sigma^{k}</tex>, назовем '''LR(k0)-ситуацией''' (англ. ''LR(k0)-item'')

LR(0)-ситуации не должны содержать терминальной В начале работы стек пуст, и указатель входной цепочки, так как <tex>k=0</tex>, то есть мы можем записывать их следующим образом: <tex>[A \to w_1 \cdot w_2]</tex>находится перед ее первым символом.Стартовому Этому состоянию соответствует ситуация <tex>[E_0 \to \cdot E]</tex>, где <tex>E_0</tex> {{---}} нетерминал, добавленный при пополнении грамматики, <tex>E</tex> {{---}} стартовый нетерминал. Далее Наховем это состояние <tex>0</tex>. Входная цепочка может начинаться с любого терминального символа, с которого начинается правая часть любого правила с левой частью <tex>E</tex>. Построим соответствующий переход: <tex>{[} A \to \alpha \cdot B \beta] \xrightarrow{\varepsilon} {[} B \to \cdot \gamma] </tex> Теперь мы должны выяснить, что произойдет, если анализатор выполнит перенос. Предположим, что мы строим переходы к другим ситуациям по следующей схемевыполним перенос <tex>c</tex> или перенос <tex>B</tex>:

Таким образом, мы определяем новые состояния, в которое автомат перейдет после переноса того или иного терминала или нетерминала. Заметим, что хранить в каждом состоянии только по одной ситуации не имеет смысла, поэтому пусть в каждое стостояние будет представлять множество ситуаций. Для этого определим базовые операции <tex>closure (I)</tex> и <tex>goto (I, X)</tex>, где <tex>I</tex> – множество ситуаций, <tex>X</tex> – символ грамматики (терминал или нетерминал). Операция <tex>closure</tex> добавляет ситуации к множеству ситуаций, у которых точка стоит слева от нетерминала. Добавляются те ситуации, которые получаются из правил, в левой части которого находится этот нетерминал. {| border="0" |align="left" colspan="4"|<font size=2> [] '''closure''' (I) '''do''' '''for''' каждой ситуации [} A <tex>\to </tex> w.Xv] из I '''for''' каждого правила грамматики X <tex>\alpha to</tex> u I += [X <tex>\cdot B to</tex> .u] <font color=green> // Операция += добавляет элемент к множеству </font> '''while''' I изменилось '''return''' I </font>|}  Операция <tex>goto</tex> "переносит" точку после символа <tex>X</tex>. Это означает переход из одного состояния в другое под воздействием символа <tex>X</tex>. {| border="0" |align="left" colspan="4"|<font size=2> [] '''goto''' (I, X) J={} <font color=green> // {} обозначает пустое множество </font> '''for''' каждой ситуации [A <tex>\betato</tex> w.Xv] из I J += [A <tex> \xrightarrowto </tex>wX.v] '''return''' closure (J)</font>|} === Алгоритм построения конечного автомата ===Теперь обсудим алгоритм построения анализатора. Обозначим <tex>T</tex> множество состояний, <tex>E</tex> – множество переходов. {| border="0" |align="left" colspan="4"|<font size=2> E, T '''build'''() E = {\varepsilon} T = {closure ([S' <tex>\to</tex> .S])} B '''do''' '''for''' каждого состояния I из T '''for''' каждой ситуации [A <tex>\to </tex> w.Xv] из I J = goto(I, X) T += {J} <font color=green> // ко множеству состояний добавляется новое состояние </font> E += (I <tex>\cdot \gamma] to</tex>J) <font color=green> // ко множеству ребер добавляется ребро, идущее из состояния I в состояние J. Этот переход осуществляется по символу X </font> '''while''' E или T изменились '''return''' E, T</font>|}

Получаем [[Недетерминированные конечные автоматы|НКА]]Поскольку для символа <tex>\$</tex> операция <tex>goto(I , \$)</tex> не определена , мы выполняем действие <tex>accept</tex>.