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

Наш проект делает упор на разработку следующих идей:

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

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

Кроме использования стандарта самого языка, мы опираемся на еще один замечательный документ - ASIS (Ada Semantic Interface Specification). В этом документе систематизированы конструкции языка, их свойства и взаимосвязи. В нем определен независимый от производителя компилятора интерфейс для получения синтаксической и семантической информации о программе на языке Ада. Опираясь на этот стандарт, могут быть созданы различные программы по анализу и обработки Ада текстов. Мы используем ASIS как основу нашего компилятора. Фактически, генератор кода будет получать всю необходимую информацию через этот интерфейс.

Построение генератора машинного кода на данном этапе не входит в цели проекта. Эта задача по своей сложности сравнима с построением семантической части компилятора. Существуют готовые системы, которые хорошо решают эту задачу, и мы рассчитываем использовать их для генерации кода. Как пример одной из таких систем можно назвать проект TenDRA. Одна из его компонент (installer) как раз и предназначена для данной цели. Она воспринимает описание программы в архитектурно нейтральном формате (ANDF) и генерирует машинный код под целевую платформу.

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

Спецификация Семантического Интерфейса к языку Ада (Ada Semantic Interface Specification, ASIS) - это стандарт Международной Организации по Стандартизации (ISO/IEC 15291:1999). Он определяет интерфейс к окружению языка программирования Ада со стороны инструментальных средств, нуждающихся в лексической, синтаксической и семантической информации. К таким инструментальным средствам можно отнести трансляторы, программы навигации по тексту, средства контроля стиля кодирования, инструменты для реструктуризации исходного текста, генерации документации, обратной инженерии, вычисления различных метрик, генерации тестовых наборов, автоматического доказательства корректности и многое другое. ASIS разрабатывался как интерфейс, который не зависит от внутренней архитектуры используемой Ада-системы, обеспечивая, таким образом, переносимость инструментальных средств. ASIS предоставляет информацию о программах в высокоуровневых терминах, находящихся в хорошем соответствии со стандартом языка Ада, скрывая, таким образом, всю сложность архитектуры и внутреннего представления реализации компилятора Ада.

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

Компилятор можно разделить на три большие части. Gela ASIS, проверка корректности Ада программы и генератор кода. Модуль Gela ASIS вобрал в себя лексический и синтаксический анализ, построение AST (Abstract Syntax Tree), разрешение неоднозначностей и вычисление семантических свойств. Этот модуль отлавливает небольшую часть ошибок, при наличии которых во входной программе AST просто не может быть построено. Остальные, более тонкие ошибки должен найти модуль проверки. После всех проверок генератор кода может приступить к своей работе. Как генератор кода, так и модуль проверки корректности получает данные о программе через ASIS интерфейс.

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

В Аде один и тот же идентификатор может обозначать разные сущности в зависимости от положения в тексте. Значение идентификатора определяется правилами видимости. Первое, что делает компилятор после построения синтаксического дерева, это, следуя правилам видимости (Visibility Rules) определяет значения идентификаторов. Этот процесс называется разрешением имен.

Синтаксис некоторых конструкций языка не однозначен. Например, вызов функции, доступ к элементу массива, преобразование типа и взятие отрезка массива синтаксически выглядят одинаково. Чтобы распознать правильно конструкцию нужно выполнить специальную процедуру. Назовем ее разрешением перегрузок (Overload resolution). Разрешения имен и перегрузки входят в работу модуля Gela ASIS.

При проектировании языка Ада немало внимания уделялось переносимости программ. Рассмотрим, как мы можем использовать свойства переносимости языка для построения машинно-независимого транслятора.

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

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

declare
   type Int_1 is range 1 .. 10;
   type Int_2 is range 1 .. 20;
   procedure F (X : Int_1);
   procedure F (X : Int_2);

   Arr : array (Int_1, Int_2) of Boolean;
begin
   for K in Arr'Range (Integer'Size / 16) loop
      F (K);
   end loop;
end;


  

Очевидно, что, если транслятор не знает размера типа Integer (а эта информация зависит от целевой платформы), то ему не известно, какого типа будет выражение Arr'Range (...) и, следовательно, тип переменной K. Без знания типа переменной K мы не в состоянии выбрать, какую функцию F нужно вызвать внутри цикла. Поэтому мы не можем преобразовать эту программу в машинно-независимый код.

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

declare
   type Rec (Value : Integer) is record
      case Value is
         when 1 =>
            X : Int_1;
         when others =>
            Y : Int_2;
      end case;
   end record;

   Var : Rec := (Integer'Size / 16, 1);

  

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

Единственным реализованным на данный момент модулем проекта Gela является ASIS. И даже он, пока, реализован с ограничениями. К таким ограничениям можно отнести:

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

Основой для построения синтаксического дерева является иерархия теговых типов. Каждый тип из этой иерархии соответствует одному виду (Kind) элементов ASIS. Базовые типы вводят общие свойства элементов, которые наследуются дочерними типами. Дочерние типы расширяют набор свойств специфичными для соответствующего вида элементов ASIS свойствами. В этой иерархии также присутствуют абстрактные типы не соответствующие никакому виду элементов ASIS. Они введены для хранения общих свойств нескольких дочерних элементов. Иерархия описывается в XML файле.

Рисунок 1. Базовый элемент иерархии Base_Element_Node и его дочерние типы.

Используя тот же XML файл, что и для построения лексического анализатора можно построить входной текст для программы ayacc. Но синтаксис языка Ада, в том виде, в котором он дан в стандарте языка, не является LR(1) грамматикой. Чтобы ayacc воспринял этот синтаксис нужно устранить неоднозначности. Например, выражение X (Y) может быть интерпретировано как

Чтобы упростить грамматику и привести ее к виду необходимому для ayacc мы удалим или заменим некоторые элементы синтаксиса. Операции по изменению синтаксиса описаны в файле fix.xml. Это позволяет произвести изменения синтаксиса при помощи XSLT преобразование, а также легко получить читаемый документ о произведенных изменениях . Здесь представлен откорректированный синтаксис . Изменения синтаксиса компенсируются на последующих стадиях работы компилятора.

Входной текст для ayacc кроме синтаксиса описывает и действия, выполняемые для построения синтаксического дерева. Так как элементы ASIS описаны в тех же понятиях что и синтаксические конструкции в стандарте языка Ада, в большинстве случаев построение синтаксического дерева тривиально. Например, правило "selected_component ::= prefix.selector_name" может быть обработано так

selected_component :
     prefix dot selector_name
{
   declare
      New_Node : constant Selected_Component_Ptr :=
        New_Selected_Component (The_Context);
   begin
      $$ := YYSTYPE (New_Node);
      Set_Start_Position (New_Node.all, Start_Position ($1.all));
      Set_Prefix (New_Node.all, $1);
      Set_Selector (New_Node.all, $3);
      Set_End_Position (New_Node.all, End_Position ($3.all));
   end;
}
;
        

В других случаях требуется более сложная обработка, такая как явное обозначение атрибута для синтаксической конструкции (поместить type_definition в поле Type_Declaration_View), уточнение типа создаваемого узла (создавать Constant_Declaration если есть слово constant, иначе Variable_Declaration), создавать промежуточные узлы (для Defining_Enumeration_Literal_Node создать дополнительно Enumeration_Literal_Specification_Node), указать тип списка для списков синтаксических элементов (создавать тип Primary_Declaration_Lists.List для component_item_list) и прочее. Правила создания кода для подобных случаев сгруппированны в файле code.xml. Этот файл довольно сложен для обработки при помощи XSL. Его обрабатывает отдельная программа на языке Аде. Эта программа берет синтаксис fixed.xml и правила code.xml и выдает входной файл для ayacc. Программа ayacc, обработав его, генерирует синтаксический анализатор, строящий абстрактное синтаксическое дерево (AST).

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

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

Следующий проход (Asis.Gela.Resolver) выполняет построение декларативных регионов и разрешение имен, описание неявных определений и вызов процедуры разрешения перегрузок на полных контекстах разрешения перегрузок (ПКРП). Сама процедура разрешения перегрузок требует еще двух проходов по ПКРП. Первый проход снизу вверх определяет наличие единственной интерпретации, второй сверху вниз модифицирует AST и семантические признаки, приводя их в соответствие с выбранной интерпретацией.

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

RTL пока представлена только спецификациями модулей из ядра стандарта языка. Платформо-зависимые типы определены как приватные, а реализованы при помощи директивы pragma Import. В дальнейшем это позволит иметь разную реализацию RTL на разных платформах и предполагает использование инструментов, аналогичных понятию Token в технологии TenDRA.

By now RTL are represented by specifications of predefined library units. Platform depended types defined as 'private' and implemented by pragma Import. In the future we plan implement pragma Import by TenDRA Token mechanism. This allows us to have different representation of predefined types on each target platform.