Contents | < Browse | Browse >

>> Go Back to GccGuide. <<

   This manual documents version 1.20 of Bison.

* 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          Debugging Bison parsers that parse wrong.
* Invocation         How to run Bison (to produce the parser source file).
* Table of Symbols   All the keywords of the Bison language are explained.
* Glossary           Basic concepts are explained.
* 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.
* 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.

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.
* 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.  Bison and C 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 

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

* C Declarations     Syntax and usage of the C declarations section.
* Bison Declarations   Syntax and usage of the Bison declarations section.
* Grammar Rules      Syntax and usage of the grammar rules section.
* C Code             Syntax and usage of the additional C code section.

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.

Bison Declarations

* 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.
* Expect Decl        Suppressing warnings about shift/reduce 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.

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 Positions    How `yylex' must return the text position
                        (line number, etc.) of the token, if the
                         actions want that.
* Pure Calling       How the calling convention differs
                        in a pure 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.
* Stack Overflow     What happens when stack gets full.  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.

Invoking Bison

* Bison Options      All the options described in detail,
			in alphabetical order by short options.
* Option Cross Key   Alphabetical list of long options.
* VMS Invocation     Bison command syntax on VMS.