Table of Contents

Introduction
Conditions for Using Bison
GNU GENERAL PUBLIC LICENSE

Preamble
How to Apply These Terms to Your New Programs

1. The Concepts of Bison

1.1 Languages and Context-Free Grammars
1.2 From Formal Rules to Bison Input
1.3 Semantic Values
1.4 Semantic Actions
1.5 Bison Output: the Parser File
1.6 Stages in Using Bison
1.7 The Overall Layout of a Bison Grammar

2. Examples

2.1 Reverse Polish Notation Calculator

2.1.1 Declarations for rpcalc
2.1.2 Grammar Rules for rpcalc

2.1.2.1 Explanation of input
2.1.2.2 Explanation of line
2.1.2.3 Explanation of expr

2.1.3 The rpcalc Lexical Analyzer
2.1.4 The Controlling Function
2.1.5 The Error Reporting Routine
2.1.6 Running Bison to Make the Parser
2.1.7 Compiling the Parser File

2.2 Infix Notation Calculator: calc
2.3 Simple Error Recovery
2.4 Multi-Function Calculator: mfcalc

2.4.1 Declarations for mfcalc
2.4.2 Grammar Rules for mfcalc
2.4.3 The mfcalc Symbol Table

2.5 Exercises

3. Bison Grammar Files

3.1 Outline of a Bison Grammar

3.1.1 The C Declarations Section
3.1.2 The Bison Declarations Section
3.1.3 The Grammar Rules Section
3.1.4 The Additional C Code Section

3.2 Symbols, Terminal and Nonterminal
3.3 Syntax of Grammar Rules
3.4 Recursive Rules
3.5 Defining Language Semantics

3.5.1 Data Types of Semantic Values
3.5.2 More Than One Value Type
3.5.3 Actions
3.5.4 Data Types of Values in Actions
3.5.5 Actions in Mid-Rule

3.6 Bison Declarations

3.6.1 Token Type Names
3.6.2 Operator Precedence
3.6.3 The Collection of Value Types
3.6.4 Nonterminal Symbols
3.6.5 Suppressing Conflict Warnings
3.6.6 The Start-Symbol
3.6.7 A Pure (Reentrant) Parser
3.6.8 Bison Declaration Summary

3.7 Multiple Parsers in the Same Program

4. Parser C-Language Interface

4.1 The Parser Function yyparse
4.2 The Lexical Analyzer Function yylex

4.2.1 Calling Convention for yylex
4.2.2 Semantic Values of Tokens
4.2.3 Textual Positions of Tokens
4.2.4 Calling Conventions for Pure Parsers

4.3 The Error Reporting Function yyerror
4.4 Special Features for Use in Actions

5. The Bison Parser Algorithm

5.1 Look-Ahead Tokens
5.2 Shift/Reduce Conflicts
5.3 Operator Precedence

5.3.1 When Precedence is Needed
5.3.2 Specifying Operator Precedence
5.3.3 Precedence Examples
5.3.4 How Precedence Works

5.4 Context-Dependent Precedence
5.5 Parser States
5.6 Reduce/Reduce Conflicts
5.7 Mysterious Reduce/Reduce Conflicts
5.8 Stack Overflow, and How to Avoid It

6. Error Recovery
7. Handling Context Dependencies

7.1 Semantic Info in Token Types
7.2 Lexical Tie-ins
7.3 Lexical Tie-ins and Error Recovery

8. Debugging Your Parser
9. Invoking Bison

9.1 Bison Options
9.2 Option Cross Key
9.3 Invoking Bison under VMS

A. Bison Symbols
B. Glossary
Index