Автоматно-лингвистические и алгоритмические основы разработки и программной реализации трансляторов, компиляторов и интерпретаторов

2004 г.

Глава 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.
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.
Arvind Gostelow K.P. A new interpreter for data flow schemas and its implications for computer architecture, TR 72, Dept. Inform. and Comput. Sci. Univ. Calif., Irvine: 1975, Nov.
Backus J. Can Programming Be Liberated from von Neuman Style? A Functional Style and Its Algebra of Pro-grams. //CACM.: 1978, vol.21, N8. p. 613-641.
Bezdushny, V. Serebriakov. The use of the parsing method for optimal code generation and common subexpres-sion elimination//Techn. et Sci. Inform. 1993. V.12. N.1. P.69-92.
Dennis J.B., Ken K.S. Weng Application of data flow computation for the weather problem, high speed com-puter and algorithm organization. // Acad. Press. 1977. p. 143-157.
Emmelman H.,Schroer F.W.,Landweher R. BEG-a generator for efficient back-ends// ACM SIGPLAN. 1989. V.11. N 4.p.227-237
Fraser C.W., Hanson D.R. A Retargetable compiler for ANSI C.// SIGPLAN Notices. 1991. V 26.
Gelly O. LAU system software: A high level data driven language for parallel programming. - In: Proc. of the 1976 Intern. Conf on Parallel Processing, p.255-262.
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.
J.Backus. Can Programming Be Liberated from von Neumann Style? A Functional Style and Its Algebra of Pro-grams. - CACM, 1978, v. 21, n.8, 613-641.
Kuzmin D.A., Kazakov F.A., Legalov A.I. Description of parallel-functional programming language // Ad-vances in Modeling & Analysis. AMSE Press. Vol. 28, №3. 1995. PP.1-17.
А.Ахо, Д.Ульман Теория синтаксического анализа, перевода и компиляции. т.1,2 - М.:Мир, 1978.
Абрамов С.А. Начала программирования на языке Паскаль. - М.: Наука, 1987.- 112 с.
Адельсон-Вельский Г.М., Ландис Е.М. Один алгоритм организации информации// ДАН СССР. 1962. Т. 146. N 2. С. 263-266.
Алгоритмы, математическое обеспечение и архитектура многопроцессорных вычислительных систем. / под ред. А.П. Ершова. М.: Наука, 1982.
Ахо А., Ульман Д. Теория синтаксического анализа, перевода и компиляции. М.: Мир, 1978.
Б.В. Мартемьянов, В.В. Андреева. Технология проектирования программного обеспечения.- Самара: РИО Самар. гос. техн. ун-та, 1999, - 32с
Б.В. Мартемьянов. Арифметические основы ЭВМ.- Самара: РИО Самар. гос. техн. ун-та, 1999, - 64с
Базисный рефал и его реализация на вычислительных машинах (методические рекомендации). - ЦНИПИАСС, Госстрой СССР, 1977.
Баррон Д. Введение в языки программирования. М.: Мир, 1980.- 190 с.
Бринч-Хансен. Методы проектирования операционных систем.
В.Л.Темов. Метаалгоритмическая система общего назначения МАСОН.
В.М.Пентковский. Язык программирования Эль-76.
Вальковский В.А. Распараллеливание алгоритмов и программ. Структурный подход. // М., Радио и связь 1989
Грис Д. Построения компиляторов для цифровых вычислительных машин. М.: Мир, 1975.
Д.Грис. Наука программирования.-М.: Мир, 1984.
Денис Дж.Б., Фоссин Дж.Б., Линдерман Дж.П. Схемы потоков данных // В кн. Теория программирова-ния. Ч 2. Новосибирск: ВЦ СО АН CCCР, 1972 г. с 7-43.
Дж.Хьюз, Дж.Мичтом. Структурный подход к программироованию. - М.: Мир, 1980.
Казаков Ф.А., Кузьмин Д.А., Легалов А.И. Параллельный язык управления потоков данных // Математи-ческое обеспечение и архитектура ЭВМ: Сб. научных работ. Вып. 2. КГТУ. Красноярск, 1997. С. 105-113.
Кнут Д. Искусство программирования для ЭВМ. В 3-х т.: Пер. с англ. / Под ред. К.И. Бабенко и В.С. Штаркмана. - М.: Мир, 1976.- 735 с.
Кнут Д. Искусство программирования для ЭВМ. Т. 1. Основные алгоритмы. М.: Мир, 1976.
Курочкин В.М. Алгоритм распределения регистров для выражений за один обход дерева вывода//2 Всес. Конф "Автоматизация производства ППП и трансляторов". 1983. С. 104-105.
Лавров С.С., Гончарова Л.И. Автоматическая обработка данных. Хранение информации в памяти ЭВМ. М.: Наука, 1971.
Легалов А.И. Управление в вычислительных системах и языках программирования. // Материалы кон-ференции "Проблемы информатизации города". Красноярск, 1994. С.198-202.
Легалов А.И., Казаков Ф.А., Кузьмин Д.А. Водяхо А.И. Модель параллельных вычислений функцио-нального языка // Известия ГЭТУ. Вып. 500. Структуры и математическое обеспечение специализиро-ванных средств. С.-Петербург, 1996. С. 56-63.
Легалов А.И., Казаков Ф.А., Кузьмин Д.А. Потоковая модель параллельных вычислений // Вестник Красноярского государственного технического университета. Вып. 6. Красноярск, 1996. С. 60-67.
Мартемьянов А.Б. Трансляция алгебраических выражений. Самара, СамГТУ, 2000, 30 с.
Н. Вирт. Алгоритмы + структуры данных = программы. - М.: Мир, 1985.
Н.Вирт. Модула-2. (Пер. с английского Л.А.Захарова.- В кн.: Языки программирования.- М.:Наука,1985. (Алгоритмы и алгоритмические языки).
Надежин Д.Ю., В.А.Серебряков, В.М.Ходукин. Промежуточный язык Лидер (предварительное сообще-ние)//Обработка символьной информации.М.: ВЦ АН СССР, 1987. С. 50-63.
Орлов С.П., Мартемьянов Б.В., Мартемьянов А.Б. Арифметические и логические основы схемотехни-ки. Учебное пособие. Самара, СамГТУ, 2002.- 347 с.
П.Вегнер. Программирование на языке Ада.
Пайл Я. "Ада - язык встроенных систем" (М., Ф. и С., 1984), главы 9 и 10.
Перминов О.Н. Программирование на языке Паскаль. М.: Радио и связь., 1988.- 224 с.
Прайс Д. Программирование на языке Паскаль. Практическое руководство: Пер. с англ. / Под ред. О.Н. Перминова. - М.: Мир, 1987.- 232 с.
Р.Хантер. Проектирование и конструирование компиляторов.- М.:Финансы и статистика,1984.
С.С.Лавров. Основные понятия и конструкции языков программирования. - М.: Финансы и статистика, 1982.
С.Янг. Алгоритмические языки реального времени. Конструирование и разработка. - М.: Мир, 1985.
Сергиевский М.В., Шалашов А.В., Турбо Паскаль 7.0. М.: Машиностроение, 1994. - 253 с.
Т. Пратт. Языки программирования. Разработка и реализация.
Ф. Брукс. Как проектируются и создаются программные комплексы.
Фаронов В.В. Основы Турбо Паскаля 6.0. - М.: МВТУ-ФЕСТО ДИДАКТИК, 1992. - 286 с.
Хендерсон П. Функциональное программирование. Применение и реализация: Пер. с англ. - М.: Мир, 1983. - 349 с.
Хоар Ч. Взаимодействующие последовательные процессы. М.: Мир, 1989.
Э.З.Любимский, В.В.Мартынюк, Н.П.Трифонов. Программирование. - М.:Наука, 1979.