- •Лекция 11
- •Лексический анализатор.
- •Атрибуты лексем
- •Использование грамматик для лексического анализа
- •Регулярные выражения
- •Построение лексического анализатора по регулярному выражению
- •Структура Lex-программы
- •Способы записи регулярных выражений в Lex-программе
- •Лекция 12
- •Синтаксический анализ
- •Нисходящий разбор.
- •Нисходящий анализ.
- •Ll(1) - грамматики
- •Лекция 13
- •Восходящий разбор.
- •Восходящий синтаксический анализ.
- •Лекция 14
- •Видозависимый (семантический) анализ
- •Организация таблиц символов
- •Оптимизация кода
- •Генерация кода
- •Генераторы генераторов кода
- •Лекция 16
- •Промежуточные формы представления программ
- •Польская запись
- •Алгоритм вычисления выражений в обратной польской записи
- •Алгоритм э.Дейкстры перевода выражения в полиз (метод стека с приоритетами):
- •Тетрады (четверки).
- •Триады.
- •Перевод в полиз условных опереторов, операторов присваивания, операторов циклов.
- •Лекция 17
- •Формальные методы описания перевода.
Оптимизация кода
Основная цель фазы оптимизации (code optimization) заключается в преобразовании промежуточного представления программы в целях повышения эффективности результирующей объектной программы. Отметим, что существуют различные критерии эффективности, например, скорость исполнения или объем памяти, требуемый программе. Очевидно, что все преобразования, осуществляемые на фазе оптимизации, должны приводить к программе, эквивалентной исходной.
Некоторые оптимизации тривиальны, другие требуют достаточно сложного анализа программы. Позже мы рассмотрим наиболее распространенные оптимизации:
константные вычисления
уменьшение силы операций
выделение общих подвыражений
чистка циклов и т.д.
Генерация кода
Наконец, по оптимизированной версии промежуточного представления генерируется объектная программа. Эту задачу решает фаза генерации кода (code generator) . Во многих случаях такой подход может значительно улучшить качество порождаемого кода.
Помимо собственно генерации кода, на этом этапе необходимо решить множество сопутствующих проблем, например:
распределение памяти, т.е. отображение имен исходной программы в адреса памяти
распределение регистров, т.е. определение для каждой точки программы множества переменных, которые должны быть размещены в регистрах
выбор такой последовательности записи значений в регистры, которая избавила бы от необходимости частой выгрузки значений из регистров, а затем повторной загрузки
Генераторы генераторов кода
Задача генератора кода - построение для программы на входном языке эквивалентной машинной программы. Обычно в качестве входа для генератора кода служит некоторое промежуточное представление программы.
Генерация кода включает ряд специфических, относительно независимых подзадач: распределение памяти (в частности, распределение регистров), выбор команд, генерацию объектного (или загрузочного) модуля. Конечно, независимость этих подзадач относительна: например, при выборе команд нельзя не учитывать схему распределения памяти, и, наоборот, схема распределения памяти (регистров, в частности) ведет к генерации той или иной последовательности команд. Однако удобно и практично эти задачи все же разделять, обращая при этом внимание на их взаимодействие.
В какой-то мере схема генератора кода зависит от формы промежуточного представления. Ясно, что генерация кода из дерева отличается от генерации кода из троек, а генерация кода из префиксной записи отличается от генерации кода из ориентированного графа. В то же время все генераторы кода имеют много общего, и основные применяемые алгоритмы отличаются, как правило, только в деталях, связанных с используемым промежуточным представлением.
В дальнейшем в качестве промежуточного представления мы будем использовать префиксную нотацию. А именно, алгоритмы генерации кода будем излагать в виде атрибутных схем со входным языком Лидер.
Лекция 16
Промежуточные формы представления программ.
Промежуточные формы представления программ
Компилятор в целом определяет перевод исходной программы, представленной в виде цепочки символов на языке программирования высокого уровня в объектный код. На каждом этапе компиляции идет перевод в некоторый, присущий данному этапу, код. Например, лексический анализатор преобразует цепочки символов в цепочки лексем. Синтаксический анализатор преобразует цепочки лексем в некоторую промежуточную форму, являющуюся линейной формой записи синтаксического дерева программы. На следующем этапе эта промежуточная форма переводится в объектный код.
Общепринятыми промежуточными формами представления программы являются:
польская инверсная запись;
тетрады (четверки);
триады (тройки);
связанные описывающие структуры;
байт-код для виртуальной машины Java (Ява).