Реферат: Проектирование трансляторов
ния результатов атома ХРАНЕНИЕ в FOR-операторах. В областях
КОНСТАНТЫ и ПЕРЕМЕННЫЕ хранятся соответственно значения констант
и переменных.
Область ВРЕМЕННЫЕ РЕЗУЛЬТАТЫ используется для хранения про-
межуточных результатов.
Генератор кода использует табличные эдементы для хранения
информации о параметрах атомов. Каждый табдичный элемент имеет
поле ВИД, указывающее вид об'екта, описываемого этим элементом,
а также одно или два других поля. Поле ВИД содержит одно из сле-
дующих пяти значений: КОНСТАНТА, ПЕРЕМЕННАЯ, ПРОМЕЖУТОЧНЫЙ РЕ-
ЗУЛЬТАТ, ХРАНИМЫЙ РЕЗУЛЬТАТ или МЕТКА.
Мы предполагаем, что генератор кода содержит процедуру, на-
зываемую ГЕН, которая строит двоичное представление генерируемой
команды. ГЕН вызывается с двумя параметрами: кодом операции и
указателем на табличный элемент, соответствующий полю адреса ге-
нерируемой команды. Процедура ГЕН выполняет следующие действия:
1. Формируется двоичный код, соответствующий первому
параметру процедуры ГЕН.
2. Формируется двоичный код, соответствующий второму
параметру процедуры ГЕН.
3. Двоичный код, образующий сгенерированную команду,
помещается в ячейку, соответствующую текущему зна-
чению СЧЕТКОМ.
4. СЧЕТКОМ увеличивается и сравнивается с ГРАНКОМ.
Здесь СЧЕТКОМ и ГРАНКОМ - переменные периода компиляции.
Генерация кода для некоторых типичных конструктов
Покажем, как генерируеися код для некоторых конструктов,
типичных для языков программирования высокого уровня.
I. Присваивания
В соответствии с терминологией Алгола 68 присвамвание
имеет вид
destination := source
Смысл его состоит в том, что значение, соответствующее
источнику, присваивается значению, которое является адресом
( или именем ), заданным получателем. Например, в
p := x + y
значение "х+у" присваивается р.
Допустим, что статические характеристики источника и по-
лучателя уже находятся в вершине нижнего стека. Опишем дейс-
твия, выполняемые во время компиляции для осуществления прис-
ваивания. Прежде всего из нижнего стека удаляются два верхних
элемента, после чего происходит следующее:
1. Проверяется непртиворечивость типов получателя и ис-
точника. Так как получатель представляет собой адрес, источ-
ник должен давать что-нибудь приемлемое для присваивания это-
му адресу. В зависимости от реализуемого языка типы
получателя и источника можно определенным образом изменять до
выполнения присваивания. Например, если тип источника - целое
число, то его можно сначала преобразовать в вещественное, а
затем присвоить адрес, имеющему тип вещественного числа.
2. Там, где это необходимо, проверяются правила области
действия. В Алголе 68 источник не может иметь меньшую область
действия, чем получатель. Например, в
begin ref real xx;
begin real x;
xx := x
end
присваивание недопустимо, и это может быть обнаружено во вре-
мя компиляции, если в таблице символов или в нижнем стеке
имеется информация об области действия. Однако в процессе
компиляции нельзя обнаружить все нарушения правил области
действия, и в некоторых случаях для проверки этой области
приходится создавть код во время прогона.
3. Генерируется код для присваивания, имеющий форму
ASSIGN type,S,D
где S - адрес источника, а D - адрес получателя.
4. Если язык ориентирован на выражения ( то есть само
присвоение имеет значение ), статические характеристики этого
значения помещаются в нижний стек.
II. Условные зависимости
Почти все языки содержат условное выражение или опера-
тор, аналогичный следующему:
if B then C else D fi
При генерации кода для такой условной зависимости во
время компиляции выполняются три действия. Грамматика с вклю-
ченными действиями:
CONDITIONAL -> if B <A1> then C <A2> else D <A3> fi
Действия А1, А2 и А3 означают (next - значение номера
следующей метки, присваиваемое компилятором):
А1. Проверить тип В, применяя любые необходимые преобра-
зования (приведения) типа для получения логического значения.
Выдать код для перехода к L<next>, если В есть "ложь":
JUMPF L<next>,<address of B>
Поместить в стек значение next ( обычно для этого служит
стек знаков операций ). Увеличить next на 1. (Угловые скобки
(<,>), в которые заключаются "next" и "address of B", исполь-
зуются для обозначения значений этих величин, и их не следует
путать со скобками, в которые заключаются действия в порожда-
ющих правилах грамматики.)
А2. Генерировать код для перехода через ветвь else (
т.е. перехода к концу условной зависимости )
GOTO L<next>
Удалить из стека номер метки ( помещенный в стек дейс-
твием А1 ), назвать i, генерировать код для размещения метки
SETLEBEL L<i>
Поместить в стек значение next. Увеличить next на 1.
А3. Удалить из стека номер метки (j). Генерировать код
для размещения метки
SETLABEL L<j>
Если условная зависимость сама является выражением ( а
не оператором ), компилятор должен знать, где хранить его
значение, независимо от того, какая часть вычисляется - then
или else. Это можно сделать, специфицируя адрес, который ука-
зывает на данное значение, или пересылая значение, заданное
частью then либо частью else, по указанному адресу.
Аналогично можно обращаться с вложенными условными выра-
жениями или операторами.
III. Описания идентификаторов
Допустим, что типы всех идентификаторов полностью выяс-
нены в предыдущем проходе и помещены в таблицу символов. Ад-
реса распределяются во время прохода, гененрирующего код.
Рассмотрим описание
somemode x
еречислим действия, выполняемые во время компиляции:
1. В таблице символов производится поиск записи, соот-
ветствующей x.
2. Текущее значение указателя стека идентификаторов дает
адрес, который нужно выделить для x. Этот адрес
(idstack, current block number, idstack pointer)
включается в таблицу символов, а указатель стека идентифика-
торов увеличивается на статический размер значения, соответс-
твующего х. (В Алголе 68, если вид х начинается с ref, обьем
памяти должен выделяться для значения, на которое ссылается
х, а не для самого х; это обозначается с помощью адреса дру-
гого типа. )
3. Если х имеет динамическую часть, например в случае
массива, то генерируется код для размещения динамической па-
мяти во время прогона.
IV. Вход и выход из блока
При входе в блок ( последовательное предложение с описа-
ниями в Алгол 68 ) предположим, что во время предыдущего про-
хода получена определенная информация. Она состоит из таблиц
видов и символов, дающих типы или виды всех идентификаторов и
т.п. Тогда при входе в блок нужно выполнить следующие основ-
ные действия:
1. Прочитать в таблице символов информацию, касающуюся
блока, и связать ее с информацией включающих блоков таким об-
разом, чтобы можно было выполнить "внешние" поиски определяю-
щих реализаций идентификаторов и т.д.
2. Поместить в стек (idstack pointer). Поместить в стек
(wostack pointer). Поместить в стек (block number). Все эти
значения ссылаются на включающий блок и могут потребоваться
вновь после того, как будет покинуть блок, в который только
что осуществлен вход:
idstack pointer := 0
wostack pointer := 0
3. Генерировать код для исправления DISPLAY
BLOCK ENTRY block number
4. Увеличить номер уровня блока на 1. Увеличить наиболь-
ший использованный до сих пор номер блока на 1 и присвоить
это значение номеру блока.
5. Прочитать информацию о виде и добавить ее в таблицу
видов ( если в языке имеются такие "сложные" виды, как в Ал-
голе 68 ).
При выходе из блока требуется:
1. Обновить таблицу блоков, задав размер стека идентифи-
каторов и т.п. для покинутого блока.
2. Исключить информацию в виде таблицы символов для по-
кинутого блока.
3. Генерировать код для изменения дисплея
BLOCK EXIT block number
4. Удалить из стека (block number). Удалить из стека
(wostack pointer). Удалить из стека (idstack pointer). Умень-
шить номер уровня на 1.
5. Поместить результат (при необходимости) в рамку стека
вызывающего блока.
ЛЕКЦИЯ 16
КОНТЕКСТНЫЕ УСЛОВИЯ ЯЗЫКОВ ПРОГРАММИРОВАНИЯ
КОНТЕКСТНЫЕ УСЛОВИЯ 1-ОГО И 2-ОГО ТИПА
1. Условия, связанные с описанием правил идентификаторов
В каждом блоке без внутренних блоков идентификатор нельзя
описывать более одного раза.
Для процедур и функций ни один идентификатор не должен вхо-
дить более одного раза в список формальных параметров в совокуп-
ности спецификаций.
2. Правила соответствия между определяющими и использующими
вхождениями идентификаторов.
.
Правила поиска часто называют алгоритмами идентификации.
Проверим одно контекстное условие:
1. Рассмотрим min блок.
2. Ищем определяющее вхождение идентификатора в рассмотрен-
ном блоке. Если оно найдено, то процедура идентификации законче-
на.
Иначе - шаг 3.
3. Ищем min блок, который мы рассмотрели в шаге 2. Если та-
кой блок найден, рассмотрим его и переходим к шагу 2. Иначе,
процедура закончена.
Это мы проверяем одно контекстное условие.
Однако, задача идентификации сложнее, т.к. обычно рассмат-
ривается группа контекстных условий.
1. Каждый идентификатор, входящий в совокупность специфика-
ций, должен также входить в список формальных параметров.
2. Каждый идентификатор, входящий в список значений, должен
входить в совокупность спецификаций.
3. Идентификаторы, входящие в тело процедуры, могут быть
описаны в блоке, вне этого блока или могут быть включены в
список формальных параметров.
Список спецификаций - заголовок (имя) функции, описание ти-
па функции.
Список значений - те параметры, кот. меняются при изменении
функции, т.е. результат.
КОНТЕКСТНЫЕ УСЛОВИЯ ТРЕТЬЕГО ТИПА
Они регламентируют:
1) Соответствие видов величин, входящих в синтаксические
конструкции программ.
2) Задание допустимых соотношений между формальными парамет-
рами в процессах и формальными описаниями соответствующих проце-
дур.
3) Сравнение индексов переменных в использующем и определяю-
щем вхождениях идентификаторов.
4) Сравнение размерности массива в используемом и определяю-
щем вхождении идентификатора.
КОНТЕКСТНЫЕ УСЛОВИЯ ЧЕТВЕРТОГО ТИПА
Некоторые логические ограничения, которые относятся к реа-
лизации той или иной версии транслятора.
Массив может быть с неограниченным размером.
ЛЕКЦИЯ 17
ПРОГРАММНЫЕ ГРАММАТИКИ
Правила вывода этих грамматик имеют тот же вид, что и у
классических, однако в отличии от последних на каждом шаге выво-
да правила, кот. могут быть применены, зависит не только от це-
почек вывода, но и от того, какие правила применялись на преды-
дущих шагах.
Gp = { Vт, Vn, P, I, S }
G - конечное множество целых положительных чисел
(множество меток)
** **
r) Ф -> psi │ W1 │ W2 │, W1, W2 - некоторое подмножество меток
│ * * *
метка,соотв. Ф,psi ( Vт U Vn )
выводу
* - соответствующий класс грамматическим правилам
** - обозначается некоторое подмножество
В терм. порожденной грамматике сформируем использование
данного грамматического файла.
w - промежуточная цепочка.
Если w содержит вхождения по цепочке Ф, то левое вхождение
Ф в цепочке заменяем на psi.
После чего к полученной цепочке вывода применяется правило,
помеченное метками из множества W1.
Если w не содержит вхождения строки Ф, то строка w не моди-
фицируется, и к ней применяется некоторое правило, полученное
меткой из множества W2.
Язык, порожденный этой грамматикой, содержит только терми-
нальные символы.
В зависимости от ограничений на классическую часть различа-
ют:
1) контекстно-свободные,
2) контекстно-зависимые,
3) укорачивающие грамматики.
Имеют место теории, которые доказывают, что программные кон-
текстно-свободной грамматики более мощные, чем просто контек-
стные-свободные грамматики, в то время как зависимые контек-
стно-свободные грамматики совпадают с программно контекстно-сво-
бодными грамматиками.
Когда применяются программные грамматики процесс трансляций
выполняется в 2 этапа:
1) Порождается промежуточная форма программы.
Имеет место некоторый промежуточный язык, в котором некото-
рые синтаксические конструкции отсутствуют (например, внутр.
блоки), а те, которые представлены - состоят из терминальных
символов-двойников, соответствующим терминальным символам прог-
раммы.
2) Промежуточная форма программы проверяется на предмет
соотношения контекстных условий и выполняется замена симво-
лов-двойников на терминальные символы программы.
Все терминальные символы в т.ч. и двойники должны использо-
ваться в различных модификациях.
После первого этапа выполняется проверка контекстных усло-
вий (2 этап).
Каждая проверка заключается в следующем:
- сначала выделяются конструкции, участвующие в проверке;
- выделение производится путем модификации символов, из ко-
торых эта конструкция состоит (присвоение индекса);
- далее производится сравнение выделенных конструкций;
способ зависит от конкретного контекстного условия (сравнение
может производиться на сравнение и не сравнение, т.д.)
Если результаты положительные, то производится вывод неко-
торых построенных конструкций.
На выходе все двойники заменяются на терминальные символы
(соответствующие).
КОНТЕКСТНЫЕ УСЛОВИЯ ДЛЯ ПРОГРАММНЫХ ГРАММАТИК
1. В каждом блоке без внутренних блоков каждый идентифика-
тор должен быть описан не более одного раза (это условие приме-
няется и для меток).
2. По каждому использующему вхождению идентификатора или
целого, представляющего метку, в данном или объемлющем блоках
должно быть описание этого идентификатора.
3. Все переменные в левых частях при присваивании должны
быть одного типа.
4. Количество индексов у переменных с индексами должно сов-
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
