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 Семантический анализ

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

1) ведение табличных символов;

2) включение неявной информации (по умолчанию);

3) обнаружение ошибок;

4) макрообработка и операции, выполняемые во время компиляции.

После проведения синтаксического анализа формируется дерево грамматического разбора, представленное в виде таблицы. По этому дереву на этапе семантического анализа производится новый смотр.

Одно из предназначений семантического анализатора – поиск ошибок. Существуют следующие критерии поиска ошибок:

1) не должно быть повторного описания идентификатора;

2) все идентификаторы, используемые в программе, должны быть описаны;

3) запрещается присвоение значению переменной одного типа значение другого типа (возможно только присвоение вещественному типу целого значения);

4) результат деления “ / “ всегда вещественное число;

5) перед использованием переменной (идентификатора) ей должно быть присвоено значение (данная ошибка не относится к критическим).

6) в цикле FOR, структуре <index-exp>, идентификатор должен быть целого типа, как и оба значения возвращаемые структурой <exp>.

Пример неправильно написанных элементов программы.

VAR

A,B,C:INTEGER;

C,D:REAL – повторное описание переменной C

BEGIN

A:=3.5; – присвоение переменной целого типа вещественного значения

B:=A/2; – присвоение переменной целого типа вещественного значения, образующегося при делении

D:=F*5; – не описана переменная F

FOR A:=1 TO D DO C:=C+A – переменная D вещественного типа

END.

2.5 Формирование промежуточного кода

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

Разница между этими методами в том, что результат каждого из этапов в тетрадах представляется отдельной промежуточной переменной, в связи с чем требуется большое количество памяти на хранение этих переменных. Представление промежуточных данных кроме всего имеет большую наглядность по этому за основу был принят метод четверок (тетрад).

Циклы

При адресации используются следующие команды.

C $BR – безусловный переход на позицию (индекс) в массиве, содержащем тетрады.

L $BRL – безусловный переход на метку

L - имя в таблице символов. Значение его - адрес перехода. Основная проблема при реализации этого оператора – определение адреса перехода.

<операнд1> <операнд2> BRZ|$BRM|$BRP|$BRMZ|$BRPZ

<операнд1> - значение арифметического выражения,

<операнд2> - номер или место позиции (адрес).

$BRZ - переход по значению 0,

$BRM - переход по значению <0,

$BRP - переход по значению >0,

$BRMZ - переход по значению <=0,

$BRPZ - переход по значению >=0.

Реализация циклов не вызывает сложностей. Имея оператор безусловного перехода и условный оператор, можно сконструировать цикл "вручную". Например, цикл вида

FOR I=N1 TO N2 DO operator

может быть сконструирован на исходном языке:

I := N1;

L1: IF I>N2 THEN GOTO L2;

operator;

I:=I+1;

GOTO L1;

L2:

Представление конструкции FOR I=N1 TO N2 DO operator в виде тетрад показано в таблице 15.

Таблица 15 – конструкция for в виде тетрад

Далее рассмотрены циклы WHILE, REPEAT, а также конструкция IF…THEN…ELSE.

В таблице 16 разобрана конструкция WHILE a<b DO operator.

Таблица 16 – Конструкция while