Войти
 | |
| Автор (ы) | Роберт Корбетт |
|---|---|
| Разработчик (и) | Проект GNU |
| Первоначальный выпуск | июнь 1985 г.; 35 лет назад (1985-06) |
| Стабильный выпуск | 3.7.2 / 5 сентября 2020 г.; 45 дней назад (05.09.2020) |
| Репозиторий |  |
| Написано на | C и m4 |
| Операционная система | Unix-подобная |
| Тип | Генератор парсера |
| Лицензия | GPL |
| Веб-сайт | https: //savannah.gnu. org / projects / bison / www.gnu.org / software / bison /, https: / / savannah.gnu.org / projects / bison / |
GNU Bison, широко известный как Bison, представляет собой генератор парсеров , который является частью проекта GNU. Bison читает спецификацию контекстно-свободного языка, предупреждает о любых неоднозначностях парсинга и генерирует синтаксический анализатор (либо в C, C ++, либо в Java ), который считывает последовательности токенов и решает, соответствует ли последовательность синтаксису, заданному грамматикой. Сгенерированные парсеры переносимы: они не требуют каких-либо конкретных компиляторов. Bison по умолчанию генерирует парсеры LALR (1), но он также может генерировать канонические LR, IELR (1) и GLR парсеры.
В Режим POSIX, Bison совместим с Yacc, но также имеет несколько расширений по сравнению с этой предыдущей программой, в том числе:
Flex, автоматический лексический анализатор, часто используется с Bison для токенизации входных данных и предоставления Bison токенов.
Изначально Bison был написан Робертом Корбеттом в 1985 году. Позже, в 1989 году, Роберт Корбетт выпустил еще одну книгу. Генератор rser с именем Berkeley Yacc. Bison был сделан Yacc-совместимым Ричардом Столлманом.
Bison является бесплатным программным обеспечением и доступен под Стандартной общественной лицензией GNU, за исключением (обсуждается ниже), разрешающего его сгенерированный код, который будет использоваться без активации требований лицензии copyleft.
.
Одной из деликатных проблем с генераторами парсеров LR является разрешение конфликтов (конфликты сдвига / уменьшения и уменьшения / уменьшения). Разрешение конфликтов обычно требует анализа автомата парсера, как описано в отчетах, и некоторого опыта со стороны пользователя. Контрпримеры помогают быстро понять некоторые конфликты и даже могут фактически доказать, что проблема в том, что грамматика на самом деле неоднозначна.
Например, для грамматики, страдающей от печально известной проблемы dangling else, Bison сообщает
doc / if-then-else.y: warning: shift / reduce конфликт при token "else" [-Wcounterexamples] Пример: "if" expr "then" "if" expr "then" stmt • "else" stmt Получение сдвига if_stmt ↳ "if" expr "then" stmt ↳ if_stmt ↳ "if" expr " then "stmt •" else "stmt Пример:" if "expr" then "" if "expr" then "stmt •" else "stmt Уменьшить вывод if_stmt ↳" if "expr" then "stmt" else "stmt ↳ if_stmt ↳" if "expr", то "stmt" •
Повторная входимость - это функция, добавленная в Bison и не существующая в Yacc.
Обычно Bison генерирует синтаксический анализатор, который не повторно входим. Чтобы добиться повторного входа, необходимо использовать объявление % define api.pure. Более подробную информацию о повторном вхождении Bison можно найти в руководстве Bison.
Bison может генерировать код для C, C ++ и Java. Также доступен экспериментальный бэкэнд для D.
Для использования синтаксического анализатора Bison с других языков можно использовать инструмент привязки языка, такой как SWIG. использоваться.
Поскольку Bison генерирует исходный код, который, в свою очередь, добавляется к исходному коду других программных проектов, возникает ряд простых, но интересных вопросов об авторских правах.
Код, созданный Bison, включает значительное количество кода из самого проекта Bison. Пакет Bison распространяется в соответствии с условиями Стандартной общественной лицензии GNU (GPL), но было добавлено исключение, чтобы GPL не применялась к выходным данным.
Предусмотрены более ранние версии 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; / * / < type of operation */ int value; /* /< valid only when type is eVALUE */ struct tagSExpression *left; /* /< left side of the tree */ struct tagSExpression *right; /* /< right side of the tree */ } SExpression; /** * @brief It creates an identifier * @param value The number value * @return The expression or NULL in case of no memory */ SExpression *createNumber(int value); /** * @brief It creates an operation * @param type The operation type * @param left The left operand * @param right The right operand * @return The expression or NULL in case of no memory */ SExpression *createOperation(EOperationType type, SExpression *left, SExpression *right); /** * @brief Deletes a expression * @param b The expression */ void deleteExpression(SExpression *b); #endif /* __EXPRESSION_H__ *// * * Expression.c * Реализация функций, используемых для построения синтаксического дерева. * / #include "Expression.h" #include/ ** * @brief Выделяет место для выражения * @return Выражение или NULL, если недостаточно памяти * / static SExpression * allocateExpression () {SExpression * b = (SExpression *) malloc (sizeof (SExpression)); если (b == NULL) вернуть NULL; b->type = eVALUE; b->значение = 0; b->left = NULL; b->right = NULL; return b; } SExpression * createNumber (целое значение) {SExpression * b = allocateExpression (); если (b == NULL) вернуть NULL; b->type = eVALUE; б->значение = значение; return b; } SExpression * createOperation (тип EOperationType, SExpression * слева, SExpression * справа) {SExpression * b = allocateExpression (); если (b == NULL) вернуть NULL; б->тип = тип; b->left = left; b->right = right; return b; } void deleteExpression (SExpression * b) {если (b == NULL) return; deleteExpression (b->слева); deleteExpression (b->право); бесплатно (б); }
Токены, необходимые синтаксическому анализатору Bison, будут сгенерированы с использованием flex.
% {/ * * Файл Lexer.l * Чтобы сгенерировать лексический анализатор, выполните: "flex Lexer.l" * / #include "Expression.h" #include "Parser.h" #include %}% option outfile = "Lexer.c" header-file = "Lexer.h"% option warn nodefault% option reentrant noyywrap never-interactive nounistd% option bison-bridge %% [\ r \ n \ t] * {continue; / * Пропускаем пробелы. * /} [0-9] + {sscanf (yytext, "% d", yylval->значение); вернуть TOKEN_NUMBER; } "*" {return TOKEN_STAR; } "+" {return TOKEN_PLUS; } "(" {return TOKEN_LPAREN;} ")" {return TOKEN_RPAREN; }. { Продолжать; / * Игнорировать неожиданные символы. * /} %% int yyerror (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, мы должны предоставить средства для связи между анализатором и лексером. Тип данных, используемый для связи, YYSTYPE, устанавливается с помощью объявления Bison% union.
Так как в этом примере мы используем реентерабельную версию как flex, так и yacc, мы вынуждены предоставлять параметры для функции yylex при вызове из yyparse. Это делается с помощью объявлений Bison% lex-param и% parse-param.
% {/ * * Файл Parser.y * Чтобы сгенерировать парсер, выполните: "bison Parser.y" * / #include "Expression.h" #include "Parser.h" #include "Lexer.h" int yyerror (SExpression ** выражение, yyscan_t scanner, const char * msg) {/ * Добавить процедуру обработки ошибок по мере необходимости * /}%}% code requires {typedef void * yyscan_t; }% output "Parser.c"% определяет "Parser.h"% define api.pure% lex-param {yyscan_t scanner}% parse-param {SExpression ** expression}% parse-param {yyscan_t scanner}% union {int ценность; SExpression * выражение; }% token TOKEN_LPAREN "("% token TOKEN_RPAREN ")"% token TOKEN_PLUS "+"% token TOKEN_STAR "*"% token TOKEN_NUMBER "number"% type expr / * Приоритет (возрастающий) и ассоциативность: a + b + c равно (a + b) + c: левая ассоциативность a + b * c является a + (b * c): приоритет «*» выше, чем приоритет «+». * /% left "+"% left "*" %% input: expr {* выражение = $ 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" #includeint yyparse (выражение SExpression **, сканер yyscan_t); SExpression * getAST (const char * expr) {SExpression * выражение; yyscan_t сканер; Состояние YY_BUFFER_STATE; if (yylex_init (scanner)) {/ * не удалось инициализировать * / вернуть NULL; } состояние = yy_scan_string (выражение, сканер); if (yyparse (expression, scanner)) {/ * анализ ошибки * / return NULL; } yy_delete_buffer (состояние, сканер); yylex_destroy (сканер); возвращаемое выражение; } int оценить (SExpression * e) {переключатель (e->type) {case eVALUE: return e->value; case eMULTIPLY: вернуть оценку (е->влево) * оценить (е->вправо); case eADD: вернуть оценку (е->влево) + оценку (е->вправо); по умолчанию: / * здесь не должно быть * / return 0; }} int main (void) {char test = "4 + 2 * 10 + 3 * (5 + 1)"; SEExpression * e = getAST (тест); int результат = оценка (е); printf ("Результат '% s'% d \ n", тест, результат); deleteExpression (е); возврат 0; }
Вот простой make-файл для сборки проекта.
# Makefile FILES = Lexer.c Parser.c Expression.c main.c CC = g ++ CFLAGS = -g -ansi test: $ (FILES) $ (CC) $ (CFLAGS) $ (FILES) -o test Lexer.c: Lexer.l flex Lexer.l Parser.c: Parser.y Lexer.c bison Parser.y clean: rm -f *.o * ~ Lexer.c Lexer.h Parser.c Parser.h test
.
Портал свободного программного обеспечения с открытым исходным кодом 