(bison) Top
Info Catalog
(dir) Top
(bison) Introduction
Bison
*****
This manual is for GNU Bison (version 1.75, 14 October 2002), the
GNU parser generator.
Copyright (C) 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998, 1999,
2000, 2001, 2002 Free Software Foundation, Inc.
Permission is granted to copy, distribute and/or modify this
document under the terms of the GNU Free Documentation License,
Version 1.1 or any later version published by the Free Software
Foundation; with no Invariant Sections, with the Front-Cover texts
being "A GNU Manual," and with the Back-Cover Texts as in (a)
below. A copy of the license is included in the section entitled
"GNU Free Documentation License."
(a) The FSF's Back-Cover Text is: "You have freedom to copy and
modify this GNU Manual, like GNU software. Copies published by
the Free Software Foundation raise funds for GNU development."
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 Understanding or debugging Bison parsers.
* 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.
* FAQ Frequently Asked Questions
* 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. Prologue (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
* Prologue Syntax and usage of the prologue (declarations section).
* Bison Declarations Syntax and usage of the Bison declarations section.
* Grammar Rules Syntax and usage of the grammar rules section.
* Epilogue Syntax and usage of the epilogue (additional 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 ( 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.
* Generalized LR Parsing Parsing arbitrary context-free grammars.
* 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.
Understanding or Debugging Your Parser
* Understanding Understanding the structure of your parser.
* Tracing Tracing the execution of your parser.
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.
Frequently Asked Questions
* Parser Stack Overflow Breaking the Stack Limits
Copying This Manual
* GNU Free Documentation License License for copying this manual.
Info Catalog
(dir) Top
(bison) Introduction
automatically generated byinfo2html