Что такое bison linux

Что такое bison linux

Bison is upward compatible with Yacc: all properly-written Yacc grammars ought to work with Bison with no change. Anyone familiar with Yacc should be able to use Bison with little trouble. You need to be fluent in C or C++ programming in order to use Bison. Java is also supported as an experimental feature.

Downloading Bison

Bison can be found on the main GNU ftp server: http://ftp.gnu.org/gnu/bison/ (via HTTP) and ftp://ftp.gnu.org/gnu/bison/ (via FTP). It can also be found on the GNU mirrors; please use a mirror if possible.

Documentation

Documentation for Bison is available online, as is documentation for most GNU software. You may also find more information about Bison by running info bison or man bison, or by looking at /usr/share/doc/bison/, /usr/local/doc/bison/, or similar directories on your system. A brief summary is available by running bison —help.

Mailing lists

Bison has the following mailing lists:

• bug-bison is used to discuss most aspects of Bison, including development and enhancement requests, as well as bug reports.
• help-bison is for general user help and discussion.
• bison-patches is for patches to the source code, to improve or fix bugs in Bison. We prefer patches against the latest Savannah sources.

Announcements about Bison and most other GNU software are made on info-gnu (archive).

Security reports that should not be made immediately public can be sent directly to the maintainer. If there is no response to an urgent issue, you can escalate to the general security mailing list for advice.

Getting involved

Development of Bison, and GNU in general, is a volunteer effort, and you can contribute. For information, please read How to help GNU. If you’d like to get involved, it’s a good idea to join the discussion mailing list (see above).

Test releases Trying the latest test release (when available) is always appreciated. Test releases of Bison can be found at http://alpha.gnu.org/gnu/bison/ (via HTTP) and ftp://alpha.gnu.org/gnu/bison/ (via FTP). Development For development sources, issue trackers, and other information, please see the Bison project page at savannah.gnu.org. Translating Bison To translate Bison’s messages into other languages, please see the Translation Project page for Bison. If you have a new translation of the message strings, or updates to the existing strings, please have the changes made in this repository. Only translations from this site will be incorporated into Bison. For more information, see the Translation Project. Maintainer Bison is currently being maintained by Akim Demaille and Paul Eggert. Please use the mailing lists for contact.

Licensing

Bison is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3 of the License, or (at your option) any later version.

“The Free Software Foundation (FSF) is a nonprofit with a worldwide mission to promote computer user freedom. We defend the rights of all software users.”

Please send general FSF & GNU inquiries to . There are also other ways to contact the FSF. Broken links and other corrections or suggestions can be sent to .

For information on coordinating and submitting translations of our web pages, see Translations README. —> Please see the Translations README for information on coordinating and submitting translations of this article.

Copyright © 2014 Free Software Foundation, Inc.

Источник

Что такое bison linux

The README-hacking.md file is about building, modifying and checking Bison. See its «Working from the Repository» section to build Bison from the git repo. Roughly, run:

then proceed with the usual configure && make steps.

Build from tarball

See the INSTALL file for generic compilation and installation instructions.

Running a non installed bison

Once you ran make , you might want to toy with this fresh bison before installing it. In that case, do not use src/bison : it would use the installed files (skeletons, etc.), not the local ones. Use tests/bison .

As an experimental feature, diagnostics are now colored, controlled by the —color and —style options.

To use them, install the libtextstyle library, 0.20.5 or newer, before configuring Bison. It is available from https://alpha.gnu.org/gnu/gettext/, for instance https://alpha.gnu.org/gnu/gettext/libtextstyle-0.20.5.tar.gz, or as part of Gettext 0.21 or newer, for instance https://ftp.gnu.org/gnu/gettext/gettext-0.21.tar.gz.

The option —color supports the following arguments:

• always, yes: Enable colors.
• never, no: Disable colors.
• auto, tty (default): Enable colors if the output device is a tty.

To customize the styles, create a CSS file, say bison-bw.css , similar to

then invoke bison with —style=bison-bw.css , or set the BISON_STYLE environment variable to bison-bw.css .

In some diagnostics, bison uses libtextstyle to emit special escapes to generate clickable hyperlinks. The environment variable NO_TERM_HYPERLINKS can be used to suppress them. This may be useful for terminal emulators which produce garbage output when they receive the escape sequence for a hyperlink. Currently (as of 2020), this affects some versions of emacs, guake, konsole, lxterminal, rxvt, yakuake.

If you pass —enable-relocatable to configure , Bison is relocatable.

A relocatable program can be moved or copied to a different location on the file system. It can also be used through mount points for network sharing. It is possible to make symlinks to the installed and moved programs, and invoke them through the symlink.

See «Enabling Relocatability» in the documentation.

Bison supports two catalogs: one for Bison itself (i.e., for the maintainer-side parser generation), and one for the generated parsers (i.e., for the user-side parser execution). The requirements between both differ: bison needs ngettext, the generated parsers do not. To simplify the build system, neither are installed if ngettext is not supported, even if generated parsers could have been localized. See https://lists.gnu.org/r/bug-bison/2009-08/msg00006.html for more details.

See the section FAQ in the documentation (doc/bison.info) for frequently asked questions. The documentation is also available in PDF and HTML, provided you have a recent version of Texinfo installed: run make pdf or make html .

If you have questions about using Bison and the documentation does not answer them, please send mail to help-bison@gnu.org.

Please send bug reports to bug-bison@gnu.org. Be sure to include the version number from bison —version , and a complete, self-contained test case in each bug report.

For any copyright year range specified as YYYY-ZZZZ in this package, note that the range specifies every single year in that closed interval.

Источник

Национальная библиотека им. Н. Э. Баумана
Bauman National Library

Персональные инструменты

GNU Bison

GNU Bison

Разработчики:	проект GNU
Предыдущий выпуск:	3.0.4 / 23 January 2015 года ; 6 years ago ( 2015-01-23 )
Написана на:	C
Операционная система:	UNIX-подобные
Тип ПО:	генератор синтаксических анализаторов
Лицензия:	GNU General Public License
Веб-сайт	www .gnu .org /software /bison /

GNU Bison — программа, предназначенная для автоматического создания синтаксических анализаторов по данному описанию грамматики, являющаяся частью проекта GNU.

В режиме POSIX, Bison совместим с yacc. Обычно используется в комплексе с лексическим анализатором flex. Flex используется для описания базовых токенов и создания программы (кода на C или C++), перерабатывающей поток символов в поток токенов. Bison используется для описания грамматики, построенной на базе алфавита токенов, и используется для генерации программы (кода на языке C, C++ или Java), которая получает на вход поток токенов и находит в этом потоке структурные элементы (нетерминальные токены) согласно заданной грамматике. Bison по умолчанию генерирует LALR парсеры, но и может создать GLR парсеры. [1]

Программа Bison была написана в 1988 году Робертом Корбеттом. Позже, в 1990 году, Роберт Корбетт написал еще один генератор синтактических анализаторов под названием Berkeley Yacc. Совместимость Bison и yacc обеспечил Ричард Столлман. Вильфред Хансен добавил поддержку многосимвольных литералов и другие возможности.

Содержание

Условия использования Bison

Начиная с версии 1.24 Bison были изменены условия распространения yyparse. Было разрешено использовать продукт работы Bison в несвободных программах. Ранее анализаторы, сгенерированные Bison, могли быть использованы только в программах, являющихся свободным программным обеспечением.

Другие инструменты GNU для программирования, такие как компилятор C GNU, никогда не содержали такого требования. Они всегда могли использоваться в несвободном программном обеспечении. Bison отличался от них не из-за какого-то особого политического решения, просто ко всему исходному коду Bison применялась обычная Универсальная Общественная Лицензия (GPL).

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

Однако ограничение использования Bison свободным программным обеспечением не слишком способствовало производству с его помощью других свободных программ. Тогда было принято решение сделать практические условия использования Bison теми же, что и для других инструментов GNU.

Принципы Bison

Рассмотрим основные понятия Bison для его дальнейшего детального описания.

Языки и контекстно-свободные грамматики

Для того, чтобы Bison мог разобрать программу на каком-то языке, этот язык должен быть описан контекстно-свободной грамматикой. Это означает, что вы определяете одну или более синтаксических групп и задаёте правила их сборки из составных частей. Например, в языке C одна из групп называется «выражение». Правило для составления выражения может выглядеть так: «Выражение может состоять из знака «минус» и другого выражения». Другое правило: «Выражением может быть целое число». Как вы может видеть, правила часто бывают рекурсивными, но должно быть по крайней мере одно правило, выводящее из рекурсии.

Наиболее распространённой формальной системой для представления таких правил в удобном для человека виде является форма Бэкуса-Наура (БНФ, Backus-Naur Form, BNF), которая была разработана для описания языка Algol 60. Любая грамматика, выраженная в форме Бэкуса-Наура является контекстно-свободной грамматикой. Bison принимает на вход, в сущности, особый вид БНФ, адаптированный для машинной обработки.

Bison может работать не со всеми контекстно-свободными грамматиками, а только с грамматиками класса LALR(1). Коротко, это означает, что должно быть возможно определить, как разобрать любую часть входа, заглядывая вперёд не более, чем на одну лексему. Строго говоря, это описание LR(1)-грамматики, класс LALR(1) имеет дополнительные ограничения, которые не так просто объяснить. Но в обычной практике редко встречаются LR(1)-грамматики, которые не являются LALR(1). Загадочные конфликты свёртка/свёртка, для получения большей информации.

В правилах формальной грамматики языка каждый вид синтаксических единиц или групп называется символом. Те из них, которые формируются группировкой меньших конструкций в соответствии с правилами грамматики, называются нетерминальными символами, а те, что не могут разбиты — терминальными символами или типами лексем. Мы называем часть входного текста, соответствующую одному терминальному символу лексемой, а соответствующую нетерминальному символу — группой.

Для примера терминальных и нетерминальных символов можно использовать язык C. Лексемами C являются идентификаторы, константы (числовые и строковые), и различные ключевые слова, знаки арифметических операций и пунктуации. Таким образом, терминальные символы грамматики C это: ‘идентификатор’, ‘число’, ‘строка’ и по одному символу на каждое ключевое слово, знак операции или пунктуации: ‘if’, ‘return’, ‘const’, ‘static’, ‘int’, ‘char’, ‘знак плюс’, ‘открывающая скобка’, ‘закрывающая скобка’, ‘запятая’ и многие другие (эти лексемы могут быть разбиты на литеры, но это уже вопрос составления словарей, а не грамматики).

Синтаксические группы C это: выражение, оператор, объявление и определение функции. Они представлены в грамматике C нетерминальными символами ‘выражение’, ‘оператор’, ‘объявление’ и ‘определение функции’. Полная грамматика, для того, чтобы выразить смысл этих четырёх, использует десятки дополнительных языковых конструкций, каждой из которых соответствует свой нетерминальный символ.

Каждому нетерминальному символу должны быть сопоставлены правила грамматики, показывающие, как он собирается из более простых конструкций. Например, одним из операторов C является оператор return, это может быть описано правилом грамматики, неформально читающимся так: ‘Оператор’ может состоять из ключевого слова ‘return’, ‘выражения’ и ‘точки с запятой’.

Должно существовать множество других правил для ‘оператор’, по одному на каждый вид оператора C.

Один нетерминальный символ должен быть отмечен как специальный, определяющий завершённое высказывание на языке. Он называется начальным символом. В компиляторе это означает полную программу на входе. В языке C эту роль играет нетерминальный символ `последовательность определений и объявлений’.

Например,’1 + 2′ является правильным выражением C — правильной частью программы на C — но не является правильной целой программой на C. В контекстно-свободной грамматике C это следует из того, что ‘выражение’ не является начальным символом.

Анализатор Bison читает на входе последовательность лексем и группирует их, используя правила грамматики. Если вход правилен, конечным результатом будет свёртка всей последовательности лексем в одну группу, которой соответствует начальный символ грамматики. Если мы используем грамматику C, весь входной текст в целом должен быть `последовательностью определений и объявлений’. Если это не так, анализатор сообщит о синтаксической ошибке.

От формальных правил к входному тексту Bison

Формальная грамматика — это математическая конструкция. Чтобы определить язык для Bison, вы должны написать файл, описывающий грамматику в синтаксисе Bison — файл грамматики Bison.

Нетерминальный символ формальной грамматики на входе Bison представляется идентификатором, таким же как идентификатор C. По соглашению их нужно записывать в нижнем регистре, например: expr, stmt или declaration.

Представление в Bison нетерминальных символов также называется типом лексем. Типы лексем также могут быть представлены идентификаторами в стиле C. По соглашению эти идентификаторы следует записывать в верхнем регистре, чтобы отличить их от нетерминалов, например, INTEGER, IDENTIFIER, IF, или RETURN. Терминальный символ, соответствующий конкретному ключевому слову языка следует называть так же, как это ключевое слово выглядит в верхнем регистре. Терминальный символ error зарезервирован для восстановления после ошибок.

Терминальный символ также может быть представлен как однолитерная константа, как однолитерная константа C. Вам стоит делать так всегда, когда лексема представляет собой просто одиночную литеру (скобку, знак плюс и т.д.) — используйте ту же литеру в качестве терминального символа для этой лексемы.

Третий способ представления терминального символа — представление строковой константой C из нескольких литер.

Правила грамматики также содержат выражение в синтаксисе Bison. Например, вот правило Bison для оператора C return. Точка с запятой в кавычках является однолитерной лексемой, представляющей часть синтаксиса оператора C, а отдельная точка с запятой и двоеточие являются знаками пунктуации Bison, используемыми во всех правилах.

Семантические значения

Формальная грамматика выбирает лексемы только по их виду, например, если в правиле упоминается терминальный символ ‘целочисленная константа’, это означает, что в этой позиции грамматически допустима любая целочисленная константа. Точное значение константы не имеет значения для разбора — если ‘x+4′ грамматически допустимо, то ‘x+1′ или ‘x+3989′ равно допустимы.

Но точное значение очень важно, чтобы после разбора определить, что означает входной текст. Компилятор, не могущий различить в программе константы 4, 1 и 3989, бесполезен. Поэтому каждая лексема в грамматике Bison характеризуется как типом лексемы, так и семантическим значением.

Тип лексемы — это терминальный символ, определённый в грамматике, такой как INTEGER, IDENTIFIER или ‘,’. Он даёт всю информацию, необходимую для принятия решения, где допустимо появления лексемы и как группировать её с другими лексемами. Правила грамматик не знают о лексемах ничего, кроме их типов.

Семантическое значение несёт всю остальную информацию о смысле лексемы, такую как значение целого или имя идентификатора (такие лексемы как ‘,’, просто знаки пунктуации, не нуждаются в каком-либо семантическом значении).

Например, входная лексема может классифицироваться как лексема типа INTEGER и иметь семантическое значение 4. Другая входная лексема может иметь тот же тип INTEGER, но значение 3989. Если правило грамматики говорит, что допустима лексема типа INTEGER, будет принята любая из этих двух лексем, потому что обе они имеют тип INTEGER. Когда анализатор принимает лексему, он отслеживает её семантическое значение.

Каждая группа, так же как и её нетерминальный символ, может иметь семантическое значение. Например, в калькуляторе выражение обычно имеет семантическое значение, представляющее собой число. В компиляторе языка программирования выражение обычно имеет семантическое значение в виде дерева, описывающего смысл выражения.

Семантические действия

Чтобы быть полезной, программа должна делать нечто большее, чем разбор входного текста — она должны также создавать некий выход, основанный на входе. В грамматике Bison правило грамматики может содержать действие, состоящее из операторов C. Каждый раз, когда анализатор распознаёт текст, соответствующий правилу, выполняется его действие.

Чаще всего целью действия является вычисление семантического значения всей конструкции по семантическим значениям её частей. Предположим, например, что у нас есть правило, гласящее, что выражение может быть суммой двух выражений. Когда анализатор распознаёт такую сумму, каждое из подвыражений имеет семантическое значение, описывающее, как оно построено. Действию этого правила следует создать значение подобного вида для только что распознанного большего выражения.

Например, вот правило, говорящее, что выражение может быть суммой двух подвыражений:

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

Положения

Многие приложения, такие как интерпретаторы или компиляторы, должны генерировать подробные и информативные сообщения об ошибках. Для обеспечения этого должно быть возможно отслеживать позицию в тексте или положение каждой синтаксической конструкции. Bison предоставляет механизм работы с такими положениями.

Каждая лексема имеет семантическое значение. Аналогично, каждой лексеме сопоставлено положение, но тип положений одинаков для всех лексем и групп. Более того, создаваемый анализатор снабжён структурой данных для информации о положениях, задаваемой по умолчанию.

Как и с семантическими значениями, в действиях можно получить доступ к положениям, используя специальный набор конструкций. В приведённом выше примере положение группы в целом — @$, в то время как положения подвыражений — @1 и @3.

Когда обнаруживается текст, соответствующий правилу, для вычисления семантического значения его левой части используется действие по умолчанию. Точно так же, для положений используется другое действие по умолчанию. Однако действия для положений в большинстве случаев достаточно, в том смысле, что обычно не нужно описывать формирование @$ для каждого правила. При вычислении нового положения для данной группы по умолчанию анализатор берёт начало первого символа и конец последнего.

Выходной текст Bison: файл анализатора

Когда вы запускаете Bison, вы подаёте ему на вход файл грамматики Bison. Выходным текстом является исходный текст на C, осуществляющий разбор языка, описываемого грамматикой. Этот файл называется анализатором Bison. Важно помнить, что утилита Bison и анализатор Bison — это две разные программы: утилита Bison — это программа, создающая на выходе анализатор Bison, который затем становится частью вашей программы.

Задачей анализатора Bison является сборка лексем в группы в соответствии с правилами грамматики, например, объединение идентификаторов и знаков операций в выражения. По мере выполнения этой задачи анализатор выполняет действия, сопоставленные используемым правилам грамматики.

Лексемы поступают из функции, называемой лексическим анализатором, которую вы должны каким-либо образом предоставить (например, написав её на C). Анализатор Bison вызывает лексический анализатор каждый раз, когда ему нужна новая лексема. Он не знает, что находится «внутри» лексемы (хотя её семантическое значение может отражать это). Обычно лексический анализатор получает лексемы анализом литер текста, но Bison не зависит от этого.

Файл анализатора Bison — это код на C, определяющий функции yyparse, реализующую грамматику. Эта функция не образует целую программу на C — вы должны предоставить некоторые дополнительные функции. Одна из них — лексический анализатор. Другая — функция, вызываемая анализатором для сообщения об ошибке. Кроме того, выполнение программы на C должно начинаться с функции main: вы должны создать её и вызывать из неё yyparse, иначе анализатор никогда не заработает.

Все имена переменных и функций в файле анализатора Bison, помимо определённых в написанных вами действиях и имён типов лексем, начинаются с ‘yy’или’YY’. Сюда входят интерфейсные функции, такие как функция лексического анализатора yylex, функция сообщения об ошибке yyerror и сама функция анализатора yyparse. Также это относится к многочисленным идентификаторам, используемым во внутренних целях. Поэтому вам следует избегать использования идентификаторов C, начинающихся с’yy’или ‘YY’в грамматике Bison, за исключением определённых в этом руководстве.

В некоторых случаях файл анализатора Bison включает системные заголовки, и тогда при написании вашего кода следует учитывать, что некоторые идентификаторы зарезервированы такими заголовками. На некоторых не-GNU системах включаются заголовки , и , поскольку это необходимо для объявления функций выделения памяти и связанных типов. Другие системные заголовки могут быть включены, если вы придадите ненулевое значение YYDEBUG.

Этапы использования Bison

Реальный процесс разработки языка с использованием Bison, от спецификации грамматики до работающего компилятора или интерпретатора, содержит следующие этапы:

• Формально описать грамматику в виде, распознаваемом Bison (см. раздел 4. Файлы грамматики Bison). Для каждого правила грамматики языка описать действия, которые должны выполняться при распознавании текста, соответствующего этому правилу. Действие описывается последовательностью операторов C.
• Написать лексический анализатор для обработки входного текста и передачи лексем анализатору. Лексический анализатор может быть написан вручную на C. Он также может быть создан с помощью Lex.
• Написать управляющую функцию, вызывающую анализатор, созданный Bison.
• Написать процедуру сообщения об ошибках.

Чтобы превратить этот исходный код в работающую программу, вы должны выполнить следующие шаги:

• Обработайте описание грамматики Bison чтобы получить анализатор.
• Скомпилируйте код, созданный Bison, так же, как любой другой файл с исходным кодом.
• Соберите объектные файлы чтобы получить конечный продукт.

Обзор схемы грамматики Bison

Входной файл утилиты Bison — это файл грамматики Bison. Общий вид файла грамматики Bison следующий:

‘%%’,’%<‘и`%>’— это знаки пунктуации, присутствующие в любом файле грамматики Bison для разделения его секций.

Объявления C могут определять типы и переменные, используемые в действиях. Вы также можете использовать команды препроцессора для определения используемых там макросов и #include для включения файлов заголовков, делающих всё вышеперечисленное.

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

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

Дополнительный код на C может содержать любой код на C, который вы хотите использовать. Часто здесь находится определение лексического анализатора yylex и подпрограммы, вызываемые действиями правил грамматики. В простых программах здесь может находится и вся остальная часть программы.

Создание реентерабельного парсера

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

Токены, необходимые Bison, создаются flex.

Поскольку токены обеспечиваются при помощи flex, мы должны предоставить средства для обмена данными между анализатором и лексером. Тип данных, используемый для связи, YYSTYPE, устанавливается с помощью объявления %union.

Так как в данном примере мы используем возвратные версии flex и yacc, мы вынуждены предоставить параметры для функции yylex при вызове из yyparse. Это делается с помощью объявлений %lex-param и %parse-param.

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

Простой Makefile для сборки проекта заключается в следующем.

Реентерабельность

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

По общему правилу, Bison генерирует нереентерабельные парсеры. Чтобы достичь реентерабельности необходимо использовать объявление %define api.pure .

Использование

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

Однако Bison имеет ряд особенностей, не присущих yacc, которые делают возможным «использование» некоторыми проектами только Bison.

Ниже приведен список проектов, использующие инструменты Bison:

Источник