Автор: В.А.Серебряков

Глава 9. Системы автоматизации построения трансляторов

Системы автоматизации построения трансляторов (САПТ) предназначены для автоматизации процесса разработки трансляторов. Очевидно, что для того, чтобы описать транслятор, необходимо иметь формализм для описания. Этот формализм затем реализуется в виде входного языка САПТ. Как правило, формализмы основаны на атрибутных грамматиках. Ниже описаны две САПТ, получившие распространение: СУПЕР и Yacc. В основу первой системы положены LL(1)-грамматики и L-атрибутные вычислители, в основу второй - LALR(1)-грамматики и S- атрибутные вычислители.

9.1. Система Супер

Программа на входном языке Супер ("метапрограмма") состоит из следующих разделов:

 - Заголовок;
 - Раздел констант;
 - Раздел типов;
 - Алфавит;
 - Раздел файлов;
 - Раздел библиотеки;
 - Атрибутная схема.

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

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

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

 A ::= B [ C ] ( D ) ( E / ',' )

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

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

Суффикс A задает выполнение оператора перед каждым вхождением синтаксической конструкции, заключенной в скобки повторений (). Суффикс B задает выполнение оператора после каждого вхождения синтаксической конструкции, заключенной в скобки повторений (). Суффикс M задает выполнение оператора между вхождениями синтаксической конструкции, заключенной в скобки повторений (). Суффикс E задает выполнение оператора в том случае, когда конструкция, заключенная в скобки [], отсутствует. Атрибутные зависимости в случае повторяющегося нетерминала показаны на рис. 9.1.

                         +---+
                         | A |<---------------+
                         +---+                |
                           |                  |
            +------------------------------+  |
            |       |             |        |  |
            v       v             v        v  |
  +---+   +---+   +---+         +---+   +---+ |  +---+
->| B |-->| X |-->| X |-->...-->| X |-->| X |--->| C |-
  +---+   +---+   +---+         +---+   +---+    +---+
    |       ^       ^             ^       ^
    |       |       |             |       |
    +-------------------------------------+

                  Рис. 9.1

Пример. Использование меток атрибутных формул.

  D ::= 'd' =>
           $0.y:=$0.x+1;.

  A  ::= B (C) [D] =>
           $2.x:=1;
        2M:$2.x:=$2.x+1;
           $3.x:=$2.x;
        3E:$3.y:=$3.x;
        3 :writeln($3.y);.

Процедура WRITELN напечатает число вхождений символа C в C- список, если D опущено. В противном случае напечатанное число будет на единицу больше.

9.2. Система Yacc

В основу системы Yacc положен синтаксический анализатор типа LALR(1), генерируемый по входной (мета) программе. Эта программа состоит из трех частей:

 %{
  Си-текст
 %}
 %token Список имен лексем
 %%
 Список правил трансляции
 %%
 Служебные Си-подпрограммы

Си-текст (который вместе с окружающими скобками %{ и %} может отсутствовать) обычно содержит Си-объявления (включая #include и #define), используемые в тексте ниже. Этот Си-текст может содержать и объявления (или предобъявления) функций. Список имен лексем содержит имена, которые преобразуются Yacc-препроцессором в объявления констант (#define). Как правило, эти имена используются как имена классов лексем и служат для определения интерфейса с лексическим анализатором.

Каждое правило трансляции имеет вид

Левая-часть : альтернатива_1 {семантические действия 1}
            | альтернатива_2  {семантические действия 2}
            |...
            | альтернатива_n  {семантические действия n}
            ;

Каждое семантическое действие - это последовательность операторов Си. При этом каждому нетерминалу может быть сопоставлен один синтезируемый атрибут. На атрибут нетерминала левой части ссылка осуществляется посредством значка $$, на атрибуты символов правой части - посредством значков $1, $2 ,..., причем номер соответствует порядку элементов правой части, включая семантические действия. Каждое семантическое действие может вырабатывать значение в результате выполнения присваивания $$=Выражение. Исполнение текого оператора в последнем семантическом действии определяет значение атрибута символа левой части.

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

- конфликты типа свертка/свертка разрешаются выбором правила, предшествующего во входной метапрограмме;

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

Например, объявление

 %left '+' '-'

определяет + и -, имеющими одинаковый приоритет и имеющими левую ассоциативность. Операцию можно определить как правоассоциативную в результате объявления

 %right '^'

Бинарную операцию можно определить как неассоциативную (т.е. не допускающую появления объединения двух подряд идущих знаков операции):

 %nonassoc '<'

Символы, перечисленные в одном объявлении, имеют одинаковое старшинство. Старшинство выше для каждого последующего объявления.

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

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

%prec терминал

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

Восстановление после ошибок управляется пользователем с помощью введения в грамматику "правил ошибки" вида A->error w. Здесь error - ключевое слово Yacc. Когда встречается синтаксическая ошибка, анализатор трактует состояние, набор ситуаций для которого содержит правило для error, некоторым специальным образом: символы из стека выталкиваются до тех пор, пока на верхушке стека не будет обнаружено состояние, для которого набор ситуаций содержит ситуацию вида [A-> . error w]. После чего в стек фиктивно помещается символ error, как если бы он встретился во входной строке.

Если w пусто, делается свертка. После этого анализатор пропускает входные символы, пока не найдет такой, с которым можно продолжить нормальный разбор. Если w не пусто, просматривается входная строка и делается попытка свернуть w. Если w состоит только из терминалов, эта строка ищется во входном потоке.

Литература

• Aho A., Sethi R., Ullman J. Compilers: principles, techniques and tools. N.Y.: Addison-Wesley, 1986.
• Грис Д. Построения компиляторов для цифровых вычислительных машин. М.: Мир, 1975.
• Fraser C.W., Hanson D.R. A Retargetable compiler for ANSI C.// SIGPLAN Notices. 1991. V 26.
• Надежин Д.Ю., В.А.Серебряков, В.М.Ходукин. Промежуточный язык Лидер (предварительное сообщение)//Обработка символьной информации.М.: ВЦ АН СССР, 1987. С. 50-63.
• Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978.
• Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. М.: Мир, 1976.
• Лавров С.С., Гончарова Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971.
• Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации// ДАН СССР. 1962. Т. 146. N 2. С. 263-266.
• Курочкин В.М. Алгоритм распределения регистров для выражений за один обход дерева вывода//2 Всес. конф "Автоматизация производства ППП и трансляторов". 1983. С. 104-105.
• Emmelman H.,Schroer F.W.,Landweher R. BEG-a generator for efficient back-ends// ACM SIGPLAN. 1989. V.11. N 4.p.227-237
• Aho A.U.,Ganapathi M.,Tjiang S.W. Code generation using tree matching and dynamic programing// ACM Trans. Program. Languages and Systems.1989. V.11.N 4.
• A. Bezdushny, V. Serebriakov. The use of the parsing method for optimal code generation and common subexpression elimination//Techn. et Sci. Inform. 1993. V.12. N.1. P.69-92.
• Graham S.L., Harrison M.A., Ruzzo W.L. Am improved context-free recognizer// ACM Trans. Program. Languages and Systems. 1980. N.2.
• Harrison M.A. Introduction to formal language theory. Reading, Mass.: Addison-Wesley, 1978.