В процессе трансляции программы используется промежуточное представление (ПП) программы, предназначенное для эффективной генерации кода и проведения различных оптимизаций программы. Сама форма ПП зависит от целей его использования. Наиболее часто используемыми формами ПП является ориентированный граф (иногда абстрактное синтаксическое дерево), тройки, четверки, префиксная или постфиксная запись, атрибутированное абстрактное дерево.
Представление в виде ориентированного графа
Простейшей формой промежуточного представления является синтаксическое дерево программы. Более полную информацию о входной программе дает ориентированный ациклический граф (ОАГ), в котором в одну вершину объединены вершины синтаксического дерева, представляющие одни и те же константы, переменные и общие подвыражения. На рис. 1 приведены оба ПП программы.
Рис. 1. Промежуточные представления программы.
Трехадресный код
Трехадресный код- это последовательность операторов вида x:= y op z, где x,y и z - имена, константы или сгенерированные компилятором временные объекты. Здесь op - двуместная операция, например операция плавающей или фиксированной арифметики, логическая или побитовая. В правую часть может входить только один знак операции.
Составные выражения должны быть разбиты на подвыражения, при этом могут появиться временные имена (переменные). Смысл термина "трехадресный код" в том, что каждый оператор обычно имеет три адреса: два для операндов и один для результата. Трехадресный код - это линеаризованное представление синтаксического дерева или ОАГ, в котором явные имена соответствуют внутренним вершинам дерева или графа. Например, выражение x+y*z может быть протранслировано в последовательность операторов
t1:=y*z
t2:=x+t1
где t1 и t2 - имена, сгенерированные компилятором.
В виде трехадресного кода представляются не только двуместные операции, входящие в выражения. В таком же виде представляются операторы управления программы и одноместные операции. В этом случае некоторые из компонент трехадресного кода могут не использоваться. Например, условный оператор
if A>B then S1 else S2
может быть представлен следующим кодом:
t:=A-B
JGT t,S2
.....
Здесь JGT - двуместная операция условного перехода, не вырабатывающая результата.
Разбиение арифметических выражений и операторов управления делает трехадресный код удобным (???) при генерации машинного кода и оптимизации. Использование имен промежуточных значений, вычисляемых в программе, позволяет легко переупорядочивать трехадресный код.
|
t1 := -c t2 := b * t1 t3 := -c t4 := b * t3 t5 := t2 + t1 a := t5 |
t1 := -c t2 := b * t1 t5 := t2 + t2 a := t5 |
| а) | б) |
Представления синтаксического дерева и графа рис. 1 в виде трехадресного кода дано на рис. 2. а) и 2. б), соответственно.
Трехадресный код - это абстрактная форма промежуточного кода. В реализации трехадресный код может быть представлен записями с полями для операции и операндов. Рассмотрим три реализации трехадресного кода: четверки, тройки и косвенные тройки.
Четверка - это запись с четырьмя полями, которые будем называть op, arg1, arg2 и result. Поле op содержит код операции. В операторах с унарными операциями типа x:=-y или x:=y arg2 не используется. В некоторых операциях (типа "передать параметр") могут не использоваться ни arg2, ни result. Условные и безусловные переходы помещают в result метку перехода. Обычно содержимое полей arg1, arg2 и result - это указатели на входы таблицы символов для имен, представляемых этими полями. Временные имена вносятся в таблицу символов по мере их генерации.
Чтобы избежать внесения новых имен в таблицу символов, на временное значение можно ссылаться, используя позицию вычисляющего его оператора. В этом случае трехадресные операторы могут быть представлены записями только с тремя полями: op, arg1 и arg2. Поля arg1 и arg2 - это либо указатели на таблицу символов (для имен, определенных программистом, или констант), либо указатели на тройки (для временных значений). Такой способ представления трехадресного кода называют тройками. Тройки соответствуют представлению синтаксического дерева или ОАГ с помощью массива вершин.
При генерации объектного кода каждой переменной, как временной, так и определенной в исходной программе, назначается память периода исполнения, адрес которой обычно хранится в таблице генератора кода. При использовании четверок этот адрес легко получить через эту таблицу.
Линеаризованные представления
В качестве промежуточных представлений весьма распространены линеаризованные представления. Линеаризованное представление позволяет относительно легко хранить промежуточное представление на внешней памяти и обрабатывать его в порядке чтения. Самая распространенная форма линеаризованного представления - это запись дерева либо в порядке его обхода снизу-вверх (постфиксная запись, или обратной польской), либо в порядке обхода его сверху-вниз (префиксная запись, или прямой польской).
Таким образом, постфиксная запись (обратная польская) - это список вершин дерева, в котором каждая вершина следует непосредственно за своими потомками. Дерево на рис. 1 в постфиксной записи может быть представлено следующим образом:
a b c - * b c * + :=
В постфиксной записи вершины синтаксического дерева явно не присутствуют. Они могут быть восстановлены из порядка, в котором следуют вершины и из числа операндов соответствующих операций. Восстановление вершин аналогично вычислению выражения в постфиксной записи с использованием стека.
В префиксной записи сначала указывается операция, а затем ее операнды. Например, для приведенного выше выражения имеем
:= a + * b - c * b - c
Организация информации в генераторе кода
Чисто синтаксическое дерево несет только информацию о структуре программы. На самом деле в процессе генерации кода требуется также информация о переменных (например, их адреса), процедурах (также адреса, уровни), метках и т.д. Для представления этой информации возможны различные решения. Наиболее распространены два. 1) всю эту информацию можно хранить в таблицах генератора кода; 2) информация хранится в вершинах дерева с соответствующими указателями.
При входе в процедуру в таблице уровней процедур заводится новый вход - указатель на таблицу описаний. При выходе указатель восстанавливается на старое значение. Если промежуточное представление - дерево, то информация может храниться в вершинах самого дерева.
Уровень промежуточного представления
Промежуточное представление программы может в различной степени быть близким либо к исходной программе, либо к машине. Например, промежуточное представление может содержать адреса переменных, и тогда оно требует обработки перед перенесением на другую машину. С другой стороны, промежуточное представление может содержать раздел описаний программы, и тогда информацию об адресах можно извлечь из обработки описаний. В то же время ясно, что первое более эффективно, чем второе.
Операторы управления в промежуточном представлении могут быть представлены в исходном виде (в виде операторов языка if, for, while и т.д.), а могут содержаться в виде переходов. В первом случае некоторая информация может быть извлечена из самой структуры (например, для оператора for - информация о переменной цикла, которую, может быть, разумно хранить на регистре, для оператора case - информация о таблице меток и т.д.). Во втором случае возможно представление проще и унифицированней.
Некоторые формы промежуточного представления лучше годятся для различного рода оптимизаций (например, ориентированные графы), некоторые - хуже (например, префиксная запись для этого плохо подходит). Алгоритм перевода выражения в ПОЛИЗ Одним из фундаментальных алгоритмов, использующихся в разного рода трансляторах, является перевод выражения из инфиксной записи в обратную польскую запись.
Рассмотрим алгоритм.
Сначала определяются приоритеты операций, организовывается стек операций, изначально пустой. Пусть самые приоритетный операторы имеют самый маленький численный приоритет. Припишем круглым скобкам максимальный приоритет. Пример таблицы приоритетов дан ниже.
| Оператор | Приоритет |
| - (унарный) | 1 |
| not | 2 |
| ^^ | 3 |
| *, /,% | 4 |
| +, - | 5 |
| and, or, xor | 6 |
| (, ) | 100 |
В ходе преобразования мы имеем входную строку, выходную строку и стек операций. (Ниже в таблице показа пример разбора выражения). Если нам встречается символ (идентификатор), то мы его просто переписываем в выходную строку. Если нам попадается открывающая скобка, то она просто вносится в стек операций. Если нам попадается любой иной символ операции, то мы определяем его приоритет и начинаем обозревать вершину стека операторов. Пока приоритет вершины стека менее или равен (согласно числу в таблице) чем приоритет текущего оператора, переносим операцию с вершины стека в конец выходной строки. Это продолжается, пока не встретится операция большая по числу приоритета или пока стек не опустеет. Открывающая скоба отбрасывается, а не дописывается к строке, закрывающая скобка в стек не вносится. При окончании входной строки мы заканчиваем разбор, "вталкивая" закрывающую скобку в стек операций.
Пример разбора показан в таблице.
| Входная строка | Стек операций | Выходная строка |
| a*b/c+a*b+(a-c)*d | ||
| *b/c+a*b+(a-c)*d | a | |
| b/c+a*b+(a-c)*d | * | a |
| /c+a*b+(a-c)*d | * | ab |
| c+a*b+(a-c)*d | / | ab* |
| +a*b+(a-c)*d | / | ab*c |
| a*b+(a-c)*d | + | ab*c/ |
| *b+(a-c)*d | + | ab*c/a |
| b+(a-c)*d | +* | ab*c/a |
| +(a-c)*d | +* | ab*c/ab |
| (a-c)*d | + | ab*c/ab*+ |
| a-c)*d | +( | ab*c/ab*+ |
| -c)*d | +( | ab*c/ab*+a |
| c)*d | +(- | ab*c/ab*+a |
| )*d | +(- | ab*c/ab*+ac |
| *d | + | ab*c/ab*+ac- |
| d | +* | ab*c/ab*+ac- |
| +* | ab*c/ab*+ac-d | |
| ab*c/ab*+ac-d*+ |
Синтаксически управляемый перевод на примере перевода арифметического
выражения в ПОЛИЗ.
Продолжая рассмотренный алгоритм, приведём реальный пример перевода выражения с языка Паскаль в обратную польскую запись.
Для этого сделаем несколько дополнений, в частности мы можем ввести операции с наивысшим приоритетом:
| Оператор | Приоритет |
| := | 101 |
| ^,. | 0 |
Так как выражение присваивания обычно имеет вид <переменная>:= <выражение>, то приоритет операции присваивания должен быть менее приоритета скобок, а приоритет операций ссылки по указателю, и ссылки на структуру наивысший. Отдельно отметим, что операция адресации "@" прямо не является операцией, а лишь префиксом, который отменяет последнюю адресацию, хотя при соответствующем генераторе кода с возможностью отмены последней ссылки адресация может быть обработана как обычная операция в стеке.
Последний штрих - после конца строки мы выталкиваем оператор присваивания неким фиктивным оператором, приоритет которого менее приоритета оператора присваивания.
Для исполнения выражения, записаного в обратной польской записи необходима организация арифметического стека. Арифметический стек используется для хранения промежуточных результатов. Переменные (их значения), встречающиеся в правой части выражения заносятся на стек, операторы преобразовывают верхние два, три или одно число в результат, операнды снимаются со стека и туда помещается результат. Оператор присваивания снимает со стека адрес переменной и значение, которое надо поместить по этому адресу. Детальнее расмотрим алгоритм генерации кода через раздел.
Представление условных операторов, операторов цикла и
оператора безусловного перехода в ПОЛИЗ.
Условные операторы, операторы цикла и операторы безусловного перехода довольно легко представляются в обратной польской записи. В любом случае внутри этих операторов лежат безусловный и условный переходы. Безусловный переход достаточно просто определяется - как в соответствующем языке ассемблера
JMP метка
оператор условного перехода требует большей работы. Вспомним, что любое логическое выражение оставляет на арифметическом стеке булево значение, обычно не нуль или нуль. Таким образом фрагмент программы может выглядеть так:
pop ax
test ax,ax
jnz метка_перехода
Генерация кода на языке ассемблер, для вычисления
арифметического выражения.
Одно важное свойство, присущее генерации кода для выражения в обратной польской записи, это то, что код строится последовательно, фактически дописывая кусочек кода за кусочком, соответствующий семантике данного выражения.
Рассмотрим таблицу случаев генерации кода для процессора 8086/8087, для случая - один для 8086, другой для сопроцессора 8087. Условимся, что вершина арифметического стека кешируется в 8086 процессоре в регистре bx.
| Действие | Код для 8086 | Код для 8087 |
| := | pop ax ; адрес xchg ax,bx mov [bx],ax ; двигаем |
fstp dword ptr [bx]; в bx адрес pop bx |
| Внесение левой части в стек (или любого адреса) | push bx mov bx, offset var |
|
| Внесение переменной в стек | push bx mov bx, var |
fld var |
| Унарный минус | neg bx | fchs |
| Бинарная операция: вычитание | pop ax xchg ax,bx sub bx,ax |
fsub |
| Бинарная операция: сложение | pop ax add bx,ax |
fadd |
| Ссылка по адресу | mov bx,[bx] | |
| Ссылка на структуру | mov bx,[bx+offset field] | |
| Тернарная условная операция | test bx,bx pop bx pop ax jz exit1 xchg ax,bx exit1: ... |
fistp temp wait mov ax,temp and ax,ax jz exit2 fxch exit2: fincstp ffree st |
| Загрузка значения по адресу | mov bx, [bx] | fld dword ptr [bx] |
Вообще, есть немало способов реализации генерации кода для выражения, записанного в обратной польской записи. В любом случае, на основании этой таблицы можно придумать аналогию для любого процессора.
Генерация кода для операторов READ и
WRITE языка ПАСКАЛЬ.
Напомним формат вывода и ввода для языка Паскаль, например:
write[ln]('File has ',l,' lines and ',w,'words');
Естественно, мы должны определить некоторые соглашения по вызову таких функций - основной сложностью является то, что функция принимает переменное количество аргументов. Так как гораздо проще реализовать усложнённую функцию печати сообщений, чем усложнять компилятор, договоримся, что мы будем дополнительно передавать в функцию количество её аргументов, но непосредственно перед вызовом, чтобы вызываемая функция могла их вообще получить. Договоримся, что будем передавать каждый аргумент двумя фактическими параметрами: адресом аргумента и ярлыком типа аргумента. Независимо от операции WRITE или READ фактически списки аргументов не отличаются.Ещё условимся, что вызываемая функция очищает стек.
Рассмотрим генерацию кода для приведённого оператора:
| str_1 db 9,"File has "; str_2 db 10,"lines and" str_3 db 5,"words" |
Определим в сегменте данных три строки в формате Паскаль |
| ... | |
| push offset str_3 push STRING |
Адрес строки и ярлык строки |
| push offset w push INTEGER |
Адрес целого числа, опции форматирования можно добавить к ярлыку |
| push offset str_2 push STRING |
Адрес строки и ярлык |
| push offset l push FLOAT |
Адрес плавающего числа и ярлык - пусть число строк будет плавающим |
| push offset str_1 push STRING |
Адрес строки и ярлык |
| push 5 | Число параметров |
| call _writeln_ | Собственно вызов функции |
| ... |
Генерация кода для условного оператора IF, вложенного
оператора IF языка ПАСКАЛЬ.
Для генерации кода для любых вложенных операторов управления нам нужны дополнительные структуры. Условно назовём такую структуру стеком вложенных операторов. Условимся, что в стеке будут хранится некие структуры одинакового вида. Структура будет как минимум содержать ярлык управляющей структуры и некоторые необходимые данные. Для начала условимся, что будет как минимум ярлык - целое число. Рассмотрим детально процесс генерации кода.
| if (условие) then |
test bx,bx jne метка_ХХХ |
Генерируем код с уникальным именем метки, имя этой метки вместе с ярлыком _IF_ ложим на стек |
| ... else ... | jmp метка_YYY метка_XXX: |
Здесь мы достаём из стека ярлык _IF_ вместе с сгенерированным ранее именем метки, вставляем эту метку в ассемблеровский листинг, затем ложим на стек новую уникальную метку YYY с ярлыком _ELSE_ |
| ... ; | метка_YYY: |
Достаём из стека ярлык _ELSE_ с меткой, которую вставляем в листинг |
Дополнительные комментарии к примеру вряд ли требуются. Ясно, что стек управляющих операторов позволяет обрабатывать сколь угодно вложенные структуры.
Генерация кода для оператора цикла FOR, вложенного
оператора FOR языка ПАСКАЛЬ.
Продолжаем обсуждение, но уже рассматривая цикл FOR:
| FOR var:=Value1 | push dx mov dx, Value1 |
Инициализируем индексную переменную - регистр dx, сохраняя прежнюю в стеке |
| TO|DOWNTO Value2 | loop_XXX: cmp dx,Value2 ja|jb loop_exit_XXX |
Здесь мы генерируем уникальную метку (на самом деле только суффикс XXX), которую мы ложим на стек вместе с ярлыком _FOR_ и пометкой, увеличивается или уменьшается в цикле индексная переменная |
| DO ... | ... ;тело цикла | в dx - индексная переменная |
| ... ; | inc|dec dx jmp loop_XXX loop_exit_XXX: pop dx |
Вынимаем из стека управляющих операторов ярлык _FOR_, генерируем инкремент или декремент индексной переменной, генерируем переход к началу цикла, метку окончания цикла и восстанавливаем регистр, содержащий индексную переменную |
Аналогично, вряд ли требуются дополнительные комментарии и ясно, как поддерживаются вложенные операторы FOR.
Генерация кода для операторов цикла WHILE, REPEAT языка
ПАСКАЛЬ.
Закончим обсуждение генерации кода примером для условным циклов. Первым
будет цикл WHILE.
| WHILE (условие) DO |
w_loop_XXX: ...;код вычисления ...;условия test bx,bx jz w_loop_exit_XXX |
Здесь мы генерируем уникальную метку (реально только уникальный суффикс), которую мы ложим на стек вместе с ярлыком _WHILE_, заметим, что между метками располагается не показанный здесь код вычисления условия, который возвращает булево значение на вершине стека |
| ... ; | jmp w_loop_XXX w_loop_exit_XXX: |
Вынимаем из стека управляющих операторов ярлык _WHILE_, генерируем переход к началу циклаb метку окончания цикла |
Аналогичный пример для REPEAT:
| REPEAT ... |
r_loop_XXX: ... |
Здесь мы генерируем уникальную метку, которую мы ложим на стек вместе с ярлыком _REPEAT_ |
| UNTIL(условие); | ...;код вычисления ...;условия test bx,bx jnz r_loop_XXX |
Вынимаем из стека управляющих операторов ярлык _WHILE_, генерируем код вычисления условия, который возвращает булево значение на вершине стека и генерируем переход к началу цикла |
Аналогично, вряд ли требуются дополнительные комментарии и ясно, как поддерживаются вложенные операторы WHILE/REPEAT.