Смекни!
smekni.com

Проектирование трансляторов (стр. 19 из 31)

<инд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

СТРУКТУРЫ ДАННЫХ И ОРГАНИЗАЦИЯ ПАМЯТИ

Некоторые применяемые языки требуют динамического распреде-

ления памяти; блоки оперативной памяти при этом выделяются произ-

вольно, а затем освобождаются. Область данных - это блок ОП, вы-

деленный для данных.

Области данных могут принадлежать также к статическому клас-

су. Статическая область данных имеет постоянное число ячеек, а

динамическая область данных не всегда присутствует во время счета.

Если вызов процедуры происходит рекурсивно, то существует

несколько областей данных в ОП, каждая для отдельного вызова про-

цедуры.

Если компилятор знает все характеристики переменных во вре-

мени, то он может сгенерировать полностью команды обращеиня к пе-

ременным, основываясь на этих характеристиках.

Память выделяется компилятором не только для переменных, но

и для описателей, содержащих атрибуты, определяемые во время сче-

та. Этот описатель заполняется и изменяется во время счета. Типы

данных исходной программы должны быть отображены на типы данных

машины. Целые переменные содержатся обычно в одном слове.

Информационные таблицы

При анализе программы из описаний, заголовков процедур, цик-

лов и т.д. извлекается информация и сохраняется для последующего

использования. Эта информация обнаруживается в отдельных точках

программы и организуется так, чтобы к ней можно было обратиться

из любой части компилятора. В каждом компиляторе в той или иной

форме используется таблица символов. Это таблица идентификаторов,

встречающихся в программе, вместе с их атрибутами.

При разборке компилятора невозможно определить вид и содер-

жание информации, которую следует собирать, до тех пор, пока не

будут достаточно обстоятельно продуманы команды обьектной прог-

раммы для каждой инструкции исходной программы и сама синтезирую-

щая часть компилятора.

При проверке правильности семантики и генерации кода тре-

буются знания характеристики идентификатора. Эти характеристики

выясняются из описания и накапливаются в таблице символов. Наип-

ростейшая таблица символов для каждого элемента имеет поле аргу-

мента и значения. Аргументами таблицы являются символы или иден-

тификаторы, а значениями - их характеристики. Так как число ли-

тер в идентификаторе непостоянно, в аргументе часто помещают сим-

волы вместо самого идентификатора. Это позволяет сохранить фикси-

рованный размер аргумента. Идентификаторы хранятся в специальном

списке строк.

При проходе исходной программы через компилятор при встрече

конструкции описания происходит запись идентификатора исходной

программы в таблицу символов вместе с его атрибутами. В результа-

те дальнейшего чтения исходной программы, в компиляторе при на-

хождении любого идентификатора программа обращается к таблице

символов и ищет в ней данный идентификатор. Если идентификатор не

обнаружен, то выдается сообщение, что данный идентификатор не оп-

ределен. Если же он обнаружен, то производится сравнение данного

идентификатора с записанным в таблице символов и производятся

необходимые преобразования.

При работе с таблицей символов нужно разработать правила ор-

ганизации и обращения к таблице символов. Таблицы символов могут

быть как упорядоченными, так и неупорядоченными.

При упорядоченном списке элементов наиболее результативным

является бинарный или логарифмический поиск. Иногда один и тот же

идентификатор может быть описан и использован много раз в различ-

ных блоках и процедурах, и каждое такое описание должно быть

единственным. Соответственно нужно разделять таблицу симводов.

При этом устанавливается правило нахождения соответствующего

идентификатора. Оно состоит в следующем: сначала просматривается

текущий блок, затем обьемлющий блок и т.д., до тех пор, пока не

будет найдено описание данного идентификатора.

При осуществлении поиска все элементы таблицы хранятся для

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

Информация об идентификаторе хранится в той части таблицы,

которую мы определили как "значение".

Таблица символов состоит из 5-ти различных списков:

- список меток;

- список арифметических констант;

- список имен общих блоков,имен подпрограмм и имен перемен-

ных;

- список общих блоков;

- список имен подпрограмм.

Элементы всех этих списков помещаются в одной и той же таб-

лице; первые два байта каждого элемента используются для ссылки

на следующий элемент в том же списке.

ЛЕКЦИЯ 13

ВНУТРЕННИЕ ФОРМЫ ИСХОДНОЙ ПРОГРАММЫ

Ввиду сложности реальных языков программирования и предъяв-

ления повышенных требований к эффективности самого процесса ком-

пиляции и к готовым программам, разработчики вынуждены проектиро-

вать многопроходные компиляторы. При этом для связи между прохо-

дами, необходимы внутренние (промежуточные) формы исходной прог-

раммы. В большинстве внутренних форм, операторы располагаются в

том порядке, в котором они должны выполняться, что означает пос-

ледующий анализ и итерацию об'ектного кода. (Эти внутренние пред-

ставления можно использовать для интерпретации).

Внутренняя форма является более развернутым представлением

исходной программы, к которой предъявлялись требования лаконич-

ности и краткости. Более подробное представление обеспечивает

проведение глубокого анализа и оптимизации программ.

Как правило, в одном компиляторе для разных синтаксических

единиц (выражений, условных операторов, операторов присваивания и

т.д.) используются разные, наиболее подходящие с точки зрения

разработчика, внутренние формы.

1.1. Опреанды и операторы

Внутренние формы содержат операторы и операнды. В различных

видах представлений существенное отличие заключается в форме сое-

динения операторов и операндов.

Операторы: + , - , / , * , BR (branch) и т.п. Операнды : -

простые имена (переменных, процедур и т.д.);

- константы;

- временные переменные, генерируемые компилятором;

- переменные с индексами.

Каждый операнд (за исключением переменных с индексом) пред-

ставляется указателем на соответствующий элемент в таблице симво-

лов, констант или временных переменных.

В поле операнда предусматривается признак косвенной адреса-

ции, чтобы указать таким путем, что значение в таблице, на кото-

рое указывает операнд, является адресом расположения значения,

которое требуется операнду при исполнении команды.

Пременную с индексами А[i,j,...,k] можно обрабатывать сле-

дующим образом:

- сначала включить последовательность операций для вычисления

VARPART и запоминания ее во внешней ячейке Т;

- сам операнд представить двумя указателями: на элемент с име-

нем массива и на значение VARPART, т.е. А[i,j,...,k] можно

представить в виде А[T]. Такой операнд занимает две ячейки

во внутреннем представлении, но зато позволяет генерировать

более эффективную объективную программу. Простая переменная

┌───┬───┬─────────────────────────────────────┐

│ 1 │ I │ указатель на эл-т таблицы символов │ I - признак

└───┴───┴─────────────────────────────────────┘ косвенной

Константа адресации

┌───┬───┬─────────────────────────────────────┐