Bison 3.5.1

Table of Contents

Next:   [Contents][Index]

Bison

This manual (19 January 2020) is for GNU Bison (version 3.5.1), the GNU parser generator.

Copyright © 1988–1993, 1995, 1998–2015, 2018–2020 Free Software Foundation, Inc.

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  What GNU Bison is.
• Conditions  Conditions for using Bison and its output.
• 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.
• History  How Bison came to be
• FAQ  Frequently Asked Questions
• Table of Symbols  All the keywords of the Bison language are explained.
• Glossary  Basic concepts are explained.
• GNU Free Documentation License  Copying and sharing 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 for GLR  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.
• Midrule 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 Midrule
• Using Midrule Actions  Putting an action in the middle of a rule.
• Typed Midrule Actions  Specifying the semantic type of their values.
• Midrule Action Translation  How midrule actions are actually processed.
• Midrule Conflicts  Midrule 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.
• Symbol Decls  Summary of the Syntax of Symbol Declarations.
• 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.
• Tokens from Literals  Finding token types from string aliases.
• 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. 

Bison Options
• Operation Modes  Options controlling the global behavior of bison
• Diagnostics  Options controlling the diagnostics
• Tuning the Parser  Options changing the generated parsers
• Output Files  Options controlling the output 

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
• A Simple C++ Example  A short introduction to C++ parsers
• C++ Bison Interface  Asking for C++ parser generation
• C++ Parser Interface  Instantiating and running the parser
• C++ Semantic Values  %union vs. C++
• C++ Location Values  The position and location classes
• 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
• Exposing the Location Classes  Using the Bison location class in your project
• 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  %token and %nterm 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 

A Brief History of the Greater Ungulates
• Yacc  The original Yacc
• yacchack  An obscure early implementation of reentrancy
• Byacc  Berkeley Yacc
• Bison  This program
• Other Ungulates  Similar programs 

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
• Enabling Relocatability  Moving Bison/using it through network shares
• 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
• GNU Free Documentation License  Copying and sharing this manual

Next:   [Contents][Index]