www.delorie.com/gnu/docs/bison/bison.html   search  
Buy the book!

Bison 1.875

[Top] [Contents] [Index] [ ? ]

Bison 1.875


Conditions for Using Bison  
GNU GENERAL PUBLIC LICENSE  The GNU General Public License says how you can copy and share Bison

Tutorial sections:
1. The Concepts of Bison  Basic concepts for understanding Bison.
2. Examples  Three simple explained examples of using Bison.

Reference sections:
3. Bison Grammar Files  Writing Bison declarations and rules.
4. Parser C-Language Interface  C-language interface to the parser function yyparse.
5. The Bison Parser Algorithm  How the Bison parser works at run-time.
6. Error Recovery  Writing rules for error recovery.
7. Handling Context Dependencies  What to do if your language syntax is too messy for Bison to handle straightforwardly.
8. Debugging Your Parser  Understanding or debugging Bison parsers.
9. Invoking Bison  How to run Bison (to produce the parser source file).
A. Bison Symbols  All the keywords of the Bison language are explained.
B. Glossary  Basic concepts are explained.
10. Frequently Asked Questions  
C. Copying This Manual  License for copying this manual.
Index  Cross-references to the text.

 -- The Detailed Node Listing ---

The Concepts of Bison

1.1 Languages and Context-Free Grammars  Languages and context-free grammars, as mathematical ideas.
1.2 From Formal Rules to Bison Input  How we represent grammars for Bison's sake.
1.3 Semantic Values  Each token or syntactic grouping can have a semantic value (the value of an integer, the name of an identifier, etc.).
1.4 Semantic Actions  Each rule can have an action containing C code.
1.5 Writing GLR Parsers  Writing parsers for general context-free languages
1.6 Locations  Tracking Locations.
1.7 Bison Output: the Parser File  What are Bison's input and output, how is the output used?
1.8 Stages in Using Bison  Stages in writing and running Bison grammars.
1.9 The Overall Layout of a Bison Grammar  Overall structure of a Bison grammar file.


2.1 Reverse Polish Notation Calculator  Reverse polish notation calculator; a first example with no operator precedence.
2.2 Infix Notation Calculator: calc  Infix (algebraic) notation calculator. Operator precedence is introduced.
2.3 Simple Error Recovery  Continuing after syntax errors.
2.4 Location Tracking Calculator: ltcalc  Demonstrating the use of @n and @$.
2.5 Multi-Function Calculator: mfcalc  Calculator with memory and trig functions. It uses multiple data-types for semantic values.
2.6 Exercises  Ideas for improving the multi-function calculator.

Reverse Polish Notation Calculator

2.1.1 Declarations for rpcalc  Prologue (declarations) for rpcalc.
2.1.2 Grammar Rules for rpcalc  Grammar Rules for rpcalc, with explanation.
2.1.3 The rpcalc Lexical Analyzer  The lexical analyzer.
2.1.4 The Controlling Function  The controlling function.
2.1.5 The Error Reporting Routine  The error reporting function.
2.1.6 Running Bison to Make the Parser  Running Bison on the grammar file.
2.1.7 Compiling the Parser File  Run the C compiler on the output code.

Grammar Rules for rpcalc Explanation of input Explanation of line Explanation of expr  

Location Tracking Calculator: ltcalc

2.4.1 Declarations for ltcalc  Bison and C declarations for ltcalc.
2.4.2 Grammar Rules for ltcalc  Grammar rules for ltcalc, with explanations.
2.4.3 The ltcalc Lexical Analyzer.  The lexical analyzer.

Multi-Function Calculator: mfcalc

2.5.1 Declarations for mfcalc  Bison declarations for multi-function calculator.
2.5.2 Grammar Rules for mfcalc  Grammar rules for the calculator.
2.5.3 The mfcalc Symbol Table  Symbol table management subroutines.

Bison Grammar Files

3.1 Outline of a Bison Grammar  Overall layout of the grammar file.
3.2 Symbols, Terminal and Nonterminal  Terminal and nonterminal symbols.
3.3 Syntax of Grammar Rules  How to write grammar rules.
3.4 Recursive Rules  Writing recursive rules.
3.5 Defining Language Semantics  Semantic values and actions.
3.6 Tracking Locations  Locations and actions.
3.7 Bison Declarations  All kinds of Bison declarations are described here.
3.8 Multiple Parsers in the Same Program  Putting more than one Bison parser in one program.

Outline of a Bison Grammar

3.1.1 The prologue  Syntax and usage of the prologue.
3.1.2 The Bison Declarations Section  Syntax and usage of the Bison declarations section.
3.1.3 The Grammar Rules Section  Syntax and usage of the grammar rules section.
3.1.4 The epilogue  Syntax and usage of the epilogue.

Defining Language Semantics

3.5.1 Data Types of Semantic Values  Specifying one data type for all semantic values.
3.5.2 More Than One Value Type  Specifying several alternative data types.
3.5.3 Actions  An action is the semantic definition of a grammar rule.
3.5.4 Data Types of Values in Actions  Specifying data types for actions to operate on.
3.5.5 Actions in Mid-Rule  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

3.6.1 Data Type of Locations  Specifying a data type for locations.
3.6.2 Actions and Locations  Using locations in actions.
3.6.3 Default Action for Locations  Defining a general way to compute locations.

Bison Declarations

3.7.1 Token Type Names  Declaring terminal symbols.
3.7.2 Operator Precedence  Declaring terminals with precedence and associativity.
3.7.3 The Collection of Value Types  Declaring the set of all semantic value types.
3.7.4 Nonterminal Symbols  Declaring the choice of type for a nonterminal symbol.
3.7.5 Freeing Discarded Symbols  Declaring how symbols are freed.
3.7.6 Suppressing Conflict Warnings  Suppressing warnings about shift/reduce conflicts.
3.7.7 The Start-Symbol  Specifying the start symbol.
3.7.8 A Pure (Reentrant) Parser  Requesting a reentrant parser.
3.7.9 Bison Declaration Summary  Table of all Bison declarations.

Parser C-Language Interface

4.1 The Parser Function yyparse  How to call yyparse and what it returns.
4.2 The Lexical Analyzer Function yylex  You must supply a function yylex which reads tokens.
4.3 The Error Reporting Function yyerror  You must supply a function yyerror.
4.4 Special Features for Use in Actions  Special features for use in actions.

The Lexical Analyzer Function yylex

4.2.1 Calling Convention for yylex  How yyparse calls yylex.
4.2.2 Semantic Values of Tokens  How yylex must return the semantic value of the token it has read.
4.2.3 Textual Positions of Tokens  How yylex must return the text position
                        (line number, etc.) of the token, if the
                        actions want that.
4.2.4 Calling Conventions for Pure Parsers  How the calling convention differs in a pure parser (@pxref{Pure Decl, ,A Pure (Reentrant) Parser}).

The Bison Parser Algorithm

5.1 Look-Ahead Tokens  Parser looks one token ahead when deciding what to do.
5.2 Shift/Reduce Conflicts  Conflicts: when either shifting or reduction is valid.
5.3 Operator Precedence  Operator precedence works by resolving conflicts.
5.4 Context-Dependent Precedence  When an operator's precedence depends on context.
5.5 Parser States  The parser is a finite-state-machine with stack.
5.6 Reduce/Reduce Conflicts  When two rules are applicable in the same situation.
5.7 Mysterious Reduce/Reduce Conflicts  Reduce/reduce conflicts that look unjustified.
5.8 Generalized LR (GLR) Parsing  Parsing arbitrary context-free grammars.
5.9 Stack Overflow, and How to Avoid It  What happens when stack gets full. How to avoid it.

Operator Precedence

5.3.1 When Precedence is Needed  An example showing why precedence is needed.
5.3.2 Specifying Operator Precedence  How to specify precedence in Bison grammars.
5.3.3 Precedence Examples  How these features are used in the previous example.
5.3.4 How Precedence Works  How they work.

Handling Context Dependencies

7.1 Semantic Info in Token Types  Token parsing can depend on the semantic context.
7.2 Lexical Tie-ins  Token parsing can depend on the syntactic context.
7.3 Lexical Tie-ins and Error Recovery  Lexical tie-ins have implications for how error recovery rules must be written.

Debugging Your Parser

8.1 Understanding Your Parser  Understanding the structure of your parser.
8.2 Tracing Your Parser  Tracing the execution of your parser.

Invoking Bison

9.1 Bison Options  All the options described in detail, in alphabetical order by short options.
9.2 Option Cross Key  Alphabetical list of long options.
9.3 Yacc Library  Yacc-compatible yylex and main.

Frequently Asked Questions

10.1 Parser Stack Overflow  Breaking the Stack Limits

Copying This Manual

C.1 GNU Free Documentation License  License for copying this manual.

  webmaster   donations   bookstore     delorie software   privacy  
  Copyright 2003   by The Free Software Foundation     Updated Jun 2003