Проектирование трансляторов
-вычисление адреса хранения массива;
-вычисление адреса хранения допвектора;
-занесение этих адресов в соответствующие ячейки.
Для массивов с постоянными границами компоненты допвектора
вычисляются в ходе трансляции и помещаются среди констант. Чтобы
отличить переменные граничные пары от постоянных нужно ввести до-
полнительный анализ операндов ADEC, являющихся граничными парами.
Допвектора могут располагаться вслед за парой ячеек, выделенной
последнему массиву или среди констант(для массива с постоянными
границами.
ЛЕКЦИЯ 12
СТРУКТУРЫ ДАННЫХ И ОРГАНИЗАЦИЯ ПАМЯТИ
Некоторые применяемые языки требуют динамического распреде-
ления памяти; блоки оперативной памяти при этом выделяются произ-
вольно, а затем освобождаются. Область данных - это блок ОП, вы-
деленный для данных.
Области данных могут принадлежать также к статическому клас-
су. Статическая область данных имеет постоянное число ячеек, а
динамическая область данных не всегда присутствует во время счета.
Если вызов процедуры происходит рекурсивно, то существует
несколько областей данных в ОП, каждая для отдельного вызова про-
цедуры.
Если компилятор знает все характеристики переменных во вре-
мени, то он может сгенерировать полностью команды обращеиня к пе-
ременным, основываясь на этих характеристиках.
Память выделяется компилятором не только для переменных, но
и для описателей, содержащих атрибуты, определяемые во время сче-
та. Этот описатель заполняется и изменяется во время счета. Типы
данных исходной программы должны быть отображены на типы данных
машины. Целые переменные содержатся обычно в одном слове.
Информационные таблицы
При анализе программы из описаний, заголовков процедур, цик-
лов и т.д. извлекается информация и сохраняется для последующего
использования. Эта информация обнаруживается в отдельных точках
программы и организуется так, чтобы к ней можно было обратиться
из любой части компилятора. В каждом компиляторе в той или иной
форме используется таблица символов. Это таблица идентификаторов,
встречающихся в программе, вместе с их атрибутами.
При разборке компилятора невозможно определить вид и содер-
жание информации, которую следует собирать, до тех пор, пока не
будут достаточно обстоятельно продуманы команды обьектной прог-
раммы для каждой инструкции исходной программы и сама синтезирую-
щая часть компилятора.
При проверке правильности семантики и генерации кода тре-
буются знания характеристики идентификатора. Эти характеристики
выясняются из описания и накапливаются в таблице символов. Наип-
ростейшая таблица символов для каждого элемента имеет поле аргу-
мента и значения. Аргументами таблицы являются символы или иден-
тификаторы, а значениями - их характеристики. Так как число ли-
тер в идентификаторе непостоянно, в аргументе часто помещают сим-
волы вместо самого идентификатора. Это позволяет сохранить фикси-
рованный размер аргумента. Идентификаторы хранятся в специальном
списке строк.
При проходе исходной программы через компилятор при встрече
конструкции описания происходит запись идентификатора исходной
программы в таблицу символов вместе с его атрибутами. В результа-
те дальнейшего чтения исходной программы, в компиляторе при на-
хождении любого идентификатора программа обращается к таблице
символов и ищет в ней данный идентификатор. Если идентификатор не
обнаружен, то выдается сообщение, что данный идентификатор не оп-
ределен. Если же он обнаружен, то производится сравнение данного
идентификатора с записанным в таблице символов и производятся
необходимые преобразования.
При работе с таблицей символов нужно разработать правила ор-
ганизации и обращения к таблице символов. Таблицы символов могут
быть как упорядоченными, так и неупорядоченными.
При упорядоченном списке элементов наиболее результативным
является бинарный или логарифмический поиск. Иногда один и тот же
идентификатор может быть описан и использован много раз в различ-
ных блоках и процедурах, и каждое такое описание должно быть
единственным. Соответственно нужно разделять таблицу симводов.
При этом устанавливается правило нахождения соответствующего
идентификатора. Оно состоит в следующем: сначала просматривается
текущий блок, затем обьемлющий блок и т.д., до тех пор, пока не
будет найдено описание данного идентификатора.
При осуществлении поиска все элементы таблицы хранятся для
каждого блока в смежных ячейках и используется список блоков.
Информация об идентификаторе хранится в той части таблицы,
которую мы определили как "значение".
Таблица символов состоит из 5-ти различных списков:
- список меток;
- список арифметических констант;
- список имен общих блоков,имен подпрограмм и имен перемен-
ных;
- список общих блоков;
- список имен подпрограмм.
Элементы всех этих списков помещаются в одной и той же таб-
лице; первые два байта каждого элемента используются для ссылки
на следующий элемент в том же списке.
ЛЕКЦИЯ 13
ВНУТРЕННИЕ ФОРМЫ ИСХОДНОЙ ПРОГРАММЫ
Ввиду сложности реальных языков программирования и предъяв-
ления повышенных требований к эффективности самого процесса ком-
пиляции и к готовым программам, разработчики вынуждены проектиро-
вать многопроходные компиляторы. При этом для связи между прохо-
дами, необходимы внутренние (промежуточные) формы исходной прог-
раммы. В большинстве внутренних форм, операторы располагаются в
том порядке, в котором они должны выполняться, что означает пос-
ледующий анализ и итерацию об'ектного кода. (Эти внутренние пред-
ставления можно использовать для интерпретации).
Внутренняя форма является более развернутым представлением
исходной программы, к которой предъявлялись требования лаконич-
ности и краткости. Более подробное представление обеспечивает
проведение глубокого анализа и оптимизации программ.
Как правило, в одном компиляторе для разных синтаксических
единиц (выражений, условных операторов, операторов присваивания и
т.д.) используются разные, наиболее подходящие с точки зрения
разработчика, внутренние формы.
1.1. Опреанды и операторы
Внутренние формы содержат операторы и операнды. В различных
видах представлений существенное отличие заключается в форме сое-
динения операторов и операндов.
Операторы: + , - , / , * , BR (branch) и т.п. Операнды : -
простые имена (переменных, процедур и т.д.);
- константы;
- временные переменные, генерируемые компилятором;
- переменные с индексами.
Каждый операнд (за исключением переменных с индексом) пред-
ставляется указателем на соответствующий элемент в таблице симво-
лов, констант или временных переменных.
В поле операнда предусматривается признак косвенной адреса-
ции, чтобы указать таким путем, что значение в таблице, на кото-
рое указывает операнд, является адресом расположения значения,
которое требуется операнду при исполнении команды.
Пременную с индексами А[i,j,...,k] можно обрабатывать сле-
дующим образом:
- сначала включить последовательность операций для вычисления
VARPART и запоминания ее во внешней ячейке Т;
- сам операнд представить двумя указателями: на элемент с име-
нем массива и на значение VARPART, т.е. А[i,j,...,k] можно
представить в виде А[T]. Такой операнд занимает две ячейки
во внутреннем представлении, но зато позволяет генерировать
более эффективную объективную программу. Простая переменная
┌───┬───┬─────────────────────────────────────┐
│ 1 │ I │ указатель на эл-т таблицы символов │ I - признак
└───┴───┴─────────────────────────────────────┘ косвенной
Константа адресации
┌───┬───┬─────────────────────────────────────┐
│ 2 │ │ указатель на эл-т таблицы констант │
└───┴───┴─────────────────────────────────────┘
Временная переменная
┌───┬───┬─────────────────────────────────────┐
│ 3 │ I │ указатель на эл-т табл. врем. перем.│
└───┴───┴─────────────────────────────────────┘
Перменная с индексами
┌───┬───┬─────────────────┬───┬───┬───────────────┐
│ 4 │ I │ ук-ль на эл-т │ х │ I │ ук-ль на эл-т │
│ │ │ с именем массива│ │ │ с индексом │
└───┴───┴─────────────────┴───┴───┴───────────────┘
┌─────────────────────────┘
│ описание индексов
х = 1 - указатель на табл. символов
2 - указатель на табл. констант
3 - указатель на табл. временных переменных
Форматы операндов
Польская запись
1.Польский логик Я.Лукашевич впервые применил запись арифмети-
ческих и логических выражений, которая без скобок указывает точ-
ный порядок выполнения операций. В ней операторы следуют непос-
редственно за операндами (постфиксная запись). Она определяется
следующими правилами:
1) операнды следуют в том же порядке, как они представлены в
префиксной записи;
2) операторы следуют в том же порядке, в каком они должны
вычисляться (слева направо);
3) опер-ры располаг-ся непосредственно за своими оп-дами.
Это можно представить следующими правилами: <операн-
д>::=<идентификатор>|<операнд><операнд><оператор>
<оператор>::= + | - | / | * | ... Для унарных оперций можно
ввести новый символ ( например @ для -) и еще одно правило
<операнд>::=<операнд>@ Пример A * ( B + C / D ) <=> ABCD / + *
A + ( -B + C * D ) <=> AB@CD * + +
(C таким же успехом можно применять префиксную запись).
Вычисление арифметических выражений
Данные правила определяют порядок обработки выражения с по-
мощью стека за один просмотр выражения слева направо, начиная с
самого левого символа входной цепочки:
1. Если сканируемый символ идентификатор, то его значение
заносим в стек и переходим к следующему символу (правило <оп-
реанд>::= идентификатор)
2. Если сканируемый символ - бинарный оператор, он приме-
няется к двум верхним операндам в стеке и замещает их на получен-
ный результат, что эквивалентно правилу <операнд>::= <операнд><о-
перанд><оператор>.
3. Если сканируемый символ - унарный оператор, то он приме-
няется к верхнему символу стека и затем замещает его результатом
(правило <операнд>::= <операнд><оператор> [ Д/З - стр.282 ]
Включение в польскую запись других операторов
1) Присваивание <пер.>::= <выр.> ( <=><пер.><выр.>:= )
прим.: А := В * С + D <=> АВС * D + :=
- После выполнения оператора := из стека исключаются <пер.> и
<выр.>, т.к. этот оператор не имеет результирующего значения в
отличие от бинарных арифметических операторов.
- Кроме того, в стеке находится не значение <пер.> (оно нам
не нужно), а ее адрес, т.к. в рез-те присвоения по нему заносит-
ся значение <выр.>
2) Оператор GOTO А <=> A BRL,
где метка А представлена адресом соответствующего ей эл-та
таблицы символов. Оператор BRL (Branch to label)
3) Условные переходы
<операнд1><операнд2> BP, где первый операнд является значе-
нием арифметического выражения, второй указывает номер (место)
символа в цепочке польской записи. Если операнд1 положителен
(positive), то в качестве следующего берется символ, на который
указывает операнд2, иначе работа продолжается как обычно.
BP - переход по положительному значению, ВМ - по минусу, BZ
- по нулю, BPZ - по неотрицательному значению, и т.д.
4) Условная инструкция
IF<выр>THEN<инстр.1>ELSE<инстр.2><=><выр><С1>BZ<инср.1><С2>BR<инстр.2>
С1 - номер имвола, с которого начинается <инстр.2>.
С2 - номер символа,следующего за <инстр.2>.
Операторы BZ и BR не порождают результирующего значения.
Часть их работы состоит в исключении из стека двух верхних эле-
ментов (значения <выр> и <С1>) для BZ и соответственно одного
<С2> для BR. Оператор безусловного перехода <С2>BR - использует-
ся метка <С2> для внутренних генерируемых переходов. В то время
как оператор <метка> BRL в качестве значения <метка> использует
адрес эл-та таблицы символов.
5) Описание массива. ARRAY A[Li:Ui,...,Ln:Un]
можно представить в виде:
LiUi...LnUn A ADEC, где ADEC - оператор, имеющий переменное
число операндов, зависящее от числа индексов. Операнд А - оче-
видно, адрес элемента таблицы символов для А -> При вычислении
ADEC, следовательно, из этого элемента таблицы извлекается ин-
формация о размерности массива А (т.е. и о числе операндов ADEC)
- с этой целью изменен порядок записи операндов.
6) Переменная с индексами A[<выр.i>,...,<выр.n>] преставляется
в виде <выр.1>...<выр.2> A SUBS
Оператор SUBS используя элемент А таблицы символов и ин-
дексные выражения, вычисляет адрес элемента массива. Затем опе-
ранды исключаются из стека и на их место заносится новый опе-
ранд, определяемый адресом элемента массива и его типом.
Использование для индексирования специального оператора
SUBS - более удобный способ для польской записи.
Пример: BEGIN INTEGER K; ARRAY[1:I-j]; K:=0;
L:IF I>j THEN K:=K+A[I-j]*6 ELSE
BEGIN I:=I+1;I:=I+1;COTOL END
END
(1) BLOCK 1 IJ - A ADEC K0 := Польская запись
(11) IJ - 29 BMZ
(16) K KIJ - A SUBS 6*+:= 41 BR Для каждого символа отво-
(29) II1 + := II1 + := L BRL дится одна строка (место)
(41) BLCEND
Как видно, описание INTEGER K (не требующее генерации ко-
манд) отсутствует во внутреннем представлении. Оно нужно для
формирования элемента таблицы символов для К.
Введены два оператора без операндов BLOCK (начало блока) и
BLCKEND (конец блока).
N содерж. N содерж. таблица
слова слова символ слова слова символ символов
┌────┬────┬────┬───────┬────┬────┬────┬────────┬───┬─────┐
│ 1 │ 11 │ │ BLOCK │ 36 │ 6 │ │ SUBS │ 1 │ I │
├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤
│ 2 │ 1 │ 1 │ 1 │ 37 │ 1 │ 6 │ 6 │ 2 │ Y │
├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤
│ 4 │ 2 │ 1 │ I │ 39 │ 15 │ │ * │ 3 │ A │
├────┼────┼────┼───────┼────┼────┼────┼────────┼───┼─────┤
│ 6 │ 2 │ 2 │ Y │ 40 │ 14