Из Википедии, бесплатной энциклопедии
  (Перенаправлено из GNU bison )
Перейти к навигации Перейти к поиску
GNU Bison
Heckert GNU white.svg
Автор (ы) оригиналаРоберт Корбетт
Разработчики)Проект GNU
Первый выпускИюнь 1985 г . ; 35 лет назад [1] ( 1985-06 )
Стабильный выпуск
3.7.6 / 9 марта 2021 г . ; 58 дней назад [2] ( 2021-03-09 )
Репозиторий
Отредактируйте это в Викиданных
Написано вC и m4
Операционная системаUnix-подобный
ТипГенератор парсеров
ЛицензияGPL
Веб-сайтwww .gnu .org / software / bison / Отредактируйте это в Викиданных

GNU Bison , широко известный как Bison, - это генератор парсеров, который является частью проекта GNU . Bison читает спецификацию контекстно-свободного языка , предупреждает о любых неоднозначностях синтаксического анализа и генерирует синтаксический анализатор (на C , C ++ или Java ), который считывает последовательности токенов и решает, соответствует ли последовательность синтаксису, указанному в грамматике. Сгенерированные парсеры переносимы: они не требуют каких-либо конкретных компиляторов. Bison по умолчанию генерирует парсеры LALR (1), но он также может генерировать канонические парсеры LR , IELR (1) и GLR .[3]

В режиме POSIX Bison совместим с Yacc , но также имеет несколько расширений по сравнению с этой более ранней программой, в том числе:

  • Генерация контрпримеров конфликтам
  • Отслеживание местоположения (например, файл, строка, столбец)
  • Богатые и интернационализированные синтаксические сообщения об ошибках в сгенерированных синтаксических анализаторах
  • Настраиваемая генерация синтаксических ошибок,
  • Реентерабельные парсеры
  • Push-парсеры с автозаполнением
  • Поддержка именованных ссылок
  • Несколько типов отчетов (графический, XML) по сгенерированному парсеру
  • Поддержка нескольких языков программирования

Flex , автоматический лексический анализатор , часто используется с Bison для токенизации входных данных и предоставления Bison токенов. [4]

Первоначально Bison был написан Робертом Корбеттом в 1985 году. [1] Позже, в 1989 году, Роберт Корбетт выпустил еще один генератор синтаксического анализатора, названный Berkeley Yacc . Bison был сделан Yacc-совместимым Ричардом Столлманом . [5]

Bison - бесплатное программное обеспечение и доступно под Стандартной общественной лицензией GNU , за исключением (обсуждается ниже), позволяющего использовать его сгенерированный код, не вызывая требований авторского лева лицензии.

Особенности [ править ]

Генерация контрпримера [ править ]

Одной из деликатных проблем с генераторами парсеров LR является разрешение конфликтов (конфликты сдвига / уменьшения и уменьшения / уменьшения). Разрешение конфликтов обычно требует анализа автомата парсера, как описано в отчетах, и некоторого опыта со стороны пользователя. Контрпримеры помогают быстро разобраться в некоторых конфликтах и ​​даже могут фактически доказать, что проблема в том, что грамматика на самом деле неоднозначна.

Например, о грамматике, страдающей от печально известной проблемы с зависанием else , сообщает Bison.

doc / if-then-else.y: предупреждение : конфликт сдвига / уменьшения на токене "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 "then" stmt  •

Повторный вход [ править ]

Повторный вход - это функция, которая была добавлена ​​в Bison и не существует в Yacc.

Обычно Bison генерирует синтаксический анализатор, который не является реентерабельным . Для достижения повторного входа %define api.pureнеобходимо использовать декларацию . Более подробную информацию о повторном вхождении Bison можно найти в руководстве Bison. [6]

Языки вывода [ править ]

Bison может генерировать код для C , C ++ и Java . [7] Также доступен экспериментальный бэкэнд для D. [8]

Для использования синтаксического анализатора, созданного Bison с других языков, можно использовать инструмент привязки к языку , такой как SWIG .

Лицензия и распространение сгенерированного кода [ править ]

Поскольку Bison генерирует исходный код, который, в свою очередь, добавляется к исходному коду других программных проектов, возникает ряд простых, но интересных вопросов об авторских правах.

Лицензия, совместимая с GPL, не требуется [ править ]

Код, сгенерированный Bison, включает значительное количество кода из самого проекта Bison. Пакет Bison распространяется в соответствии с условиями Стандартной общественной лицензии GNU (GPL), но было добавлено исключение, так что GPL не применяется к выходным данным. [9] [10]

В более ранних выпусках Bison оговаривалось, что часть его вывода также была лицензирована под GPL из-за включения в вывод функции yyparse () из исходного исходного кода.

Распространение пакетов с помощью Bison [ править ]

Проекты свободного программного обеспечения, использующие 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.

  • Оболочка Bash использует грамматику yacc для анализа ввода команды.
  • Собственный синтаксический анализатор грамматики Bison генерируется Bison. [11]
  • CMake использует несколько грамматик Bison. [12]
  • GCC начал использовать Bison, но перешел на рукописный синтаксический анализатор с рекурсивным спуском для C ++ в 2004 г. (версия 3.4), [13] и для C и Objective-C в 2006 г. (версия 4.1) [14]
  • Язык программирования Go (GC) использовал Bison, но в версии 1.5 перешел на рукописный сканер и парсер. [15]
  • LilyPond требует, чтобы Bison сгенерировал свой парсер. [16]
  • MySQL [17]
  • GNU Octave использует синтаксический анализатор, созданный Bison. [18]
  • Perl 5 использует синтаксический анализатор, созданный Bison, начиная с версии 5.10. [19]
  • Язык программирования PHP (Zend Parser).
  • PostgreSQL [20]
  • Ruby MRI , эталонная реализация языка программирования Ruby , основывается на грамматике Bison. [21]
  • syslog-ng использует несколько собранных вместе грамматик Bison. [22]

Пример полного реентерабельного парсера [ править ]

В следующем примере показано, как использовать 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 ;  / * / <допустимо, только если тип равен 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  тип ,  выражение SE  * слева ,  выражение SE  * справа );/ ** * @brief Удаляет выражение * @param b Выражение * / void  deleteExpression ( SExpression  * b );#endif / * __EXPRESSION_H__ * /
/ * * Expression.c * Реализация функций, используемых для построения синтаксического дерева. * /#include  "Expression.h"#include  <stdlib.h>/ ** * @brief Распределяет пространство для выражения * @return Выражения или NULL , если не хватает памяти * / статического  SExpression  * allocateExpression () {  SExpression  * Ь  =  ( SExpression  * ) таНос ( SizeOf ( SExpression )); если  ( b  ==  NULL )  вернуть  NULL ; b -> type  =  eVALUE ;  б -> значение  =  0 ; b -> left  =  NULL ;  b -> right  =  NULL ; return  b ; }SExpression  * createNumber ( INT  значение ) {  SExpression  * б  =  allocateExpression (); если  ( b  ==  NULL )  вернуть  NULL ; b -> type  =  eVALUE ;  б -> значение  =  значение ; return  b ; }SExpression  * createOperation ( EOperationType  тип ,  SExpression  * влево ,  SExpression  * правая ) {  SExpression  * б  =  allocateExpression (); если  ( b  ==  NULL )  вернуть  NULL ; б -> тип  =  тип ;  b -> left  =  left ;  б -> право  =  право ; 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  <stdio.h>% }% option  outfile = "Lexer.c"  header - file = "Lexer.h" % option  warn  nodefault% Вариант  возвратного  noyywrap  никогда - интерактивный  nounistd % вариант  зубр - мост%%[  \ r \ n \ t ] *  {  продолжить ;  / * Пропускаем пробелы. * /  } [ 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, мы должны предоставить средства для связи между анализатором и лексером . [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"int  yyerror ( SExpression  ** выражение ,  yyscan_t  scanner ,  const  char  * msg )  {  / * При необходимости добавить процедуру обработки ошибок * / }% }% code  требует  {  typedef  void *  yyscan_t ; }% output  "Parser.c" % определяет  "Parser.h"% определить  api . чистый % lex - param  {  yyscan_t  scanner  } % parse - param  {  SExpression  ** expression  } % parse - param  {  yyscan_t  scanner  }% union  {  int  value ;  SExpression  * выражение ; }% token  TOKEN_LPAREN  "(" % token  TOKEN_RPAREN  ")" % token  TOKEN_PLUS  "+" % token  TOKEN_STAR  "*" % token  < значение >  TOKEN_NUMBER  "число"% тип  < выражение >  выражение/ * Приоритет (возрастание) и ассоциативность:  a + b + c is (a + b) + c: левая ассоциативность  a + b * c is a + (b * c): приоритет "*" выше, чем у " + ". * / % left  "+" % left  "*"%%ввод  :  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"#include  <stdio.h>int  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 :  вернуть  оценку ( e -> слева )  +  оценить (д -> право );  по умолчанию :  / * здесь не должно быть * /  return  0 ;  } }int  main ( void ) {  char  test []  =  "4 + 2 * 10 + 3 * (5 + 1)" ;  SE expression  * e  =  getAST ( тест );  int  результат  =  оценка ( е );  printf ( "Результат '% s'% d \ n " ,  тест ,  результат );  deleteExpression ( е );  возврат  0 ; }

Вот простой make-файл для сборки проекта.

# MakefileФАЙЛЫ  = Lexer.c Parser.c Expression.c main.c CC  = g ++ CFLAGS  = -g -ansitest :  $ ( FILES ) $ ( CC )  $ ( CFLAGS )  $ ( FILES ) -o testLexer.c :  Лексер . лflex Lexer.lParser.c :  Parser . y  Lexer . cbison Parser.yclean :	rm -f * .o * ~ Lexer.c Lexer.h Parser.c Тест Parser.h

См. Также [ править ]

  • Berkeley Yacc (byacc) - еще одна бесплатная замена Yacc, имеющая того же автора, что и GNU Bison

Ссылки [ править ]

  1. ^ a b Корбетт, Роберт Пол (июнь 1985 г.). Статическая семантика и исправление ошибок компилятора (Ph.D.). Калифорнийский университет в Беркли . DTIC ADA611756 .
  2. ^ "[Bison-Announce] Выпущен Bison 3.7.6" .
  3. ^ Руководство Bison: Введение.
  4. ↑ Левин, Джон (август 2009 г.). флекс и зубр . O'Reilly Media. ISBN 978-0-596-15597-1.
  5. ^ «АВТОРЫ» . bison.git. GNU Savannah . Проверено 26 августа 2017 .
  6. ^ Руководство Bison: Чистый (реентерабельный) синтаксический анализатор
  7. ^ Руководство Bison: Резюме декларации Bison
  8. ^ https://savannah.gnu.org/forum/forum.php?forum_id=9639 Выпущен Bison 3.5
  9. ^ Руководство Bison: Условия использования Bison
  10. ^ Файл исходного кода parse-gram.c, который включает исключение
  11. ^ "parse-gram.y" . bison.git. GNU Savannah . Проверено 29 июля 2020 .
  12. ^ «LexerParser в CMake» . github.com .
  13. ^ GCC 3.4 Release Series Изменения, новые функции и исправления
  14. ^ Изменения, новые функции и исправления выпусков GCC 4.1
  15. ^ Определение грамматики Голанга
  16. ^ https://git.savannah.gnu.org/cgit/lilypond.git/tree/lily/parser.yy
  17. ^ https://www.safaribooksonline.com/library/view/flex-bison/9780596805418/ch04.html
  18. ^ http://octave.org/doxygen/4.0/d5/d60/oct-parse_8cc_source.html
  19. ^ "Что нового в Perl 5.10.0?" . perl.org.
  20. ^ «Стадия парсера» . postgresql.org.
  21. ^ "Ruby MRI Parser" . github.com .
  22. ^ "Синтаксический анализатор XML syslog-ng" . github.com .
  23. ^ a b Руководство по Flex: Сканеры C с анализаторами Bison, архивировано 17 декабря 2010 г. на Wayback Machine
  24. ^ Руководство Bison: Соглашения о вызовах для чистых парсеров

Дальнейшее чтение [ править ]

  • Левин, Джон (август 2009 г.). флекс и зубр . O'Reilly Media. ISBN 978-0-596-15597-1.

Внешние ссылки [ править ]

  • Веб-сайт в проекте GNU
    • Руководство по эксплуатации
  • Проект Bison в GNU Savannah
  • Запись в Каталог бесплатного программного обеспечения
  • Внутреннее устройство синтаксических анализаторов C, созданных GNU Bison
  • Как загрузить и установить Bison (GNU Parser Generator) в Linux
  • Бинарные файлы Win32 от GnuWin32 (версия 2.4.1)