Go forward to Introduction.
Go backward to (dir).
Go up to (dir).

   This manual documents version 1.25 of Bison.

Menu

Introduction
Conditions
Copying
The GNU General Public License says how you can copy and share Bison

Tutorial sections:

Concepts
Basic concepts for understanding Bison.
Examples
Three simple explained examples of using Bison.

Reference sections:

Grammar File
Writing Bison declarations and rules.
Interface
C-language interface to the parser function `yyparse'.
Algorithm
How the Bison parser works at run-time.
Error Recovery
Writing rules for error recovery.
Context Dependency
What to do if your language syntax is too messy for Bison to handle straightforwardly.
Debugging
Debugging Bison parsers that parse wrong.
Invocation
How to run Bison (to produce the parser source file).
Table of Symbols
All the keywords of the Bison language are explained.
Glossary
Basic concepts are explained.
Index
Cross-references to the text. -- The Detailed Node Listing --

The Concepts of Bison

Language and Grammar
Languages and context-free grammars, as mathematical ideas.
Grammar in Bison
How we represent grammars for Bison's sake.
Semantic Values
Each token or syntactic grouping can have a semantic value (the value of an integer, the name of an identifier, etc.).
Semantic Actions
Each rule can have an action containing C code.
Bison Parser
What are Bison's input and output, how is the output used?
Stages
Stages in writing and running Bison grammars.
Grammar Layout
Overall structure of a Bison grammar file.

Examples

RPN Calc
Reverse polish notation calculator; a first example with no operator precedence.
Infix Calc
Infix (algebraic) notation calculator. Operator precedence is introduced.
Simple Error Recovery
Continuing after syntax errors.
Multi-function Calc
Calculator with memory and trig functions. It uses multiple data-types for semantic values.
Exercises
Ideas for improving the multi-function calculator.

Reverse Polish Notation Calculator

Decls: Rpcalc Decls
Bison and C declarations for rpcalc.
Rules: Rpcalc Rules
Grammar Rules for rpcalc, with explanation.
Lexer: Rpcalc Lexer
The lexical analyzer.
Main: Rpcalc Main
The controlling function.
Error: Rpcalc Error
The error reporting function.
Gen: Rpcalc Gen
Running Bison on the grammar file.
Comp: Rpcalc Compile
Run the C compiler on the output code.

Grammar Rules for `rpcalc'

Rpcalc Input
Rpcalc Line
Rpcalc Expr

Multi-Function Calculator: `mfcalc'

Decl: Mfcalc Decl
Bison declarations for multi-function calculator.
Rules: Mfcalc Rules
Grammar rules for the calculator.
Symtab: Mfcalc Symtab
Symbol table management subroutines.

Bison Grammar Files

Grammar Outline
Overall layout of the grammar file.
Symbols
Terminal and nonterminal symbols.
Rules
How to write grammar rules.
Recursion
Writing recursive rules.
Semantics
Semantic values and actions.
Declarations
All kinds of Bison declarations are described here.
Multiple Parsers
Putting more than one Bison parser in one program.

Outline of a Bison Grammar

C Declarations
Syntax and usage of the C declarations section.
Bison Declarations
Syntax and usage of the Bison declarations section.
Grammar Rules
Syntax and usage of the grammar rules section.
C Code
Syntax and usage of the additional C code section.

Defining Language Semantics

Value Type
Specifying one data type for all semantic values.
Multiple Types
Specifying several alternative data types.
Actions
An action is the semantic definition of a grammar rule.
Action Types
Specifying data types for actions to operate on.
Mid-Rule Actions
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

Token Decl
Declaring terminal symbols.
Precedence Decl
Declaring terminals with precedence and associativity.
Union Decl
Declaring the set of all semantic value types.
Type Decl
Declaring the choice of type for a nonterminal symbol.
Expect Decl
Suppressing warnings about shift/reduce conflicts.
Start Decl
Specifying the start symbol.
Pure Decl
Requesting a reentrant parser.
Decl Summary
Table of all Bison declarations.

Parser C-Language Interface

Parser Function
How to call `yyparse' and what it returns.
Lexical
You must supply a function `yylex' which reads tokens.
Error Reporting
You must supply a function `yyerror'.
Action Features
Special features for use in actions.

The Lexical Analyzer Function `yylex'

Calling Convention
How `yyparse' calls `yylex'.
Token Values
How `yylex' must return the semantic value of the token it has read.
Token Positions
How `yylex' must return the text position (line number, etc.) of the token, if the actions want that.
Pure Calling
How the calling convention differs in a pure parser (see A Pure (Reentrant) Parser: Pure Decl.).

The Bison Parser Algorithm

Look-Ahead
Parser looks one token ahead when deciding what to do.
Shift/Reduce
Conflicts: when either shifting or reduction is valid.
Precedence
Operator precedence works by resolving conflicts.
Contextual Precedence
When an operator's precedence depends on context.
Parser States
The parser is a finite-state-machine with stack.
Reduce/Reduce
When two rules are applicable in the same situation.
Mystery Conflicts
Reduce/reduce conflicts that look unjustified.
Stack Overflow
What happens when stack gets full. How to avoid it.

Operator Precedence

Why Precedence
An example showing why precedence is needed.
Using Precedence
How to specify precedence in Bison grammars.
Precedence Examples
How these features are used in the previous example.
How Precedence
How they work.

Handling Context Dependencies

Semantic Tokens
Token parsing can depend on the semantic context.
Lexical Tie-ins
Token parsing can depend on the syntactic context.
Tie-in Recovery
Lexical tie-ins have implications for how error recovery rules must be written.

Invoking Bison

Bison Options
All the options described in detail, in alphabetical order by short options.
Option Cross Key
Alphabetical list of long options.
VMS Invocation
Bison command syntax on VMS.