Преобразование недетерминированною таблицу переходов в детерминированную

Преобразование рассмотрим на примере:

I -> I1 + T1
I -> T2
T -> (I3)
T -> i

ВПОСЛЕ(h0) = {I0, I1, T2, (, i }
ВПОСЛЕ(+) = {T1, (, i }
ВПОСЛЕ( ( ) = {I3, I1, T2, (, i }
ВПОСЛЕ( I3 ) = { ) }

	I	+	T	(	)	i
I1		+
I3					)
+			T1	(		i
T1
T2
(	I3,I0		T2	(		i
)
i
h0	I0,I1		T2	(		i

Заменяем I3,I0 на Iy, а I0,I1 на Ix.

Тогда:

I -> Iy + T1
I -> T2
T -> (Ix)
T -> i

	I	+	T	(	)	i
Iy		+
Ix		+			)
+			T1	(		i
T1
T2
(	Ix		T2	(		i
)
i
h0	Iy		T2	(		i

	+	(	)	i	Ik
Iy	П	П	П	П	Д
Ix	П	П	П	П	О
+	П	П	П	П	О
T1	С(1)	С(1)	С(1)	С(1)	С(1)
T2	С(2)	С(2)	С(2)	С(2)	С(2)
(	П	П	П	П	О
)	С(3)	С(3)	С(3)	С(3)	С(3)
i	С(4)	С(4)	С(4)	С(4)	С(4)
h0	П	П	П	П	О

Рассмотрим пример:

(i+i)+i	h0	П
i+i)+i	h0(	П
+i)+i	h0(i	C(4)
+i)+i	h0(T2	C(2)
i)+i	h0(Iy	П
i)+i	h0(Iy+	П
)+i	h0(Iy + i	C(4)
)+i	h0(Iy + T1	C(1)
)+i	h0(Ix	П
+i	h0(Ix)	С(3)
+i	h0T2	C(2)
+i	h0Iy	П
i	h0Iy+	П
Ik	h0Iy+i	C(4)
Ik	h0Iy+T1	C(1)
Ik	h0I0	Д

Пример:

I -> tA1
A -> A2, B2
A -> B3
B -> a
B -> b

	t	A	B	,	a	b	I
t		A1/A2	B3	,	a	b
A1
A2
,			B2		a	b
B2
B3
a
b
h0

Заменяем на:

I -> tAx
A -> Ax, B2
A -> B3
B -> a
B -> b

	t	A	B	,	a	b	I
t		Ax	B3		a	b
A1
A2
,			B2		a	b
B2
B3
a
b
h0	t

При построении управляющей таблицы, получим следующую ситуацию:

Так как в первом правиле Ax стоит последним, в строке Ax и во всех столбцах мы должны поставить свертку по первому правилу.При обращении ко второму правилу в строке Ax и в столице «,», мы должны поставить перенос. Так как не понятно, что выполнять при поступлении переноса (свертку или перенос). Следовательно, построить RR0 распознаватель невозможно.

RL(1) распознаватель строится следующим образов.

Переписываем правила грамматики, используя грамматические вхождения.
Находим функции ВПЕРВ, ВПОСЛЕ.
Строим таблицу переходов по правилам построения RR0 распознавателя.
Управляющая таблица строится следующим образом:
1. Для правых нетерминальных символов ищется функция СЛЕД. Функция след ищется для I0.
2. Для правила N. A -> aP. В столбцах x принадлежащих функции СЛЕД(А). Ставиться оператор свертка с номером правила.
3. Для всех грамматических вхождений не являющихся крайними грамматическими вхождением и столбцов x, ставиться оператор перенос. Операция перенос будет соответствовать операции перенос содержащих терминальные символы. I0 -> Д (допустить). Оставшиеся являются запрещенными.

	t	a	b	,	Ik
t		П	П
Ax
,		П	П
B2				С(2)	С(2)
B3				С(3)	С(3)
a				С(4)	С(4)
b				С(5)	С(5)
h0	П
I0
					Д

Дата добавления: