bison.texinfo

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

to the parse that interprets the example as a
@code{decl}, which implies that @code{x} is a declarator.
The parser therefore prints

@example
"x" y z + T <init-declare>
@end example

The @code{%dprec} declarations only come into play when more than one
parse survives.  Consider a different input string for this parser:

@example
T (x) + y;
@end example

@noindent
This is another example of using @acronym{GLR} to parse an unambiguous
construct, as shown in the previous section (@pxref{Simple GLR Parsers}).
Here, there is no ambiguity (this cannot be parsed as a declaration).
However, at the time the Bison parser encounters @code{x}, it does not
have enough information to resolve the reduce/reduce conflict (again,
between @code{x} as an @code{expr} or a @code{declarator}).  In this
case, no precedence declaration is used.  Again, the parser splits
into two, one assuming that @code{x} is an @code{expr}, and the other
assuming @code{x} is a @code{declarator}.  The second of these parsers
then vanishes when it sees @code{+}, and the parser prints

@example
x T <cast> y +
@end example

Suppose that instead of resolving the ambiguity, you wanted to see all
the possibilities.  For this purpose, you must merge the semantic
actions of the two possible parsers, rather than choosing one over the
other.  To do so, you could change the declaration of @code{stmt} as
follows:

@example
stmt : expr ';'  %merge <stmtMerge>
     | decl      %merge <stmtMerge>
     ;
@end example

@noindent
and define the @code{stmtMerge} function as:

@example
static YYSTYPE
stmtMerge (YYSTYPE x0, YYSTYPE x1)
@{
  printf ("<OR> ");
  return "";
@}
@end example

@noindent
with an accompanying forward declaration
in the C declarations at the beginning of the file:

@example
%@{
  #define YYSTYPE char const *
  static YYSTYPE stmtMerge (YYSTYPE x0, YYSTYPE x1);
%@}
@end example

@noindent
With these declarations, the resulting parser parses the first example
as both an @code{expr} and a @code{decl}, and prints

@example
"x" y z + T <init-declare> x T <cast> y z + = <OR>
@end example

Bison requires that all of the
productions that participate in any particular merge have identical
@samp{%merge} clauses.  Otherwise, the ambiguity would be unresolvable,
and the parser will report an error during any parse that results in
the offending merge.

@node Compiler Requirements
@subsection Considerations when Compiling @acronym{GLR} Parsers
@cindex @code{inline}
@cindex @acronym{GLR} parsers and @code{inline}

The @acronym{GLR} parsers require a compiler for @acronym{ISO} C89 or
later.  In addition, they use the @code{inline} keyword, which is not
C89, but is C99 and is a common extension in pre-C99 compilers.  It is
up to the user of these parsers to handle
portability issues.  For instance, if using Autoconf and the Autoconf
macro @code{AC_C_INLINE}, a mere

@example
%@{
  #include <config.h>
%@}
@end example

@noindent
will suffice.  Otherwise, we suggest

@example
%@{
  #if __STDC_VERSION__ < 199901 && ! defined __GNUC__ && ! defined inline
   #define inline
  #endif
%@}
@end example

@node Locations Overview
@section Locations
@cindex location
@cindex textual location
@cindex location, textual

Many applications, like interpreters or compilers, have to produce verbose
and useful error messages.  To achieve this, one must be able to keep track of
the @dfn{textual location}, or @dfn{location}, of each syntactic construct.
Bison provides a mechanism for handling these locations.

Each token has a semantic value.  In a similar fashion, each token has an
associated location, but the type of locations is the same for all tokens and
groupings.  Moreover, the output parser is equipped with a default data
structure for storing locations (@pxref{Locations}, for more details).

Like semantic values, locations can be reached in actions using a dedicated
set of constructs.  In the example above, the location of the whole grouping
is @code{@@$}, while the locations of the subexpressions are @code{@@1} and
@code{@@3}.

When a rule is matched, a default action is used to compute the semantic value
of its left hand side (@pxref{Actions}).  In the same way, another default
action is used for locations.  However, the action for locations is general
enough for most cases, meaning there is usually no need to describe for each
rule how @code{@@$} should be formed.  When building a new location for a given
grouping, the default behavior of the output parser is to take the beginning
of the first symbol, and the end of the last symbol.

@node Bison Parser
@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 symbols defined in the Bison parser file itself
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.

In some cases the Bison parser file includes system headers, and in
those cases your code should respect the identifiers reserved by those
headers.  On some non-@acronym{GNU} hosts, @code{<alloca.h>},
@code{<stddef.h>}, and @code{<stdlib.h>} are included as needed to
declare memory allocators and related types.  @code{<libintl.h>} is
included if message translation is in use
(@pxref{Internationalization}).  Other system headers may
be included if you define @code{YYDEBUG} to a nonzero value
(@pxref{Tracing, ,Tracing Your Parser}).

@node Stages
@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
@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{Prologue}
%@}

@var{Bison declarations}

%%
@var{Grammar rules}
%%
@var{Epilogue}
@end example

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

The prologue 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.
You need to declare the lexical analyzer @code{yylex} and the error
printer @code{yyerror} here, along with any other global identifiers
used by the actions in the grammar rules.

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 epilogue can contain any code you want to use.  Often the
definitions of functions declared in the prologue go here.  In a
simple program, all the rest of the program can go here.

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

@node RPN Calc
@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.  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.
@end menu

@node Rpcalc Decls
@subsection Declarations for @code{rpcalc}