Евгений Зуев: Редкая профессия

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

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

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

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

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

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

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

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