Bison

The Yacc-compatible Parser Generator

23 October 2013, Bison Version 3.0.1

by Charles Donnelly and Richard Stallman

This manual (23 October 2013) is for GNU Bison (version 3.0.1), 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.3 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.”

Published by the Free Software Foundation
51 Franklin Street, Fifth Floor
Boston, MA 02110-1301 USA
Printed copies are available from the Free Software Foundation.
ISBN 1-882114-44-2

Cover art by Etienne Suvasa.

Bison

This manual (23 October 2013) is for GNU Bison (version 3.0.1), 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.3 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 implementation).
10 Parsers Written In Other Languages		Creating C++ and Java parsers.
11 Frequently Asked Questions
Appendix A Bison Symbols		All the keywords of the Bison language are explained.
Appendix B Glossary		Basic concepts are explained.
Appendix C Copying This Manual		License for copying this manual.
Bibliography		Publications cited in this manual.
Index of Terms		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		Overview of location tracking.
1.7 Bison Output: the Parser Implementation 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		Considerations for semantic values and deferred actions.
1.5.4 Controlling a Parse with Arbitrary Predicates		Controlling a parse with arbitrary computations.
1.5.5 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 Implementation File		Run the C compiler on the output code.
Grammar Rules for `rpcalc`
2.1.2.1 Explanation of `input`		Explanation of the `input` nonterminal
2.1.2.2 Explanation of `line`		Explanation of the `line` nonterminal
2.1.2.3 Explanation of `expr`		Explanation of the `expr` nonterminal
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.
2.5.4 The `mfcalc` Lexer		The lexical analyzer.
2.5.5 The `mfcalc` Main		The controlling function.
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 Grammar Rules		How to write grammar rules.
3.4 Defining Language Semantics		Semantic values and actions.
3.5 Tracking Locations		Locations and actions.
3.6 Named References		Using named references in 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.
Grammar Rules
3.3.1 Syntax of Grammar Rules		Syntax of the rules.
3.3.2 Empty Rules		Symbols that can match the empty string.
3.3.3 Recursive Rules		Writing recursive rules.
Defining Language Semantics
3.4.1 Data Types of Semantic Values		Specifying one data type for all semantic values.
3.4.2 More Than One Value Type		Specifying several alternative data types.
3.4.3 Generating the Semantic Value Type		Generating the semantic value type.
3.4.4 The Union Declaration		Declaring the set of all semantic value types.
3.4.5 Providing a Structured Semantic Value Type		Providing a structured semantic value type.
3.4.6 Actions		An action is the semantic definition of a grammar rule.
3.4.7 Data Types of Values in Actions		Specifying data types for actions to operate on.
3.4.8 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.
Actions in Mid-Rule
3.4.8.1 Using Mid-Rule Actions		Putting an action in the middle of a rule.
3.4.8.2 Mid-Rule Action Translation		How mid-rule actions are actually processed.
3.4.8.3 Conflicts due to Mid-Rule Actions		Mid-rule actions can cause conflicts.
Tracking Locations
3.5.1 Data Type of Locations		Specifying a data type for locations.
3.5.2 Actions and Locations		Using locations in actions.
3.5.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 Nonterminal Symbols		Declaring the choice of type for a nonterminal symbol.
3.7.5 Performing Actions before Parsing		Code run before parsing starts.
3.7.6 Freeing Discarded Symbols		Declaring how symbols are freed.
3.7.7 Printing Semantic Values		Declaring how symbol values are displayed.
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.
3.7.13 %define Summary		Defining variables to adjust Bison’s behavior.
3.7.14 %code Summary		Inserting code into the parser source.
Parser C-Language Interface
4.1 The Parser Function `yyparse`		How to call `yyparse` and what it returns.
4.2 The Push Parser Function `yypush_parse`		How to call `yypush_parse` and what it returns.
4.3 The Pull Parser Function `yypull_parse`		How to call `yypull_parse` and what it returns.
4.4 The Parser Create Function `yystate_new`		How to call `yypstate_new` and what it returns.
4.5 The Parser Delete Function `yystate_delete`		How to call `yypstate_delete` 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 Conflicts		Conflicts that look unjustified.
5.8 Tuning LR		How to tune fundamental aspects of LR-based parsing.
5.9 Generalized LR (GLR) Parsing		Parsing arbitrary context-free grammars.
5.10 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 and associativity.
5.3.3 Specifying Precedence Only		How to specify precedence only.
5.3.4 Precedence Examples		How these features are used in the previous example.
5.3.5 How Precedence Works		How they work.
5.3.6 Using Precedence For Non Operators		Using precedence for general conflicts.
Tuning LR
5.8.1 LR Table Construction		Choose a different construction algorithm.
5.8.2 Default Reductions		Disable default reductions.
5.8.3 LAC		Correct lookahead sets in the parser states.
5.8.4 Unreachable States		Keep unreachable parser states for debugging.
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 Visualizing Your Parser		Getting a visual representation of the parser.
8.3 Visualizing your parser in multiple formats		Getting a markup representation of the parser.
8.4 Tracing Your Parser		Tracing the execution of your parser.
Tracing Your Parser
8.4.1 Enabling Traces		Activating run-time trace support
8.4.2 Enabling Debug Traces for `mfcalc`		Extending `mfcalc` to support traces
8.4.3 The `YYPRINT` Macro		Obsolete interface for semantic value reports
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
C++ Location Values
10.1.3.1 C++ `position`		One point in the source file
10.1.3.2 C++ `location`		Two points in the source file
10.1.3.3 User Defined Location Type		Required interface for locations
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 Java Push Parser Interface		Instantiating and running the a push parser
10.2.8 Differences between C/C++ and Java Grammars
10.2.9 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
11.10 More Languages		Parsers in C++, Java, and so on
11.11 Beta Testing		Experimenting development versions
11.12 Mailing Lists		Meeting other Bison users
Copying This Manual
Appendix C Copying This Manual		License for copying this manual.

This document was generated on December 1, 2013 using texi2html 5.0.