bison.texinfo

bison源代码.bison 是替代yacc的语法分析程序生成器. yacc是 Yet Another Compiler Compiler的缩写. bison又是什么呐 是一个生成可以分析文本文件结构

\input texinfo @c -*-texinfo-*-
@comment %**start of header
@setfilename bison.info
@settitle Bison 1.25
@setchapternewpage odd

@iftex
@finalout
@end iftex

@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 next time, consider using @set for edition number, etc...

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

@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

@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

@ifinfo
This file documents the Bison parser generator.

Copyright (C) 1988, 89, 90, 91, 92, 93, 1995 Free Software Foundation, Inc.

Permission is granted to make and distribute verbatim copies of
this manual provided the copyright notice and this permission notice
are preserved on all copies.

@ignore
Permission is granted to process this file through Tex and print the
results, provided the printed document carries copying permission
notice identical to this one except for the removal of this paragraph
(this paragraph not being relevant to the printed manual).

@end ignore
Permission is granted to copy and distribute modified versions of this
manual under the conditions for verbatim copying, provided also that the
sections entitled ``GNU General Public License'' and ``Conditions for
Using Bison'' are included exactly as in the original, and provided that
the entire resulting derived work is distributed under the terms of a
permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual
into another language, under the above conditions for modified versions,
except that the sections entitled ``GNU General Public License'',
``Conditions for Using Bison'' and this permission notice may be
included in translations approved by the Free Software Foundation
instead of in the original English.
@end ifinfo

@ifset shorttitlepage-enabled
@shorttitlepage Bison
@end ifset
@titlepage
@title Bison
@subtitle The YACC-compatible Parser Generator
@subtitle November 1995, Bison Version 1.25

@author by Charles Donnelly and Richard Stallman

@page
@vskip 0pt plus 1filll
Copyright @copyright{} 1988, 89, 90, 91, 92, 93, 1995 Free Software
Foundation 

@sp 2
Published by the Free Software Foundation @*
59 Temple Place, Suite 330 @*
Boston, MA  02111-1307  USA @*
Printed copies are available for $15 each.@*
ISBN 1-882114-45-0

Permission is granted to make and distribute verbatim copies of
this manual provided the copyright notice and this permission notice
are preserved on all copies.

@ignore
Permission is granted to process this file through TeX and print the
results, provided the printed document carries copying permission
notice identical to this one except for the removal of this paragraph
(this paragraph not being relevant to the printed manual).

@end ignore
Permission is granted to copy and distribute modified versions of this
manual under the conditions for verbatim copying, provided also that the
sections entitled ``GNU General Public License'' and ``Conditions for
Using Bison'' are included exactly as in the original, and provided that
the entire resulting derived work is distributed under the terms of a
permission notice identical to this one.

Permission is granted to copy and distribute translations of this manual
into another language, under the above conditions for modified versions,
except that the sections entitled ``GNU General Public License'',
``Conditions for Using Bison'' and this permission notice may be
included in translations approved by the Free Software Foundation
instead of in the original English.
@sp 2
Cover art by Etienne Suvasa.
@end titlepage
@page

@node Top, Introduction, (dir), (dir)

@ifinfo
This manual documents version 1.25 of Bison.
@end ifinfo

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

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

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

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 Positions::   How @code{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 (@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.
* 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.
@end menu

@node Introduction, Conditions, Top, Top
@unnumbered Introduction
@cindex introduction

@dfn{Bison} is a general-purpose parser generator that converts a
grammar description for an LALR(1) context-free grammar into a C
program to parse that grammar.  Once you are proficient with Bison,
you may use it to develop a wide range of language parsers, from those
used in simple desk calculators to complex programming languages.

Bison is upward compatible with Yacc: all properly-written Yacc grammars
ought to work with Bison with no change.  Anyone familiar with Yacc
should be able to use Bison with little trouble.  You need to be fluent in
C programming in order to use Bison or to understand this manual.

We begin with tutorial chapters that explain the basic concepts of using
Bison and show three explained examples, each building on the last.  If you
don't know Bison or Yacc, start by reading these chapters.  Reference
chapters follow which describe specific aspects of Bison in detail.

Bison was written primarily by Robert Corbett; Richard Stallman made it
Yacc-compatible.  Wilfred Hansen of Carnegie Mellon University added
multicharacter string literals and other features.

This edition corresponds to version 1.25 of Bison.

@node Conditions, Copying, Introduction, Top
@unnumbered Conditions for Using Bison