Методики создания компилятора

Написание компилятора может потребоваться в самых разнообразных условиях – для различных языков, целевых платформ, с различными требованиями к работе компилятора и т.д. Например, одна из типичных проблем написания компилятора связана с тем, что на целевой платформе могут отсутствовать подходящие средства для разработки. Именно так обычно обстоят дела при создании новой компьютерной архитектуры: на начальном этапе жизни компьютера системные программисты не имеют никаких средств разработки, кроме системы команд самого компьютера (на этом этапе даже ассемблер может отсутствовать). Бывают и такие случаи, когда компилятор создается для еще не существующей целевой платформы.

Таким образом, цели и условия написания компиляторов могут очень сильно варьироваться от одного проекта к другому. Поэтому существует целый ряд методик разработки компиляторов; мы остановимся на наиболее распространенных из них:

· прямой, в котором целевым языком и языком реализации является язык ассемблера

· метод раскрутки

· использование кросс-трансляторов

· использование виртуальных машин

· компиляция "на лету"

Метод раскрутки

Компилятор – это весьма большая и сложная программа; на написание и отладку компилятора на языке ассемблера можно истратить слишком много времени. Для того, чтобы как-то справиться с этой проблемой, был придуман метод раскрутки, суть которого заключается в следующем.

Пусть есть компилятор K_A: P→A, где P – некоторый язык более высокого уровня, чем язык ассемблера. Тогда напишем K_P: L→A, а затем применим компилятор K_A к компилятору K_P, т.е. получим K_A=K_A(K_P): L→A. Такая схема проиллюстрирована с помощью Т-диаграмм на слайде и называется раскруткой (bootstrapping [2]); компилятор K_P как бы "раскручивается" с помощью компилятора K_A.

Описанная схема может быть использована при написании компилятора некоторого языка на нем самом. Пусть у нас есть компилятор некоторого подмножества S языка L в язык A, написанный на языке A, K_A: S→A. Тогда мы можем написать K_L: L→A и получим новый компилятор K_A = K_A(K_L). Мы используем это подмножество S для того, чтобы написать компилятор языка L в язык A, K_S: L→A. Если теперь мы применим компилятор K_A к программе K_S, то получим K_A=K_A(K_S): L→A.

Впервые такая схема была применена в 1960 году при реализации языка Neliac. В 1971 году Вирт написал с использованием раскрутки транслятор языка Pascal, причем самый первый компилятор был оттранслирован вручную. Количество шагов раскрутки было больше 1, т.е. была построена последовательность языков и построена последовательность компиляторов: K_A: S₁→A, K_A¹=K_A(K_S1: S₂→A),...

Раскрутку можно использовать и в следующей ситуации. Пусть у нас есть недостаточно эффективный компилятор K_­A: L→A. Можно написать более эффективный компилятор K_L: L→A, а затем применить раскрутку.

Кросс-транслятор

Пусть у нас есть два компьютера: компьютер M с языком ассемблера A и компьютер M₁ с языком ассемблера A₁. Кроме того, предположим, что имеется компилятор K_A1: P→A₁, а сам компьютер M по каким-то причинам не доступен либо пока еще не существует компилятор K_­A­: P→A. Нас интересует компилятор K_­A­: L→A. В такой ситуации мы можем использовать M₁ в качестве инструментальной машины и написать компилятор K_P: L→A, который принято называть кросс-транслятором (cross-compiler). Как только машина M станет доступной, мы сможем перенести K_P на M и "раскрутить" его с помощью K_A. Понятно, что это решение достаточно трудоемко, поскольку могут возникнуть проблемы при переносе, например, из-за различий операционных систем.

Под переносимой (portable) программой понимается программа, которая может без перетрансляции выполняться на нескольких (по меньшей мере, на двух) платформах. В связи с этим возникает вопрос о переносимости объектных программ, создаваемых компилятором. Компиляторы, созданные по методикам, рассмотренным выше, порождают непереносимые (non-portable) объектные программы. Поскольку компилятор, в конечном итоге, является программой, то мы можем говорить и о переносимых компиляторах. Одним из способов получения переносимых объектных программ является генерация объектной программы на языке более высокого уровня, чем язык ассемблера. Такие компиляторы иногда называют конвертерами (converter).

Виртуальная машина

Другой способ получения переносимой (portable) объектной программы связан с использованием виртуальных машин (virtual machine). При таком подходе исходный язык транслируется в коды некоторой специально разработанной машины, которую никто не собирается реализовывать "в железе". Затем для каждой целевой платформы пишется интерпретатор виртуальной машины.

Понятно, что архитектура виртуальной машины должна быть разработана таким образом, чтобы конструкции исходного языка удобно отображались в систему команд и сама система команд не была слишком сложной. При выполнении этих условий можно достаточно быстро написать интерпретатор виртуальной машины.

Одна из первых широко известных виртуальных машин была разработана в 70-х годах Н. Виртом при написании компилятора Pascal-P. Этот компилятор генерировал специальный код, названный P-кодом и представляющий собой последовательность инструкций гипотетической стековой машины. Сегодня идея виртуальных машин приобрела широкую известность благодаря языку Java, компиляторы которого обычно генерируют так называемый байт-код, т.е. объектный код, который представляет собой последовательность команд виртуальной Java-машины.

Компиляция "на лету"

Основная неприятность, связанная с использованием виртуальных машин, заключается в том, что обычно время выполнения интерпретируемой программы значительно больше, чем время работы программы, оттранслированной в "родной" машинный код. Для того, чтобы увеличить скорость работы приложений, была разработана технология компиляции " на лету" (Just-In-Time compiling; иногда такой подход называют также динамической компиляцией). Идея заключается в том, что JIT-компилятор генерирует машинный код прямо в оперативной памяти, не сохраняя его. Это приводит к значительному увеличению скорости выполнения приложения. Как мы уже говорили в лекции 1, именно так и устроена платформа.NET.

Часто JIT-компилятор используется вместе с интерпретатором виртуальной машины. Организовывается это следующим образом. Вначале сгенерированный байт-код поступает на вход интерпретатору виртуальной машины, которая его интерпретирует. Одновременно с интерпретатором работает программа, которая вычисляет время интерпретации какого-то куска байт-кода, например, процедуры. Если оказывается, что время интерпретации некоторого куска кода достаточно большое, то вызывается JIT-компилятор, который транслирует его в "родные" машинные коды. Когда при выполнении приложения произойдет повторное обращение к этому куску кода, то он уже не будет интерпретироваться, а будет выполняться сгенерированный фрагмент машинного кода.

Использование связки "компилятор+интерпретатор+JIT-компилятор" позволяет заметно повысить скорость выполнения исходной программы, причем переносимость кода, создаваемого компилятором, естественно, сохраняется.

Фазы компиляции

Процесс создания компилятора можно свести к решению нескольких задач, которые принято называть фазами компиляции (compilation phases). Обычно компилятор состоит из следующих фаз:

· лексический анализ

· синтаксический анализ

· видозависимый анализ

· оптимизация

· генерация кода.

Сформулируем основные цели каждой из фаз компиляции. Мы продемонстрируем преобразования, которым подвергается исходная программа на перечисленных фазах компиляции, на небольшом примере — мы рассмотрим оператор присваивания

position = initial + rate * 60, причем предположим, что все переменные вещественные.

Лексический анализ

Входом компилятора служит программа на исходном языке программирования. С точки зрения компилятора это просто последовательность символов. Задача первой фазы компиляции, лексического анализатора (lexical analysis), заключается в разборе входной цепочки и выделении некоторых более "крупных" единиц, лексем, которые удобнее для последующего разбора. Примерами лексем являются основные ключевые слова, идентификаторы, константные значения (числа, строки, логические) и т.п.

На этапе лексического анализа обычно также выполняются такие действия, как удаление комментариев и обработка директив условной компиляции.

Для отображения некоторых лексем достаточно всего одного числа (это может быть, например, номер ключевого слова согласно внутренней нумерации компилятора), в то время как для записи других лексем может потребоваться пара, состоящая из номера лексического класса и ссылки в таблицу внешних представлений. Хорошая модель лексического анализатора – конечный преобразователь.