Реферат: Проектирование трансляторов
стеков.
Рассмотрим несколько алгоритмов семантической обработки
для языка типа АЛГОЛ.
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>,<выр>
<инд1>.COUNT:=<инд2>.COUNT-1; -подсчет индексов
<инд1>.ARR:=<инд2>.ARR; -эапомнить тип элемента
<инд1>.ENTRY:=<инд2>.ENTRY+1;-в <инд1>.ENTRY занесли ук-ль на эл-тST для di
P1:=<инд2>.ENTRY2; -в P1 и в ENTRY2 адреса элемента ST для VARPART
<инд1>.ENTRY2:=P1;
ENTER(*,P1,<инд>.ENTRY,P1); -генерация тетрады VARPART=VARPART*di
P:=<выр>.ENTRY; -генерация тетрад преобразования R->I(если надо)
ENTER(+,P!,P,P!); -генерация тетрады VARPART=VARPART+индекс
Заметим, что мы всегда имеем дело не с самим выражением, а с
указателем на элемент ST, описывающий результат вычисления этого
выражения. Для правила <пер>::=<инд>) надо проверить (при компи-
ляции) количество индексных выражений и построить элемент STс
описанием элемента массива.
<пер>::=<инд>)
IF <инд>.COUNT!=0
THEN ERROR(6);
GENERATETEMP(P); -генерирование временной переменной для описателя
P.TYPE1%=3; элемента массива
P.TYPE:=<инд>.ARR.TYPE; -занести тип1,адресс эл-та ST дляVARPART,
P.ADRESS:=<инд>.ENTRY2; адрес эл-та ST, содержащего имя массива
P.NUMBER:=<инд>.ARR.NUMBER;
Трансляция описаний массивов
1) В польской записи описание массива
ARRAY A [L1:U1,...Ln:Un] можно представить в виде
L1U1...LnUn A ADEC
2) Для тетрад в виде
BOUNDS L1,U1
...
BOUNDS Ln,Un
ADEC A
Операция ADEC выполняет при семантической обработке следу-
щие действия:
-заносит запись о каждом массиве в ST;
-выделяет для каждого массива две ячейки:одну для хранеия
адреса начала массива, другую - для хранения адреса допвектора;
-формирует в обьектной программе (при генерации кода) коман-
ды, обеспечивающие перед входом в блок:
-вычисление компонент допвектора;
-вычисление адреса хранения массива;
-вычисление адреса хранения допвектора;
-занесение этих адресов в соответствующие ячейки.
Для массивов с постоянными границами компоненты допвектора
вычисляются в ходе трансляции и помещаются среди констант. Чтобы
отличить переменные граничные пары от постоянных нужно ввести до-
полнительный анализ операндов ADEC, являющихся граничными парами.
Допвектора могут располагаться вслед за парой ячеек, выделенной
последнему массиву или среди констант(для массива с постоянными
границами.
ЛЕКЦИЯ 12
СТРУКТУРЫ ДАННЫХ И ОРГАНИЗАЦИЯ ПАМЯТИ
Некоторые применяемые языки требуют динамического распреде-
ления памяти; блоки оперативной памяти при этом выделяются произ-
вольно, а затем освобождаются. Область данных - это блок ОП, вы-
деленный для данных.
Области данных могут принадлежать также к статическому клас-
су. Статическая область данных имеет постоянное число ячеек, а
динамическая область данных не всегда присутствует во время счета.
Если вызов процедуры происходит рекурсивно, то существует
несколько областей данных в ОП, каждая для отдельного вызова про-
цедуры.
Если компилятор знает все характеристики переменных во вре-
мени, то он может сгенерировать полностью команды обращеиня к пе-
ременным, основываясь на этих характеристиках.
Память выделяется компилятором не только для переменных, но
и для описателей, содержащих атрибуты, определяемые во время сче-
та. Этот описатель заполняется и изменяется во время счета. Типы
данных исходной программы должны быть отображены на типы данных
машины. Целые переменные содержатся обычно в одном слове.
Информационные таблицы
При анализе программы из описаний, заголовков процедур, цик-
лов и т.д. извлекается информация и сохраняется для последующего
использования. Эта информация обнаруживается в отдельных точках
программы и организуется так, чтобы к ней можно было обратиться
из любой части компилятора. В каждом компиляторе в той или иной
форме используется таблица символов. Это таблица идентификаторов,
встречающихся в программе, вместе с их атрибутами.
При разборке компилятора невозможно определить вид и содер-
жание информации, которую следует собирать, до тех пор, пока не
будут достаточно обстоятельно продуманы команды обьектной прог-
раммы для каждой инструкции исходной программы и сама синтезирую-
щая часть компилятора.
При проверке правильности семантики и генерации кода тре-
буются знания характеристики идентификатора. Эти характеристики
выясняются из описания и накапливаются в таблице символов. Наип-
ростейшая таблица символов для каждого элемента имеет поле аргу-
мента и значения. Аргументами таблицы являются символы или иден-
тификаторы, а значениями - их характеристики. Так как число ли-
тер в идентификаторе непостоянно, в аргументе часто помещают сим-
волы вместо самого идентификатора. Это позволяет сохранить фикси-
рованный размер аргумента. Идентификаторы хранятся в специальном
списке строк.
При проходе исходной программы через компилятор при встрече
конструкции описания происходит запись идентификатора исходной
программы в таблицу символов вместе с его атрибутами. В результа-
те дальнейшего чтения исходной программы, в компиляторе при на-
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
