Нисходящий автомат с одним состоянием, управляемый входным символом и символом, находящимся на верхушке стека, страница 3

Грамматика G a1
0	Z: Su
1	S : S + T
2	S : T
3	T : T * F
4	T : F
5	F : ( S )
6	F : i <идентификатор>
7	F : c <константа>

x+y*z„

История работы:

Шаг	0	1	2	3	4	5	6	7	8
Вход	x+y*z„	+y*z„	+y*z„	+y*z„	+y*z„	y*z„	*z„	*z„	*z„
Опер.		S	R6	R4	R2	S	S	R6	R4
Стек		x	F	T	S	+	y	F	T
						S	+	+	+
							S	S	S

На шаге 8 конфликт «свертка / свертка»:                                                                                                           Основа T – правая часть правила                                                                                                           S : T

                                                                           Основа S + T – правая часть правила                                                                                                           S : S + T

Если для свертки выбрать основу T, то продолжение истории будет выглядеть так:

Шаг	9	10	11	12	13	14	15
Вход	*z„	z„	„	„	„	„	„
Опер.	R2	S	S	R6	R4	R2	Error
Стек	S	*	z	F	T	S
	+	S	*	*	*	*
	S	+	S	S	S	S
		S	+	+	+	+
			S	S	S	S

Предложение правильное, следовательно неверно выбрали основу на шаге 8

Выбирает основу S + T, и получаем другое продолжение истории работы автомата:

Шаг	9	10	11	12	13	14	15
Вход	*z„	z„	„	„	„	„	„
Опер.	R1	S	S	R6	R4	R2	Error
Стек	S	*	z	F	T	S
		S	*	*	*	*
			S	S	S	S

Оказывается, на шаге 9 ни свертку R1, ни свертку R2 применять нельзя, потому что в этот момент кроме конфликта «свертка / свертка» имеет место конфликт «перенос / свертка».

Если вместо любой свертки на этом шаге выполнить перенос, то продолжение истории работы выглядит так

(на шаге 12 опять конфликт «свертка / свертка», разрешенный в пользу R1):

Шаг	9	10	11	12	13	15
Вход	*z„	z„	„	„	„	„
Опер.	S	S	R6	R3	R1	Stop
Стек	*	z	F	T	S
	T	*	*	+
	+	T	T	S
	S	+	+
		S	S

Нет в УП

Стековый автомат с несколькими состояниями