- 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 (see 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.
- 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.