Bison 3.0.4: Top

Bison

This manual (23 January 2015) is for GNU Bison (version 3.0.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.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.”

• 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:		Understanding or debugging Bison parsers.
• Invocation:		How to run Bison (to produce the parser implementation).
• Other Languages:		Creating C++ and Java parsers.
• FAQ:		Frequently Asked Questions
• Table of Symbols:		All the keywords of the Bison language are explained.
• Glossary:		Basic concepts are explained.
• 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
• 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.
• GLR Parsers:		Writing parsers for general context-free languages.
• Locations:		Overview of location tracking.
• 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.
Writing GLR Parsers
• Simple GLR Parsers:		Using GLR parsers on unambiguous grammars.
• Merging GLR Parses:		Using GLR parsers to resolve ambiguities.
• GLR Semantic Actions:		Considerations for semantic values and deferred actions.
• Semantic Predicates:		Controlling a parse with arbitrary computations.
• Compiler Requirements:		GLR parsers require a modern C compiler.
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.
• Location Tracking Calc:		Demonstrating the use of @`n` and @$.
• 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
• Rpcalc Declarations:		Prologue (declarations) for rpcalc.
• Rpcalc Rules:		Grammar Rules for rpcalc, with explanation.
• Rpcalc Lexer:		The lexical analyzer.
• Rpcalc Main:		The controlling function.
• Rpcalc Error:		The error reporting function.
• Rpcalc Generate:		Running Bison on the grammar file.
• Rpcalc Compile:		Run the C compiler on the output code.
Grammar Rules for `rpcalc`
• Rpcalc Input:		Explanation of the `input` nonterminal
• Rpcalc Line:		Explanation of the `line` nonterminal
• Rpcalc Expr:		Explanation of the `expr` nonterminal
Location Tracking Calculator: `ltcalc`
• Ltcalc Declarations:		Bison and C declarations for ltcalc.
• Ltcalc Rules:		Grammar rules for ltcalc, with explanations.
• Ltcalc Lexer:		The lexical analyzer.
Multi-Function Calculator: `mfcalc`
• Mfcalc Declarations:		Bison declarations for multi-function calculator.
• Mfcalc Rules:		Grammar rules for the calculator.
• Mfcalc Symbol Table:		Symbol table management subroutines.
• Mfcalc Lexer:		The lexical analyzer.
• Mfcalc Main:		The controlling function.
Bison Grammar Files
• Grammar Outline:		Overall layout of the grammar file.
• Symbols:		Terminal and nonterminal symbols.
• Rules:		How to write grammar rules.
• Semantics:		Semantic values and actions.
• Tracking Locations:		Locations and actions.
• Named References:		Using named references in 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
• Prologue:		Syntax and usage of the prologue.
• Prologue Alternatives:		Syntax and usage of alternatives to the prologue.
• Bison Declarations:		Syntax and usage of the Bison declarations section.
• Grammar Rules:		Syntax and usage of the grammar rules section.
• Epilogue:		Syntax and usage of the epilogue.
Grammar Rules
• Rules Syntax:		Syntax of the rules.
• Empty Rules:		Symbols that can match the empty string.
• Recursion:		Writing recursive rules.
Defining Language Semantics
• Value Type:		Specifying one data type for all semantic values.
• Multiple Types:		Specifying several alternative data types.
• Type Generation:		Generating the semantic value type.
• Union Decl:		Declaring the set of all semantic value types.
• Structured Value Type:		Providing a structured semantic value type.
• 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.
Actions in Mid-Rule
• Using Mid-Rule Actions:		Putting an action in the middle of a rule.
• Mid-Rule Action Translation:		How mid-rule actions are actually processed.
• Mid-Rule Conflicts:		Mid-rule actions can cause conflicts.
Tracking Locations
• Location Type:		Specifying a data type for locations.
• Actions and Locations:		Using locations in actions.
• Location Default Action:		Defining a general way to compute locations.
Bison Declarations
• Require Decl:		Requiring a Bison version.
• Token Decl:		Declaring terminal symbols.
• Precedence Decl:		Declaring terminals with precedence and associativity.
• Type Decl:		Declaring the choice of type for a nonterminal symbol.
• Initial Action Decl:		Code run before parsing starts.
• Destructor Decl:		Declaring how symbols are freed.
• Printer Decl:		Declaring how symbol values are displayed.
• Expect Decl:		Suppressing warnings about parsing conflicts.
• Start Decl:		Specifying the start symbol.
• Pure Decl:		Requesting a reentrant parser.
• Push Decl:		Requesting a push parser.
• Decl Summary:		Table of all Bison declarations.
• %define Summary:		Defining variables to adjust Bison’s behavior.
• %code Summary:		Inserting code into the parser source.
Parser C-Language Interface
• Parser Function:		How to call `yyparse` and what it returns.
• Push Parser Function:		How to call `yypush_parse` and what it returns.
• Pull Parser Function:		How to call `yypull_parse` and what it returns.
• Parser Create Function:		How to call `yypstate_new` and what it returns.
• Parser Delete Function:		How to call `yypstate_delete` 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.
• Internationalization:		How to let the parser speak in the user’s native language.
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 Locations:		How `yylex` must return the text location (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).
The Bison Parser Algorithm
• Lookahead:		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.
• Mysterious Conflicts:		Conflicts that look unjustified.
• Tuning LR:		How to tune fundamental aspects of LR-based parsing.
• Generalized LR Parsing:		Parsing arbitrary context-free grammars.
• Memory Management:		What happens when memory is exhausted. How to avoid it.
Operator Precedence
• Why Precedence:		An example showing why precedence is needed.
• Using Precedence:		How to specify precedence and associativity.
• Precedence Only:		How to specify precedence only.
• Precedence Examples:		How these features are used in the previous example.
• How Precedence:		How they work.
• Non Operators:		Using precedence for general conflicts.
Tuning LR
• LR Table Construction:		Choose a different construction algorithm.
• Default Reductions:		Disable default reductions.
• LAC:		Correct lookahead sets in the parser states.
• Unreachable States:		Keep unreachable parser states for debugging.
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.
Debugging Your Parser
• Understanding:		Understanding the structure of your parser.
• Graphviz:		Getting a visual representation of the parser.
• Xml:		Getting a markup representation of the parser.
• Tracing:		Tracing the execution of your parser.
Tracing Your Parser
• Enabling Traces:		Activating run-time trace support
• Mfcalc Traces:		Extending `mfcalc` to support traces
• The YYPRINT Macro:		Obsolete interface for semantic value reports
Invoking Bison
• Bison Options:		All the options described in detail, in alphabetical order by short options.
• Option Cross Key:		Alphabetical list of long options.
• Yacc Library:		Yacc-compatible `yylex` and `main`.
Parsers Written In Other Languages
• C++ Parsers:		The interface to generate C++ parser classes
• Java Parsers:		The interface to generate Java parser classes
C++ Parsers
• C++ Bison Interface:		Asking for C++ parser generation
• C++ Semantic Values:		%union vs. C++
• C++ Location Values:		The position and location classes
• C++ Parser Interface:		Instantiating and running the parser
• C++ Scanner Interface:		Exchanges between yylex and parse
• A Complete C++ Example:		Demonstrating their use
C++ Location Values
• C++ position:		One point in the source file
• C++ location:		Two points in the source file
• User Defined Location Type:		Required interface for locations
A Complete C++ Example
• Calc++ --- C++ Calculator:		The specifications
• Calc++ Parsing Driver:		An active parsing context
• Calc++ Parser:		A parser class
• Calc++ Scanner:		A pure C++ Flex scanner
• Calc++ Top Level:		Conducting the band
Java Parsers
• Java Bison Interface:		Asking for Java parser generation
• Java Semantic Values:		%type and %token vs. Java
• Java Location Values:		The position and location classes
• Java Parser Interface:		Instantiating and running the parser
• Java Scanner Interface:		Specifying the scanner for the parser
• Java Action Features:		Special features for use in actions
• Java Push Parser Interface:		Instantiating and running the a push parser
• Java Differences:		Differences between C/C++ and Java Grammars
• Java Declarations Summary:		List of Bison declarations used with Java
Frequently Asked Questions
• Memory Exhausted:		Breaking the Stack Limits
• How Can I Reset the Parser:		`yyparse` Keeps some State
• Strings are Destroyed:		`yylval` Loses Track of Strings
• Implementing Gotos/Loops:		Control Flow in the Calculator
• Multiple start-symbols:		Factoring closely related grammars
• Secure? Conform?:		Is Bison POSIX safe?
• I can't build Bison:		Troubleshooting
• Where can I find help?:		Troubleshouting
• Bug Reports:		Troublereporting
• More Languages:		Parsers in C++, Java, and so on
• Beta Testing:		Experimenting development versions
• Mailing Lists:		Meeting other Bison users
Copying This Manual
• Copying This Manual:		License for copying this manual.

• 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:

Understanding or debugging Bison parsers.

• Invocation:

How to run Bison (to produce the parser implementation).

• Other Languages:

Creating C++ and Java parsers.

• FAQ:

Frequently Asked Questions

• Table of Symbols:

All the keywords of the Bison language are explained.

• Glossary:

Basic concepts are explained.

• 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

• 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.

• GLR Parsers:

Writing parsers for general context-free languages.

• Locations:

Overview of location tracking.

• 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.


Writing GLR Parsers

• Simple GLR Parsers:

Using GLR parsers on unambiguous grammars.

• Merging GLR Parses:

Using GLR parsers to resolve ambiguities.

• GLR Semantic Actions:

Considerations for semantic values and deferred actions.

• Semantic Predicates:

Controlling a parse with arbitrary computations.

• Compiler Requirements:

GLR parsers require a modern C compiler.


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.

• Location Tracking Calc:

Demonstrating the use of @n and @$.

• 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

• Rpcalc Declarations:

Prologue (declarations) for rpcalc.

• Rpcalc Rules:

Grammar Rules for rpcalc, with explanation.

• Rpcalc Lexer:

The lexical analyzer.

• Rpcalc Main:

The controlling function.

• Rpcalc Error:

The error reporting function.

• Rpcalc Generate:

Running Bison on the grammar file.

• Rpcalc Compile:

Run the C compiler on the output code.


Grammar Rules for rpcalc

• Rpcalc Input:

Explanation of the input nonterminal

• Rpcalc Line:

Explanation of the line nonterminal

• Rpcalc Expr:

Explanation of the expr nonterminal


Location Tracking Calculator: ltcalc

• Ltcalc Declarations:

Bison and C declarations for ltcalc.

• Ltcalc Rules:

Grammar rules for ltcalc, with explanations.

• Ltcalc Lexer:

The lexical analyzer.


Multi-Function Calculator: mfcalc

• Mfcalc Declarations:

Bison declarations for multi-function calculator.

• Mfcalc Rules:

Grammar rules for the calculator.

• Mfcalc Symbol Table:

Symbol table management subroutines.

• Mfcalc Lexer:

The lexical analyzer.

• Mfcalc Main:

The controlling function.


Bison Grammar Files

• Grammar Outline:

Overall layout of the grammar file.

• Symbols:

Terminal and nonterminal symbols.

• Rules:

How to write grammar rules.

• Semantics:

Semantic values and actions.

• Tracking Locations:

Locations and actions.

• Named References:

Using named references in 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

• Prologue:

Syntax and usage of the prologue.

• Prologue Alternatives:

Syntax and usage of alternatives to the prologue.

• Bison Declarations:

Syntax and usage of the Bison declarations section.

• Grammar Rules:

Syntax and usage of the grammar rules section.

• Epilogue:

Syntax and usage of the epilogue.


Grammar Rules

• Rules Syntax:

Syntax of the rules.

• Empty Rules:

Symbols that can match the empty string.

• Recursion:

Writing recursive rules.



Defining Language Semantics

• Value Type:

Specifying one data type for all semantic values.

• Multiple Types:

Specifying several alternative data types.

• Type Generation:

Generating the semantic value type.

• Union Decl:

Declaring the set of all semantic value types.

• Structured Value Type:

Providing a structured semantic value type.

• 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.


Actions in Mid-Rule

• Using Mid-Rule Actions:

Putting an action in the middle of a rule.

• Mid-Rule Action Translation:

How mid-rule actions are actually processed.

• Mid-Rule Conflicts:

Mid-rule actions can cause conflicts.


Tracking Locations

• Location Type:

Specifying a data type for locations.

• Actions and Locations:

Using locations in actions.

• Location Default Action:

Defining a general way to compute locations.


Bison Declarations

• Require Decl:

Requiring a Bison version.

• Token Decl:

Declaring terminal symbols.

• Precedence Decl:

Declaring terminals with precedence and associativity.

• Type Decl:

Declaring the choice of type for a nonterminal symbol.

• Initial Action Decl:

Code run before parsing starts.

• Destructor Decl:

Declaring how symbols are freed.

• Printer Decl:

Declaring how symbol values are displayed.

• Expect Decl:

Suppressing warnings about parsing conflicts.

• Start Decl:

Specifying the start symbol.

• Pure Decl:

Requesting a reentrant parser.

• Push Decl:

Requesting a push parser.

• Decl Summary:

Table of all Bison declarations.

• %define Summary:

Defining variables to adjust Bison’s behavior.

• %code Summary:

Inserting code into the parser source.


Parser C-Language Interface

• Parser Function:

How to call yyparse and what it returns.

• Push Parser Function:

How to call yypush_parse and what it returns.

• Pull Parser Function:

How to call yypull_parse and what it returns.

• Parser Create Function:

How to call yypstate_new and what it returns.

• Parser Delete Function:

How to call yypstate_delete 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.

• Internationalization:

How to let the parser speak in the user’s native language.


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 Locations:

How yylex must return the text location (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).


The Bison Parser Algorithm

• Lookahead:

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.

• Mysterious Conflicts:

Conflicts that look unjustified.

• Tuning LR:

How to tune fundamental aspects of LR-based parsing.

• Generalized LR Parsing:

Parsing arbitrary context-free grammars.

• Memory Management:

What happens when memory is exhausted. How to avoid it.


Operator Precedence

• Why Precedence:

An example showing why precedence is needed.

• Using Precedence:

How to specify precedence and associativity.

• Precedence Only:

How to specify precedence only.

• Precedence Examples:

How these features are used in the previous example.

• How Precedence:

How they work.

• Non Operators:

Using precedence for general conflicts.


Tuning LR

• LR Table Construction:

Choose a different construction algorithm.

• Default Reductions:

Disable default reductions.

• LAC:

Correct lookahead sets in the parser states.

• Unreachable States:

Keep unreachable parser states for debugging.


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.


Debugging Your Parser

• Understanding:

Understanding the structure of your parser.

• Graphviz:

Getting a visual representation of the parser.

• Xml:

Getting a markup representation of the parser.

• Tracing:

Tracing the execution of your parser.


Tracing Your Parser

• Enabling Traces:

Activating run-time trace support

• Mfcalc Traces:

Extending mfcalc to support traces

• The YYPRINT Macro:

Obsolete interface for semantic value reports


Invoking Bison

• Bison Options:

All the options described in detail, in alphabetical order by short options.

• Option Cross Key:

Alphabetical list of long options.

• Yacc Library:

Yacc-compatible yylex and main.


Parsers Written In Other Languages

• C++ Parsers:

The interface to generate C++ parser classes

• Java Parsers:

The interface to generate Java parser classes


C++ Parsers

• C++ Bison Interface:

Asking for C++ parser generation

• C++ Semantic Values:

%union vs. C++

• C++ Location Values:

The position and location classes

• C++ Parser Interface:

Instantiating and running the parser

• C++ Scanner Interface:

Exchanges between yylex and parse

• A Complete C++ Example:

Demonstrating their use


C++ Location Values

• C++ position:

One point in the source file

• C++ location:

Two points in the source file

• User Defined Location Type:

Required interface for locations


A Complete C++ Example

• Calc++ --- C++ Calculator:

The specifications

• Calc++ Parsing Driver:

An active parsing context

• Calc++ Parser:

A parser class

• Calc++ Scanner:

A pure C++ Flex scanner

• Calc++ Top Level:

Conducting the band


Java Parsers

• Java Bison Interface:

Asking for Java parser generation

• Java Semantic Values:

%type and %token vs. Java

• Java Location Values:

The position and location classes

• Java Parser Interface:

Instantiating and running the parser

• Java Scanner Interface:

Specifying the scanner for the parser

• Java Action Features:

Special features for use in actions

• Java Push Parser Interface:

Instantiating and running the a push parser

• Java Differences:

Differences between C/C++ and Java Grammars

• Java Declarations Summary:

List of Bison declarations used with Java


Frequently Asked Questions

• Memory Exhausted:

Breaking the Stack Limits

• How Can I Reset the Parser:

yyparse Keeps some State

• Strings are Destroyed:

yylval Loses Track of Strings

• Implementing Gotos/Loops:

Control Flow in the Calculator

• Multiple start-symbols:

Factoring closely related grammars

• Secure? Conform?:

Is Bison POSIX safe?

• I can't build Bison:

Troubleshooting

• Where can I find help?:

Troubleshouting

• Bug Reports:

Troublereporting

• More Languages:

Parsers in C++, Java, and so on

• Beta Testing:

Experimenting development versions

• Mailing Lists:

Meeting other Bison users


Copying This Manual

• Copying This Manual:

License for copying this manual.

Bison 3.0.4

Table of Contents

Bison