Реферат: Проектирование трансляторов
инструкциями и описаниями явно не заданы.
В дереве отражены прямые связи (указатели) с инструкциями, в
то время как в триадах эти связи подразумеваются.
Промежуточная форма исходной программы
Первоначальная исходная программа переводится в некоторую
внутреннюю форму, удобную для простой машинной обработки. Внут-
реннее представление исохдной программы в значительной степени
зависит от дальнейшего использования. Это может быть дерево, от-
ражающее синтаксис исходной программы. Это может быть исходная
программа в польской записи. Используется также форма - список
тетрад (операнд, операнд, операнд, результат) в порядке их выпол-
нения.
После синтаксического анализа можно считать, что исходная
программа преобразована в дерево, называемое синтаксическим. В
этом дереве внутренние вершины в основном соответствуют опера-
циям, а листья представляют операнды, состаящие из указателей
входов в таблицу имен. Структура синтаксического дерева отражает
синтаксические языка программирования, на котором написана исход-
ная программа. Для физического представления существует нес-
колько способов. Во внутренней форме операторы не изменяют поря-
док следования. Все внутренние представления обычно содержат 2
вещи: операторы и операнды. Различие состоит в том, как эти опе-
раторы и операнды соединяются.
Промежуточная программа должна отражать синтаксическую
структуру исходной программы. Операндами являются простые имена
(переменные, константы, процедуры и т.д.). Компиляторы, осущес-
твляющие значительную работу по оптимизации кода, создают де-
тальное представление промежуточной программы, точно описывающее
порядок выполнения исходной программы. В других компиляторах
представлением промежуточной программы служит простое представле-
ние синтаксического дерева, такое как польская запись.
Польская запись
Для представления арифметических и логических выражений ис-
пользуется польская запись. Она имеет ряд преимуществ перед ин-
фиксной: формула может быть записана без скобок; эта форма пред-
ставления очень удобна для ЭВМ со стековой адресацией; если зна-
ки операций в инфиксной форие различаются по старшинству, то
польская запись устраняет эту систему приоритетов).
В польской записи операнды следуют непосредственно за опера-
торами. Вычисление таких записей производится с помощью стека,
где будут находиться все операнды, встретившиеся при просмотре
выражения.
Просмотр начинается с самого левого символа. Прочитав его и
обработав, переходим к следующему. Последовательность обработки
такова:
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 является сильносвязанной областью, состоящей из мно-
жества блоков, каждый из которых предшетвует сам себе и следует
сам за собой внутри этого множества;
Страницы: 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
