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.