Основы компиляторов

Основные задачи компиляторов

Компьютеры сами по себе способны выполнять только очень ограниченный набор операций, называемых машинными кодами. В старые времена, когда появились первые компьютеры, программы писались в машинных кодах, представляющих собой последовательности двоичных чисел, однозначно воспринимаемых компьютером. В конце 50-х кодов прошлого века появились первые языки программирования, такие как язык ассемблера и Фортран. Для того, чтобы компьютер мог понять программу, написанную на каком-то языке программирования, необходим переводчик (транслятор) такой программы в машинные коды. Отметим, что, если оператор языка ассемблера отображается при трансляции чаще всегоНекоторые операторы языка ассемблера, например, такие, как операторы ввода/вывода, отображаются в несколько машинных команд. в одну машинную инструкцию, предложения языков более высокого уровня отображаются, вообще говоря, в несколько машинных инструкций.

Трансляторы бывают двух типов: компиляторы (compiler) и интерпретаторы (interpreter). Процесс компиляции состоит из двух частей: анализа (analysis) и синтеза (synthesis). Анализирующая часть компилятора разбивает исходную программу на составляющие ее элементы (конструкции языка) и создает промежуточное представление исходной программы. Синтезирующая часть из промежуточного представления создает новую программу, которую компьютер в состоянии понять. Такая программа называется объектной программой. Объектная программа может в дальнейшем выполняться без перетрансляции. В качестве промежуточного представления обычно используются деревья, в частности, так называемые деревья разбора. Под деревом разбора понимается дерево, каждый узел которого соответствует некоторой операции, а сыновья этого узла - операндам.

Интерпретатор

В отличие от компилятора, интерпретатор не создает никакой новой программы, а просто выполняет каждое предложение языка программирования. Можно сказать, что результатом работы интерпретатора является "число".

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

В том случае, если исходный язык достаточно прост (например, если это язык ассемблера или Basic), то никакое промежуточное представление не нужно, и тогда интерпретатор - это простой цикл. Он выбирает очередную инструкцию языка из входного потока, анализирует и выполняет ее. Затем выбирается следующая инструкция. Этот процесс продолжается до тех пор, пока не будут выполнены все инструкции, либо пока не встретится инструкция, означающая окончание процесса интерпретации.

Компилятор

Компилятор переводит программы с одного языка на другой. Входом компилятора служит цепочка символов, составляющая исходную программу на языке программирования $$L_{1}$$. Выход компилятора (объектная программа) также представляет собой цепочку символов, но принадлежащую другому языку $$L_{2}$$, например, языку некоторого компьютера. При этом сам компилятор написан на языке $$L_{3}$$, возможно, отличающемся от первых двух. Будем называть язык $$L_{1}$$ исходным языком, язык $$L_{2}$$ - целевым языком, а язык $$L_{3}$$ - языком реализации. Таким образом, можно говорить о компиляторе как об отображении множества $$L_{1}$$ в множество $$L_{2}$$, т.е. $$K_{L3}: L_{1}\to L_{2}$$.

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

Существует огромное количество различных языков программирования, начиная с таких традиционных языков программирования как Fortran и Pascal и кончая современными объектно-ориентированными языками такими, как C# и Java. Практически каждый язык программирования имеет какие-то особенности с точки зрения создателя транслятора. Однако мы начнем с рассмотрения разнообразных целевых языков компиляторов.

Объектная программа

Объектная программа может быть

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

Однако для более сложных программ необходимо создавать объектные программы в форме последовательности перемещаемых машинных команд. Перемещаемая машинная команда представляет собой команду, в которой адресация ячеек памяти производится относительно некоторого подвижного начала. Объектную программу называют также перемещаемым объектным сегментом. Этот сегмент может быть связан с другими сегментами, такими, как независимо компилируемые подпрограммы пользователя, подпрограммы ввода-вывода и библиотечные функции.

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

Трансляция в ассемблер

Трансляция программы в ассемблер несколько упрощает конструирование компилятора. Однако, такой подход удлиняет технологическую цепочку выполнения программы, так как объектная программа, порожденная компилятором, должна быть впоследствии обработана ассемблером, а также редактором связей и загрузчиком.

У трансляции в ассемблер есть несколько ощутимых преимуществ:

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

T-диаграммы

Мы обозначили компилятор, переводящий цепочки языка $$L_{1}$$ в цепочки языка $$L_{2}$$ и написанный на языке $$L_{3}$$, следующим образом: $$K_{L_3 } : L_{1} \to L_{3}$$. Для представления компилятора мы можем использовать также так называемые Т-диаграммы:

Компилятор, переводящий язык L в язык ассемблера A и написанный на языке A можно представить следующими способами: $$K_{A}: L \to A$$ или

Т-диаграммы достаточно удобны при обсуждении различных способов получения компиляторов.

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

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

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

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

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

Пусть есть компилятор $$K_{A} : P \to A$$, где P - некоторый язык более высокого уровня, чем язык ассемблера. Тогда напишем $$K_{P} : L \to A$$, а затем применим компилятор $$K_{A}$$ к компилятору $$K_{P}$$, т.е. получим $$K_{A}=K_{A}(K_{P}): L \to A$$. Такая схема проиллюстрирована с помощью Т-диаграмм на слайде и называется раскруткой ( bootstrappingНазвание метода раскрутки произошло от фразы "to pull oneself up by one's bootstrap", т.е. "вытянуть себя за шнурки", аналогично легендарному методу барона Мюнхгаузена ); компилятор $$K_{P}$$ как бы "раскручивается" с помощью компилятора $$K_{A}$$.

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

Впервые такая схема была применена в 1960 году при реализации языка Neliac. В 1971 году Вирт написал с использованием раскрутки транслятор языка Pascal, причем самый первый компилятор был оттранслирован вручную. Количество шагов раскрутки было больше 1, т.е. была построена последовательность языков $$S_1 \subset S_2 \subset ...S_n = L $$ и построена последовательность компиляторов: $$K_{A}: S_{1} \to A, K_{A}^{1}=K_{A}(K_{S1}: S_{2} \to A), ..$$.

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

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

Пусть у нас есть два компьютера: компьютер M с языком ассемблера A и компьютер $$M_{1}$$ с языком ассемблера $$A_{1}$$. Кроме того, предположим, что имеется компилятор $$K_{A1} : P \to A_{1}$$, а сам компьютер M по каким-то причинам не доступен либо пока еще не существует компилятор $$K_{A} : P \to A$$. Нас интересует компилятор $$K_{A} : L \to A $$. В такой ситуации мы можем использовать $$M_{1}$$ в качестве инструментальной машины и написать компилятор $$K_{P} : L \to 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) , заключается в разборе входной цепочки и выделении некоторых более "крупных" единиц, лексем, которые удобнее для последующего разбора. Примерами лексем являются основные ключевые слова, идентификаторы, константные значения (числа, строки, логические) и т.п.

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

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

Лексический анализ будет подробно рассмотрен в лекции 5.

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

Синтаксический анализатор (syntax analyzer, parser) получает на вход результат работы лексического анализатора и разбирает его в соответствии с некоторой грамматикой. Эта грамматика аналогична грамматике, используемой при описании входного языка. Однако грамматика входного языка обычно не уточняет, какие конструкции следует считать лексемами.

Синтаксический анализ является одной из наиболее формализованных и хорошо изученных фаз компиляции. Лекции 4 посвящена математическому аппарату, используемому при описании языков и создании синтаксических анализаторов. Различные методы построения синтаксических анализаторов будут рассмотрены в лекции 6, лекции 7 и лекции 8.

После синтаксического анализа можно считать, что исходная программа преобразована в некоторое промежуточное представление. Некоторые распространенные формы промежуточного представления программы будут рассмотрены в лекции 9. Пока же мы остановимся на одной форме промежуточного представления, которая будет использована в нашем курсе, - на дереве разбора программы (иногда его также называют синтаксическим деревом). В дереве разбора программы внутренние узлы соответствуют операциям, а листья представляют операнды.

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

Видозависимый анализ (type checking) , иногда также называемый семантическим анализом (semantic analysis) , обычно заключается в проверке правильности типов данных, используемых в программе. Кроме того, на этом этапе компилятор должен также проверить, соблюдаются ли определенные контекстные условия входного языка. В современных языках программирования одним из примеров контекстных условий может служить обязательность описания переменных: для каждого использующего вхождения идентификатора должно существовать единственное определяющее вхождение. Другой пример контекстного условия: число и атрибуты фактических параметров вызова процедуры должны быть согласованы с определением этой процедуры.

Такие контекстные условия не всегда могут быть проверены во время синтаксического анализа и потому обычно выделяются в отдельную фазу. Эта фаза компиляции подробно обсуждается в лекции 9.

Оптимизация кода

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

Некоторые оптимизации тривиальны, другие требуют достаточно сложного анализа программы. В лекции 11 и лекции 12 мы рассмотрим анализ потоков управления программы и анализ потоков данных. Затем в лекции 13 мы рассмотрим сам этап оптимизации программ и рассмотрим наиболее распространенные оптимизации:

Генерация кода

Наконец, по оптимизированной версии промежуточного представления генерируется объектная программа. Эту задачу решает фаза генерации кода (code generator) . В лекции 14 мы изучим основные свойства целевой платформы .NET и рассмотрим процесс генерации кода для этой платформы. В лекции 15 мы рассмотрим более сложные алгоритмы генерации, использующие методику восходящего переписывания деревьев (BURS). Во многих случаях такой подход может значительно улучшить качество порождаемого кода.

Помимо собственно генерации кода, на этом этапе необходимо решить множество сопутствующих проблем, например:

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

Внешний и внутренний интерфейсы

Нетрудно заметить, что одни фазы компиляции в большей степени зависят от входного языка и в меньшей степени от целевого. Другие фазы, наоборот, в меньшей степени зависят от входного языка и в большей степени от целевого. Например, лексический, синтаксический, видозависимый анализ и некоторые оптимизации не слишком значительно зависят от целевого языка. Эти фазы иногда объединяют вместе под названием внешний интерфейс или front-end. Front-end подразумевает также обработку ошибок, которые могут встретиться на перечисленных фазах (вопросы обработки ошибок обсуждаются в лекции 9). Остальные фазы, несущие на себе отпечаток целевого языка, называются внутренним интерфейсом (back-end) .

Таким образом, если мы хотим иметь компиляторы некоторого языка на разных платформах, то наша задача сводится к написанию нескольких back-end'ов без изменения front-end'а. С другой стороны, для создания многоязыкового компилятора достаточно написать несколько front-end'ов.

Просмотры

Обсудим еще один важный термин, а именно, просмотр (passes) . Под просмотром (или проходом) компилятора понимается процесс обработки всего, возможно, уже преобразованного, текста исходной программы.

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

Передача информации между просмотрами происходит в терминах так называемых промежуточных языков. Таким образом, если компилятор состоит из N просмотров, то должно быть определено N-1 промежуточных языков. Каков этот промежуточный язык, зависит от разработчиков компилятора. Обычно программа на промежуточном языке представляет собой синтаксическое дерево и, возможно, какие-то внутренние таблицы компилятора.

Желательно иметь относительно мало просмотров, т.к. для чтения программы на одном промежуточном языке и записи ее на другом промежуточном языке может занимать довольно много времени. С другой стороны, объединяя несколько фаз в один просмотр, мы должны помнить о том, что иногда мы не можем выполнить некоторую фазу, не получив информацию из предыдущих фаз. Например, C# позволяет использовать имя метода до того, как он был описан. Понятно, что мы не можем выполнить видозависимый анализ до тех пор, пока мы не будем знать имена и типы всех методов объектов. Таким образом, эти задачи должны решаться на разных просмотрах.

Техника "заплат"

Аналогично, если в языке есть оператор go to, то мы можем использовать его не только для перехода назад, но и для перехода вперед. Таким образом, мы не всегда можем определить операнд команды перехода, по крайней мере до тех пор, пока не доберемся до конца программы. Однако в простых случаях мы можем использовать технику "заплат" (backpatching) . Рассмотрим фрагмент программы на языке ассемблера:

...
               goto target;
               ...
               goto target;
               ...
target:        mov foobar, r1

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

Литература к лекции