Недоря А.Е. - Диссертация. Глава 2

2. Семейство Modula-2/Oberon-2 компиляторов и трансляторов

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

Компиляторы с языка Модула-2 реализованы на всех известных нам машинах, и основная проблема - это отсутствие стандарта и проблема совместимости различных версий. Заметим, что реализация языка на станциях КРОНОС содержит набор расширений языка и так же не полностью совместима с другими реализациями.

Еще более сложна проблема с реализацией языка Оберон-2. В момент начала проекта (весна 1991 г.) таких реализаций просто не существовало, а язык Оберон был реализован только на машинах, нам не недоступных (Ceres, Mac, SparcStation).

Единственным выходом была разработка собственного переносимого компилятора с языка Оберон-2. Забегая немного вперед, заметим, что наша реализация языка Оберон-2 появилась практически одновременно с появлением окончательной версии языка. Это стало возможно благодаря постоянной связи с одним из авторов языка проф. Моссенбоком.

Реализация языка Модула-2/КРОНОС не выдерживала критики с точки зрения переносимости. Поэтому было принято решение о разработке пары переносимых компиляторов.

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

2.1. Выбор схемы трансляции и понятие биязыковой транслирующей системы

Рассмотрим способы реализации пары переносимых компиляторов. Эти компиляторы можно было бы реализовать полностью независимо, но хотелось найти способы, позволяющие уменьшить затраты на разработку. Очевидное решение - это реализовать многоязыковую транслирующую систему, позволяющую для N языков и для M целевых машин реализовать N фаз анализа, транслирующих некоторой язык программирования в промежуточное представление, и M фаз синтеза, транслирующих промежуточное представление в коды конкретной ЭВМ, и тем самым существенно сократить затраты на реализацию (с N*M до N+M).

Такой общий подход принят в системе Бета [12]. Промежуточное представление определяется языком ВЯЗ. В рамках проекта были выполнены реализации языков Паскаль, Симула-67 и Фортран и подмножества языков Модула-2 и Ада. Наибольшая нагрузка в проекте выпадает на внутреннее представление (внутренний язык). Требования, предъявляемые к ВЯЗу, весьма противоречивы. С одной стороны, все конструкции языков программирования должны достаточно удобно отображаться в него, с другой стороны, он должен быть достаточно удобен для генерации кода. Соответственно, уровень его должен быть достаточно низок (очевидно, что все операторы управления могут быть представлены в терминах переходов управления), и достаточно высок, для того чтобы можно было выполнять оптимизацию и генерацию кода на разные машины.

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

Отрицательный результат экспериментов с многоязыковыми системами (не только с системой Бета) является отражением того факта, что проблема в целом неразрешима (или пока неразрешима) и для достижения успеха необходимо пойти на некоторые ограничения. Если для систем типа системы Бета использовать обозначение N->M, то естественно рассмотреть случаи, когда N или M равно 1, то есть компиляция одного языка на множество машин, или компиляция множества языков на одну машину. Введение таких ограничений оказывается вполне достаточным. Примером удачной системы N->1 является система TopSpeed, в которой реализованы языки Модула-2, Паскаль, C, C++ для IBM PC, а примером удачной системы 1->M является Оберон-компилятор OP2 [13], который в настоящее время перенесен на такие существенно различные архитектуры, как SPARC [14], MC 680x0 [15], MIPS, RS/6000 и i80386.

Как нам кажется, успех таких систем обусловлен тем, что в обоих случаях существует определенность на одном конце системы. Для системы 1->M определен входной язык, и вся дальнейшая работа может выполняться в его терминах. Промежуточное представление соответствует входному языку. Для системы N->1 задана целевая архитектура, и каждый входной язык системы транслируется в некоторое промежуточное представление, близкое к целевой архитектуре. Необходимо также отметить неявное задание семантики, что существенно облегчает разработку промежуточного представления. В случае неограниченной системы (N->M) все семантические особенности языков должны быть явно отражены в промежуточном представлении.

Проведенный анализ показывает трудности разработки многоязыковых систем. С другой стороны, мы не можем ограничиться схемой 1->M или N->1. Выход из этого тупика нам дает анализ необходимых для системы входных языков. Язык Оберон-2 является расширенным подмножеством языка Модула-2. Большинство конструкций этих языков обладают сходной семантикой.

Таким образом, мы приходим к отображению 1+e -> M, где e определяет количество дополнительных конструкций, необходимых для реализации второго входного языка (e << 1). При таком подходе мы будем (как и в Бете) строить промежуточное представление как отображение объединения двух языков, но, в отличие от системы Бета, набор входных языков определен изначально и не может быть расширен, и, что очень важно, семантика этих языков для большинства конструкций совпадает. Так как промежуточное представление является общим для обоих языков, то и фазы синтеза для каждой целевой архитектуры совпадают, а при реализации фазы анализа мы выделили все общие компоненты компилятора (подробнее см. 2.4).

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

 Процедурный интерфейс

Интерфейс между фазой анализа и синтеза оформляется в виде набора процедур. Анализ вызывает процедуру, соответствующую синтаксической (под-)конструкции после разбора данной конструкции. Так, разбор условного оператора может быть задан процедурами if, else, endif. Например, при компиляции условного оператора

может быть порождена последовательность вызовов:

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

Процедурный интерфейс был реализован автором в компиляторе mx [16]. Кроме генератора для ЭВМ КРОНОС [17,18], была также реализована версия генерации для NS32x32. Эти эксперименты показали, что реализация переносимого компилятора по этой схеме хотя и возможна, но требует больших усилий.

 Промежуточный язык

При этом подходе фаза анализа строит текст на некотором промежуточном языке, а фаза синтеза выполняет разбор текста на промежуточном языке, а затем выполняет генерацию кода. В практике разработки компиляторов промежуточные языки в основном использовались не для построения переносимых компиляторов, а для разбиения компилятора на последовательность достаточно небольших проходов, которые могли выполняться на ограниченных ресурсах системы. Блестящим примером такого подхода является шестипроходный Concurrent Pascal компилятор [19] для ЭВМ PDP-11. Другим примером является четырехпроходный Модула-2 компилятор, число проходов которого изначально было определено объемом памяти ЭВМ Lilith, и который затем был перенесен на другие платформы. Для этого необходимо было переписать проходы фазы синтеза. Промежуточные языки также широко используются в многоязыковых транслирующих системах [12].

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

 Промежуточная структура в памяти

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

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

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

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

2.2. Входные языки системы

Существенно разные решения были приняты при фиксации входных языков системы. Мы полагаем, для языка Оберон-2 – основного входного языка системы - важно реализовать стандарт языка [10]. Поэтому мы добавили только несколько расширений, не изменяя языка.

Ситуация с языком Модула-2 является в данный момент достаточно неясной. Во-первых, существует стандарт де-факто языка PIM3 [7] и проект стандарта языка, который в данный момент готовит рабочая группа WG13 ISO. Некоторые черты языка существенно отличаются в этих двух описаниях. Во-вторых, каждая известная нам реализация языка вносила существенные изменения. Так, достаточно далекой как от PIM3, так и от проекта стандарта является реализация языка в системе TopSpeed.

Мы попытались найти некоторое равновесие между проектом стандарта, PIM3 и, кроме того, приблизить язык к языку Оберон-2. Кратко перечислим основные особенности реализованной версии языка Модула-2.

1) Базовые типы

Набор числовых типов существенно расширен; кроме типов INTEGER, CARDINAL, REAL и LONGREAL добавлены типы SHORTINT, LONGINT, SHORTCARD, LONGCARD. Важной особенностью реализации является понятие включения типов (см. Оберон), то есть значение некоторого числового типа является также значением объемлющего числового типа. Компилятор поддерживает следующую иерархию типов:

SHORTINT  <= INTEGER  <= LONGINT
                                  <= REAL <= LONGREAL
SHORTCARD <= CARDINAL <= LONGCARD

Знак "<=" в данном случае обозначает включение.

2) Многомерные динамические массивы

В соответствии с проектом стандарта, параметр процедуры может быть многомерным открытым массивом. Также реализованы многомерные динамические массивы в духе Оберона-2.

Например:

3) Экспорт только для чтения

Переменные в определяющем модуле могут быть помечены символом "-":

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

4) Переименование при импорте

В секции импорта можно задать внутреннее имя для импортируемого модуля. Это свойство взято из языка Оберон.

5) Процедуры с переменным числом параметров

Введен специальный синтаксис для процедур с переменным числом параметров. Последний параметр такой процедуры описывается в виде:

Вместо такого параметра может быть подставлена любая последовательность параметров (в том числе и пустая) любого типа. Это низкоуровневое средство позволяет реализовать процедуры форматного вывода, аналогичные стандартной процедуре printf библиотек языка C.

Это расширение упрощает реализацию библиотек ввода/вывода, которые являются узким местом во всех реализациях Модулы-2.

2.3. Внутреннее представление

Как уже упоминалось в пункте 2.2, для внутреннего представления нами выбрано синтаксическое дерево (СД) единицы компиляции. Это представление не является идеальным для выполнения оптимизаций и качественной генерации. Впрочем, для разных оптимизаций требуется различная форма представления. Мы полагаем, что для выполнения оптимизаций дерево может перестраиваться в некоторую удобную форму. Такое преобразование гораздо удобней выполнять с деревом, чем с другими видами промежуточных представлений. В двух реализованных генерациях (см. 2.6.1, 2.6.3) для оптимизации структур управления по дереву строится граф управления. Для простой, неоптимизирующей генерации СД достаточно удобно.

Большое влияние на выбор формы СД оказало внутреннее представление Оберон-2 компилятора OP2, описанное в [13]. Мы взяли это представление за основу и добавили конструкции, соответствующие расширенному набору типов и операторов языка Модула-2.

Внутреннее представление образовано узлами четырех видов: NODE (Узел), OBJECT (Объект), STRUCT (Структура) и VALUE (Значение). Операторная часть программы отображается в дерево, состоящее из Узлов. Кроме того, в дерево входят Узлы, соответствующие единице компиляции и процедурам. Кроме ссылок на левое и правое поддеревья Узел содержит ссылку для определения последовательности Узлов. Единица компиляции отображается в дерево вида:

                      модуль

                    /       \

                  /      оператор -> ... -> оператор

                /

            процедура -> .... -> процедура

В свою очередь,

                    процедура

                    /       \

                  /      оператор -> ... -> оператор

                /

            процедура -> .... -> процедура

Блок (процедура или модуль) содержит ссылку на последовательность операторов и на список вложенных процедур. Локальные модули не отображаются в синтаксическом дереве.

Узел, соответствующий объекту (переменной, константе или процедуре), содержит ссылку на описатель объекта (запись типа OBJECT). Все узлы, кроме операторных, содержат ссылку на типовое значение (запись вида STRUCT). Объекты-константы и узлы, соответствующие константам и литералам, содержат ссылку на значение (запись типа VALUE).

Приведем примеры представления некоторых конструкций.

 Для описания типа:

будет построен объект с видом "тип" и два типовых значения с видами "указатель" и "открытый массив"

        OBJECT      STRUCT      STRUCT      STRUCT

         type
         base ----> pointer
         "T"        base   ---> array_of
                                base    ----> char

 Оператор

будет отображен в следующую структуру

                        WHILE
                       /     \
                      /       \
                     /        INC ------->    :=
                    >         /             /    \
                  /   \      n             i     DIV
                i      0                        /   \
                                              i       2

Важно отметить, что в СД отображаются все описания и операторы обоих входных языков. Это не только уменьшает затраты на перенос компилятора, но и позволяет писать на смеси языков. Так, в Оберон-2 модуле можно использовать типы, которых нет в этом языке (например, SET OF). Для этого достаточно проимпортировать тип из модуля на языке Модула-2.

2.4. Структура компилятора

Компилятор состоит из интерфейсного слоя, парсера (front-end), генератора (back-end) и утилитного слоя.

                        утилитный слой
                       /              \
                      /                \
                 парсер               генератор
                      \                /
                       \              /
                       интерфейсный слой

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

Алгоритм компиляции выглядит следующим образом (cu – корень синтаксического дерева единицы компиляции):

Парсер выполняет синтаксический и семантический анализ, строит СД единицы компиляции и возвращает его корень. Если при этом были обнаружены ошибки, то компиляции завершается. Генератор всегда работает с корректным синтаксическим деревом. Генератор выполняет проход по объектам модуля, вычисляя необходимые атрибуты: размер типов, размещение переменных, размер области параметров и т.д., после чего выполняется запись симфайла. Затем выполняется собственно генерация кода.

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

Структура генератора для разных платформ может сильно различаться (см. 2.6). Генератор может выполняться в несколько проходов по СД и может включать в себя фазу машинно-зависимой оптимизации. Машинно-независимая оптимизация может быть вставлена между фазами анализа и синтеза.

Рассмотрим подробнее структуру парсера. Парсер состоит из ядра, реализующего следующие функции:

• лексический анализ;
• описание и поиск объектов, чтение/запись симфайлов;
• построение СД, семантический контроль.

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

Такая реализация парсера возможна только благодаря близости входных языков. При разработке парсера мы старались выбирать алгоритмы, учитывающие разницу языков естественным образом. В качестве примера рассмотрим алгоритм идентификации. С точки зрения идентификации разница в языках заключается в следующем:

• локальные модули есть только в Модуле-2;
• расширение типа записи есть только в Обероне-2.

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

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

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

Три (определяемые пользователем) файла используются интерфейсным слоем для построения удобной среды программирования: файл конфигурации, файл поиска и файл сообщений.

Файл конфигурации задает различные параметры, такие как расширения файлов, ограничения на число ошибок и т.д.

Файл поиска (redirection file) задает пути поиска файлов и директории для записи создаваемых файлов.

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

Утилитный слой определяет способ доступа к исходному тексту и способ выдачи сообщений об ошибках. Для инструментальной машины характерно большое количество вариантов утилитного слоя и, тем самым, различных компиляторов. Так, в инструментальной среде на Кроносе в данное время используется 12 = 2*2*3 различных компиляторов:

• два входных языка
• пакетный компилятор/турбо-компилятор
• генерация для Кроноса/трансляция в ANSI C/генерация для i386.

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

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

2.5. Взаимодействие генератора с парсером

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

Рассмотрим различные способы взаимодействия. Следующая схема определяет порядок выполнения частей парсера и генератора. Здесь на одной строке записаны действия, выполняемые на одной стадии.

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

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

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

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

• вообще говоря, в этом случае симфайл должен также содержать для каждого объекта множество опций компилятора, так как от этого может зависеть размещение объекта;
• потеря преемственности: при модификации алгоритма вычисления размещения объекта может нарушиться согласованность размещений при описании и использовании объекта.

Этот вариант был отброшен, и рассматривались только различные способы размещения информации. Был выбран наиболее простой способ: после записи машинно-зависимой информации об объекте вызывается процедура генерации, которая записывает дополнительные атрибуты (аналогично - при чтении объекта).

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

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

Таким образом для реализации генератора необходимо выполнить следующие действия:

• определить параметры окружения;
• реализовать операцию вычисления машинно-зависимых операций;
• реализовать обход всех объектов единицы компиляции для вычисления машинно-зависимых атрибутов;
• реализовать операции чтения/записи машинно-зависимых атрибутов;
• реализовать генерацию кода (маленький такой пунктик).

2.6. Состав семейства

В настоящее время в состав семейства входят компиляторы для рабочих станций Кронос и для машин на базе i386/486 и трансляторы в ANSI C. В следующих пунктах дается краткое описание особенностей разработки генерации.

2.6.1. Компиляторы для рабочих станций Кронос

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

Компилятор является стандартным с точки зрения ОС Excelsior, то есть он порождает стандартный кодофайл и стандартный файл с отладочной информацией. Компилятор позволяет импортировать модули, скомпилированные компилятором mx. Для этого реализована специальная утилита "конвертор симфайлов", которая переводит симфайл из стандарта mx в стандарт переносимого компилятора.

Оберон-2 компилятор дополнительно записывает в кодофайл образ типовой системы. Этот образ необходим для реализации операций управления памятью, сборки мусора и динамической типизации. Модуль динамической поддержки (RTS) неявно импортируется в каждый Оберон-модуль. При инициализации модуля RTS по образу типовой системы строит структуры, необходимые для его дальнейшей работы. Описание и анализ таких структур можно найти в работе [23]. Модуль динамической поддержки реализован А.Хапугиным.

2.6.2. Трансляторы в ANSI C

В качестве одного из генераторов семейства нами реализован генератор, порождающий текст на языке ANSI C. В последнее время язык C часто используется в качестве промежуточного языка. Так, большинство компиляторов с современных ОО языков (Eiffel, Sather, Modula-3) порождают текст на языке C. В первую очередь это объясняется широким распространением языка C. Реализовав генерацию в C, мы фактически получаем компилятор для всех машин сразу. С другой стороны, язык C достаточно удобен в качестве промежуточного языка. Мы рассматриваем язык C в качестве переносимого ассемблера, неудобного и ненадежного для ручного программирования, но вполне подходящего для генерации.

Язык С не создавался для использования в качестве промежуточного языка, и он обладает некоторыми недостатками, усложняющими трансляцию на него:

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

Транслятор в ANSI C может быть использован двумя разными способами. В первом варианте такой транслятор является первым проходом компилятора, причем вторым проходом вызывается C компилятор. Во втором варианте используется собственно порожденный текст на языке C; например, он переносится на другую платформу.

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

Генератор состоит из головного модуля, реализующего процедуры

"размещение_объектов_модуля" и

"генерация_кода" (см. 2.4)

и компонент, реализующих следующие функции:

генерация описаний;

генерация выражений;

генерация операторов.

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

Модуль генераций описаний порождает описания объектов на языке С по их внутреннему представлению. Практически всем типам и объектам языков Оберон-2/Модула-2 соответствуют аналоги в языке C. Исключение составляют вариантные записи и расширенные записи.

Приведем примеры трансляции описаний. Мы будем опускать некоторые детали для упрощения примеров.

Modula-2	C
TYPE   P = POINTER TO INTEGER;   TYPE   R = RECORD     CASE male: BOOLEAN OF       |TRUE : salary: REAL;       |FALSE: beauty: LONGINT;     END;   END;     TYPE   Vector = POINTER TO               ARRAY OF REAL;     Matrix = ARRAY [0..7] OF Vector;   VAR   matrix: Matrix;   i,j: INTEGER;   r: REAL;	typedef INTEGER *P;     typedef struct R_STR {   BOOLEAN male;   union {     REAL salary;     LONGINT beauty;   } X1; } R;     typedef struct   { INDEX Len0; } *Vector;   typedef Vector Matrix[8];     Matrix matrix; INTEGER i; INTEGER j; REAL r;

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

Рассмотрим генерацию на примере оператора присваивания:

где переменные matrix, i, j, r описаны выше.

Этому оператору соответствует синтаксическое дерево:

                      :=
                    /    \
                   r    index
                       /     \
                      ^       j
                    /
                 index
                /     \
            matrix      i

Динамические массивы (POINTER TO ARRAY OF) представляются в виде указателя на дескриптор, содержащий длины всех измерений. Тело массива расположено непосредственно за дескриптором. Для выполнения второй индексации нам необходимо использовать указатель на дескриптор для доступа к телу массива и для проверки коректности индекса. Следовательно, необходимо сохранить этот указатель во временной переменной.

Первый обход оператора объявит временную переменную и преобразует оператор в последовательность операторов следующим образом:

       :=      ----->      :=
     /    \              /    \
    V    index          r    index
        /     \             /     \
    matrix     i           ^       j
                         /
                        V

где V - временная переменная типа Vector.

В результате мы получим следующий C текст:

где функция CHKINX выполняет проверку индекса массива.

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

Описание процедуры будет отображено в последовательность следующих описаний:

1) Структуры, содержащей все используемые переменные:

2) Описания локальных процедур с дополнительными параметрами - указателем на структуру и указателями на дополнительные параметры:

3) Описание процедуры, в которой вместо всех используемых во вложенных процедурах переменных описана переменная типа структура:

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

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

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

Все модули транслятора можно разделить на две существенно разные по размеру части: меньшая часть - интерфейсный и утилитный слои - является потенциально не переносимой, большая часть, а именно парсер и генератор, являются переносимы. При переносе транслятора интерфейсный и утилитный слои были переписаны на языке C. Причем переписывались только реализующие модули, а определяющие модули просто транслировались. Также на языке C была реализована библиотека вспомогательных функций и динамической поддержки. Чтобы избежать зависимости от различных реализаций языка C при реализации этих слоев, использовался минимальный набор функций из стандартизованных ANSI библиотек. Впрочем, полной независимости интерфейсного слоя достичь не удалось. Так, для реализации поиска файла по путям поиска необходимо знать разделитель в полном имени файла. Таким разделителем является символ "/" для ОС Unix, "\" для MS-DOS, а для VMS разделитель отсутствует. Для того чтобы учитывать это и другие различия, мы использовали стандартную технику: в заголовке стандартной библиотеки определяется вид платформы, и только это определение платформы необходимо поменять при переносе транслятора.

Изучение различий и разработка переносимого интерфейсного слоя заняли довольно много времени, но в результате удалось получить продукт с очень высокими показателями переносимости. Так, в настоящее время трансляторы работают на следующих платформах: ОС Excelsior, MS-DOS, VAX/VMS (перенос выполнен автором), Sun SparcStation, HP-700, Silicon Graphics INDIGO (перенос выполнен Д.Кузнецовым). Время переноса на очередную платформу измеряется несколькими часами и, как правило, определяется скоростью чтения флоппи-диска.

2.6.3. Компиляторы для машин на базе i80386/486

Описание компиляторов можно найти в [24]. Реализация генерации кода была выполнена А.Денисовым и О.Шатохиным. В переносе компилятора активное участие принимал А.Хапугин. Он же реализовал модуль динамической поддержки для языка Оберон-2.

Одним из наиболее существенных вопросов при разработке нового компилятора является выбор целевой исполняющей системы, то есть выбор модели задачи, в рамках которой исполняется порожденный компилятором код. Традиционным решением для процессоров серии i80x86 является генерация кода фактически для самого младшего процессора семейства ("виртуальный 8086"), создание стандартного загрузочного или объектного модуля (.EXE- или .OBJ- файла) и использование штатных механизмов ОС MS-DOS по распределению ресурсов.

Однако для целей нашего проекта путь этот представляется неудовлетворительным, так как он не позволяет полностью использовать возможности, предоставляемые старшими моделями семейства - i80386/i80486.

Было принято решение изначально ориентироваться на модель задачи, способной исполняться только на процессорах i80386/i80486 и достаточно полно использовать такие предоставляемые аппаратурой возможности, как 32-разрядная арифметика, наличие 4-Гбайтного адресного пространства, большая физическая память, страничный диспетчер, механизм защиты. В силу этого задачи должны исполняться в защищенном режиме процессора. При этом используется "почти плоская" модель памяти, то есть используются только два сегмента памяти, один из которых содержит данные всех модулей, а другой - коды всех модулей задачи.

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

Кроме компилятора был реализован специальный загрузчик, который переводит процессор в защищенный режим (protected mode PM), после чего взаимодействие с ОС происходит путем "ретрансляции" аппаратных и системных прерываний в незащищенный режим (real mode RM), т.е. загрузчик переключает процессор в RM, давая возможность ОС выполнить свои функции в RM, затем возбуждает прерывание с таким же номером, после чего возвращает процессор в PM для продолжения исполнения загруженной задачи. Время, затрачиваемое на переключение процессора в RM и возврат его в PM, пренебрежимо мало по сравнению со временем обработки большинства аппаратных и системных прерываний, поэтому производительность системы практически не снижается.

Для получения информации о наличии и использовании расширенной памяти загрузчик обращается к драйверу расширенной памяти (extended memory manager XMM), что исключает возможные конфликты с иным програмным обеспечением MS-DOS, использующим расширенную память. Вся полученная таким образом память с помощью страничного диспетчера "выстраивается" в линейном пространстве адресов в непрерывный участок памяти, начинающийся с некоторого фиксированного адреса. Это позволяет избежать дополнительной настройки образа задачи после его загрузки и устраняет влияние фрагментации памяти в момент запуска задачи.

2.7. Особенности реализации языка Оберон-2

Необходимо отметить две существенные особенности реализации языка Оберон-2:

• канонизация симфайла;
• динамическая типизация и вызов методов.

2.7.1. Канонизация симфайла

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

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

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

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

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

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

Например, пусть дерево видимости выглядит следующим образом:

                K
               / \
              A   P
                 / \
                N   X
                     \
                      Z

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

A -> K -> N -> P -> X -> Z

Далее список будет перестроен, и объекты будут записаны в симфайл в следующем порядке:

N -> K -> A -> X -> P -> Z

И при чтении симфайла мы получим сбалансированное дерево:

                N
               / \
              K   X
             /   / \
            A   P   Z

2.7.2. Динамическая типизация и вызов методов

В работе [23] описана структура дескриптора типа, позволяющая выполнять динамическую типизацию и вызов методов за константное время. Дескриптор типа состоит из таблицы указателей на дескрипторы базовых типов (фиксированного размера), таблицы методов и некоторой дополнительной информации, необходимой для работы алгоритма сборки мусора. Для каждого типа статически известен уровень типизации, и динамическая проверка типа p IS T транслируется в следующее действие:

  дескриптор(p)^.таблица_типов[уровень_типа(T)] = дескриптор(T)

То есть, динамический тип p является расширением типа T, если его предок уровня типа T равен T.

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

Описатель типа записи содержит следующую информацию:

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

Размер записи используется процедурами выделения памяти и сборки мусора. Ссылка на базовый тип записи позволяет сформировать таблицу типов. Описатели методов определяют таблицу методов. Информация о размещении полей указательного типа используется в фазе маркировки алгоритма сборки мусора.

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

2.8. Характеристики семейства и сравнение его представителей

Еще раз отметим основные особенности реализации семейства:

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

Приведем далее некоторые характеристики компиляторов.

Размеры модулей парсера указаны в строках. В скобках приведены размеры определяющего модуля.

определение внутреннего представления	45(270)
лексический анализ	480(90)
видимость, чтение/запись симфайлов	1270(120)
построение дерева, семантический контроль	1800(100)
синтаксический анализ (Модула-2)	1750(15)
синтаксический анализ (Оберон-2)	1535(15)

Итого, размер фазы анализа для языка Модула-2 - 5345(595) строк, а для языка Оберон-2 - 5130(595). Причем, общая часть составляет 3595(580) строк. Небольшие размеры фазы анализа подтверждают правильность выбора схемы трансляции.

Далее проведем сравнение различных генераций:

Характеристика	Кронос	ANSI C	i386/486
Размер генератора (в строках)	4600	4100	11000
Время разработки (человекомесяцев)	3	8	24
Скорость компиляции (строк/минуту)	2000	8000	30000
оценка скорости ЭВМ (Dhrystones/sec)	1200 (Kronos-2.6WS)	4200 (i386 14Mhz)	25000 (i496 33Mhz)
Время самокомпиляции (секунды)	600	70	40

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