ENTER('@',0,T.SEM,E.SEM)
(6) T ::= F T.SEM:=F.SEM
(7) T ::= T*F
(8) T ::= T/F
(9) F ::= I
(10)F ::= (E) F.SEM:=E.SEM
Реализация семантических программ и семантических стеков
Для привязки семантических атрибутов к нетерминалам ис-
пользуются семантические стеки для каждого атрибута (или один
стек с отдельными полями для хранения синтаксического символа и
его семантических атрибутов). Эти стеки должны хранить семанти-
ческую информацию, которая связана с нетерминалами, входящими в
текущую сентенциальную форму. Эти стеки работают параллельно с
синтаксическим стеком S (т.е. удаление и занесение в них синхро-
низировано). Семантическая программа имеет доступ ко всем стекам.
┌───┬────────┬──────┬───────┬────┐
│ E │ │ REAL │ │ 20 │
├───┼────────┼──────┼───────┼────┤
│ + │ │ │ │ │
├───┼────────┼──────┼───────┼────┤
│ T │ │ INT │ │ 40 │
├───┼────────┼──────┼───────┼────┤
│ . │ │ . │ │ . │
│ . │ │ . │ │ . │
│ . │ │ . │ │ . │
└───┴────────┴──────┴───────┴────┘
В действительности не имеет значения, сколько используется
стеков.
Рассмотрим несколько алгоритмов семантической обработки
для языка типа АЛГОЛ.
1.Условные инструкции
<инстр1>::=<условие><инстр2>ELSE<инстр3>│<условие><инстр2>
<условие>::=IF<выраж>THEN,
где <выраж> должно иметь тип BOOLEAN.
Необходимо сгенерировать тетрады одного из двух видов: (1)
тетрады для Т::=<выраж> (1) тетрады для Т::=<выраж> (p) BZ
q+1,T,0 (p) BZ q,T,0
<инстр2> <инстр2>
(q) BR r (q)
(q+1) <инстр3>
(r)
Программа генерации (Р)тетрады связана с правилом:
<условие>::=IF<выраж>THEN и имеет следующий вид:
(1) Р:=<выраж>,ENTRY;─занести в Р адрес элемента TS для <выфаж>
(2) CHECKTYPE(P,BOOLEAN); ─проверить, что тип <выраж> BOOLEAN
(3) <условие>,JUMP:=NEXTQUAD; ─запомнить номер следущей тетрады
(4) ENTER(BZ,0,P,0); ─генерация BZ─тетрады
Общее правило для доступа к семантическим стекам: Если осно-
ва х рассматриваемой сентенциальной формы должна быть приведена с
помощью правила U::=x к U, то для работы с семантикой символов
используется программа, которая:
1) заносит информацию в TS или проверяет ее;
2) проверяет семантическую информацию, связанную с х;
3) генерирует тетрады;
4) связывает семантическую информацию с U;
Для обращения в стеки за семантической информацией SEM, свя-
занной с U, применяем обозначение U.SEM. 1.I.NAME ─ указатель,
используется для доступа к имени идентификатора
2.<пер>ENTRY ─ выдает указатель на элемент таблицы символов для переменной <пер>
3.<выр>ENTRY ─ указатель на значение (уже выполненного) выражения <выр>
4.<условие>JUMP ─ содержит номер BZ тетрады, в которую позднее надо добавить адрес перехода, который еще не известен
Следущая редукция будет связана с правилом: <инстр1>::=<ус-
ловие><инстр2> I:=<условие>.JUMP Занести номер следущей тетрады
во вторую QU- AD(I,2):=NEXTQUAD компоненту тетрады с помощью I,
т.е. получить (BZq+1,p,0)
Операнды во внутренней форме будем представлять указателем Р
на соответствующий элемент таблицы символов. Ссылка на его атри-
бут будет иметь вид: Р.TYPE,P.TYPE1. Очевидно, если инструкция
содержит ELSE, то между <инстр2> и <инстр3> нужно как бы вста-
вить команду BR. Но при таком синтаксисе конструкция <инстр1> с
ELSE будет распознана лишь после разбора <инстр2> и <инстр3>.
Т.е. будет специфицирована цепочка команд для <инстр2> и <инстр3>.
Преобразуем синтаксис в соответствии с желаемой семантикой:
<инстр1>::=<ист.часть><инстр3>
<ист.часть>::=<условие><инстр2>ELSE
<ист.часть>::=<условие><инстр2>ELSE
<ист.часть>.JUMP:=NEXTQUAD; ─ запомнить номер следущей тетрады
ENTER(BR,0,0,0); в стеке
I:=<условие>.JUMP; ─ занести в BZ переход через <инстр1>
QUAD(I,2):=NEXTQUAD;
<инстр1>::=<ист.часть><инстр3>
I:=<ист.часть>.JUMP; - вставить адрес перехода через
QUAD(I,2):=NEXTQUAD; <инстр2> в (BR...)
Выводы:
1. Когда редуцируется основа XY..Z, тетрады для всех нетер-
миналов, которые есть в основе, уже сгенерированы. Чтобы вста-
вить между ними дополнительные тетрады, следует изменить синтак-
сис в соответствии с требуемой семантикой.
2. Показано, как используется семантика, связанная с симво-
лом, для запоминания информации, которая потребуется позже. Оче-
видно, что можно допустить любое количество вложенных друг в дру-
га условных операторов, если на некоторых стадиях разбора иметь
произвольное число символов <условие>. С каждым из них будет свя-
зано свое <условие>.JUMP значение в семантическом стеке. Стеко-
вый механизм обеспечивает автоматическое сохранение каждой такой
компоненты отдельно.
Метки и переходы
Метка I определяется следущим образом:
<инстр1>::=I:<инстр2>,где
I - нетерминал, обозначающий идентификатор.
Метке I нужно присвоить адрес начала <инстр2>. Чтобы это
можно было сделать, изменим синтаксис таким образом:
<инстр1>::=<опред.метки><инстр2>
<опред.метки>::=I:
Имея ввиду, что в программе ссылаться на метку можно раньше,
чем она определялась, составим следущую семантическую программу:
<опред.метки>::=I;
LOOKUPDEC(I.NAME,P);- поиск описания метки с именем NAME среди иден-
IF P=0 THEN тификаторов. Если его нет(возвращается Р=0),то
BEGIN занести новый элемент с именем NAME в ST.
INSERT(I.NAME,P); Присвоить ему тип LABEL.
P.TYPE:=LABEL;
END
ELSE BEGIN
CHECKTYPE(P,LABEL); Cравнивает тип в ST (P.TYPE) с типом LABEL
IF P.DECLARED=1 THEN Проверяет не повторное ли это определение
ERROR (3) Печать ошибки
END
P.DECLARED:=1; Если нет, то установить признак метка опре-
P.ADRESS:=NEXTQUAD; делена и занести значение в поле ADRESS
Замечание:
1.сли Р-указатель на элемент ST, то для ссылки на его атрибуты
достаточно написать P.ADRESS и т.д. 2.Используем следущие атри-
буты(поля ST):
-TYPE (0=UNSIGNED;1=REAL;2=INT;3=BOOLEAN;4=LABEL)
-TYPE1 (1=простая перем.,2=имя массива,3=перем. с индексом)
-TEMPORARY (1=временная перем.,0-нет)
-DECLARED (0=неопределена,1=определена)
-ADBEWS Номер помеченной тетрады или адрес другого элемента ST
-NUMBER Размерность массива
Т.к. правило <инстр1>::=<опред.метки><инстр2> редуцируется
после генерации тетрад <инстр2>, то с ним не связывается никакой
дополнительной семантики ZB: инструкция GOTO в Фортране ис-
пользует подпрограмму просмотра всей ST (LOOKUP) ,т.к. метки ин-
струкций не должны повторяться.
<инстр>::=GOTO I
LOOKUP(I.NAME,P);
IF P=0 THEN
BEGIN INSERT(I.NAME,P);
P.TYPE:=LABEL;
P.DECLARED:=0;
END
ELSE CHECKTYPE(P,LABEL);
ENTER(BRL,P,0,0);
Подпрограмма CHECKTYPE(P,LABEL) сравнивает тип элемента ST,
на который указывает P с LABEL. В случае несовпадения печатается
сообщение об ошибке и ABORT.
3.Переменные и выражения
<пер>::=I|I(<список выр>)
<список выр>::=выр|<списоквыр>,<выр>
<пер>:=I -тетрад не генерирует
LOOKUP(I.NAME,P); поиск идентификатора
IF P=0 THEN ERROR(4);
<пер>.ENTRY:=P; связать с <пер> адрес найденного в ST элемента
В фортране если Р=0 нужно с помощью процедуры INSERT внести
идентифика тор в ST и установить TYPE равнымREAL или INT в зави-
симости от первой буквы идентификатора.
При обработке переменной с индексом I (<список выр>) необхо-
димо:
-сформировать тетрады для вычисления всех индексных выражений;
-вычислить адрес элемента массива, используя известный нам ме-
тод.
Чтобы вычислить VARPART необходимо преобразовать синтаксис
<инд>::=I(<выр>|<инд>,<выр> <пер>::=<инд>)
Программа для <инд>::=I(<выр> должна найти идентификатор
массива, сгенерировать тетрады для VARPART:=<выр> и связать с
<инд> адрес элемента ST для d1. <инд>::=I(<выр> LOOKUP(I.NAME,P);
-поиск идентификатора IF P=0 OR P.TYPE !=2 -он должен быть в ST и
иметь тип ARRAY.
THEN ERROR(5)
<инд>.COUNT:=P.NUMBER-1;-подсчет количества индексов
<инд>.ARR:=P; -запомнить адрес описателя массива
<инд>.ENTRY:=P+1; -занести в ENTRY адрес элемента ST для d1
GENERATETEMP(P); -генерация временной перем. типа INT для VARPART
P.TYPE:=INTEGER; -запомнить ее адрес
<инд>.ENTRY2:=P; -генерация тетрад для преобразования типа, если
CONVERTRI(<выр>.ENTRY); они нужны
P:=<выр>.ENTRY;
ENTER(:=,P,,<инд>.ENTRY2); -генерация тетрады занесения первого
индекса в VARPART
Подпрограмма GENERATETEMP(P) заносит в ST элемент для вре-
менной переменной, а адрес этого нового элемента возвращает в P.
Подпрограмма CONVERTRI(P)проверяет тип P-го элемента ST. Если тип
- INT, то ничего не делается, если REAL, то с помощью
GENERATETEMP заводится новая временная переменная типа INT и ге-
нерируется CVRI-тетрада для преобразования заданной переменной в
тип INT и занесения результата в новую временную переменную. Ука-
затель на временную переменную в ST остается в P. Если тип тип
Р-го элемента не INT и не REAL, то выдается сообщение об ошибке.
Перечислим семантическую информацию (в стеках), связанную с
<инд>:
1.<инд>.ENTRY -адрес элемента ST для d1(для di,если сгенери-
рован код i-го индексного выражения)
2.<инд>.ENTRY2 -адрес элемента ST для VARPART
3.<инд>.COUNT -[размерность - i], если сгенерирован код для
i-го индексного выражения
4.<инд>.ARR -адрес описателя имени массива в ST
Теперь для правила <инд1>::=<инд2>,<выр> надо сгенерировать
код, реализующий формулу VARPART:=VARPART*d1+<выр>, если это
второе по счету индексное выражение.
<инд1>::=<инд2>,<выр>