Компилятор как таковой: таблицы и деревья

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

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

Во-вторых, компилятор должен формировать некоторый образ исходной программы?—?внутреннее представление программы в целом или ее некоторой части, которая вданный момент обрабатывается. Именно на основе такой структуры обычновыполняется семантический анализ программы, производятся различные оптимизациии осуществляется генерация результирующего кода. Как правило, такое внутреннеепредставление строится в виде дерева и потому называется деревом программы.

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

Структура таблиц была придумана в целом по образцам из книг по теории ипрактике компиляции, которые в изобилии выходили у нас в 70-80-х годах иописывали, как правило, языки с относительно простой и, самое главное,регулярной структурой и несложной семантикой,-- такие как Алгол-60, Паскаль,Модула-2. Многое из того, что есть в Си++, с трудом "втискивалось" вакадемические построения, и приходилось дополнять и развивать их. В результатетаблицы представляют собой причудливую смесь классической стековой модели сдисплеем для отображения текущего контекста и наворотов вроде средствдинамического перестроения контекста для обработки функций-членов классов,нетривиальной поддержки областей действия имен (namespaces), буферов дляотложенной компиляции и т.д. К тому же таблицы должны быть динамическирасширяемыми, чтобы быть в состоянии вобрать в себя очень большое количествоимен, типичное для программ на Си++. Помучиться пришлось изрядно, идалеко не сразу таблицы заработали стабильно и надежно.

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

С деревом программы ситуация была обратной. Будучи один раз спроектированными,принципы организации дерева далее практически не изменялись. Впротивоположность таблицам, структура которых создавалась, чтобынепосредственно отражать контекстные отношения языка Си++, деревооказалось практически полностью языко-независимым. Иными словами, используяосновной строительный элемент дерева?—?терминальный узел?—?можно конструироватьпроизвольные конфигурации, отображающие конструкции любых языковпрограммирования. Все узлы дерева имеют идентичную структуру, различаясь лишьзначениями своих (немногочисленных) атрибутов. Каждый узел имеет четыре ссылки(вверх, вниз, влево и вправо), с помощью которых легко формировать "плоские"конфигурации, соответствующие тем или иным конструкциям входного языка. Какправило, горизонтальные ссылки отражают верхний уровень структуры некоторойконструкции, а вертикальные используются для поддеревьев, соответствующихэлементам этой конструкции, или вложенным конструкциям.

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

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

Этот раздел хочется завершить несколько неожиданным выводом. Наличие вкомпиляторе двух базовых структур?—?семантических таблиц и дерева программы?—?сейчас расценивается нами как один из самых серьезных недостатков компилятора.Эти структуры реализованы на различных принципах, работа с ними организованапо-разному, однако они существуют вместе, пронизаны взаимными ссылками (можносказать, переплетены, как корни растущих рядом деревьев) и в некоторых случаяхпросто дублируют друг друга. Сходная информация о структуре программыприсутствует и в таблицах, и в дереве, что долго приводило к путанице, и сейчасвыглядит довольно нелепо. Например, в дереве имеются узлы, соответствующиеобъявлениям; это естественно, так как образы объявлений могут попадать врезультирующий код. Что же касается таблиц, то они как раз и составлены наоснове информации, извлеченной из объявлений. Поэтому в узлах-объявленияхсодержится ссылка на соответствующее слово в таблицах. Семантическое слово, всвою очередь, имеет обратную ссылку на узел "своего" объявления, которая в рядеслучаев оказалась необходимой. Инициализатор переменной из объявленияпредставляется поддеревом, на которое имеются ссылки как из узла-объявления,так и из семантического слова. И так далее… Все это работает и даже вполнеэффективно, но, конечно, с точки зрения программного дизайна весьма далеко отсовершенства.

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

Теперь мы это хорошо понимаем. В следующей версии компилятора все будет сделанопо-другому.