Bison 2.4.1

Bison

This manual (19 November 2008) is for GNU Bison (version 2.4.1), the GNU parser generator.

Copyright © 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008 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.2 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 source file).
• 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.
• 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.
• GLR Parsers: Writing parsers for general context-free languages.
• Locations Overview: Tracking Locations.
• 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: Deferred semantic actions have special concerns.
• 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
• Rpcalc Line
• Rpcalc Expr

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.

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

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

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.

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.
• Union Decl: Declaring the set of all semantic value types.
• 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.
• 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.

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.
• Mystery Conflicts: Reduce/reduce conflicts that look unjustified.
• 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 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.

Debugging Your Parser

• Understanding: Understanding the structure of your parser.
• Tracing: Tracing the execution of your parser.

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

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