Программно методический комплекс для обучения процессу создания компиляторов (стр. 11 из 14)

Шаги	Таблица кодов лексем				Имя в программе	Элемент грамматики БНФ					Результат сравнения	Формируемая таблица переходов					Выполненное действие
												текущая позиция			следующая позиция
	позиция	табл	код, специф	тип		имя	текущая конструкция	тип	табл	код (для ТС)		строка	столбец	вносимое значение	строка	столбец
79	18	1	@17,3	18	2
80	21	2	2	ИД	а	id	<factor>	ИД	2	+	18	2	$2,2	18	3
81	22	1	33	ТС	–	18	3	18	1	конец конструкции
82	22	1	33	ТС	–	18	1	17	3	переход
83	22	1	33	ТС	–	*	<term>	ТС	1	34	–	17	3
84	22	1	33	ТС	–	DIV	<term>	ТС	1	17	–	17	3
85	22	1	33	ТС	–	/	<term>	ТС	1	37	–	17	3
86	22	1	33	ТС	–	17	3	17	1	конец конструкции
87	22	1	33	ТС	–	17	1	16	3	переход
88	22	1	33	ТС	–	+	<exp>	ТС	1	32	–	16	3
89	22	1	33	ТС	–	–	<exp>	ТС	1	33	+	16	3	$1,33	16	4
90	23	2	4	ИД	с	<term>	<exp>	НС	16	4	@19,2	19	1
91	23	2	4	ИД	с	19	1	@16,5	19	2
92	23	2	4	ИД	с	<factor>	<term>	НС	19	2	@20,2	20	1
93	23	2	4	ИД	с	20	1	@19,3	20	2
94	23	2	4	ИД	c	id	<factor>	ИД	2	+	20	2	$2,4	20	3
95	24	1	36	ТС	)	<factor>	20	3	20	1	конец конструкции
96	24	1	36	ТС	)	20	1	19	3	переход
97	24	1	36	ТС	)	*	<term>	–	19	3
98	24	1	36	ТС	)	DIV	<term>	–	19	3
99	24	1	36	ТС	)	/	<term>	–	19	3
100	24	1	36	ТС	)	<term>	19	3	19	1	конец конструкции
101	24	1	36	ТС	)	19	1	16	5	переход
102	24	1	36	ТС	)	+	<exp>	ТС	1	32	–	16	5
103	24	1	36	ТС	)	–	<exp>	ТС	1	33	–	16	5
104	24	1	36	ТС	)	<exp>	16	5	16	1	конец конструкции
105	24	1	36	ТС	)	16	1	15	4	переход
106	24	1	36	ТС	)	)	<factor>	ТС	1	36	+	15	4	$1,36	15	5
107	25	1	27	ТС	;	<factor>	15	5	15	1	конец конструкции
108	25	1	27	ТС	;	15	1	13	5	переход
109	25	1	27	ТС	;	*	<term>	ТС	1	34	–	13	5
110	25	1	27	ТС	;	DIV	<term>	ТС	1	17	–	13	5
111	25	1	27	ТС	;	/	<term>	ТС	1	37	–	13	5
112	25	1	27	ТС	;	13	5	13	1	конец конструкции
113	25	1	27	ТС	;	13	1	10	5	переход
114	25	1	27	ТС	;	+	<exp>	ТС	1	32	10	5
115	25	1	27	ТС	;	–	<exp>	ТС	1	33	10	5
116	25	1	27	ТС	;	10	5	10	1	конец конструкции
117	25	1	27	ТС	;	10	1	9	5	переход

Продолжение таблицы 13

Шаги	Таблица кодов лексем				Имя в программе	Элемент грамматики БНФ					Результат сравнения	Формируемая таблица переходов					Выполненное действие
												текущая позиция			следующая позиция
	позиция	табл	код, специф	тип		имя	текущая конструкция	тип	табл	код (для ТС)		строка	столбец	вносимое значение	строка	столбец
118	25	1	27	ТС	;	<assign>	9	5	9	1	конец конструкции
119	25	1	27	ТС	;	9	1	8	3	переход
120	25	1	27	ТС	;	<stmt>	8	3	8	1	конец конструкции
121	25	1	27	ТС	;	8	1	7	3	переход
122	25	1	27	ТС	;	;	<stmt-list>	–ТС	1	27	+	7	3	$1,27	7	4
123	26	1	4	ТС	END	<stmt-list>	7	4	7	1	конец конструкции
124	26	1	4	ТС	END	7	1	1	8	переход
125	26	1	4	ТС	END	END	<prog>	ТС	1	4	+	1	8	$1,4	1	9
126	27	1	30	ТС	.	.	<prog>	ТС	1	30	+	1	9	$1,30	1	10
127	1	10	1	1	конец конструкции
128	1	1

Таблица 14 – Формируемая таблица переходов

1	2	3	4	5	6	7	8	9	10
1	PROGRAM$1,1	<prog-name>@2,2	VAR$1,2	<dec-list>@3,2	BEGIN$1,3	<stmt-list>@7,2	END$1,4	.$1,30
2	<prog-name>	@1,4	prog1$2,1	;$1,27
3	<dec-list>	@1,6	<dec>@4,2	;$1,27
4	<dec>	@3,3	<id-list>@5,2	:$1,31	<type>@6,2
5	<id-list>	@4,3	a$2,2	,$1,29	b$2,3	,$1,29	c$2,4
6	<type>	@4,5	INTEGER$1,5
7	<stmt-list>	@1,8	<stmt>@8,2	;$1,27
8	<stmt>	@7,3	<assign>@9,2
9	<assign>	@8,3	a$2,2	:=$1,28	<exp>@10,2
10	<exp>	@9,5	<term>@11,2	+$1,32	<term>@13,2
11	<term>	@10,3	<factor>@12,2
12	<factor>	@11,3	1$3,1
13	<term>	@10,5	<factor>@14,2	*$1,34	<factor>@15,2
14	<factor>	@13,3	b$2,3
15	<factor>	@13,5	($1,35	<exp>@16,2	)$1,36
16	<exp>	@15,4	<term>@17,2	–$1,33	<term>@19,2
17	<term>	@16,3	<factor>@18,2
18	<factor>	@17,3	a$2,2
19	<term>	@16,5	<factor>@20,2
20	<factor>	@19,3	c$2,4

2.4.6 Построение деревьев

Для наглядного отображения полученных грамматик используют синтаксические деревья, пример показан на рисунке 3.

На основе введенных значений формируемой таблицы переходов в программу SINAN строится (формируется) синтаксическое дерево (дерево грамматического разбора).

Деревья могут быть представлены в вертикально как показано на рисунке 5, а и горизонтально – рисунок 5, б.

Рассмотрим выражение: a := c – (1 + b)

а)

б)

Рисунок 5 – а) вертикальное дерево, б) горизонтальное дерево

Рисунок 6 – Горизонтальное синтаксическое дерево

На рисунке 6 показано горизонтальное синтаксическое дерево, построенное по следующей программе:

PROGRAM prog1;

VAR a,b:INTEGER;

s:STRING;

BEGIN

b:=78;

s:='Дерево';

WRITE(s);

a:=b*(2+a);

END.

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

Функции семантического анализатора: