1.5. Группировка фаз
Фазы компиляции, рассмотренные в разделе 1.3, представляют собой логическую организацию компилятора. При реализации зачастую происходит объединение действий, выполняемых в различных фазах.
Предварительная и заключительная стадии
Зачастую фазы объединяются в начальную (front end) и заключительную (back end) стадии. Начальная стадия объединяет те фазы компилятора (или части фаз), которые зависят в первую очередь от исходного языка и практически не зависят от целевой машины. Обычно сюда входят лексический и синтаксический анализ, создание таблицы символов, семантический анализ и генерация промежуточного кода. На этом этапе может быть выполнена и определенная часть оптимизации кода. Кроме того, начальная стадия включает обработку ошибок, которая сопровождает каждую фазу компилятора.
Заключительная стадия состоит из тех фаз компилятора, которые в первую очередь зависят от целевой машины, для которой выполняется компиляция, и, вообще говоря, не зависят от исходного языка (а только от промежуточного). Кроме того, сюда входит часть оптимизации кода и генерация выходного кода, сопровождаемые необходимой обработкой ошибок и работой с таблицей символов.
Таким образом, создание компиляторов одного и того же исходного языка для различных машин является достаточно простой операцией. При этом можно использовать одну и ту же начальную стадию, не зависящую от целевой машины. Более того, при умелой разработке заключительной стадии не потребуется даже внесение существенных изменений в нее (см. главу 9, "Генерация кода"). Соблазнительно также компилировать различные исходные языки в один промежуточный и использовать общую заключительную стадию для разных предварительных стадий, получая тем самым ряд компиляторов для различных языков с одной целевой машиной. Однако в данном случае успех не гарантирован из-за множества нюансов в различных языках программирования.
Проходы
Обычно фазы компиляции реализуются в одном проходе (pass), состоящем из чтения входного файла и записи выходного. Имеется множество способов группировки фаз компилятора по проходам, и поэтому рассмотрение процесса компиляции в данной книге в большей степени привязано к фазам, а не проходам. В главе 12, "Некоторые компиляторы" будут рассмотрены некоторые типичные компиляторы и способы распределения фаз компиляции по проходам.
Как упоминалось, группирование нескольких фаз в одном проходе широко распространено; их выполнение чередуется во время прохода. Например, лексический, синтаксический и семантический анализы, а также генерация промежуточного кода могут быть сгруппированы в одном проходе. В этом случае поток токенов после лексического анализа может быть транслирован непосредственно в промежуточный код. Синтаксический анализ можно рассматривать как "руководящий" процесс. Он получает поток токенов с помощью вызова лексического анализатора для получения следующего токена в потоке. После того как определена грамматическая структура, синтаксический анализатор вызывает генератор промежуточного кода для семантического анализа и генерации части кода. Такой компилятор описан в главе 2, "Простой однопроходный компилятор".
Уменьшение количества проходов
Желательно иметь компилятор с минимальным числом проходов, особенно если учесть время, необходимое для чтения и записи промежуточных файлов. Однако при группировании нескольких фаз в одном проходе может потребоваться размещение программы в памяти целиком — поскольку одной фазе может потребоваться информация в порядке, отличном от того, в котором ее выдает предыдущая фаза. Программа во внутреннем представлении может быть значительно больше исходной программы или программы, получаемой в результате работы компилятора, поэтому вопрос о пространстве далеко не тривиален.
Группировка некоторых фаз в одном проходе не представляет проблем. Как упоминалось выше, с одной стороны, интерфейс между лексическим и синтаксическим анализами зачастую ограничивается единственным токеном. С другой стороны, часто очень сложно выполнить генерацию кода до завершения создания промежуточного представления. Например, языки типа PL/I и Algol 68 позволяют использование переменных до их объявления. Невозможно сгенерировать целевой код для языковой конструкции, если не известны типы используемых в ней переменных. Подобная же ситуация возникает и в языках, которые позволяют использовать оператор безусловного перехода вперед по коду (таких языков программирования подавляющее большинство). Определить целевой адрес такого оператора безусловного перехода невозможно без генерации кода для инструкций между оператором безусловного перехода и его местом назначения.
Иногда удается оставить необходимое для отсутствующей информации пустое место и заполнить его позже, когда информация станет доступной. В частности, генерация промежуточного и целевого кодов часто может быть объединена в один проход с использованием технологии "обратных поправок" (backpatching). До тех пор, пока в главе 8, "Генерация промежуточного кода", не будут рассмотрены вопросы, связанные с генерацией промежуточного кода, невозможно пояснить все детали этой технологии. Однако мы попытаемся проиллюстрировать технологию обратных поправок на примере ассемблера. В предыдущем разделе рассматривался двухпроходный ассемблер, когда в первом проходе производился поиск всех идентификаторов, представляющих ячейки памяти, и происходило назначение им адресов, а во втором — идентификаторы заменялись адресами.
Можно скомбинировать эти действия следующим образом. При использовании ассемблерной инструкции со ссылкой вперед
GOTO target
мы генерируем инструкцию с машинным кодом операции GOTO и пустым местом вместо адреса. Все инструкции с пустыми местами вместо адреса target хранятся в списке, связанном с записью для идентификатора target в таблице символов. Эти пустые места заполняются, как только появляется инструкция типа
target: MOV foobar, R1
и определяется значение идентификатора target, которое является адресом текущей инструкции. Затем производим "обратную поправку", проходя по списку, связанному с идентификатором target, и внося реальное значение адреса в пустые поля адресов. Такой подход прост в реализации, если инструкции хранятся в памяти до определения всех целевых адресов.
Такой подход вполне допустим в ассемблере, который может хранить весь свой вывод в памяти. Поскольку промежуточное и окончательное представления кода в случае ассемблера практически одинаковы и имеют близкие размеры, применение технологии обратных поправок не сталкивается с неразрешимыми проблемами. Однако в компиляторах с большим промежуточным кодом, возможно, придется ограничить использование метода обратных поправок некоторым диапазоном, определяемым доступной памятью.