(bison.info.gz) Top
Info Catalog
(dir) Top
(bison.info.gz) Introduction
Bison
*****
This manual is for GNU Bison (version 2.3, 30 May 2006), the GNU parser
generator.
Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999,
2000, 2001, 2002, 2003, 2004, 2005, 2006 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 freedom to copy and
modify this GNU Manual, like GNU software. Copies published by
the Free Software Foundation raise funds for GNU development."
Menu
* 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).
* C++ Language Interface Creating C++ parser objects.
* 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
* Decls Rpcalc Decls. Prologue (declarations) for rpcalc.
* Rules Rpcalc Rules. Grammar Rules for rpcalc, with explanation.
* Lexer Rpcalc Lexer. The lexical analyzer.
* Main Rpcalc Main. The controlling function.
* Error Rpcalc Error. The error reporting function.
* Gen Rpcalc Gen. Running Bison on the grammar file.
* Comp Rpcalc Compile. Run the C compiler on the output code.
Grammar Rules for `rpcalc'
* Rpcalc Input
* Rpcalc Line
* Rpcalc Expr
Location Tracking Calculator: `ltcalc'
* Decls Ltcalc Decls. Bison and C declarations for ltcalc.
* Rules Ltcalc Rules. Grammar rules for ltcalc, with explanations.
* Lexer Ltcalc Lexer. The lexical analyzer.
Multi-Function Calculator: `mfcalc'
* Decl Mfcalc Decl. Bison declarations for multi-function calculator.
* Rules Mfcalc Rules. Grammar rules for the calculator.
* Symtab Mfcalc Symtab. 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.
* 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.
* Decl Summary Table of all Bison declarations.
Parser C-Language Interface
* Parser Function How to call `yyparse' 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 ( A Pure (Reentrant) Parser Pure Decl.).
The Bison Parser Algorithm
* Look-Ahead 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'.
C++ Language Interface
* C++ Parsers The interface to generate C++ parser classes
* A Complete C++ Example Demonstrating their use
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
* 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
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
* Other Languages Parsers in Java and others
* Beta Testing Experimenting development versions
* Mailing Lists Meeting other Bison users
Copying This Manual
* GNU Free Documentation License License for copying this manual.
Info Catalog
(dir) Top
(bison.info.gz) Introduction
automatically generated by
info2html