- •Понятие транслятора. Структура транслятора. Фазы трансляции. Основные блоки транслятора.
- •Понятие транслятора. Многопроходная организация взаимодействия блоков транслятора.
- •Понятие транслятора. Однопроходная организация взаимодействия блоков транслятора.
- •Понятие транслятора. Комбинированные взаимодействия блоков транслятора.
- •Способы определения языков. Механизмы порождения и распознавания.
- •Формальные грамматики. Порождающие грамматики Хомского.
- •Конечные автоматы. Детерминированные конечные автоматы.
- •Конечные автоматы. Недетерминированные конечные автоматы.
- •Автоматы с магазинной памятью. Устройство автомата с магазинной памятью.
- •Автоматы с магазинной памятью. Детерминированные и недетерминированные автоматы с магазинной памятью.
- •Машина Тьюринга. Устройство машины Тьюринга. Отличия конечного автомата от машины Тьюринга.
- •Машина Тьюринга. Линейно-ограниченные автоматы.
- •Системы Линденмайера (l-системы). Внутреннее устройство l-систем.
- •Системы автоматической генерации компиляторов. Основные спецификации и идеологии.
- •Системы автоматической генерации компиляторов. Проект Coco/r.
- •Системы автоматической генерации компиляторов. Проект Yacc.
- •Системы автоматической генерации компиляторов. Генерация лексического анализатора.
- •Системы автоматической генерации компиляторов. Генерация синтаксического анализатора.
- •Понятие компилятора. Этапы анализа исходной программы.
- •Понятие компилятора. Лексический анализ.
- •Понятие компилятора. Синтаксический анализ.
- •Понятие компилятора. Семантический анализ.
- •Понятие компилятора. Основные фазы компиляции.
- •Понятие компилятора. Генерация кода. Основные подходы к генерации кода. Понятие целевой машины.
- •Понятие компилятора. Оптимизация кода. Основные источники оптимизации.
Понятие компилятора. Генерация кода. Основные подходы к генерации кода. Понятие целевой машины.
Последней стадией в модели компиляции является генератор кода, который получает на вход промежуточное представление исходной программы и выводит эквивалентную целевую программу.
Традиционно к генератору кода предъявляются жесткие требования. Получаемый код должен быть корректным и высококачественным, что означает эффективное использование ресурсов целевой машины. Кроме того, эффективно должен работать и сам генератор кода.
Математически проблема генерации оптимального кода является неразрешимой. На практике мы вынуждены довольствоваться эвристическими технологиями, дающими хороший, но не обязательно оптимальный код. Выбор эвристики очень важен, так как тщательно разработанный алгоритм генерации кода может давать код, работающий в несколько раз быстрее кода, полученного с помощью недостаточно продуманного алгоритма.
Хотя мелкие детали генератора кода зависят от целевой машины и операционной системы, такие вопросы, как управление памятью, выбор инструкций, распределение регистров и порядок вычислений, свойственны практически всем задачам, связанным с генерацией кода.
Вход генератора кода
Входной поток генератора кода представляет собой промежуточное представление исходной программы, полученное на начальной стадии компиляции, вместе с таблицей символов, которая используется для определения адресов времени исполнения объектов данных, обозначаемых в промежуточном представлении именами.
Целевые программы
Выходом генератора кода является целевая программа. Подобно промежуточному коду, выход генератора кода может принимать различные виды: абсолютный машинный язык, перемещаемый машинный язык, или язык ассемблера.
Управление памятью
Отображение имен исходной программы в адреса объектов данных в памяти во время работы программы выполняется совместно начальной стадией компилятора и генератором кода.
Выбор инструкций
Набор инструкций целевой машины определяет сложность их выбора. Важными факторами этого выбора являются единообразие и полнота множества инструкций. Если целевая машина не поддерживает все типы данных единообразно, то каждое исключение из общего правила потребует специальной обработки.
Другими важными факторами являются скорость выполнения инструкций и идиомы языка целевой машины.
Распределение регистров
Инструкции, использующие в качестве операндов регистры, обычно короче и быстрее выполняются, чем инструкции, работающие с операндами, расположенными в памяти. Следовательно, эффективное использование регистров — еще одна важная составляющая генерации хорошего целевого кода. Использование регистров часто разделяется на две подзадачи.
В процессе распределения регистров мы выбираем множество переменных, которые будут находиться в регистрах в некоторой точке программы.
В последующей фазе назначения регистров мы выбираем конкретные регистры для размещения в них переменных.
Выбор порядка вычислений
Порядок, в котором выполняются вычисления, также может существенно влиять на эффективность целевого кода. Как мы увидим, изменение порядка вычислений может привести к уменьшению количества необходимых для работы регистров.
Подходы к генерации кода
Несомненно, самым важным критерием работы генератора кода является корректность производимого кода. Корректность приобретает особую значимость из-за огромного количества частных случаев и исключений из правил, с которыми приходится сталкиваться генератору кода. С учетом приоритета корректности, важной целью разработки генератора кода является создание легко реализуемого, тестируемого и поддерживаемого генератора целевого кода.
Простой алгоритм генерации кода использует информацию о последующем использовании операндов для генерации кода регистровой машины. Он рассматривает каждую инструкцию по очереди, сохраняя операнды в регистрах, насколько это оказывается возможным. Выход такого генератора может быть улучшен путем применения технологий локальной оптимизации.
Существуют технологии, оптимизирующие использование регистров путем рассмотрения потока управления в промежуточном коде. Особый упор делается на распределении регистров для интенсивно используемых операндов во внутренних циклах.
Существуют некоторые технологии выбора кода с использованием деревьев, упрощающие создание перенастраиваемых генераторов кода. Версии РСС — переносимого компилятора С — с такими генераторами кода распространились на самые разнообразные платформы, чему немало способствовала доступность операционной системы UNIX. Генерация кода может рассматриваться в качестве процесса построения дерева.
Целевая машина
Архитектура (набор программно-аппаратных средств), для которой производится компиляция, называется целевой машиной.
Одним из непременных требований к построению хорошего генератора кода является близкое знакомство с целевой машиной и ее набором инструкций. К сожалению, при обсуждении общих вопросов генераций кода невозможно описать нюансы той или иной целевой машины достаточно подробно, чтобы иметь возможность генерировать для нее хороший код. Рассмотрим регистровую машину, являющуюся типичным представителем ряда мини-компьютеров. Однако рассматриваемые здесь принципы и технологии применимы и к множеству других классов машин.
Наш целевой компьютер представляет собой машину с адресацией байтов, словом из четырех байтов и п регистрами общего назначения RO, Rl. ..., R/i-1. Он имеет двухадресные инструкции вида
op source, destination
где op— код операции, a source (источник) и destination (получатель)— поля данных. Среди прочих имеются следующие коды операций.
MOV (переместить source в destination)
ADD (прибавить source к destination)
SUB (вычесть source из destination)
Поля источника и получателя недостаточно длинны для хранения адресов памяти, поэтому определенные наборы битов в этих полях определяют, что следующее за инструкцией слово содержит операнды и/или адреса. Источник и получатель инструкции определяются комбинированием регистров и ячеек памяти с режимами адресации. В следующем далее описании contents(a) означает содержимое регистра или ячейки памяти, представленных а.
Далее приведены режимы адресации вместе с их ассемблерным представлением и стоимостью.