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 , за исключением (о котором говорится ниже), позволяющим использовать сгенерированный им код без нарушения требований лицензии copyleft .
Одной из деликатных проблем генераторов парсеров LR является разрешение конфликтов (конфликты сдвиг/свертка и свертка/свертка). Во многих генераторах парсеров LR разрешение конфликтов требует анализа автомата парсера, что требует от пользователя определенных знаний.
Чтобы помочь пользователю более интуитивно понимать конфликты, Bison может вместо этого автоматически генерировать контрпримеры. Для неоднозначных грамматик Bison часто может даже генерировать контрпримеры, которые показывают, что грамматика неоднозначна.
Например, в грамматике, страдающей от печально известной проблемы с висячими else , сообщает Bison
doc/if-then-else.y: предупреждение : конфликт сдвига/свертки на токене "else" [- Wcounterexamples ] Пример: "if" expr "then" "if" expr "then" stmt • "else" stmt Сдвиг производной if_stmt ↳ "если" expr "тогда" stmt ↳ if_stmt ↳ "если" expr "тогда" stmt • "иначе" stmt Пример: "если" expr "тогда" "если" expr "тогда" stmt • "иначе" stmt Уменьшить вывод if_stmt ↳ "если" выражение "тогда" stmt "иначе" stmt ↳ if_stmt ↳ "если" выражение "тогда" 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 ; /* /< тип операции */ int value ; /* /< действительно только когда тип 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 type , SExpression * left , SExpression * right ); /** * @brief Удаляет выражение * @param b Выражение */ void deleteExpression ( SExpression * b ); #endif /* __EXPRESSION_H__ *//* * Expression.c * Реализация функций, используемых для построения синтаксического дерева. */#include "Выражение.h" #include <stdlib.h> /** * @brief Выделяет место для выражения * @return Выражение или NULL, если недостаточно памяти */ static SExpression * allocateExpression () { SExpression * b = ( SExpression * ) malloc ( sizeof ( SExpression )); если ( b == NULL ) вернуть NULL ; b -> тип = eVALUE ; b -> значение = 0 ; b -> слева = NULL ; b -> справа = NULL ; вернуть б ; } SExpression * createNumber ( int value ) { SExpression * b = allocateExpression (); если ( b == NULL ) вернуть NULL ; b -> тип = eVALUE ; b -> значение = значение ; вернуть б ; } SExpression * createOperation ( тип EOperationType , SExpression * left , SExpression * right ) { SExpression * b = allocateExpression (); если ( b == NULL ) вернуть NULL ; b -> тип = тип ; b -> левый = левый ; b -> правый = правый ; вернуть б ; } void deleteExpression ( SExpression * b ) { if ( b == NULL ) return ; deleteExpression ( b -> left ); deleteExpression ( b -> right ); бесплатно ( б ); }Токены, необходимые парсеру Bison, будут сгенерированы с помощью flex.
% {/* * Файл Lexer.l * Для генерации лексического анализатора выполните: "flex Lexer.l" */#include "Выражение.h" #include "Парсер.h" #include <stdio.h> % }% option outfile = "Lexer.c" заголовок - file = "Lexer.h" % option warn nodefault % опция реентерабельный noyywrap никогда - интерактивный nounistd % опция bison - мост %%[ \ r \ n \ t ] * { continue ; /* Пропустить пробелы. */ } [ 0-9 ] + { sscanf ( yytext , "%d" , & yylval -> value ); return TOKEN_NUMBER ; } "*" { return TOKEN_STAR ; } "+" { return TOKEN_PLUS ; } "(" { return TOKEN_LPAREN ; } ")" { return TOKEN_RPAREN ; } . { continue ; /* Игнорировать неожиданные символы. */ } %%int yyerror ( SExpression ** выражение , yyscan_t сканер , const char * сообщение ) { fprintf ( stderr , "Ошибка: %s \n " , сообщение ); return 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 "Выражение.h" #include "Парсер.h" #include "Лексер.h" // ссылка на реализацию, представленную в Lexer.l int yyerror ( SExpression ** expression , yyscan_t scanner , const char * msg ); % }% код требует { typedef void * yyscan_t ; } % вывод "Parser.c" % определяет "Parser.h" % define api.pure % lex - param { сканер yyscan_t } % parse - param { SExpression ** выражение } % parse - param { сканер yyscan_t } % union { int value ; SExpression * expression ; } % токен TOKEN_LPAREN "(" % токен TOKEN_RPAREN ")" % токен TOKEN_PLUS "+" % токен TOKEN_STAR "*" % токен < значение > TOKEN_NUMBER "число" % тип < выражение > выражение /* Приоритет (возрастающий) и ассоциативность: a+b+c это (a+b)+c: левая ассоциативность a+b*c это a+(b*c): приоритет "*" выше, чем у "+". */ % left "+" % left "*" %%ввод : expr { * выражение = $1 ; } ; expr : expr [ L ] "+" expr [ R ] { $$ = createOperation ( eADD , $L , $R ); } | expr [ L ] "*" expr [ R ] { $$ = createOperation ( eMULTIPLY , $L , $R ); } | "(" expr [ E ] ")" { $$ = $E ; } | "число" { $$ = createNumber ( $1 ); } ; %%Код, необходимый для получения синтаксического дерева с использованием парсера, сгенерированного Bison, и сканера, сгенерированного flex, выглядит следующим образом.
/* * файл main.c */#include "Выражение.h" #include "Парсер.h" #include "Лексер.h" #include <stdio.h> int yyparse ( SExpression ** выражение , yyscan_t сканер ); SExpression * getAST ( const char * expr ) { SExpression * expression ; yyscan_t сканер ; YY_BUFFER_STATE состояние ; if ( yylex_init ( & scanner )) { /* не удалось инициализировать */ return NULL ; } состояние = yy_scan_string ( выражение , сканер ); если ( yyparse ( & expression , scanner )) { /* ошибка разбора */ return NULL ; } yy_delete_buffer ( состояние , сканер ); yylex_destroy ( сканер ); возвращаемое выражение ; } int estimate ( SExpression * e ) { switch ( e -> type ) { case eVALUE : return e -> value ; case eMULTIPLY : return estimate ( e - > left ) * estimate ( e -> right ); case eADD : return estimate ( e -> left ) + estimate ( e -> right ); default : /* здесь быть не должно */ return 0 ; } } int main ( void ) { char test [] = " 4 + 2*10 + 3*( 5 + 1 )" ; SExpression * e = getAST ( test ); int result = evaluation ( e ); printf ( "Результат '%s' равен %d \n " , test , result ); deleteExpression ( e ); return 0 ; } Ниже приведен простой make-файл для сборки проекта.
# MakefileФАЙЛЫ = Lexer.c Parser.c Expression.c main.c CC = g++ CFLAGS = -g -ansi тест : $( ФАЙЛЫ ) $( CC ) $( CFLAGS ) $( ФАЙЛЫ ) -o тест Lexer.c : Lexer . l flex Lexer.l Parser.c : Парсер . y Лексер . c bison 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}