|
|
|
|
|
|
|
|
Компилятор компиляторов Bison – первое знакомство |
|
|
|
«Теория
без применения – мертва»! Поэтому изучаемый теоретический курс по теории и
реализации языков программирования предпочтительно дополнить хотя бы кратким
знакомством с наиболее известными имеющимися программными инструментами по
автоматизации конструирования компиляторов. Один из них – Bison. На ВМК МГУ, кстати, где на изучение
подобного нашему курса отводится три семестра, проводятся и лабораторные
работы, где рассматривается применение Bison, Yacc, Lex и Super. Слишком
много времени и сил на младших курсах университета тратить на это знакомство,
конечно, тоже излишне, но если совсем не знакомится – готовность при
необходимости применить изученную теорию в разумные сроки будет слабой. 1.
Что такое Bison и зачем он нужен 2.
Кто его поддерживает и под какой ОС он пасётся 3.
Где находится исходное описание работы с Bison и где – его русский перевод 4.
Общая схема получения пользовательского компилятора с помощью Bison 4.1.
Записать КС-грамматику в понятном для Bison виде 4.2.
Запустить Bison для записанной грамматики: 4.4.
Совместная компиляция подготовленных программ обычным компилятором Си 4.5.
Запуск полученного компилятора 5.
Законченные примеры применения Bison для некоторых простых грамматик 5.1.
Пример для грамматики {а^n | n >= 0}. 5.2.
Пример для грамматики {0^n1^n | n > 0}. (Примеры
цепочек: 01, 0011, 000111, …, 0^n1^n). 5.2.1.
Входной набор данных Bison для данного языка |
|
|
|
|
1. Что такое Bison и зачем он нужен
Bison – это GNU-выпуск известной программы YACC, предназначенной
для порождения компиляторов по описанной пользователем КС-грамматике. Одним
из следствий расширения возможностей и доступности использования
вычислительной техники стало производство прикладных программных систем со всё более разнообразным и сложным поведением. При этом
краеугольный принцип кибернетики -
принцип необходимого и достаточного разнообразия, сформулированный Н.Виннером и Р.Эшби ещё до С какого-то уровня
разнообразия (сложности) управления такой системой оказывается проще и
надёжнее предложить пользователю строго определённый формальный язык, с
помощью которого пользователь сообщает системе задание на выполнение тех или
иных её основных задач, в т.ч. определяет состав и периодичность выдачи
учётных и уведомительных сообщений о ходе этого выполнения и т.п. К примеру, для управления воздушным движением, в т.ч. в
Российской Федерации, соответствующими международными организациями
разработан и используется формальный язык из нескольких десятков предложений,
однозначно сообщающих в автоматизированном и ручном режимах о каждом
достаточно значимом событии в использовании самолёта и его характеристиках:
взлёте, изменении курса, прохождении контрольной точки полёта, посадке,
возникновении различных иных вероятных обстоятельств, которые можно и нужно
предвидеть. Обычным является дополнение и
уточнение время от времени этого списка команд и/или их параметров по решению
соответствующих комитетов. Эти изменения необходимо быстро и надёжно вносить
в соответствующие системы управления. Для
проверки правильности и разбора предложений подобных формальных языков, как
известно, используют программу, именуемую компилятор. Если
мы такой компилятор научимся получать автоматически на основе описывающей
этот язык грамматики, то сможем все изменения (например, дополнения) к
пользовательскому языку, вносить очень быстро и при этом, что очень важно,
вполне надёжно. Важность
и всё большая распространённость этой задачи была осознана
в программировании довольно быстро и поэтому появился ряд
разнообразных программных инструментов для автоматизированной разработки
компиляторов для языков, определяемых контекстно-свободными грамматиками.
Так, само название известного более двух десятилетий
компилятора компиляторов YACC переводится как
«ещё один компилятор компиляторов» (Yet
another compiler compiler). В качестве
пробы сил и оттачивания мастерства производство подобных систем продолжается
и сейчас, особенно в технических университетах (см.,
например, http://www.forth.org.ru). Свой компилятор компиляторов под названием «СУПЕР» был
создан более 15 лет назад и в ВЦ АН СССР (ныне ВЦ РАН, www.ccas.ru
) под рук. лаур.
гос. премии, зав. сект. ВЦ РАН,
доц. МФТИ, к.ф.м.н. Владимира Михайловича
Курочкина, ныне покойного. Последний более 30 лет назад основал на ФУПМе и курс «Теория и реализация языков
программирования». Однако большинство этих систем (включая YACC) было разработано в коммерческом варианте, либо не обладало достаточной универсальностью, надёжностью и эффективностью. Поэтому важным событием в мире свободного (в смысле лицензии GNU) программного обеспечения стала разработка GNU-аналога компилятора YACC, получившего название BISON. Теперь этим компилятором компиляторов можно пользоваться для разработки программных комплексов с самыми высокими требованиями к качеству лицензирования применяемых инструментальных средств. 2. Кто его поддерживает и под какой ОС он пасётся
Домашней
страницей Bison является http://www.gnu.org/software/bison/ Bison доступен для установки во всех
распространённых разновидностях ОС Linux. Возможно, он
уже установлен на вашей системе. Просто наберите bison без параметров и посмотрите на её отклик… 3. Где находится исходное описание
работы с Bison и где – его русский
перевод
http://www.gnu.org/software/bison/manual/ - исходное описание руководства по Bison на английском языке (талантом писать
кратко и доступно автор наделён весьма скромно). http://www.opennet.ru/docs/RUS/bison_yacc/ -
перевод этого руководства на русский язык. 4. Общая схема получения
пользовательского компилятора с помощью Bison
4.1. Записать КС-грамматику в понятном
для Bison виде
Тип н/д должен быть “.y” (наследие YACC и способ прямой
(но не обратной, т.е Bison шире YACC) совместимости с
YACC). Например, foo.y или task.y. Тип
принимаемых будущим компилятором лексем (основных знаков) определяется макро YYSTYPE, например: #define
YYSTYPE char или #define
YYSTYPE double При
этом основные знаки алфавита пользовательской грамматики обозначаются словами
из больших (латинских) букв и должны явно определяться после ключевого слова
%token, например: %token ONE, TWO // Определяются два
осн. знака ONE
и TWO. Вспомогательные
знаки сразу можно использовать в правилах, их принято обозначать словами из
малых латинских букв. Например, для грамматики a^n: exp: exp A
// S -> Sa
(вид обозначений в пояснениях - уже из курса ТРЯП) exp: A // S -> a
;
// или, что тоже самое:
exp: exp A
| A
; Начальным
знаком (аксиомой) грамматики по умолчанию считается первый употреблённый
вспомогательный знак в первом приведённом правиле грамматики. В данном случае
как аксиома будет распознана “exp”. В
фигурных скобках после каждого правила грамматики можно указать связанные с
ним действия в стиле оператора Си. Наличие таких связок (правило + действие)
говорит о том, что это не просто КС-грамматика, а атрибутная грамматика (см.
гл. 5 по курсу ТРЯП). В данном примере подсчитывается степень правильно
введённой цепочки из n знаков ‘a’ (распознаваемых в лексическом анализаторе yylex (), который
пишется (обеспечивается) пользователем). Заодно с помощью printf () показывается
порядок применения правил. exp : exp A { $$ = $1 +1; printf ("\t I'm in middle rule\n ");}
| A { $$ = 1; printf
("\t I'm in last rule\n\n");} ; Из особых обозначений (кроме обычных для самого языка Си)
здесь используются именователи смысловых значений
правила, а именно $$ - означает имя переменной, содержащую смысловое значение
левой части правила (здесь, число прочитанных знаков ‘a’), а $1, $2, …, $n – соответственно имена переменных для смысловых значений 1-го, 2-го и
т.д. члена из правой части правила. 4.2. Запустить Bison для
записанной грамматики:
bison foo.y При
отсутствии ошибок вы должны получить н/д с именем foo.tab.c, содержащий текст разборщика предложений yyparse (). 4.3. Подготовить в ручную или с
использованием других инструментальных средств (например, LEX) лексический распознаватель yylex (), обработчик
ошибок yyerror () и главную программу main ()
Программа main () вызывает
порождённый Bison’ом разборщик
предложений yyparse (). Последняя
программа, в свою очередь, обращается по мере необходимости за очередной лексемой
к yylex (), а при
обнаружении ошибки разбора - к yyerror (). Обратите внимание, что в грамматике для
синтаксического разборщика *yyparse ()” необходимо
предусмотреть обработку (порождение) знаков конца строки и конца всего н/д, иначе никакая введённая
цепочка не будет признана правильной, поскольку содержит хотя бы один из
этих знаков. Примеры
программирования указанных функций для соответствующих языков приведены ниже
в пунктах 4.2 и 4.3. 4.4. Совместная компиляция
подготовленных программ обычным компилятором Си
Вы можете, к примеру, добавить тексты программ yylex (), yyerror () и main () в конец н/д с текстом программы yyparse в н/д foo.tab.c, либо создать короткую программку
с простейшими включениями их текстов, например,
#include "simple_CF.tab.c" #include
"lex.c" #include “error_handler.c” #include “main.c” И откомпилировать их обычным компилятором Си. Под Linux эта команда выглядит так (если все
программы для компиляции уже собраны в н/д simple_CF.tab.c, а исполнимую программу мы хотим назвать simple_CF): cc -o simple_CF simple_CF.tab.c 4.5. Запуск полученного компилятора
Производится
как обычно. Для примера выше, это: ./simple_CF Знаки
“./ “ здесь, как обычно,
указывают, что поиск выполнимого н/д производится в текущей папке. 5. Законченные примеры применения
Bison для некоторых простых грамматик
5.1. Пример для грамматики {а^n | n >= 0}.
(Примеры цепочек:
а, аа, ааа, …, а^n). 5.1.1. Входной набор данных Bison, указывающий грамматику, по которой должен быть построен
текст искомого разборщика предложений (синтаксического анализатора)
/* Simplest Context free grammar (a^n) */ %{ #define YYSTYPE char // Тип входного знака int yylex (void); void yyerror
(char const *); %} // Main symbols of grammar
(synonyms: terminals, tokens, etc.) %token A %% /*Правила грамматики и связанные с ними действия */ %% /* Grammar rules and
actions follow. */ input: /* empty */ { printf
("\n\tThis program expecting string as a^n\n");} | input line ; line: '\n' | exp '\n' {printf ("Result power of char \"a\" is n =
%i\n", $$);} ; exp: A { $$ = 1; printf
("\tI'm in last rule\n\n");} | exp A { $$ = $1 +
1; printf
("\tI'm in middle rule\n");} ; %% /* The lexical analyzer
returns a int code on the stack and the
token A, or the numeric code of
the character read if not a number. It
skips all blanks and
tabs, and returns 0 for end-of-input. */ 5.1.2. Набор данных с текстами
распознавателя слов yylex() - lexical analyzer, простого
обработчика ошибок yyerror () и главной программы-испытателя main ()
//-------------------- yylex () --------------------------- #include <ctype.h> #include <stdio.h> int yylex
(void) { int
c; /* Skip white space. */ while ((c = getchar ()) == ' ' || c ==
'\t') ; /* Process symbols. */ if (c == 'a') return A; else /* Return
end-of-input. */ if (c == EOF) return 0; /* Return a single
char. */ return c; } //----------------- yyerror ()
----------------------------- /* Called by yyparse on error.
*/ void yyerror
(char const *s) { fprintf (stderr,
"*** %s *** \n", s); fprintf (stderr, "This string is not a (a^n)\n", s); } //------------------ main () -------------------------------- int main (void) { return yyparse (); } 5.2. Пример для грамматики {0^n1^n | n > 0}.
(Примеры цепочек: 01,
0011, 000111, …, 0^n1^n).
5.2.1. Входной набор данных Bison для данного языка
/* Simplest Context free grammar
(0^n1^n) */ %{ #define YYSTYPE char // Type of input int yylex (void); void yyerror
(char const *); %} // Main symbols of grammar
(synonyms: terminals, tokens, etc.) %token ONE %token TWO %% /* Grammar rules and
actions follow. */ input: /* empty */ { printf
("\n\tThis program expecting string as
0^n1^n\n");} | input line ; line: '\n' { printf
("empty line was introduced\n");} | exp '\n'
{ printf ("\t n = %i\n", $1); } ; exp: ONE exp TWO { $$ = $2 + 1;} | ONE TWO { $$ = 1; } ; %% /* The lexical analyzer
returns the tokens ONE or TWO, or the numeric code of
the character read if not a number. It
skips all blanks and tabs, and returns 0 for end-of-input. */ 5.2.2. Набор данных с текстами
распознавателя слов yylex() - lexical analyzer, простого
обработчика ошибок yyerror () и главной программы-испытателя main ()
//-------------------- yylex ()
--------------------------- #include <ctype.h> #include <stdio.h> int yylex
(void) { int
c; /* Skip white space */ while ((c = getchar ()) == ' ' || c ==
'\t') ; /* Process symbols */ if (c == '0') { n1++; return ONE; } else if (c == '1') { n2++; return TWO; } else /* Return end-of-input. */ if (c == EOF) return 0; /* Return a single
char. */ return c; } //----------------- yyerror ()
----------------------------- /* Called by yyparse on error.
*/ void yyerror
(char const *s) { fprintf
(stderr, "stderror:
%s\n", s); } //------------------ main () -------------------------------- int main (void) { return yyparse (); } |
|
|
|
|
|
|
|
