Построение таблицы переходов

Таблица переходов содержит строки равные всем грамматическим вхождениям, плюс начальный символ грамматики I с индексом ноли и H нулевое. В качестве столбцов таблицы используется терминальные и нетерминальные символы правил грамматики. Заполняется таблица следующим образом.

Если Xkl принадлежит функции ВПОСЛЕ(Yij), то на пересечении строки Yij и столбца X ставиться грамматическое вхождение Xkl. Таблица переходов задает функцию: f(Yij, X) = Xkl;

Пример:

Задана грамматика.

I0 -> a1 I12 I13 b1
I -> c2

ВПРЕВ(a1) = {a1}
ВПРЕВ(I12) = {I12, a1, c2}
ВПРЕВ(I13) = {I13, a1, c2}
ВПРЕВ(b1) = {b1}
ВПРЕВ(c2) = {c2}
ВПРЕВ(I0) = { I0, a1, c2}
ВПОСЛЕ(a1) = {I12, a1, c2}
ВПОСЛЕ(I12) = {I13, a1, c2}
ВПОСЛЕ(I13) = {b1}
ВПОСЛЕ(b1) = {$}
ВПОСЛЕ(c2) = {$}
ВПОСЛЕ(h0) = { I0, a1, c2}

	a	b	c	I
a1	a1		c2	I12
I12	a1		c2	I13
I13		b1
b1
c2
I0
h0	a1		c2	I0

При построения таблицы переходов в одной ячейке может оказаться несколько грамматических вхождений. Такая таблица называется недетерминированной и требует преобразование в детерминированную эквивалентную таблицу.

В основе построения управляющей таблицы лежат операции: свертка C(N) , перенос (P), допустить, отвергнуть или ошибка (О).
Управляющая таблица имеет строки равные грамматическим вхождения + I0+h0 и столбцы равные терминальным символам + символам конца строки. Заполняется таблица следующим образов.

Если строка помечена грамматическим вхождением, являющимся самым правым символом с номером N, то во всех столбцах ставиться операция свертка N.
Если строка помечена грамматическим вхождением I0, то на пересечении строки I0 и столбца конец строки ставится операция допустить.
Для столбцов, являющихся терминальными символами и строк, помеченными некрайными грамматическими вхождения, ставиться операция перенос. В оставшихся ячейках ставиться операция отвергнуть.

	a	b	c	$
a1	П	П	П	О
I12	П	П	П	О
I13	П	П	П	О
b1	С(1)	С(1)	С(1)	С(1)
c2	С(2)	С(2)	С(2)	С(2)
I0	О	О	О	Д
h0	П	П	П	О

Если при построение управляющей таблицы в каждой клеточки находится только одна буква или одно действие, то LR(0) распознаватель построить возможно. Проверка процесса распознавания:
$

aaccbcb$	h0	П
accbcb$	h0a1	П
ccbcb$	h0a1a1	П
cbcb$	h0a1a1c2	C(2)
cbcb$	h0a1a1I12	П
bcb$	h0a1a1I12C2	C(2)
bcb$	h0a1a1I12I13	П
cb$	h0a1a1I12I13b1	C(1)
cb$	h0a1I12	П
b$	h0a1I12с2	C(2)
b$	h0a1I12I13	П
$	h0a1I12I13b1	C(1)
$	h0I12