Смекни!
smekni.com

Программно методический комплекс для обучения процессу создания компиляторов (стр. 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 Семантический анализ

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