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

Такт	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24
Вход	(	x	+	+	+	+	+	+	+	)	)	*	*	*	*	*	)	(	(	+	+	+	y	u	u
Cост.	0	4	5	4	3	4	2	4	9	7	9	12	0	3	0	2	8			2	0	1	7	5	7
Опер.	S(4)	S(5)	R(1,2)	G(3)	R(1,1)	G(2)	R(1,0)	G(9)	S(7)		S(12)	R(3,2)	G(3)	R(1,1)	G(2)	S(8)				R(1,0)	G(1)	S(7)	S(5)	R(1,2)
Стек	0	4	5	4	3	4	2	4	9	7	9	12	0	3	0	2	8			2	0	1	7	5	7
		0	4	0	4	0	4	0	4	9	4	9		0		0	2			0		0	1	7	1
			0		0		0		0	4	0	4					0						0	1	0
										0		0												0

Включение в грамматику «правил для типичных ошибок»

Включение специальных символов в грамматику:

G={ A_t , A_n , A_s , S, P }

Например:

F: "(" S ")"

F : "(" S error

F : S ")" error

Включение действий для обработки типичных ошибок в грамматику:

F: "(" S")"

F: "("S {error_message(“Ожидается закрывающая скобка.”);stop_convert();}

F : S  {error_message(“Отсутствует парная открывающая скобка.”);stop_convert();} ")"

Синтаксический анализ

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

a=b*c+d;    =>     abc * d + =

Синтаксическое дерево                    Дерево грамматического разбора

 

Из дерева грамматического разбора можно получить синтаксическое дерево.

1.  Удалить все листья, не являющиеся знаками операций и наименованиями операндов.

2.  Обойти дерево, начиная с корня (корень, левое поддерево, правое поддерево); если у текущего корня есть лист – знак операции, то этот знак перенести в корень, лист удалить.

3.  Обойти дерево и, если у листа есть родительский узел, помеченный нетерминалом, то пометку листа перенести в родительский узел, лист удалить.

Рекурсивный обход синтаксического дерева:

1.  Взять корень.

2.  Обойти левое поддерево.

3.  Обойти правое поддерево.

4.  Выдать содержимое корня.

позволяет получить постфиксную запись.

Включение действий в грамматику для преобразования
предложения в постфиксную форму записи

Вначале формулируем, как исходная запись (скобочных арифметических выражений) должна будет выглядеть в постфиксной форме: