Info Node: (bison.info)Top

CFHT HOME bison.info: Top

up: (dir) next: Introduction Back to Software Index 

Bison
*****

This manual (8 April 2013) is for GNU Bison (version 2.7.12-4996), the
GNU parser generator.

   Copyright (C) 1988-1993, 1995, 1998-2013 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
* 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
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.
* 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. 
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. 
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.
* 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.
* 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 (Note: 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 in Bison grammars.
* 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 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