Евгений Зуев - Редкая профессия
Спасибо, в "Зеленой книге" подсказали схему такого анализа. Не знаем, как и благодарить, сами бы ни за что не придумали…
Что такое идентификатор?
Помимо неоднозначностей в синтаксисе быстро обнаружились другие неприятности. На примерах их показать сложнее, так что придется рассказывать словами.
Синтаксис языка Си++ неудобен еще и в другом отношении. Если говорить коротко, то прямое использование в формальном описании одного из базовых синтаксических понятий — идентификатора — приводит к тому, что YACC расценивает грамматику языка как некорректную и на ее основе не может построить синтаксический анализатор. Для традиционных языков синтаксическому анализатору для разбора конструкции достаточно информации о том, что в данной позиции этой конструкции может (или должен) находиться идентификатор. Более простые языки сконструированы так, что семантика идентификатора не влияет на корректность синтаксического разбора. Вид программной сущности, обозначаемой этим идентификатором (подпрограмма, переменная, имя типа, исключение, метка и т.п.), смысл данного конкретного вхождения (объявление или использование) — все это выявляется далее, как правило, являясь предметом следующей фазы компиляции — семантического анализа.
Для языка Си++ такая схема не проходит. Чтобы быть в состоянии синтаксически распознать многие конструкции, требовалась семантическая интерпретация имени. Иными словами, на вход синтаксическому анализатору следовало поставлять не абстрактную лексему "идентификатор", а результат анализа того, что именно представляет собой этот идентификатор: "имя типа", "новое имя в объявлении", "имя не-типа в выражении" и т.д. Заметим, что синтаксическому анализатору для Java — непосредственного потомка Си++ — вполне хватает понятия идентификатора без каких-либо уточнений.
Всего для Си++ получилось около десятка таких "суперлексем", а лексема "идентификатор" вообще исчезла из синтаксиса. Понятно, что лексический анализатор, который и поставляет лексемы, пришлось наделить дополнительным "интеллектом". Теперь он должен был не просто выделять из текста программы очередную лексему, но и обращаться в таблицы трансляции за информацией о том, что за идентификатор он выловил. Реально эти действия выполняет отдельный модуль, названный "расширенным лексическим анализатором". Введение дополнительного модуля не привело к усложнению компилятора в целом, так как идентификация имен так или иначе должна производиться; мы просто перенесли ее на более ранний этап компиляции. А синтаксис заметно упростился, стал более наглядным, информативным и в конечном счете более эффективным.
Компилятор как таковой: таблицы и деревья
Однако синтаксис — это мелочи жизни. Основное в любом компиляторе — это интерпретация семантики языковых конструкций, и подавляющая часть кода приходится именно на семантические алгоритмы.
Есть два основных вида семантической информации, которые компилятор извлекает из текста исходной программы. Во-первых, это информация о различных объектах, которые используются в программе (переменные, типы, функции и т.д.), причем не только об объектах как таковых, но и об областях действия, в которых эти объекты существуют (имеют смысл), а также об отношениях этих областей между собой (контекстах). Чем сложнее устроен язык, тем больше в нем правил, связанных с объектами, и тем более изощренной должна быть та структура в компиляторе, которая описанную информацию содержит. Такая структура обычно называется семантическими таблицами.
Во-вторых, компилятор должен формировать некоторый образ исходной программы — внутреннее представление программы в целом или ее некоторой части, которая в данный момент обрабатывается. Именно на основе такой структуры обычно выполняется семантический анализ программы, производятся различные оптимизации и осуществляется генерация результирующего кода. Как правило, такое внутреннее представление строится в виде дерева и потому называется деревом программы.
Эта пара — таблицы и деревья, вместе с различными алгоритмами, работающими над ними, без преувеличения составляет две трети текста компилятора. Почти вся наша работа на протяжении всех этих лет так или иначе была связана с ними.
Структура таблиц была придумана в целом по образцам из книг по теории и практике компиляции, которые в изобилии выходили у нас в 70-80-х годах и описывали, как правило, языки с относительно простой и, самое главное, регулярной структурой и несложной семантикой,-- такие как Алгол-60, Паскаль, Модула-2. Многое из того, что есть в Си++, с трудом "втискивалось" в академические построения, и приходилось дополнять и развивать их. В результате таблицы представляют собой причудливую смесь классической стековой модели с дисплеем для отображения текущего контекста и наворотов вроде средств динамического перестроения контекста для обработки функций-членов классов, нетривиальной поддержки областей действия имен (namespaces), буферов для отложенной компиляции и т.д. К тому же таблицы должны быть динамически расширяемыми, чтобы быть в состоянии вобрать в себя очень большое количество имен, типичное для программ на Си++. Помучиться пришлось изрядно, и далеко не сразу таблицы заработали стабильно и надежно.
Опуская технические детали, следует сказать, что сейчас мы в целом недовольны тем, как спроектированы семантические таблицы. В свое оправдание отметим, что все "навороты" в них — вещи вполне объективные, которые так или иначе должны присутствовать в компиляторе. Наша неудовлетворенность имеет, скорее, эстетическую природу: таблицы не выглядят стройной системой, где каждый компонент точно подогнан к тому месту, которое для него предназначалось.
С деревом программы ситуация была обратной. Будучи один раз спроектированными, принципы организации дерева далее практически не изменялись. В противоположность таблицам, структура которых создавалась, чтобы непосредственно отражать контекстные отношения языка Си++, дерево оказалось практически полностью языко-независимым. Иными словами, используя основной строительный элемент дерева — терминальный узел — можно конструировать произвольные конфигурации, отображающие конструкции любых языков программирования. Все узлы дерева имеют идентичную структуру, различаясь лишь значениями своих (немногочисленных) атрибутов. Каждый узел имеет четыре ссылки (вверх, вниз, влево и вправо), с помощью которых легко формировать "плоские" конфигурации, соответствующие тем или иным конструкциям входного языка. Как правило, горизонтальные ссылки отражают верхний уровень структуры некоторой конструкции, а вертикальные используются для поддеревьев, соответствующих элементам этой конструкции, или вложенным конструкциям.
Несомненными достоинствами такой схемы являются высокая регулярность, простота и универсальность. Дерево для любой языковой конструкции строится по единым правилам, и все разнообразие выразительных свойств Си++ приводится к строгой единообразной регулярной конфигурации, для которой очень удобно строить всевозможные рекурсивные алгоритмы анализа, трансформации и генерации.
Однако у этих достоинств есть и оборотная сторона, которую можно определить как низкий уровень структуры дерева. В чистом виде оно не несет в себе никакой семантической информации — это лишь определенная структура и ничего более. Иными словами, для дерева как такового можно определить только достаточно примитивные операции, например, "связать два узла горизонтальными ссылками", "построить из данных узлов бинарное дерево" и т.п. Любое же мало-мальски серьезное действие, учитывающее семантику того или иного поддерева, например, его перестроение в процессе оптимизации или при генерации кода, приходится программировать специально для каждого вида конфигураций. На практике это приводит к тому, что операции над деревом не располагаются в одном или нескольких модулях, а рассредоточены по всему тексту компилятора.
Этот раздел хочется завершить несколько неожиданным выводом. Наличие в компиляторе двух базовых структур — семантических таблиц и дерева программы — сейчас расценивается нами как один из самых серьезных недостатков компилятора. Эти структуры реализованы на различных принципах, работа с ними организована по-разному, однако они существуют вместе, пронизаны взаимными ссылками (можно сказать, переплетены, как корни растущих рядом деревьев) и в некоторых случаях просто дублируют друг друга. Сходная информация о структуре программы присутствует и в таблицах, и в дереве, что долго приводило к путанице, и сейчас выглядит довольно нелепо. Например, в дереве имеются узлы, соответствующие объявлениям; это естественно, так как образы объявлений могут попадать в результирующий код. Что же касается таблиц, то они как раз и составлены на основе информации, извлеченной из объявлений. Поэтому в узлах-объявлениях содержится ссылка на соответствующее слово в таблицах. Семантическое слово, в свою очередь, имеет обратную ссылку на узел "своего" объявления, которая в ряде случаев оказалась необходимой. Инициализатор переменной из объявления представляется поддеревом, на которое имеются ссылки как из узла-объявления, так и из семантического слова. И так далее… Все это работает и даже вполне эффективно, но, конечно, с точки зрения программного дизайна весьма далеко от совершенства.
