bison.texinfo

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

language, an expression typically has a semantic value that is a tree
structure describing the meaning of the expression.

@node Semantic Actions, Bison Parser, Semantic Values, Concepts
@section Semantic Actions
@cindex semantic actions
@cindex actions, semantic

In order to be useful, a program must do more than parse input; it must
also produce some output based on the input.  In a Bison grammar, a grammar
rule can have an @dfn{action} made up of C statements.  Each time the
parser recognizes a match for that rule, the action is executed.
@xref{Actions}.
        
Most of the time, the purpose of an action is to compute the semantic value
of the whole construct from the semantic values of its parts.  For example,
suppose we have a rule which says an expression can be the sum of two
expressions.  When the parser recognizes such a sum, each of the
subexpressions has a semantic value which describes how it was built up.
The action for this rule should create a similar sort of value for the
newly recognized larger expression.

For example, here is a rule that says an expression can be the sum of
two subexpressions:

@example
expr: expr '+' expr   @{ $$ = $1 + $3; @}
        ;
@end example

@noindent
The action says how to produce the semantic value of the sum expression
from the values of the two subexpressions.

@node Bison Parser, Stages, Semantic Actions, Concepts
@section Bison Output: the Parser File
@cindex Bison parser
@cindex Bison utility
@cindex lexical analyzer, purpose
@cindex parser

When you run Bison, you give it a Bison grammar file as input.  The output
is a C source file that parses the language described by the grammar.
This file is called a @dfn{Bison parser}.  Keep in mind that the Bison
utility and the Bison parser are two distinct programs: the Bison utility
is a program whose output is the Bison parser that becomes part of your
program.

The job of the Bison parser is to group tokens into groupings according to
the grammar rules---for example, to build identifiers and operators into
expressions.  As it does this, it runs the actions for the grammar rules it
uses.

The tokens come from a function called the @dfn{lexical analyzer} that you
must supply in some fashion (such as by writing it in C).  The Bison parser
calls the lexical analyzer each time it wants a new token.  It doesn't know
what is ``inside'' the tokens (though their semantic values may reflect
this).  Typically the lexical analyzer makes the tokens by parsing
characters of text, but Bison does not depend on this.  @xref{Lexical, ,The Lexical Analyzer Function @code{yylex}}.

The Bison parser file is C code which defines a function named
@code{yyparse} which implements that grammar.  This function does not make
a complete C program: you must supply some additional functions.  One is
the lexical analyzer.  Another is an error-reporting function which the
parser calls to report an error.  In addition, a complete C program must
start with a function called @code{main}; you have to provide this, and
arrange for it to call @code{yyparse} or the parser will never run.
@xref{Interface, ,Parser C-Language Interface}.

Aside from the token type names and the symbols in the actions you
write, all variable and function names used in the Bison parser file
begin with @samp{yy} or @samp{YY}.  This includes interface functions
such as the lexical analyzer function @code{yylex}, the error reporting
function @code{yyerror} and the parser function @code{yyparse} itself.
This also includes numerous identifiers used for internal purposes.
Therefore, you should avoid using C identifiers starting with @samp{yy}
or @samp{YY} in the Bison grammar file except for the ones defined in
this manual.

@node Stages, Grammar Layout, Bison Parser, Concepts
@section Stages in Using Bison
@cindex stages in using Bison
@cindex using Bison

The actual language-design process using Bison, from grammar specification
to a working compiler or interpreter, has these parts:

@enumerate
@item
Formally specify the grammar in a form recognized by Bison
(@pxref{Grammar File, ,Bison Grammar Files}).  For each grammatical rule in the language,
describe the action that is to be taken when an instance of that rule
is recognized.  The action is described by a sequence of C statements.

@item
Write a lexical analyzer to process input and pass tokens to the
parser.  The lexical analyzer may be written by hand in C
(@pxref{Lexical, ,The Lexical Analyzer Function @code{yylex}}).  It could also be produced using Lex, but the use
of Lex is not discussed in this manual.

@item
Write a controlling function that calls the Bison-produced parser.

@item
Write error-reporting routines.
@end enumerate

To turn this source code as written into a runnable program, you
must follow these steps:

@enumerate
@item
Run Bison on the grammar to produce the parser.

@item
Compile the code output by Bison, as well as any other source files.

@item
Link the object files to produce the finished product.
@end enumerate

@node Grammar Layout,  , Stages, Concepts
@section The Overall Layout of a Bison Grammar
@cindex grammar file
@cindex file format
@cindex format of grammar file
@cindex layout of Bison grammar

The input file for the Bison utility is a @dfn{Bison grammar file}.  The
general form of a Bison grammar file is as follows:

@example
%@{
@var{C declarations}
%@}

@var{Bison declarations}

%%
@var{Grammar rules}
%%
@var{Additional C code}
@end example

@noindent
The @samp{%%}, @samp{%@{} and @samp{%@}} are punctuation that appears
in every Bison grammar file to separate the sections.

The C declarations may define types and variables used in the actions.
You can also use preprocessor commands to define macros used there, and use
@code{#include} to include header files that do any of these things.

The Bison declarations declare the names of the terminal and nonterminal
symbols, and may also describe operator precedence and the data types of
semantic values of various symbols.

The grammar rules define how to construct each nonterminal symbol from its
parts.

The additional C code can contain any C code you want to use.  Often the
definition of the lexical analyzer @code{yylex} goes here, plus subroutines
called by the actions in the grammar rules.  In a simple program, all the
rest of the program can go here.

@node Examples, Grammar File, Concepts, Top
@chapter Examples
@cindex simple examples
@cindex examples, simple

Now we show and explain three sample programs written using Bison: a
reverse polish notation calculator, an algebraic (infix) notation
calculator, and a multi-function calculator.  All three have been tested
under BSD Unix 4.3; each produces a usable, though limited, interactive
desk-top calculator.

These examples are simple, but Bison grammars for real programming
languages are written the same way.
@ifinfo
You can copy these examples out of the Info file and into a source file
to try them.
@end ifinfo

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

@node RPN Calc, Infix Calc,  , Examples
@section Reverse Polish Notation Calculator
@cindex reverse polish notation
@cindex polish notation calculator
@cindex @code{rpcalc}
@cindex calculator, simple

The first example is that of a simple double-precision @dfn{reverse polish
notation} calculator (a calculator using postfix operators).  This example
provides a good starting point, since operator precedence is not an issue.
The second example will illustrate how operator precedence is handled.

The source code for this calculator is named @file{rpcalc.y}.  The
@samp{.y} extension is a convention used for Bison input files.

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

@node Rpcalc Decls, Rpcalc Rules,  , RPN Calc
@subsection Declarations for @code{rpcalc}

Here are the C and Bison declarations for the reverse polish notation
calculator.  As in C, comments are placed between @samp{/*@dots{}*/}.

@example
/* Reverse polish notation calculator. */

%@{
#define YYSTYPE double
#include <math.h>
%@}

%token NUM

%% /* Grammar rules and actions follow */
@end example

The C declarations section (@pxref{C Declarations, ,The C Declarations Section}) contains two
preprocessor directives.

The @code{#define} directive defines the macro @code{YYSTYPE}, thus
specifying the C data type for semantic values of both tokens and groupings
(@pxref{Value Type, ,Data Types of Semantic Values}).  The Bison parser will use whatever type
@code{YYSTYPE} is defined as; if you don't define it, @code{int} is the
default.  Because we specify @code{double}, each token and each expression
has an associated value, which is a floating point number.

The @code{#include} directive is used to declare the exponentiation
function @code{pow}.

The second section, Bison declarations, provides information to Bison about
the token types (@pxref{Bison Declarations, ,The Bison Declarations Section}).  Each terminal symbol that is
not a single-character literal must be declared here.  (Single-character
literals normally don't need to be declared.)  In this example, all the
arithmetic operators are designated by single-character literals, so the
only terminal symbol that needs to be declared is @code{NUM}, the token
type for numeric constants.

@node Rpcalc Rules, Rpcalc Lexer, Rpcalc Decls, RPN Calc
@subsection Grammar Rules for @code{rpcalc}

Here are the grammar rules for the reverse polish notation calculator.

@example
input:    /* empty */
        | input line
;

line:     '\n'
        | exp '\n'  @{ printf ("\t%.10g\n", $1); @}
;

exp:      NUM             @{ $$ = $1;         @}
        | exp exp '+'     @{ $$ = $1 + $2;    @}
        | exp exp '-'     @{ $$ = $1 - $2;    @}
        | exp exp '*'     @{ $$ = $1 * $2;    @}
        | exp exp '/'     @{ $$ = $1 / $2;    @}
      /* Exponentiation */
        | exp exp '^'     @{ $$ = pow ($1, $2); @}
      /* Unary minus    */
        | exp 'n'         @{ $$ = -$1;        @}
;
%%
@end example

The groupings of the rpcalc ``language'' defined here are the expression
(given the name @code{exp}), the line of input (@code{line}), and the
complete input transcript (@code{input}).  Each of these nonterminal
symbols has several alternate rules, joined by the @samp{|} punctuator
which is read as ``or''.  The following sections explain what these rules
mean.

The semantics of the language is determined by the actions taken when a
grouping is recognized.  The actions are the C code that appears inside
braces.  @xref{Actions}.

You must specify these actions in C, but Bison provides the means for
passing semantic values between the rules.  In each action, the
pseudo-variable @code{$$} stands for the semantic value for the grouping
that the rule is going to construct.  Assigning a value to @code{$$} is the
main job of most actions.  The semantic values of the components of the
rule are referred to as @code{$1}, @code{$2}, and so on.

@menu
* Rpcalc Input::      
* Rpcalc Line::       
* Rpcalc Expr::       
@end menu

@node Rpcalc Input, Rpcalc Line,  , Rpcalc Rules
@subsubsection Explanation of @code{input}

Consider the definition of @code{input}:

@example
input:    /* empty */