Реферат: Проектирование трансляторов
(переменные, константы, процедуры и т.д.). Компиляторы, осущес-
твляющие значительную работу по оптимизации кода, создают де-
тальное представление промежуточной программы, точно описывающее
порядок выполнения исходной программы. В других компиляторах
представлением промежуточной программы служит простое представле-
ние синтаксического дерева, такое как польская запись.
Польская запись
Для представления арифметических и логических выражений ис-
пользуется польская запись. Она имеет ряд преимуществ перед ин-
фиксной: формула может быть записана без скобок; эта форма пред-
ставления очень удобна для ЭВМ со стековой адресацией; если зна-
ки операций в инфиксной форие различаются по старшинству, то
польская запись устраняет эту систему приоритетов).
В польской записи операнды следуют непосредственно за опера-
торами. Вычисление таких записей производится с помощью стека,
где будут находиться все операнды, встретившиеся при просмотре
выражения.
Просмотр начинается с самого левого символа. Прочитав его и
обработав, переходим к следующему. Последовательность обработки
такова:
1) если сканирующий символ - идентификатор или константа, то
его значение заносится в стек и осуществляется переход к следую-
щему;
2) если сканирующий символ-бинарный оператор, то он приме-
няется к двум верхним операндам в стеке и затем они заменяются на
полученный результат;
3) если сканирующий символ - унарный оператор, то он приме-
няется к верхнему операнду в стеке, который затем заменяется на
полученный результат.
Тетрады
Для бинарных операций удобной формой представления являются
тетрады. Тетрада имеет вид: <оператор> <операнд1> <операнд2>
В тетраде отсутствует поле результата. Если позже какой-ли-
бо операнд окажется результатом данной операции, то он будет на
нее непосредственно ссылаться.
Существуют и другие формы внутреннего представления.
Деревья
Мы опpеделили КС-язык, задаваемые некотоpой гpамматикой, как
множество теpминальных цепочек, котоpые можно вывести из на-
чального символа. Можно постpоить деpево вывода цепочки КСязыка.
Это легко сделать, интеpпpетиpуя подстановки, как шаги постpое-
ния деpева.Однако деpево не несет никакой инфоpмации о поpядке
пpименеия пpавил, кpоме того что пpавила должны пpименяться к
каждой веpшине деpева pаньше, чем к нетеpминальным веpшинам pас-
положенным ниже. Поскольку поpядок вывода в деpеве скpыт, то мо-
жет быть несколько выводов, соответствующих одному и тому же
деpеву вывода. Для каждого деpева существует единственный левый и
единственный пpавый вывод, котоpый получается, если всегда заме-
нять самый пpавый нетеpминал. Многие методы обpаботки языков pас-
читаны исключительно на левые или пpавые выводы,так как они очень
удобны для семантической обpаботки. Когда одна цепочка может
иметь несколько деpевьев вывода, говоpят, что соответствующая
гpамматика неоднозначна. Все сказанное можно pезюмиpовать следую-
щим обpазом:
1. Каждой цепочке, вводимой в данной КС-гpамматике, соответ-
ствует одно или несколько деpевьев вывода.
2. Каждому деpеву соответствует один или несколько выводов.
3. Каждому деpеву соответствует один пpавый и один левый вы-
вод.
4. Если каждой цепочке, вводимой в КС-гpамматике, соответ-
ствует единственное деpево вывода, эта гpамматика называется од-
нозначной; в пpотивном случае ее называют неоднозначной.
ЛЕКЦИЯ 14
ОПТИМИЗАЦИЯ ПРОГРАММЫ
Улучшение выходной программы обычно называют ее оптимиза-
цией, а часть транслятора, выполняющая эту функцию - отимизирую-
щей частью транслятора.
Оптимизирующая часть транслятора:
1. Устраняет недостатки программы,вызванные небрежностью или
низкой квалификацией программиста.
2. Устраняет излишние вычислеия, неизбежно возникающие в
процессе трансляции даже при самом тщательном написании програм-
мы на языке высокого уровня.
Если транслятор производит оптимизацию программы, необходи-
мо делать специальный проход, переводящий программу с исходного
языка на промежуточный.
Оптимизировать программу, уже протранслированную в коды ма-
шины, трудно по трем причинам: во-первых, единицы действия прог-
раммы в кодах команд слишком мелки, что уже само по себе затруд-
няет анализ, во-вторых, при трансляции входной программы в коды
машины возможна потеря имеющейся в ней информации. Например, за-
сылка промежуточных результатов в разные рабочие ячейки памяти
делает практически невозможной идентификацию одинаковых частей
программы; в-третьих из-за нестандартности форматов различных
элементов языка и рекурсивных конструкций, широко применяемых в
текстах программ.
Строго сформулировать требования, предьявляемые к промежу-
точному языку, трудно.
Однако уже из самого обоснования необходимости промежуточно-
го языка видно, что:
а) операторы языка не должны быть слишком мелкими;
б) символы, идентификаторы и числа должны иметь фиксирован-
ный формат;
в) в строении операторов желательно отсутствие рекурсивности;
г) должна сохраняться вся информация, необходимая для опти-
мизации, которая есть во входном языке;
д) язык должен быть приспособлен к выполнению оптимизирую-
щих преобразований и удобен для последующей трансляции в коды вы-
числительной машины.
Требования пп. "г" и "д" показывают, что разработать еди-
ный универсальный промежуточный язык для трансляции с любого язы-
ка программирования в коды любой ВМ трудно.
Помимо программы на промежуточном языке, состоящей из после-
довательности операторов, необходимы следующие таблицы:
1. Таблицы идентификаторов и констант с обычной информацией
о переменных и константах;
2. Таблица блоков, определяющая номера блоков, их границы,
непосредственно предшествующие и следующие блоки, а также любую
информацию о частоте повторения блока;
3. Таблица последовательности операторов, определяющая ли-
нейную последовательность операторов в блоке. Она содержит после-
довательность указателей операторов mi. Эта таблица необходима,
поскольку один указатель может принадлежать нескольким операторам.
Подстановка и устранение идентичных операторов
Подстановка - это замена переменной или mi - идентификатора
результата заданной или вычисленной константой, причем эта заме-
на производится во время трансляции, а не в процессе решения.
Подстановка является полностью внутриблочной процедурой и
выполняется перед устранением излишних команд.
Сдвиг инвариантных операторов
Сильно связанной областью называется такое множество его уз-
лов, что для любых двух вершин x и y (x != y) существует путь из
x в y.
Оператор инвариантен в сильно связанной области, если его
операнды не зависят от места определения переменных в данной об-
ласти.
Будем рассматривать сильно связанные области Ri, обладающие
следующими свойствами:
1) Ri является сильносвязанной областью, состоящей из мно-
жества блоков, каждый из которых предшетвует сам себе и следует
сам за собой внутри этого множества;
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+
Далее будем рассуждать в терминах промежуточного языка (
или обьектного ), состоящего из команд вида
тип-команды параметры
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23
