GNU Info
Info Node: (bison.info)Top
(bison.info)Top
Bison
*****
This manual documents version 1.35 of Bison, updated 25 February
2002.
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- 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
Location Tracking Calculator: `ltcalc'
Decls- Ltcalc Decls. Bison and C declarations for ltcalc.
Rules- Ltcalc Rules. Grammar rules for ltcalc, with explanations.
Lexer- Ltcalc Lexer. The lexical analyzer.
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 (Note: 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.
automatically generated by info2www version 1.2.2.9
|