bison.texinfo

GNU的词法/语法分析器bison源码

\input texinfo @c -*-texinfo-*-
@comment %**start of header
@setfilename bison.info
@include version.texi
@settitle Bison @value{VERSION}
@setchapternewpage odd

@finalout

@c SMALL BOOK version
@c This edition has been formatted so that you can format and print it in
@c the smallbook format.
@c @smallbook

@c Set following if you have the new `shorttitlepage' command
@c @clear shorttitlepage-enabled
@c @set shorttitlepage-enabled

@c Set following if you want to document %default-prec and %no-default-prec.
@c This feature is experimental and may change in future Bison versions.
@c @set defaultprec

@c ISPELL CHECK: done, 14 Jan 1993 --bob

@c Check COPYRIGHT dates.  should be updated in the titlepage, ifinfo
@c titlepage; should NOT be changed in the GPL.  --mew

@c FIXME: I don't understand this `iftex'.  Obsolete? --akim.
@iftex
@syncodeindex fn cp
@syncodeindex vr cp
@syncodeindex tp cp
@end iftex
@ifinfo
@synindex fn cp
@synindex vr cp
@synindex tp cp
@end ifinfo
@comment %**end of header

@copying

This manual is for @acronym{GNU} Bison (version @value{VERSION},
@value{UPDATED}), the @acronym{GNU} parser generator.

Copyright @copyright{} 1988, 1989, 1990, 1991, 1992, 1993, 1995, 1998,
1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.

@quotation
Permission is granted to copy, distribute and/or modify this document
under the terms of the @acronym{GNU} Free Documentation License,
Version 1.2 or any later version published by the Free Software
Foundation; with no Invariant Sections, with the Front-Cover texts
being ``A @acronym{GNU} Manual,'' and with the Back-Cover Texts as in
(a) below.  A copy of the license is included in the section entitled
``@acronym{GNU} Free Documentation License.''

(a) The @acronym{FSF}'s Back-Cover Text is: ``You have freedom to copy
and modify this @acronym{GNU} Manual, like @acronym{GNU} software.
Copies published by the Free Software Foundation raise funds for
@acronym{GNU} development.''
@end quotation
@end copying

@dircategory Software development
@direntry
* bison: (bison).       @acronym{GNU} parser generator (Yacc replacement).
@end direntry

@ifset shorttitlepage-enabled
@shorttitlepage Bison
@end ifset
@titlepage
@title Bison
@subtitle The Yacc-compatible Parser Generator
@subtitle @value{UPDATED}, Bison Version @value{VERSION}

@author by Charles Donnelly and Richard Stallman

@page
@vskip 0pt plus 1filll
@insertcopying
@sp 2
Published by the Free Software Foundation @*
51 Franklin Street, Fifth Floor @*
Boston, MA  02110-1301  USA @*
Printed copies are available from the Free Software Foundation.@*
@acronym{ISBN} 1-882114-44-2
@sp 2
Cover art by Etienne Suvasa.
@end titlepage

@contents

@ifnottex
@node Top
@top Bison
@insertcopying
@end ifnottex

@menu
* Introduction::
* Conditions::
* Copying::           The @acronym{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 @code{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).
* C++ Language Interface::  Creating C++ parser objects.
* FAQ::               Frequently Asked Questions
* 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.

@detailmenu
 --- 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.

Writing @acronym{GLR} Parsers

* Simple GLR Parsers::          Using @acronym{GLR} parsers on unambiguous grammars
* Merging GLR Parses::          Using @acronym{GLR} parsers to resolve ambiguities
* Compiler Requirements::       @acronym{GLR} parsers require a modern C compiler

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 @@@var{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 @code{rpcalc}

* Rpcalc Input::
* Rpcalc Line::
* Rpcalc Expr::

Location Tracking Calculator: @code{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: @code{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.
* 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.
* Initial Action Decl::  Code run before parsing starts.
* Destructor Decl::   Declaring how symbols are freed.
* Expect Decl::       Suppressing warnings about parsing 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 @code{yyparse} and what it returns.
* Lexical::           You must supply a function @code{yylex}
                        which reads tokens.
* Error Reporting::   You must supply a function @code{yyerror}.
* Action Features::   Special features for use in actions.
* Internationalization::  How to let the parser speak in the user's
                        native language.

The Lexical Analyzer Function @code{yylex}

* Calling Convention::  How @code{yyparse} calls @code{yylex}.
* Token Values::      How @code{yylex} must return the semantic value
                        of the token it has read.
* Token Locations::   How @code{yylex} must return the text location
                        (line number, etc.) of the token, if the
                        actions want that.
* Pure Calling::      How the calling convention differs
                        in a pure parser (@pxref{Pure Decl, ,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.
* Memory Management:: What happens when memory is exhausted.  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 @code{yylex} and @code{main}.

C++ Language Interface

* C++ Parsers::                 The interface to generate C++ parser classes
* A Complete C++ Example::      Demonstrating their use

C++ Parsers

* C++ Bison Interface::         Asking for C++ parser generation
* C++ Semantic Values::         %union vs. C++
* C++ Location Values::         The position and location classes
* C++ Parser Interface::        Instantiating and running the parser
* C++ Scanner Interface::       Exchanges between yylex and parse

A Complete C++ Example

* Calc++ --- C++ Calculator::   The specifications
* Calc++ Parsing Driver::       An active parsing context
* Calc++ Parser::               A parser class
* Calc++ Scanner::              A pure C++ Flex scanner
* Calc++ Top Level::            Conducting the band

Frequently Asked Questions

* Memory Exhausted::           Breaking the Stack Limits
* How Can I Reset the Parser:: @code{yyparse} Keeps some State
* Strings are Destroyed::      @code{yylval} Loses Track of Strings
* Implementing Gotos/Loops::   Control Flow in the Calculator

Copying This Manual

* GNU Free Documentation License::  License for copying this manual.

@end detailmenu
@end menu

@node Introduction
@unnumbered Introduction
@cindex introduction

@dfn{Bison} is a general-purpose parser generator that converts a
grammar description for an @acronym{LALR}(1) context-free grammar into a C
program to parse that grammar.  Once you are proficient with Bison,