(bison.info)Top


Bison
*****

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

   Copyright (C) 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

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
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,
Grammar in Bison: How we represent grammars for Bison's sake.
Semantic Values: Each token or syntactic grouping can have
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,
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;
Infix Calc: Infix (algebraic) notation calculator.
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.
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.

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

The Lexical Analyzer Function `yylex'

Calling Convention: How `yyparse' calls `yylex'.
Token Values: How `yylex' must return the semantic value
Token Locations: How `yylex' must return the text location
Pure Calling: How the calling convention differs in a pure 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

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

automatically generated by info2www version 1.2.2.9