Алгоритм восходящего восстановления дерева разбора. Понятие конфигурации. Связь между конфигурациями, состояниями и операциями восходящего акцептора

Алгоритм восходящего восстановления дерева разбора,

первая редакция

Используется стек символов, вначале пустой.

Вводим (временно) понятие операции Перенос, перемещающей символ со входа автомата на верхушку стека.

Будем обозначать эту операцию буквой S (от слова Shift – перемещение, перенос, сдвиг)

Основы могут находиться на верхушке стека (последним символом правой части правила вверху).

Операция Свертка снимает основу со стека и помещает нетерминал из левой части правила на верхушку стека (этот смысл операции опять же временно).

Эту операцию будем обозначать буквой R_m (от слова Reduce – свертка) с параметром m, обозначающим номер правила.

Если цепочка w u будет свернута в цепочку S u, то предложение w правильно, иначе – в предложении w ошибка.

			Нет в УП

 

Грамматика 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

Если же для свертки на шаге 9 выбрать основу 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

Нет в УП

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

 

1. 

Нет в УП

Существует начальное состояние (состояние № 0).
При запуске автомата номер начального состояния заносится в стек состояний.

Пусть некоторое правило выглядит так:

  N: s₁ s₂ … s_k