3.12.2. Пример построения lr(0)-распознавателя

В качестве иллюстрации применения описанной процедуры рассмотрим построение распознавателя для следующей грамматики:

Г _{3. 14} :1. <E>  <E₁> + <T₁>2. <E>  <T₂>3. <T>  (<E₃>)4. <T>  i

Функции ВПЕРВиВПОСЛЕдля этой грамматики имеют вид:

ВПЕРВ(<E1>)={<E1>,<T2>,(,i},	ВПОСЛЕ(<E1>) = {+},
ВПЕРВ(<T1>)={<T1>,(,i},	ВПОСЛЕ(<T1>) = ,
ВПЕРВ(<T2>)={<T2>,(,i},	ВПОСЛЕ(<T2>) = ,
ВПЕРВ(+) = {+},	ВПОСЛЕ(+) = {<T1>,(,i},
ВПЕРВ(i) = {i},	ВПОСЛЕ(i) = ,
ВПЕРВ(() = {(},	ВПОСЛЕ(()={<E1>,<E3>,<T2>,(,i},
ВПЕРВ()) = {)},	ВПОСЛЕ()) = ,
ВПЕРВ(<E3>)={<E3>,<E1>,<T2>,(,i},	ВПОСЛЕ(<E0>) = ,
	ВПОСЛЕ(h0)={<E0>,<E1>,<T2>,(,i},
	ВПОСЛЕ(<E3>) = {)}.

Таблица переходов, построенная по функциям ВПОСЛЕ, изображается так:

Таблица 3.3
	<E>	<T>	+	(	)	i
<E0>
<E1>			+
<T1>
<T2>
+		<T1>		(		i
i
(	<E1><E3>	<T2>		(		i
)
h0	<E1><E0>	<T2>		(		i
<E3>					)

Полученная таблица переходов является недетерминированной. После преобразования таблицы, обозначая множество состояний (<E₀>, <E₁>) = <E_x>и (<E₁>, <E₃>) = <E_y>и полагая, что начальным состоянием являетсяh₀, получаем:

Таблица 3.4
	<E>	<T>	+	(	)	i
<Ex>			+
<Ey>			+		)
<T1>
<T2>
+		<T1>		(		i
(	<Ey>	<T2>		(		i
)
h0	<Ex>	<T2>		(		i
i

Учитывая состав множеств, обозначенных <E_x>и<E_y>, построим таблицу действий искомого распознавателя.

Таблица 3.5
		+	(	)	i
Ex	D	П	П	П	П
Ey	О	П	П	П	П
T1	С (1)	С (1)	С (1)	С (1)	С (1)
T2	С (2)	С (2)	С (2)	С (2)	С (2)
+	О	П	П	П	П
i	С (4)	С (4)	С (4)	С (4)	С (4)
(	О	П	П	П	П
)	С (3)	С (3)	С (3)	С (3)	С (3)
h0	О	П	П	П	П

Построенный распознаватель является эквивалентным недетерминированному распознавателю, но эти распознаватели имеют разные состояния. Следовательно, им должны соответствовать эквивалентные, но не одинаковые грамматики. Такое различие должно отразиться в операциях сворачивания. В рассматриваемом случае операция Свертка(1) должна учитывать, что недетерминированному распознавателю соответствует грамматика с правилами   <E><E_x> + <T> и <E><E_y> + <T>.