GNU Bison , широко известный как Bison , представляет собой генератор синтаксического анализатора , являющийся частью проекта GNU . Bison считывает спецификацию синтаксиса Bison (описанную как «машиночитаемый BNF » [3] ), предупреждает о любых неоднозначностях синтаксического анализа и генерирует синтаксический анализатор, который считывает последовательности токенов и решает, соответствует ли последовательность синтаксису, указанному в грамматике.
Сгенерированные парсеры портативны: они не требуют каких-либо специальных компиляторов. Bison по умолчанию генерирует парсеры LALR(1) , но он также может генерировать канонические парсеры LR , IELR(1) и GLR . [4]
В режиме POSIX Bison совместим с Yacc , но также имеет несколько расширений по сравнению с этой более ранней программой, включая
Flex , автоматический лексический анализатор , часто используется с Bison для токенизации входных данных и предоставления Bison токенов. [5]
Первоначально Bison был написан Робертом Корбеттом в 1985 году. [1] Позже, в 1989 году, Роберт Корбетт выпустил еще один генератор синтаксического анализатора под названием Berkeley Yacc . Bison был сделан Yacc-совместимым Ричардом Столлманом . [6]
Bison является свободным программным обеспечением и доступен под лицензией GNU General Public License , за исключением (обсуждаемым ниже), позволяющим использовать сгенерированный код без применения требований авторского лева лицензии.
Одной из деликатных проблем с генераторами анализаторов LR является разрешение конфликтов (конфликты сдвига/сокращения и сокращения/сокращения). Во многих генераторах синтаксических анализаторов LR разрешение конфликтов требует анализа автомата синтаксического анализатора, что требует от пользователя определенных знаний.
Чтобы помочь пользователю более интуитивно понимать конфликты, Bison вместо этого может автоматически генерировать противоположные примеры. Для неоднозначных грамматик Bison часто даже может привести контрпримеры, показывающие, что грамматика неоднозначна.
Например, о грамматике, страдающей от пресловутой проблемы с висячим else , сообщает Bison.
doc/if-then-else.y: предупреждение : конфликт сдвига/сокращения токена «else» [- Wcounterexamples ] Пример: «if» выражение «then» «if» expr «then» stmt • «else» stmt Вывод сдвига if_stmt ↳ «if» выражение «then» stmt ↳ if_stmt ↳ «if» expr «then» stmt • «else» stmt Пример: «if» expr «then» « if» expr «then» stmt • «else» stmt Уменьшить вывод if_stmt ↳ "if" выражение "then" stmt "else" stmt ↳ if_stmt ↳ "if" выражение "then" stmt •
Повторный вход — это функция, которая была добавлена в Bison и не существует в Yacc.
Обычно Bison генерирует нереентерабельный парсер . Для достижения реентерабельности %define api.pureнеобходимо использовать декларацию. Более подробную информацию о реентерабельности Bison можно найти в руководстве Bison. [7]
Bison может генерировать код для C , C++ , D и Java . [8]
Для использования синтаксического анализатора, созданного Bison, с других языков можно использовать инструмент привязки языка, такой как SWIG .
Поскольку Bison генерирует исходный код, который, в свою очередь, добавляется к исходному коду других программных проектов, возникает несколько простых, но интересных вопросов об авторских правах.
Код, сгенерированный Bison, включает значительные объемы кода из самого проекта Bison. Пакет Bison распространяется на условиях GNU General Public License (GPL), но было добавлено исключение, согласно которому GPL не применяется к выходным данным. [9] [10]
В более ранних версиях Bison оговаривалось, что часть его результатов также лицензируется по лицензии GPL из-за включения в выходные данные функции yyparse() из исходного исходного кода.
Проекты бесплатного программного обеспечения, использующие Bison, могут иметь выбор: распространять ли исходный код, который их проект передает в Bison, или полученный код C, выводимый Bison. И того, и другого достаточно, чтобы получатель смог скомпилировать исходный код проекта. Однако распространение только входных данных несет в себе небольшое неудобство: у получателей должна быть установлена совместимая копия Bison, чтобы они могли генерировать необходимый код C при компиляции проекта. А распространение на выходе только кода C создает проблему, заключающуюся в том, что получателям очень сложно модифицировать синтаксический анализатор, поскольку этот код не был написан ни человеком , ни для людей - его цель - передать непосредственно в компилятор C.
Этих проблем можно избежать, распространяя как входные файлы, так и сгенерированный код. Большинство людей будут компилировать с использованием сгенерированного кода, ничем не отличающегося от любого другого программного пакета, но любой, кто хочет изменить компонент синтаксического анализатора, может сначала изменить входные файлы и повторно сгенерировать сгенерированные файлы перед компиляцией. Проекты, распространяющие оба варианта, обычно не имеют сгенерированных файлов в своих системах контроля версий . Файлы генерируются только при выпуске релиза.
Некоторые лицензии, такие как GPL , требуют, чтобы исходный код находился в « предпочтительной форме произведения для внесения в него изменений ». Таким образом, проекты под лицензией GPL, использующие Bison, должны распространять файлы, которые являются входными данными для Bison. Конечно, они также могут включать сгенерированные файлы.
Поскольку Bison был написан как замена Yacc и в значительной степени совместим, код из многих проектов, использующих Bison, также можно было бы передать в Yacc. Из-за этого сложно определить, «использует» ли проект исходный код, специфичный для Bison, или нет. Во многих случаях «использование» Bison можно тривиально заменить эквивалентным использованием Yacc или одной из его других производных.
Bison имеет функции, отсутствующие в Yacc, поэтому можно сказать, что некоторые проекты действительно «используют» Bison, поскольку Yacc будет недостаточно.
В следующем списке представлены проекты, которые, как известно, «используют» Bison в более широком смысле: они используют бесплатные инструменты разработки программного обеспечения и распространяют код, предназначенный для загрузки в Bison или пакет, совместимый с Bison.
В следующем примере показано, как использовать Bison и flex для написания простой программы-калькулятора (только сложение и умножение) и программы для создания абстрактного синтаксического дерева . Следующие два файла содержат определение и реализацию функций синтаксического дерева.
/* * Expression.h * Определение структуры, используемой для построения синтаксического дерева. */ #ifndef __EXPRESSION_H__ #define __EXPRESSION_H__/** * @brief Тип операции */ typedef enum tagEOperationType { eVALUE , eMULTIPLY , eADD } EOperationType ; /** * @brief Структура выражения */ typedef struct tagSExpression { EOperationType type ; /* /< тип операции */ целое значение ; /* /< допустимо только для типа eVALUE */ struct tagSExpression * left ; /* /< левая часть дерева */ struct tagSExpression * right ; /* /< правая часть дерева */ } SExpression ; /** * @brief Создает идентификатор * @param value Числовое значение * @return Выражение или NULL в случае отсутствия памяти */ SExpression * createNumber ( int value ); /** * @brief Создает операцию * @param type Тип операции * @param left Левый операнд * @param right Правый операнд * @return Выражение или NULL в случае отсутствия памяти */ SExpression * createOperation ( EOperationType тип , SExpression * влево , SExpression * вправо ); /** * @brief Удаляет выражение * @param b Выражение */ void deleteExpression ( SExpression * b ); #endif /* __EXPRESSION_H__ *//* * Expression.c * Реализация функций, используемых для построения синтаксического дерева. */#include "Expression.h" #include <stdlib.h> /** * @brief Выделяет пространство для выражения * @return Выражение или NULL, если недостаточно памяти */ static SExpression * allocateExpression () { SExpression * b = ( SExpression * ) malloc ( sizeof ( SExpression )); если ( b == NULL ) вернуть NULL ; б -> тип = eVALUE ; б -> значение = 0 ; б -> слева = NULL ; б -> вправо = NULL ; вернуть б ; } SExpression * createNumber ( int value ) { SExpression * b = allocateExpression (); если ( b == NULL ) вернуть NULL ; б -> тип = eVALUE ; б -> значение = значение ; вернуть б ; } SExpression * createOperation ( тип EOperationType , SExpression * left , SExpression * right ) { SExpression * b = allocateExpression (); если ( b == NULL ) вернуть NULL ; б -> тип = тип ; б -> влево = влево ; б -> вправо = вправо ; вернуть б ; } void deleteExpression ( SExpression * b ) { if ( b == NULL ) return ; deleteExpression ( b -> слева ); deleteExpression ( b -> вправо ); бесплатно ( б ); }Токены, необходимые парсеру Bison, будут сгенерированы с использованием flex.
% {/* * Файл Lexer.l * Чтобы сгенерировать лексический анализатор, запустите: «flex Lexer.l» */#include "Expression.h" #include "Parser.h" #include <stdio.h> % }% option outfile = заголовок "Lexer.c" - file = "Lexer.h" % option alert nodefault % option reentrant noyywrap никогда — интерактивный nounistd % option bison — мост %%[ \ р \ п \ т ] * { продолжить ; /* Пропускаем пробелы. */ } [ 0-9 ] + { sscanf ( yytext , "%d" и yylval - > value ); вернуть TOKEN_NUMBER ; } "*" { возврат TOKEN_STAR ; } "+" { вернуть TOKEN_PLUS ; } "(" { return TOKEN_LPAREN ; } ")" { return TOKEN_RPAREN ; } . { продолжать ; /* Игнорировать неожиданные символы. */ } %%int yyerror ( выражение SExpression ** , сканер yyscan_t , const char * msg ) { fprintf ( stderr , «Ошибка: %s \n » , msg ); вернуть 0 ; } Имена токенов обычно нейтральны: «TOKEN_PLUS» и «TOKEN_STAR», а не «TOKEN_ADD» и «TOKEN_MULTIPLY». Например, если бы мы поддерживали унарный «+» (как в «+1»), было бы неправильно называть этот «+» «TOKEN_ADD». В таком языке, как C, «int *ptr» обозначает определение указателя, а не произведения: было бы неправильно называть этот «*» «TOKEN_MULTIPLY».
Поскольку токены предоставляются flex, мы должны предоставить средства для связи между синтаксическим анализатором и лексером . [23] Тип данных, используемый для связи, YYSTYPE , устанавливается с помощью объявления Bison %union .
Поскольку в этом примере мы используем реентерабельную версию как flex, так и yacc, мы вынуждены предоставлять параметры для функции yylex при вызове из yyparse . [23] Это делается с помощью объявлений Bison %lex-param и %parse-param . [24]
% {/* * Файл Parser.y * Чтобы сгенерировать анализатор, запустите: «bison Parser.y» */#include "Expression.h" #include "Parser.h" #include "Lexer.h" // ссылка на реализацию, представленную в Lexer.l int yyerror ( SExpression ** выражение , yyscan_t Scanner , const char * msg ); % }% кода требуется { typedef void * yyscan_t ; } % вывод "Parser.c" % определяет "Parser.h" % определить API . чистый % lex - param { yyscan_t Scanner } % parse - Param { SExpression ** выражение } % parse - param { yyscan_t Scanner } % объединение { целое значение ; SExpression * выражение ; } % токена TOKEN_LPAREN "(" % токена TOKEN_RPAREN ")" % токена TOKEN_PLUS "+" % токена TOKEN_STAR "*" % токена < значение > TOKEN_NUMBER "число" % тип < выражение > выражение /* Приоритет (возрастающий) и ассоциативность: a+b+c — (a+b)+c: левая ассоциативность a+b*c — a+(b*c): приоритет «*» выше, чем у « +». */ % осталось "+" % осталось "*" %%ввод : выражение { * выражение = $1 ; } ; выражение : выражение [ L ] "+" выражение [ R ] { $$ = createOperation ( eADD , $L , $R ); } | выражение [ L ] "*" выражение [ R ] { $$ = createOperation ( eMULTIPLY , $L , $R ); } | "(" выражение [ E ] ")" { $$ = $E ; } | "число" { $$ = createNumber ( $1 ); } ; %%Код, необходимый для получения синтаксического дерева с использованием синтаксического анализатора, созданного Bison, и сканера, созданного flex, следующий.
/* * файл main.c */#include "Expression.h" #include "Parser.h" #include "Lexer.h" #include <stdio.h> int yyparse ( выражение SExpression ** , сканер yyscan_t ); SExpression * getAST ( const char * expr ) { SExpression * выражение ; yyscan_t сканер ; состояние YY_BUFFER_STATE ; if ( yylex_init ( & Scanner )) { /* не удалось инициализировать */ return NULL ; } состояние = yy_scan_string ( выражение , сканер ); if ( yyparse ( & выражение , сканер )) { /* анализ ошибок */ return NULL ; } yy_delete_buffer ( состояние , сканер ); yylex_destroy ( сканер ); вернуть выражение ; } int Assessment ( SExpression * e ) { переключатель ( e -> тип ) { case eVALUE : return e -> value ; case eMULTIPLY : вернуть оценку ( e -> left ) * оценить ( e -> right ); случай eADD : вернуть оценку ( e -> left ) + оценку ( e -> right ); default : /* здесь не должно быть */ return 0 ; } } int main ( void ) { char test [] = "4 + 2*10 + 3*( 5 + 1)" ; SExpression * e = getAST ( тест ); int result = оценить ( e ); printf ( "Результат '%s': %d \n " , test , result ); удалитьВыражение ( е ); вернуть 0 ; } Ниже приведен простой make-файл для сборки проекта.
# MakefileФАЙЛЫ = Lexer.c Parser.c Expression.c main.c CC = g++ CFLAGS = -g -ansi тест : $( ФАЙЛЫ ) $( CC ) $( CFLAGS ) $( ФАЙЛЫ ) -o тест Lexer.c : Лексер . l сгибать Lexer.l Parser.c : Парсер . и Лексер . c зубр Parser.y очистить : rm -f *.o *~ Lexer.c Lexer.h Parser.c Parser.h тест .svg/1280px-Free_and_open-source_software_logo_(2009).svg.png){kind=logo}