Реферат: Проектирование трансляторов
2) Ri != Rj;
3) для каждого i<j или Ri Rj = 0, или Ri Rj = Ri, т.е.
Rj Ri.
Как уже отмечалось, сдвиг инвариантного оператора из тела
цикла сокращает время выполнения программы. Особенность рассмат-
риваемого метода заключается в том, что оператор сдвигается из
блока во всех случаях, когда он может быть сдвинут независимо от
того, находится он внутри цикла или нет. Ухудшение программы
произойти не может.
Замена переменных в операторах условного перехода
В результате сокращения глубины операции рекурсивная прог-
раммная переменая , являющаяся управляющей в операторе условного
перехода, может быть заменена в нем генерируемой переменной t(mi-
идентификаторов).
Процедура замены переменной в операторе условного перехода
заключается в следующем. После сокращения глубины операции во
всех операторах, использующих рекурсивно определяемые програм-
мные переменные I, находят операторы условного перехода, в кото-
рых I является управляющей переменной.
Определение не используется и может быть устранено, если ре-
зультат определения не является операндом ни одного оператора ре-
курсивного определения и результат этого последнего не ис-
пользуется ни в каком другом операторе.
Как только определение устранено, все вычисления, от кото-
рых оно зависит, если они нигде больше не используются, могут
быть устранены.
Вставка псевдоблока
В процессе оптимизации операторы, сдвигаемые из блоков, со-
бираются в псевдоблок. После оптимизации области Rk операторы
псевдоблока должны быть вставлены в программу так, чтобы они вы-
полнялись до (после) выполнения операторов области Ri.
Для того, чтобы операторы псевдоблока выполнялись на всех
входных (выходых) путях области Rk, они должны вставляться во все
блоки, непосредственно предшествующие (следующие) области либо из
псевдоблока должен быть сформирован блок ,который будет вставлен
на все входные (выходные) пути области Rk.
ЛЕКЦИЯ 15
ОПТИМИЗАЦИЯ ПРОГРАММЫ (ПРОДОЛЖЕНИЕ)
Синтез (генерация) выходного текста
Промежуточный код
Промежуточные коды (или обьектные языки) можно проектиро-
вать на различных уровнях. Так, иногда промежуточный код полу-
чают, просто разбивая сложные структуры языка на более удобные
для обращения элементы. Однако можно в качестве промежуточного
кода ( в этом случае его чаще называют обьектным языком ) ис-
пользовать какой-либо обобщенный машинный код, который затем
транслируется в код реальной машины. Получение промежуточного ко-
да возможно до или после распределения памяти. Если это происхо-
дит до распределения памяти, то операндами могут служить иденти-
фикаторы программы ( или их представления после лексического ана-
лиза ) и присваиваемые компилятором идентификаторы, причем в пос-
леднем варианте используются адреса времени прогона.
Одним из видов промежуточного кода являются четверки.
Например, выражение (-a+b)*(c+d) можно представить как чет-
верки следующим образом: -a = 1
1+b = 2
c+d = 3
2*3 = 4
Здесь целые числа соответствуют идентификаторам, присва-
иваемым компилятором. Четверки можно считать промежуточным
кодом высокого уровня. Такой код часто называют трехадресным
- два адреса для операндов ( кроме тех случаев, когда имеют
место унарные операции ) и один для результата. Другой вари-
ант кода - тройки ( двухадресный код ). Каждая тройка состоит
из двух адресов операндов и знака операции. Если сам операнд
является тройкой, то используется ее позиция, что исключает
необходимость иметь в каждой тройке адрес результата.
Выражение a+b+c*d можно представить в виде четверок:
a+b = 1
c*d = 2
1+2 = 3
и в виде троек:
a+b
c*d
1+2
Тройки компактнее четверок, но если в компиляторе есть
фаза оптимизации, которая пресылает операторы промежуточного
кода, их применение затруднительно. Наилучшее решение этой
проблемы - косвенные тройки, т.е. операнд, ссылающийся на ра-
нее вычисленную тройку, должен указывать на элемент таблицы
указателей на тройки, а не на саму эту тройку.
Как тройки, так и четверки можно распространить не толь-
ко на выражения, но и на другие конструкции языка. Например,
присваивание a := b в виде четверки представляется как
a := b = 1
a в виде тройки - как a := b
Аналогично условное предложение
IF a THEN b ELSE c FI
можно считать выражением с тремя операндами, которому требу-
ются четыре адреса как четверке и три - как тройке.
Не менее популярны в качестве промежуточного кода пре-
фиксная и постфиксная нотации. В префиксной нотации каждый
знак операции появляется перед своими опреандами, а в пост-
фиксной - после. В этом и состоит их отличие от обычной ( ин-
фиксной ) нотации, в которой обозначения двухместных операций
появляются между своими операндами. Например, инфиксное выра-
жение a+b в префиксной нотации примет вид + ab , а в пост-
фиксной - вид ab +.
Префиксная нотация известна также как польская запись, а
постфиксная - как обратная польская запись. С помощью этих
нотаций можно записывать более сложные выражения. Например,
выражение (a+b)*(c+d) в префиксной форме записывается следую-
щим образом: *+ab+cd
а в постфиксной так: ab+cd+*
Каждый знак опреации в префиксной нотации ставится не-
посредственно перед своими операндами, а в постфиксной после
них.
В префиксной и постфиксной нотациях скобки уже не требу-
ются, так здесь никогда не возникает сомнений относительно
того, какие операнды принадлежат к тем или иным знакам опера-
ций. В этих нотациях не существует приоритета знаков опера-
ций, хотя при преобразовании инфиксных выражений в префиксные
или постфиксные их приоритет, несомненно, нужно учитывать.
Перегруппировку в результате преобразования
(a+b)*(c+d)
в
ab+cd+*
можно осуществить с помощью стека. Алгоритм такого преобразо-
вания хорошо известен. Это преобразование можно выполнить
также на основании грамматики инфиксных выражений. В данном
случае оно сведется к трем действиям:
1) напечатать идентификатор, когда он встретится при
чтении инфиксного выражения слева направо;
2) поместить в стек знак операции, когда он встретится;
3) когда встретится конец выражения ( или подвыражения ),
выдать на печать тот знак операций, который находится в вер-
шине стека.
Этот метод подобен методу, который применяется для полу-
чения четверок. Префиксные и постфиксные выражения можно так-
же получить из представления выражения в виде бинарного дере-
ва. Чтобы получить представление префиксного выражения, дере-
во обходят сверху в порядке, определенном Кнутом:
посещение корня;
обход левого поддерева сверху;
обход правого поддерева сверху,
что дает
+*+abcd
Для получения постфиксного представления дерево обходят
снизу. По Кнуту это выглядит так:
обход левого поддерева снизу;
обход правого поддерева снизу;
посещение корня.
В результате имеем: ab+c*d+
Далее будем рассуждать в терминах промежуточного языка (
или обьектного ), состоящего из команд вида
тип-команды параметры
Тип-команды может быть, например, вызовом стандартного
обозначения операции, тогда параметрами могут быть имя знака
операции, адреса опреандов и адрес результата. Например,
STANDOP II+,A,B,C
Здесь II+ обозначает сложение двух целых чисел, а A, B,
C cлужат во время прогона адресами двух операндов и результа-
та. Для того чтобы в промежуточном коде можно было воспользо-
ваться адресами во время прогона, распределение памяти к это-
му времени должно быть уже закончено. При распределении памя-
ти необходимо знать, какой обьем памяти занимает целое, ве-
щественное и другие значения на той машине, для которой выда-
ется обьектный код. Это означает, что промежуточный код не
является в строгом смысле интерфецсом между не зависящей и
зависящей от машины частями компилятора. Тем не менее если
речь идет о переводе фронтальной части компилятора ( т.е.
части, транслирующей исходный код в промежуточный ) с одной
машины на другую, то единственное, что здесь может потребо-
ваться, - это изменение нескольких констант.
Промежуточный код пишется на относительно низком уровне.
Он аналогичен коду, использованному для реализации Алгола 68.
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40
