Bison

This manual (2 November 2008) is for GNU Bison (version 2.4), the GNU parser generator.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation; with no Invariant Sections, with the Front-Cover texts being “A GNU Manual,” and with the Back-Cover Texts as in (a) below. A copy of the license is included in the section entitled “GNU Free Documentation License.”

(a) The FSF's Back-Cover Text is: “You have the freedom to copy and modify this GNU manual. Buying copies from the FSF supports it in developing GNU and promoting software freedom.”

Tutorial sections:
Introduction
Conditions for Using Bison
GNU GENERAL PUBLIC LICENSE		The GNU General Public License says how you can copy and share Bison
1. The Concepts of Bison		Basic concepts for understanding Bison.
2. Examples		Three simple explained examples of using Bison.
Reference sections:
3. Bison Grammar Files		Writing Bison declarations and rules.
4. Parser C-Language Interface		C-language interface to the parser function `yyparse`.
5. The Bison Parser Algorithm		How the Bison parser works at run-time.
6. Error Recovery		Writing rules for error recovery.
7. Handling Context Dependencies		What to do if your language syntax is too messy for Bison to handle straightforwardly.
8. Debugging Your Parser		Understanding or debugging Bison parsers.
9. Invoking Bison		How to run Bison (to produce the parser source file).
10. Parsers Written In Other Languages		Creating C++ and Java parsers.
11. Frequently Asked Questions
A. Bison Symbols		All the keywords of the Bison language are explained.
B. Glossary		Basic concepts are explained.
C. Copying This Manual		License for copying this manual.
Index		Cross-references to the text.
--- The Detailed Node Listing --- The Concepts of Bison
1.1 Languages and Context-Free Grammars		Languages and context-free grammars, as mathematical ideas.
1.2 From Formal Rules to Bison Input		How we represent grammars for Bison's sake.
1.3 Semantic Values		Each token or syntactic grouping can have a semantic value (the value of an integer, the name of an identifier, etc.).
1.4 Semantic Actions		Each rule can have an action containing C code.
1.5 Writing GLR Parsers		Writing parsers for general context-free languages.
1.6 Locations		Tracking Locations.
1.7 Bison Output: the Parser File		What are Bison's input and output, how is the output used?
1.8 Stages in Using Bison		Stages in writing and running Bison grammars.
1.9 The Overall Layout of a Bison Grammar		Overall structure of a Bison grammar file.
Writing GLR Parsers
1.5.1 Using GLR on Unambiguous Grammars		Using GLR parsers on unambiguous grammars.
1.5.2 Using GLR to Resolve Ambiguities		Using GLR parsers to resolve ambiguities.
1.5.3 GLR Semantic Actions		Deferred semantic actions have special concerns.
1.5.4 Considerations when Compiling GLR Parsers		GLR parsers require a modern C compiler.
Examples
2.1 Reverse Polish Notation Calculator		Reverse polish notation calculator; a first example with no operator precedence.
2.2 Infix Notation Calculator: `calc`		Infix (algebraic) notation calculator. Operator precedence is introduced.
2.3 Simple Error Recovery		Continuing after syntax errors.
2.4 Location Tracking Calculator: `ltcalc`		Demonstrating the use of @`n` and @$.
2.5 Multi-Function Calculator: `mfcalc`		Calculator with memory and trig functions. It uses multiple data-types for semantic values.
2.6 Exercises		Ideas for improving the multi-function calculator.
Reverse Polish Notation Calculator
2.1.1 Declarations for `rpcalc`		Prologue (declarations) for rpcalc.
2.1.2 Grammar Rules for `rpcalc`		Grammar Rules for rpcalc, with explanation.
2.1.3 The `rpcalc` Lexical Analyzer		The lexical analyzer.
2.1.4 The Controlling Function		The controlling function.
2.1.5 The Error Reporting Routine		The error reporting function.
2.1.6 Running Bison to Make the Parser		Running Bison on the grammar file.
2.1.7 Compiling the Parser File		Run the C compiler on the output code.
Grammar Rules for `rpcalc`
2.1.2.1 Explanation of `input`
2.1.2.2 Explanation of `line`
2.1.2.3 Explanation of `expr`
Location Tracking Calculator: `ltcalc`
2.4.1 Declarations for `ltcalc`		Bison and C declarations for ltcalc.
2.4.2 Grammar Rules for `ltcalc`		Grammar rules for ltcalc, with explanations.
2.4.3 The `ltcalc` Lexical Analyzer.		The lexical analyzer.
Multi-Function Calculator: `mfcalc`
2.5.1 Declarations for `mfcalc`		Bison declarations for multi-function calculator.
2.5.2 Grammar Rules for `mfcalc`		Grammar rules for the calculator.
2.5.3 The `mfcalc` Symbol Table		Symbol table management subroutines.
Bison Grammar Files
3.1 Outline of a Bison Grammar		Overall layout of the grammar file.
3.2 Symbols, Terminal and Nonterminal		Terminal and nonterminal symbols.
3.3 Syntax of Grammar Rules		How to write grammar rules.
3.4 Recursive Rules		Writing recursive rules.
3.5 Defining Language Semantics		Semantic values and actions.
3.6 Tracking Locations		Locations and actions.
3.7 Bison Declarations		All kinds of Bison declarations are described here.
3.8 Multiple Parsers in the Same Program		Putting more than one Bison parser in one program.
Outline of a Bison Grammar
3.1.1 The prologue		Syntax and usage of the prologue.
3.1.2 Prologue Alternatives		Syntax and usage of alternatives to the prologue.
3.1.3 The Bison Declarations Section		Syntax and usage of the Bison declarations section.
3.1.4 The Grammar Rules Section		Syntax and usage of the grammar rules section.
3.1.5 The epilogue		Syntax and usage of the epilogue.
Defining Language Semantics
3.5.1 Data Types of Semantic Values		Specifying one data type for all semantic values.
3.5.2 More Than One Value Type		Specifying several alternative data types.
3.5.3 Actions		An action is the semantic definition of a grammar rule.
3.5.4 Data Types of Values in Actions		Specifying data types for actions to operate on.
3.5.5 Actions in Mid-Rule		Most actions go at the end of a rule. This says when, why and how to use the exceptional action in the middle of a rule.
Tracking Locations
3.6.1 Data Type of Locations		Specifying a data type for locations.
3.6.2 Actions and Locations		Using locations in actions.
3.6.3 Default Action for Locations		Defining a general way to compute locations.
Bison Declarations
3.7.1 Require a Version of Bison		Requiring a Bison version.
3.7.2 Token Type Names		Declaring terminal symbols.
3.7.3 Operator Precedence		Declaring terminals with precedence and associativity.
3.7.4 The Collection of Value Types		Declaring the set of all semantic value types.
3.7.5 Nonterminal Symbols		Declaring the choice of type for a nonterminal symbol.
3.7.6 Performing Actions before Parsing		Code run before parsing starts.
3.7.7 Freeing Discarded Symbols		Declaring how symbols are freed.
3.7.8 Suppressing Conflict Warnings		Suppressing warnings about parsing conflicts.
3.7.9 The Start-Symbol		Specifying the start symbol.
3.7.10 A Pure (Reentrant) Parser		Requesting a reentrant parser.
3.7.11 A Push Parser		Requesting a push parser.
3.7.12 Bison Declaration Summary		Table of all Bison declarations.
Parser C-Language Interface
4.1 The Parser Function `yyparse`		How to call `yyparse` and what it returns.
4.6 The Lexical Analyzer Function `yylex`		You must supply a function `yylex` which reads tokens.
4.7 The Error Reporting Function `yyerror`		You must supply a function `yyerror`.
4.8 Special Features for Use in Actions		Special features for use in actions.
4.9 Parser Internationalization		How to let the parser speak in the user's native language.
The Lexical Analyzer Function `yylex`
4.6.1 Calling Convention for `yylex`		How `yyparse` calls `yylex`.
4.6.2 Semantic Values of Tokens		How `yylex` must return the semantic value of the token it has read.
4.6.3 Textual Locations of Tokens		How `yylex` must return the text location (line number, etc.) of the token, if the actions want that.
4.6.4 Calling Conventions for Pure Parsers		How the calling convention differs in a pure parser (see section A Pure (Reentrant) Parser).
The Bison Parser Algorithm
5.1 Lookahead Tokens		Parser looks one token ahead when deciding what to do.
5.2 Shift/Reduce Conflicts		Conflicts: when either shifting or reduction is valid.
5.3 Operator Precedence		Operator precedence works by resolving conflicts.
5.4 Context-Dependent Precedence		When an operator's precedence depends on context.
5.5 Parser States		The parser is a finite-state-machine with stack.
5.6 Reduce/Reduce Conflicts		When two rules are applicable in the same situation.
5.7 Mysterious Reduce/Reduce Conflicts		Reduce/reduce conflicts that look unjustified.
5.8 Generalized LR (GLR) Parsing		Parsing arbitrary context-free grammars.
5.9 Memory Management, and How to Avoid Memory Exhaustion		What happens when memory is exhausted. How to avoid it.
Operator Precedence
5.3.1 When Precedence is Needed		An example showing why precedence is needed.
5.3.2 Specifying Operator Precedence		How to specify precedence in Bison grammars.
5.3.3 Precedence Examples		How these features are used in the previous example.
5.3.4 How Precedence Works		How they work.
Handling Context Dependencies
7.1 Semantic Info in Token Types		Token parsing can depend on the semantic context.
7.2 Lexical Tie-ins		Token parsing can depend on the syntactic context.
7.3 Lexical Tie-ins and Error Recovery		Lexical tie-ins have implications for how error recovery rules must be written.
Debugging Your Parser
8.1 Understanding Your Parser		Understanding the structure of your parser.
8.2 Tracing Your Parser		Tracing the execution of your parser.
Invoking Bison
9.1 Bison Options		All the options described in detail, in alphabetical order by short options.
9.2 Option Cross Key		Alphabetical list of long options.
9.3 Yacc Library		Yacc-compatible `yylex` and `main`.
Parsers Written In Other Languages
10.1 C++ Parsers		The interface to generate C++ parser classes
10.2 Java Parsers		The interface to generate Java parser classes
C++ Parsers
10.1.1 C++ Bison Interface		Asking for C++ parser generation
10.1.2 C++ Semantic Values		%union vs. C++
10.1.3 C++ Location Values		The position and location classes
10.1.4 C++ Parser Interface		Instantiating and running the parser
10.1.5 C++ Scanner Interface		Exchanges between yylex and parse
10.1.6 A Complete C++ Example		Demonstrating their use
A Complete C++ Example
10.1.6.1 Calc++ — C++ Calculator		The specifications
10.1.6.2 Calc++ Parsing Driver		An active parsing context
10.1.6.3 Calc++ Parser		A parser class
10.1.6.4 Calc++ Scanner		A pure C++ Flex scanner
10.1.6.5 Calc++ Top Level		Conducting the band
Java Parsers
10.2.1 Java Bison Interface		Asking for Java parser generation
10.2.2 Java Semantic Values		%type and %token vs. Java
10.2.3 Java Location Values		The position and location classes
10.2.4 Java Parser Interface		Instantiating and running the parser
10.2.5 Java Scanner Interface		Specifying the scanner for the parser
10.2.6 Special Features for Use in Java Actions		Special features for use in actions.
10.2.7 Differences between C/C++ and Java Grammars
10.2.8 Java Declarations Summary		List of Bison declarations used with Java
Frequently Asked Questions
11.1 Memory Exhausted		Breaking the Stack Limits
11.2 How Can I Reset the Parser		`yyparse` Keeps some State
11.3 Strings are Destroyed		`yylval` Loses Track of Strings
11.4 Implementing Gotos/Loops		Control Flow in the Calculator
11.5 Multiple start-symbols		Factoring closely related grammars
11.6 Secure? Conform?		Is Bison POSIX safe?
11.7 I can't build Bison		Troubleshooting
11.8 Where can I find help?		Troubleshouting
11.9 Bug Reports		Troublereporting
10. Parsers Written In Other Languages		Parsers in Java and others
11.11 Beta Testing		Experimenting development versions
11.12 Mailing Lists		Meeting other Bison users
Copying This Manual
C. Copying This Manual		License for copying this manual.

[Top]

[Contents]

[Index]

[ ? ]