- •Предисловие
- •Глава 1 введение в проблематику конструирования компиляторов
- •1.1. Понятие компилятора и его структура
- •1.2. Применение компиляторов и задачи их разработки
- •Глава 2 способы задания формальных языков
- •2.1. Математический аппарат теории
- •Формальных языков, перевода и компиляции
- •1) AR*a для всех aÎa;
- •2.2 Цепочки и языки
- •2.3 Грамматики
- •2.4. Распознаватели
- •2.5 Регулярные выражения и синтаксические диаграммы
- •2.6. Автоматы с магазинной памятью (мп - автоматы )
- •2.7. Соответствия между способами описания языков
- •Глава 3 основы теории перевода
- •3.1. Определение перевода
- •3.2. Модели простейших трансляторов
- •3.2.1. Конечные преобразователи
- •3.2.2. Преобразователи с магазинной памятью
- •Глава 4 конструирование сканеров
- •4.1. Общая характеристика процесса сканирования
- •4.2. Описание лексем в языке расширенных регулярных выражений
- •4.3. Построение недетерминированного конечного автомата по расширенному регулярному выражению
- •4.4. Преобразование недетерминированного конечного автомата в детерминированный
- •Замечание. Среди состояний могут оказаться недостижимые состояния . Состояние р называется достижимым , если существует такая цепочка w , что (q0, w) *(p , e ). ¨
- •4.5. Преобразование синтаксической диаграммы в конечный автомат
- •4.6. Представление результатов сканирования
- •4.7. Методики конструирования сканеров
- •Глава 5 конструирование однопроходных нисходящих анализаторов
- •5.1. Определение синтаксического разбора
- •5.2. Нисходящий и восходящий разборы
- •5.3. Ll(k) - грамматики
- •5.4. Предсказывающие алгоритмы разбора
- •5.5. Алгоритмы построения управляющих таблиц для левых анализаторов
- •5.6. Приведение грамматик к ll - форме
- •Глава 6 основы генерации кода
- •6.1. Перевод и генерация кода
- •6.2. Представления промежуточной программы
- •6.3. Преобразование промежуточной программы в ассемблерный код
Глава 6 основы генерации кода
6.1. Перевод и генерация кода
В гл. 1 было показано , что компилятор можно расчленить на несколько промежуточных трансляторов, каждый из которых выполняет перевод некоторого представления исходной программы, пока, наконец, не будет получена объектная программа. Каждый промежуточный транслятор можно считать преобразователем, определяющим одну фазу компиляции, а композиция всех фаз дает компиляцию в целом.
Выбор того, что назвать фазой, достаточно произволен. Удобно считать основными фазами компиляции лексический анализ, синтаксический анализ и генерацию кода.
Первую фазу компиляции выполняет лексический анализатор. Он преобразует исходную программу в цепочку, состоящую из лексем и элементов таблицы имен. В ходе лексического анализа размеры исходной программы уменьшаются, так как идентификаторы заменяются лексемами, а ненужные пробелы и комментарии выбрасываются. После лексического анализа перерабатываемая информация, по существу, остается цепочкой, но некоторые части этой цепочки являются указателями на информацию в таблице имен.
Хорошей моделью лексического анализатора является конечный преобразователь, рассмотренный ранее.
Синтаксический анализатор выполняет вторую фазу. Он воспринимает выход лексического анализатора и разбирает его в соответствии с грамматикой языка . После синтаксического анализа можно считать, что исходная программа преобразована в синтаксическое дерево.
Синтаксическое дерево тесно связано с деревом вывода исходной программы и, как правило, является просто деревом вывода с удаленными цепочками цепных правил. Представление синтаксического дерева называется промежуточной программой (например, левый разбор, порождаемый анализатором, будет промежуточной программой).
Компилятор должен проверять, соблюдены ли определенные семантические соглашения входного языка, например :
а) каждая метка, используемая в операторе GOTO, должна обязательно появиться в качестве метки некоторого оператора в исходной программе ;
б) никакой идентификатор не может быть описан более одного раза ;
в) все переменные должны объявляться перед использованием ;
г) при вызове функции число аргументов и их атрибуты должны быть согласованы с определением функции.
После синтаксического анализа промежуточная программа отображается генератором кода в объектную программу. В процессе генерации кода используется информация из таблицы имен для того, чтобы правильно выбрать последовательность команд (например, код для А+В зависит от типа переменных А и В, а информация о типе находится в таблице имен ) и правильно распределить память (т. е. выяснить, является переменная скаляром или структурированным объектом ).
Реальный компилятор может осуществить фазу компиляции за один или более проходов. Проход состоит в чтении входа из внешней памяти с последующей записью промежуточных результатов во внешнюю память. В исключительных случаях возможно осуществление всех фаз компиляции за один проход .