bison.texinfo

GNU的词法/语法分析器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
multi-character string literals and other features.

This edition corresponds to version @value{VERSION} of Bison.

@node Conditions
@unnumbered Conditions for Using Bison

As of Bison version 1.24, we have changed the distribution terms for
@code{yyparse} to permit using Bison's output in nonfree programs when
Bison is generating C code for @acronym{LALR}(1) parsers.  Formerly, these
parsers could be used only in programs that were free software.

The other @acronym{GNU} programming tools, such as the @acronym{GNU} C
compiler, have never
had such a requirement.  They could always be used for nonfree
software.  The reason Bison was different was not due to a special
policy decision; it resulted from applying the usual General Public
License to all of the Bison source code.

The output of the Bison utility---the Bison parser file---contains a
verbatim copy of a sizable piece of Bison, which is the code for the
@code{yyparse} function.  (The actions from your grammar are inserted
into this function at one point, but the rest of the function is not
changed.)  When we applied the @acronym{GPL} terms to the code for
@code{yyparse},
the effect was to restrict the use of Bison output to free software.

We didn't change the terms because of sympathy for people who want to
make software proprietary.  @strong{Software should be free.}  But we
concluded that limiting Bison's use to free software was doing little to
encourage people to make other software free.  So we decided to make the
practical conditions for using Bison match the practical conditions for
using the other @acronym{GNU} tools.

This exception applies only when Bison is generating C code for an
@acronym{LALR}(1) parser; otherwise, the @acronym{GPL} terms operate
as usual.  You can
tell whether the exception applies to your @samp{.c} output file by
inspecting it to see whether it says ``As a special exception, when
this file is copied by Bison into a Bison output file, you may use
that output file without restriction.''

@include gpl.texi

@node Concepts
@chapter The Concepts of Bison

This chapter introduces many of the basic concepts without which the
details of Bison will not make sense.  If you do not already know how to
use Bison or Yacc, we suggest you start by reading this chapter carefully.

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

@node Language and Grammar
@section Languages and Context-Free Grammars

@cindex context-free grammar
@cindex grammar, context-free
In order for Bison to parse a language, it must be described by a
@dfn{context-free grammar}.  This means that you specify one or more
@dfn{syntactic groupings} and give rules for constructing them from their
parts.  For example, in the C language, one kind of grouping is called an
`expression'.  One rule for making an expression might be, ``An expression
can be made of a minus sign and another expression''.  Another would be,
``An expression can be an integer''.  As you can see, rules are often
recursive, but there must be at least one rule which leads out of the
recursion.

@cindex @acronym{BNF}
@cindex Backus-Naur form
The most common formal system for presenting such rules for humans to read
is @dfn{Backus-Naur Form} or ``@acronym{BNF}'', which was developed in
order to specify the language Algol 60.  Any grammar expressed in
@acronym{BNF} is a context-free grammar.  The input to Bison is
essentially machine-readable @acronym{BNF}.

@cindex @acronym{LALR}(1) grammars
@cindex @acronym{LR}(1) grammars
There are various important subclasses of context-free grammar.  Although it
can handle almost all context-free grammars, Bison is optimized for what
are called @acronym{LALR}(1) grammars.
In brief, in these grammars, it must be possible to
tell how to parse any portion of an input string with just a single
token of look-ahead.  Strictly speaking, that is a description of an
@acronym{LR}(1) grammar, and @acronym{LALR}(1) involves additional
restrictions that are
hard to explain simply; but it is rare in actual practice to find an
@acronym{LR}(1) grammar that fails to be @acronym{LALR}(1).
@xref{Mystery Conflicts, ,Mysterious Reduce/Reduce Conflicts}, for
more information on this.

@cindex @acronym{GLR} parsing
@cindex generalized @acronym{LR} (@acronym{GLR}) parsing
@cindex ambiguous grammars
@cindex non-deterministic parsing

Parsers for @acronym{LALR}(1) grammars are @dfn{deterministic}, meaning
roughly that the next grammar rule to apply at any point in the input is
uniquely determined by the preceding input and a fixed, finite portion
(called a @dfn{look-ahead}) of the remaining input.  A context-free
grammar can be @dfn{ambiguous}, meaning that there are multiple ways to
apply the grammar rules to get the same inputs.  Even unambiguous
grammars can be @dfn{non-deterministic}, meaning that no fixed
look-ahead always suffices to determine the next grammar rule to apply.
With the proper declarations, Bison is also able to parse these more
general context-free grammars, using a technique known as @acronym{GLR}
parsing (for Generalized @acronym{LR}).  Bison's @acronym{GLR} parsers
are able to handle any context-free grammar for which the number of
possible parses of any given string is finite.

@cindex symbols (abstract)
@cindex token
@cindex syntactic grouping
@cindex grouping, syntactic
In the formal grammatical rules for a language, each kind of syntactic
unit or grouping is named by a @dfn{symbol}.  Those which are built by
grouping smaller constructs according to grammatical rules are called
@dfn{nonterminal symbols}; those which can't be subdivided are called
@dfn{terminal symbols} or @dfn{token types}.  We call a piece of input
corresponding to a single terminal symbol a @dfn{token}, and a piece
corresponding to a single nonterminal symbol a @dfn{grouping}.

We can use the C language as an example of what symbols, terminal and
nonterminal, mean.  The tokens of C are identifiers, constants (numeric
and string), and the various keywords, arithmetic operators and
punctuation marks.  So the terminal symbols of a grammar for C include
`identifier', `number', `string', plus one symbol for each keyword,
operator or punctuation mark: `if', `return', `const', `static', `int',
`char', `plus-sign', `open-brace', `close-brace', `comma' and many more.
(These tokens can be subdivided into characters, but that is a matter of
lexicography, not grammar.)

Here is a simple C function subdivided into tokens:

@ifinfo
@example
int             /* @r{keyword `int'} */
square (int x)  /* @r{identifier, open-paren, keyword `int',}
                   @r{identifier, close-paren} */
@{               /* @r{open-brace} */
  return x * x; /* @r{keyword `return', identifier, asterisk,
                   identifier, semicolon} */
@}               /* @r{close-brace} */
@end example
@end ifinfo
@ifnotinfo
@example
int             /* @r{keyword `int'} */
square (int x)  /* @r{identifier, open-paren, keyword `int', identifier, close-paren} */
@{               /* @r{open-brace} */
  return x * x; /* @r{keyword `return', identifier, asterisk, identifier, semicolon} */
@}               /* @r{close-brace} */
@end example
@end ifnotinfo

The syntactic groupings of C include the expression, the statement, the
declaration, and the function definition.  These are represented in the
grammar of C by nonterminal symbols `expression', `statement',
`declaration' and `function definition'.  The full grammar uses dozens of
additional language constructs, each with its own nonterminal symbol, in
order to express the meanings of these four.  The example above is a
function definition; it contains one declaration, and one statement.  In
the statement, each @samp{x} is an expression and so is @samp{x * x}.

Each nonterminal symbol must have grammatical rules showing how it is made
out of simpler constructs.  For example, one kind of C statement is the
@code{return} statement; this would be described with a grammar rule which
reads informally as follows:

@quotation
A `statement' can be made of a `return' keyword, an `expression' and a
`semicolon'.
@end quotation

@noindent
There would be many other rules for `statement', one for each kind of
statement in C.

@cindex start symbol
One nonterminal symbol must be distinguished as the special one which
defines a complete utterance in the language.  It is called the @dfn{start
symbol}.  In a compiler, this means a complete input program.  In the C
language, the nonterminal symbol `sequence of definitions and declarations'
plays this role.

For example, @samp{1 + 2} is a valid C expression---a valid part of a C
program---but it is not valid as an @emph{entire} C program.  In the
context-free grammar of C, this follows from the fact that `expression' is
not the start symbol.

The Bison parser reads a sequence of tokens as its input, and groups the
tokens using the grammar rules.  If the input is valid, the end result is
that the entire token sequence reduces to a single grouping whose symbol is
the grammar's start symbol.  If we use a grammar for C, the entire input
must be a `sequence of definitions and declarations'.  If not, the parser
reports a syntax error.

@node Grammar in Bison
@section From Formal Rules to Bison Input
@cindex Bison grammar
@cindex grammar, Bison
@cindex formal grammar

A formal grammar is a mathematical construct.  To define the language
for Bison, you must write a file expressing the grammar in Bison syntax:
a @dfn{Bison grammar} file.  @xref{Grammar File, ,Bison Grammar Files}.

A nonterminal symbol in the formal grammar is represented in Bison input
as an identifier, like an identifier in C@.  By convention, it should be
in lower case, such as @code{expr}, @code{stmt} or @code{declaration}.

The Bison representation for a terminal symbol is also called a @dfn{token
type}.  Token types as well can be represented as C-like identifiers.  By
convention, these identifiers should be upper case to distinguish them from
nonterminals: for example, @code{INTEGER}, @code{IDENTIFIER}, @code{IF} or
@code{RETURN}.  A terminal symbol that stands for a particular keyword in
the language should be named after that keyword converted to upper case.
The terminal symbol @code{error} is reserved for error recovery.
@xref{Symbols}.

A terminal symbol can also be represented as a character literal, just like
a C character constant.  You should do this whenever a token is just a
single character (parenthesis, plus-sign, etc.): use that same character in
a literal as the terminal symbol for that token.

A third way to represent a terminal symbol is with a C string constant
containing several characters.  @xref{Symbols}, for more information.

The grammar rules also have an expression in Bison syntax.  For example,
here is the Bison rule for a C @code{return} statement.  The semicolon in
quotes is a literal character token, representing part of the C syntax for
the statement; the naked semicolon, and the colon, are Bison punctuation
used in every rule.

@example
stmt:   RETURN expr ';'
        ;
@end example

@noindent
@xref{Rules, ,Syntax of Grammar Rules}.

@node Semantic Values
@section Semantic Values
@cindex semantic value
@cindex value, semantic

A formal grammar selects tokens only by their classifications: for example,
if a rule mentions the terminal symbol `integer constant', it means that
@emph{any} integer constant is grammatically valid in that position.  The
precise value of the constant is irrelevant to how to parse the input: if
@samp{x+4} is grammatical then @samp{x+1} or @samp{x+3989} is equally
grammatical.

But the precise value is very important for what the input means once it is
parsed.  A compiler is useless if it fails to distinguish between 4, 1 and
3989 as constants in the program!  Therefore, each token in a Bison grammar
has both a token type and a @dfn{semantic value}.  @xref{Semantics,
,Defining Language Semantics},
for details.

The token type is a terminal symbol defined in the grammar, such as
@code{INTEGER}, @code{IDENTIFIER} or @code{','}.  It tells everything
you need to know to decide where the token may validly appear and how to
group it with other tokens.  The grammar rules know nothing about tokens
except their types.

The semantic value has all the rest of the information about the
meaning of the token, such as the value of an integer, or the name of an
identifier.  (A token such as @code{','} which is just punctuation doesn't
need to have any semantic value.)

For example, an input token might be classified as token type
@code{INTEGER} and have the semantic value 4.  Another input token might
have the same token type @code{INTEGER} but value 3989.  When a grammar
rule says that @code{INTEGER} is allowed, either of these tokens is
acceptable because each is an @code{INTEGER}.  When the parser accepts the
token, it keeps track of the token's semantic value.

Each grouping can also have a semantic value as well as its nonterminal
symbol.  For example, in a calculator, an expression typically has a
semantic value that is a number.  In a compiler for a programming
language, an expression typically has a semantic value that is a tree
structure describing the meaning of the expression.

@node Semantic Actions
@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; @}
        ;