- 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.
- Copying This Manual: License for copying this manual.
- Index: Cross-references to the text.
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.
- 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: Bison and C declarations for rpcalc.
- Rules: Grammar Rules for rpcalc, with explanation.
- Lexer: The lexical analyzer.
- Main: The controlling function.
- Error: The error reporting function.
- Gen: Running Bison on the grammar file.
- Comp: Run the C compiler on the output code.
Grammar Rules for rpcalc
- Rpcalc Input:
- Rpcalc Line:
- Rpcalc Expr:
Location Tracking Calculator: ltcalc
- Decls: Bison and C declarations for ltcalc.
- Rules: Grammar rules for ltcalc, with explanations.
- Lexer: The lexical analyzer.
Multi-Function Calculator: mfcalc
- Decl: Bison declarations for multi-function calculator.
- Rules: Grammar rules for the calculator.
- 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).
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.
- Extension Limitations Under DOS: Bison output files extension differences
depending on the DOS/Windows file system flavour used.
- VMS Invocation: Bison command syntax on VMS.
Copying This Manual
- GNU Free Documentation License: License for copying this manual.