|style="background-color:#FFF;padding:2px 20px"| <tex>r(4)</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>\to</tex> u
I += [X <tex>\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>\to</tex> w.Xv] из I
J += [A <tex> \to </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 = {}
T = {closure ([S' <tex>\to</tex> .S])}
'''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>\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>.
== Пример LR(0)-разбора ==
