Компилятор компиляторов Bison – первое знакомство
«Теория без применения – мертва»! Поэтому изучаемый теоретический курс по теории и реализации языков программирования предпочтительно дополнить хотя бы кратким знакомством с наиболее известными имеющимися программными инструментами по автоматизации конструирования компиляторов. Один из них – Bison. На ВМК МГУ, кстати, где на изучение подобного нашему курса отводится три семестра, проводятся и лабораторные работы, где рассматривается применение Bison, Yacc, Lex и Super. Слишком много времени и сил на младших курсах университета тратить на это знакомство, конечно, тоже излишне, но если совсем не знакомится – готовность при необходимости применить изученную теорию в разумные сроки будет слабой. 1. Что такое Bison и зачем он нужен. 2 2. Кто его поддерживает и под какой ОС он пасётся. 2 3. Где находится исходное описание работы с Bison и где – его русский перевод. 2 4. Общая схема получения пользовательского компилятора с помощью Bison. 2 4.1. Записать КС-грамматику в понятном для Bison виде. 2 4.2. Запустить Bison для записанной грамматики: 2 4.3. Подготовить в ручную или с использованием других инструментальных средств (например, LEX) лексический распознаватель yylex (), обработчик ошибок yyerror () и главную программу main () 2 4.4. Совместная компиляция подготовленных программ обычным компилятором Си. 3 4.5. Запуск полученного компилятора. 3 5. Законченные примеры применения Bison для некоторых простых грамматик 3 5.1. Пример для грамматики {а^n | n >= 0}. 3 5.1.1. Входной набор данных Bison, указывающий грамматику, по которой должен быть построен текст искомого разборщика предложений (синтаксического анализатора) 3 5.1.2. Набор данных с текстами распознавателя слов yylex() - lexical analyzer, простого обработчика ошибок yyerror () и главной программы-испытателя main () 3 5.2. Пример для грамматики {0^n1^n | n > 0}. 3 (Примеры цепочек: 01, 0011, 000111, …, 0^n1^n). 3 5.2.1. Входной набор данных Bison для данного языка. 3 5.2.2. Набор данных с текстами распознавателя слов yylex() - lexical analyzer, простого обработчика ошибок yyerror () и главной программы-испытателя main () 4
1. Что такое Bison и зачем он нужен Bison – это GNU-выпуск известной программы YACC, предназначенной для порождения компиляторов по описанной пользователем КС-грамматике. Одним из следствий расширения возможностей и доступности использования вычислительной техники стало производство прикладных программных систем со всё более разнообразным и сложным поведением. При этом краеугольный принцип кибернетики - принцип необходимого и достаточного разнообразия, сформулированный Н.Виннером и Р.Эшби ещё до 1960 г., гласит, что степень разнообразия управления подобной сущностью должна соответствовать степени разнообразия её поведения. С какого-то уровня разнообразия (сложности) управления такой системой оказывается проще и надёжнее предложить пользователю строго определённый формальный язык, с помощью которого пользователь сообщает системе задание на выполнение тех или иных её основных задач, в т.ч. определяет состав и периодичность выдачи учётных и уведомительных сообщений о ходе этого выполнения и т.п. К примеру, для управления воздушным движением, в т.ч. в Российской Федерации, соответствующими международными организациями разработан и используется формальный язык из нескольких десятков предложений, однозначно сообщающих в автоматизированном и ручном режимах о каждом достаточно значимом событии в использовании самолёта и его характеристиках: взлёте, изменении курса, прохождении контрольной точки полёта, посадке, возникновении различных иных вероятных обстоятельств, которые можно и нужно предвидеть. Обычным является дополнение и уточнение время от времени этого списка команд и/или их параметров по решению соответствующих комитетов. Эти изменения необходимо быстро и надёжно вносить в соответствующие системы управления. Для проверки правильности и разбора предложений подобных формальных языков, как известно, используют программу, именуемую компилятор. Если мы такой компилятор научимся получать автоматически на основе описывающей этот язык грамматики, то сможем все изменения (например, дополнения) к пользовательскому языку, вносить очень быстро и при этом, что очень важно, вполне надёжно. Важность и всё большая распространённость этой задачи была осознана в программировании довольно быстро и поэтому появился ряд разнообразных программных инструментов для автоматизированной разработки компиляторов для языков, определяемых контекстно-свободными грамматиками. Так, само название известного более двух десятилетий компилятора компиляторов 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.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 (); }
Наверх