(bison.info)Top

Next: Introduction Up: (dir)


Bison
*****



   This manual is for GNU Bison (version 1.875, 28 December 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."

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 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.
GLR Parsers: Writing parsers for general context-free languages
Locations Overview: Tracking Locations.
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 DeclsPrologue (declarations) for rpcalc.
Rules: Rpcalc RulesGrammar Rules for rpcalc, with explanation.
Lexer: Rpcalc LexerThe lexical analyzer.
Main: Rpcalc MainThe controlling function.
Error: Rpcalc ErrorThe error reporting function.
Gen: Rpcalc GenRunning Bison on the grammar file.
Comp: Rpcalc CompileRun the C compiler on the output code.

Grammar Rules for `rpcalc'

Rpcalc Input
Rpcalc Line
Rpcalc Expr

Location Tracking Calculator: `ltcalc'

Decls: Ltcalc DeclsBison and C declarations for ltcalc.
Rules: Ltcalc RulesGrammar rules for ltcalc, with explanations.
Lexer: Ltcalc LexerThe lexical analyzer.

Multi-Function Calculator: `mfcalc'

Decl: Mfcalc DeclBison declarations for multi-function calculator.
Rules: Mfcalc RulesGrammar rules for the calculator.
Symtab: Mfcalc SymtabSymbol 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.
Locations: Locations 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.
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.

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.

Tracking Locations

Location Type: Specifying a data type for locations.
Actions and Locations: Using locations in actions.
Location Default Action: Defining a general way to compute locations.

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.
Destructor Decl: Declaring how symbols are freed.
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.
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.

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.
Yacc Library: Yacc-compatible `yylex' and `main'.

Frequently Asked Questions

Parser Stack Overflow: Breaking the Stack Limits

Copying This Manual

GNU Free Documentation License: License for copying this manual.

automatically generated by info2www