• Source: GNU Bison

GNU Bison, commonly known as Bison, is a parser generator that is part of the GNU Project. Bison reads a specification in Bison syntax (described as "machine-readable BNF"), warns about any parsing ambiguities, and generates a parser that reads sequences of tokens and decides whether the sequence conforms to the syntax specified by the grammar.
The generated parsers are portable: they do not require any specific compilers. Bison by default generates LALR(1) parsers but it can also generate canonical LR, IELR(1) and GLR parsers.
In POSIX mode, Bison is compatible with Yacc, but also has several extensions over this earlier program, including

Generation of counterexamples for conflicts
Location tracking (e.g., file, line, column)
Rich and internationalizable syntax error messages in the generated parsers
Customizable syntax error generation,
Reentrant parsers
Push parsers, with autocompletion
Support for named references
Several types of reports (graphical, XML) on the generated parser
Support for several programming languages (C, C++, D, or Java)
Flex, an automatic lexical analyser, is often used with Bison, to tokenise input data and provide Bison with tokens.
Bison was originally written by Robert Corbett in 1985. Later, in 1989, Robert Corbett released another parser generator named Berkeley Yacc. Bison was made Yacc-compatible by Richard Stallman.
Bison is free software and is available under the GNU General Public License, with an exception (discussed below) allowing its generated code to be used without triggering the copyleft requirements of the licence.




Features






= Counterexample generation

=
One delicate issue with LR parser generators is the resolution of conflicts (shift/reduce and reduce/reduce conflicts). With many LR parser generators, resolving conflicts requires the analysis of the parser automaton, which demands some expertise from the user.
To aid the user in understanding conflicts more intuitively, Bison can instead automatically generate counterexamples. For ambiguous grammars, Bison often can even produce counterexamples that show the grammar is ambiguous.
For instance, on a grammar suffering from the infamous dangling else problem, Bison reports

doc/if-then-else.y: warning: shift/reduce conflict on token "else" [-Wcounterexamples]
Example: "if" expr "then" "if" expr "then" stmt • "else" stmt
Shift derivation
if_stmt
↳ "if" expr "then" stmt
↳ if_stmt
↳ "if" expr "then" stmt • "else" stmt
Example: "if" expr "then" "if" expr "then" stmt • "else" stmt
Reduce derivation
if_stmt
↳ "if" expr "then" stmt "else" stmt
↳ if_stmt
↳ "if" expr "then" stmt •




= Reentrancy

=
Reentrancy is a feature which has been added to Bison and does not exist in Yacc.
Normally, Bison generates a parser which is not reentrant. In order to achieve reentrancy the declaration %define api.pure must be used. More details on Bison reentrancy can be found in the Bison manual.




= Output languages

=
Bison can generate code for C, C++, D and Java.
For using the Bison-generated parser from other languages a language binding tool such as SWIG can be used.




License and distribution of generated code


Because Bison generates source code that in turn gets added to the source code of other software projects, it raises some simple but interesting copyright questions.




= A GPL-compatible license is not required

=
The code generated by Bison includes significant amounts of code from the Bison project itself. The Bison package is distributed under the terms of the GNU General Public License (GPL) but an exception has been added so that the GPL does not apply to output.
Earlier releases of Bison stipulated that parts of its output were also licensed under the GPL, due to the inclusion of the yyparse() function from the original source code in the output.




= Distribution of packages using Bison

=
Free software projects that use Bison may have a choice of whether to distribute the source code which their project feeds into Bison, or the resulting C code made output by Bison. Both are sufficient for a recipient to be able to compile the project source code. However, distributing only the input carries the minor inconvenience that the recipients must have a compatible copy of Bison installed so that they can generate the necessary C code when compiling the project. And distributing only the C code in output, creates the problem of making it very difficult for the recipients to modify the parser since this code was written neither by a human nor for humans - its purpose is to be fed directly into a C compiler.
These problems can be avoided by distributing both the input files and the generated code. Most people will compile using the generated code, no different from any other software package, but anyone who wants to modify the parser component can modify the input files first and re-generate the generated files before compiling. Projects distributing both usually do not have the generated files in their version control systems. The files are only generated when making a release.
Some licenses, such as the GPL, require that the source code be in "the preferred form of the work for making modifications to it". GPL'd projects using Bison must thus distribute the files which are the input for Bison. Of course, they can also include the generated files.




Use


Because Bison was written as a replacement for Yacc, and is largely compatible, the code from a lot of projects using Bison could equally be fed into Yacc. This makes it difficult to determine if a project "uses" Bison-specific source code or not. In many cases, the "use" of Bison could be trivially replaced by the equivalent use of Yacc or one of its other derivatives.
Bison has features not found in Yacc, so some projects can be truly said to "use" Bison, since Yacc would not suffice.
The following list is of projects which are known to "use" Bison in the looser sense, that they use free software development tools and distribute code which is intended to be fed into Bison or a Bison-compatible package.

Bash shell uses a yacc grammar for parsing the command input.
Bison's own grammar parser is generated by Bison.
CMake uses several Bison grammars.
GCC started out using Bison, but switched to a hand-written recursive-descent parser for C++ in 2004 (version 3.4), and for C and Objective-C in 2006 (version 4.1)
The Go programming language (GC) used Bison, but switched to a hand-written scanner and parser in version 1.5.
LilyPond requires Bison to generate its parser.
MySQL
GNU Octave uses a Bison-generated parser.
Perl 5 uses a Bison-generated parser starting in 5.10.
The PHP programming language (Zend Parser).
PostgreSQL
Ruby MRI, the reference implementation of the Ruby programming language, relies on a Bison grammar.
syslog-ng uses several Bison grammars assembled together.




A complete reentrant parser example



The following example shows how to use Bison and flex to write a simple calculator program (only addition and multiplication) and a program for creating an abstract syntax tree. The next two files provide definition and implementation of the syntax tree functions.

The tokens needed by the Bison parser will be generated using flex.

The names of the tokens are typically neutral: "TOKEN_PLUS" and "TOKEN_STAR", not "TOKEN_ADD" and "TOKEN_MULTIPLY". For instance if we were to support the unary "+" (as in "+1"), it would be wrong to name this "+" "TOKEN_ADD". In a language such as C, "int *ptr" denotes the definition of a pointer, not a product: it would be wrong to name this "*" "TOKEN_MULTIPLY".
Since the tokens are provided by flex we must provide the means to communicate between the parser and the lexer. The data type used for communication, YYSTYPE, is set using Bison %union declaration.
Since in this sample we use the reentrant version of both flex and yacc we are forced to provide parameters for the yylex function, when called from yyparse. This is done through Bison %lex-param and %parse-param declarations.

The code needed to obtain the syntax tree using the parser generated by Bison and the scanner generated by flex is the following.

A simple makefile to build the project is the following.




See also



Berkeley Yacc (byacc) – another free software Yacc replacement sharing the same author as GNU Bison
ANTLR ANother Tool for Language Recognition, another open-source parser generator




References






Further reading


Levine, John (August 2009). flex & bison. O'Reilly Media. ISBN 978-0-596-15597-1.




External links


Website in the GNU Project
Manual
Bison project at GNU Savannah
Entry in the Free Software Directory
Internals of C parsers generated by GNU Bison
How to download and install Bison (GNU Parser Generator) on Linux
Win32 binaries by GnuWin32 (version 2.4.1)

Kata Kunci Pencarian:

• Bison (disambiguasi)
• Daftar istilah komputer
• Nyumbu
• Nyumbu biru
• Daftar binatang dan tumbuhan di Zoo Tycoon Complete Collection
• Nyumbu hitam
• Daftar spesies Scarabaeidae
• GNU Bison
• Flex (lexical analyser generator)
• GNU toolchain
• GNU General Public License
• List of GNU packages
• LALR parser
• GNU Compiler Collection
• Yacc
• Bison (disambiguation)
• Canonical LR parser