Bison 1.28

This manual documents version 1.28 of Bison.

Introduction
Conditions for Using Bison
GNU GENERAL PUBLIC LICENSE		The GNU General Public License says how you can copy and share Bison

Tutorial sections:

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		Debugging Bison parsers that parse wrong.
9. Invoking Bison		How to run Bison (to produce the parser source file).
A. Bison Symbols		All the keywords of the Bison language are explained.
B. Glossary		Basic concepts are explained.
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 Bison Output: the Parser File		What are Bison's input and output, how is the output used?
1.6 Stages in Using Bison		Stages in writing and running Bison grammars.
1.7 The Overall Layout of a Bison Grammar		Overall structure of a Bison grammar file.

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 Multi-Function Calculator: mfcalc		Calculator with memory and trig functions. It uses multiple data-types for semantic values.
2.5 Exercises		Ideas for improving the multi-function calculator.

Reverse Polish Notation Calculator

2.1.1 Declarations for rpcalc		Bison and C 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

Multi-Function Calculator: mfcalc

2.4.1 Declarations for mfcalc		Bison declarations for multi-function calculator.
2.4.2 Grammar Rules for mfcalc		Grammar rules for the calculator.
2.4.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 Bison Declarations		All kinds of Bison declarations are described here.
3.7 Multiple Parsers in the Same Program		Putting more than one Bison parser in one program.

Outline of a Bison Grammar

3.1.1 The C Declarations Section		Syntax and usage of the C declarations section.
3.1.2 The Bison Declarations Section		Syntax and usage of the Bison declarations section.
3.1.3 The Grammar Rules Section		Syntax and usage of the grammar rules section.
3.1.4 The Additional C Code Section		Syntax and usage of the additional C code section.

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.

Bison Declarations

3.6.1 Token Type Names		Declaring terminal symbols.
3.6.2 Operator Precedence		Declaring terminals with precedence and associativity.
3.6.3 The Collection of Value Types		Declaring the set of all semantic value types.
3.6.4 Nonterminal Symbols		Declaring the choice of type for a nonterminal symbol.
3.6.5 Suppressing Conflict Warnings		Suppressing warnings about shift/reduce conflicts.
3.6.6 The Start-Symbol		Specifying the start symbol.
3.6.7 A Pure (Reentrant) Parser		Requesting a reentrant parser.
3.6.8 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.2 The Lexical Analyzer Function yylex		You must supply a function yylex which reads tokens.
4.3 The Error Reporting Function yyerror		You must supply a function yyerror.
4.4 Special Features for Use in Actions		Special features for use in actions.

The Lexical Analyzer Function yylex

4.2.1 Calling Convention for yylex		How yyparse calls yylex.
4.2.2 Semantic Values of Tokens		How yylex must return the semantic value of the token it has read.
4.2.3 Textual Positions of Tokens		How yylex must return the text position

                        (line number, etc.) of the token, if the
                         actions want that.

4.2.4 Calling Conventions for Pure Parsers

How the calling convention differs in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).

The Bison Parser Algorithm 

5.1 Look-Ahead 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 Stack Overflow, and How to Avoid It		What happens when stack gets full. 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.

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 Invoking Bison under VMS		Bison command syntax on VMS.