Режим переполоха. Преобразование входного текста в постфиксную форму записи

Режим переполоха

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

…

x = ( x + ) ) * ) ( ( + y ;

…

Множественные ошибки обнаруживаются при попытке разбора нетерминала Выражение в правиле, выглядящем приблизительно так:

ОператорПрисваивания : Выражение ;

Можно поступить так:

1.  В тот момент, когда будет обнаружена невозможность нейтрализации одиночной ошибки, приступить к поиску символа «;». Все остальные символы просто пропускать.

2.  При обнаружении символа «;» (в тот момент, когда этот символ стал текущим) модифицировать стек и состояние автомата так, как будто бы

a.  нисходящий автомат вернулся туда, откуда был выполнен переход для разбора нетерминала Выражение

b.  восходящий выполнил свертку основы для нетерминала Выражение и операцию перехода (Go) по этому нетерминалу.

3.  Вернуться к анализу текста.

Такая схема организации работы называется «режим переполоха».

В общем случае ситуация выглядит так:

Уровень восстанавливаемого дерева разбора можно представить себе так:

a g ▼j b

Существует вывод N => g j

В момент включения режима переполоха нужно:

-  определить множество ожидаемых символов (либо предшественников цепочки b, либо последователей нетерминала N);

-  определить состояние автомата, в котором он должен оказаться в момент выхода из режима переполоха;

-  определить, каким должно быть содержимое стека автомата к этому моменту.

Нисходящий автомат с несколькими состояниями

N	M выб состояния	Флажки				Переход
		a	s	r	e
0	( i c		1			2
1	u					Stop
2	( i c					11
3	+				1	13
4	) u			1		0
5	( i c					15
6	*				1	17
7	+ ) u			1		0
8	(				1	19
9	i				1	22
10	c					23
11	( i c		1			5
12	+ ) u					3
13	+	1				14
14	( i c					2
15	( i c		1			8
16	* + ) u					6
17	*	1				18
18	( i c					5
19	(	1				20
20	( i c		1			2
21	)	1		1		0
22	i	1		1		0
23	c	1		1		0

Такт	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22
Вход	(	(	(	(	(	(	(	x	x	x	x	x	x	x	x	+	+	+	+	+	+	)	)
Сост.	0	2	11	5	15	8	19	20	2	11	5	15	8	9	22	16	6	7	12	3	13	14
Стек		1	1	12	12	16	16	16	21	21	12	12	16	16	16	12	12	12	21	21	21	21
				1	1	12	12	12	16	16	21	21	12	12	12	21	21	21	16	16	16	16
						1	1	1	12	12	16	16	21	21	21	16	16	16	12	12	12	12
									1	1	12	12	16	16	16	12	12	12	1	1	1	1
											1	1	12	12	12	1	1	1
													1	1	1