bison.texinfo

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

@end example

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

@node GLR Parsers
@section Writing @acronym{GLR} Parsers
@cindex @acronym{GLR} parsing
@cindex generalized @acronym{LR} (@acronym{GLR}) parsing
@findex %glr-parser
@cindex conflicts
@cindex shift/reduce conflicts
@cindex reduce/reduce conflicts

In some grammars, Bison's standard
@acronym{LALR}(1) parsing algorithm cannot decide whether to apply a
certain grammar rule at a given point.  That is, it may not be able to
decide (on the basis of the input read so far) which of two possible
reductions (applications of a grammar rule) applies, or whether to apply
a reduction or read more of the input and apply a reduction later in the
input.  These are known respectively as @dfn{reduce/reduce} conflicts
(@pxref{Reduce/Reduce}), and @dfn{shift/reduce} conflicts
(@pxref{Shift/Reduce}).

To use a grammar that is not easily modified to be @acronym{LALR}(1), a
more general parsing algorithm is sometimes necessary.  If you include
@code{%glr-parser} among the Bison declarations in your file
(@pxref{Grammar Outline}), the result is a Generalized @acronym{LR}
(@acronym{GLR}) parser.  These parsers handle Bison grammars that
contain no unresolved conflicts (i.e., after applying precedence
declarations) identically to @acronym{LALR}(1) parsers.  However, when
faced with unresolved shift/reduce and reduce/reduce conflicts,
@acronym{GLR} parsers use the simple expedient of doing both,
effectively cloning the parser to follow both possibilities.  Each of
the resulting parsers can again split, so that at any given time, there
can be any number of possible parses being explored.  The parsers
proceed in lockstep; that is, all of them consume (shift) a given input
symbol before any of them proceed to the next.  Each of the cloned
parsers eventually meets one of two possible fates: either it runs into
a parsing error, in which case it simply vanishes, or it merges with
another parser, because the two of them have reduced the input to an
identical set of symbols.

During the time that there are multiple parsers, semantic actions are
recorded, but not performed.  When a parser disappears, its recorded
semantic actions disappear as well, and are never performed.  When a
reduction makes two parsers identical, causing them to merge, Bison
records both sets of semantic actions.  Whenever the last two parsers
merge, reverting to the single-parser case, Bison resolves all the
outstanding actions either by precedences given to the grammar rules
involved, or by performing both actions, and then calling a designated
user-defined function on the resulting values to produce an arbitrary
merged result.

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

@node Simple GLR Parsers
@subsection Using @acronym{GLR} on Unambiguous Grammars
@cindex @acronym{GLR} parsing, unambiguous grammars
@cindex generalized @acronym{LR} (@acronym{GLR}) parsing, unambiguous grammars
@findex %glr-parser
@findex %expect-rr
@cindex conflicts
@cindex reduce/reduce conflicts
@cindex shift/reduce conflicts

In the simplest cases, you can use the @acronym{GLR} algorithm
to parse grammars that are unambiguous, but fail to be @acronym{LALR}(1).
Such grammars typically require more than one symbol of look-ahead,
or (in rare cases) fall into the category of grammars in which the
@acronym{LALR}(1) algorithm throws away too much information (they are in
@acronym{LR}(1), but not @acronym{LALR}(1), @ref{Mystery Conflicts}).

Consider a problem that
arises in the declaration of enumerated and subrange types in the
programming language Pascal.  Here are some examples:

@example
type subrange = lo .. hi;
type enum = (a, b, c);
@end example

@noindent
The original language standard allows only numeric
literals and constant identifiers for the subrange bounds (@samp{lo}
and @samp{hi}), but Extended Pascal (@acronym{ISO}/@acronym{IEC}
10206) and many other
Pascal implementations allow arbitrary expressions there.  This gives
rise to the following situation, containing a superfluous pair of
parentheses:

@example
type subrange = (a) .. b;
@end example

@noindent
Compare this to the following declaration of an enumerated
type with only one value:

@example
type enum = (a);
@end example

@noindent
(These declarations are contrived, but they are syntactically
valid, and more-complicated cases can come up in practical programs.)

These two declarations look identical until the @samp{..} token.
With normal @acronym{LALR}(1) one-token look-ahead it is not
possible to decide between the two forms when the identifier
@samp{a} is parsed.  It is, however, desirable
for a parser to decide this, since in the latter case
@samp{a} must become a new identifier to represent the enumeration
value, while in the former case @samp{a} must be evaluated with its
current meaning, which may be a constant or even a function call.

You could parse @samp{(a)} as an ``unspecified identifier in parentheses'',
to be resolved later, but this typically requires substantial
contortions in both semantic actions and large parts of the
grammar, where the parentheses are nested in the recursive rules for
expressions.

You might think of using the lexer to distinguish between the two
forms by returning different tokens for currently defined and
undefined identifiers.  But if these declarations occur in a local
scope, and @samp{a} is defined in an outer scope, then both forms
are possible---either locally redefining @samp{a}, or using the
value of @samp{a} from the outer scope.  So this approach cannot
work.

A simple solution to this problem is to declare the parser to
use the @acronym{GLR} algorithm.
When the @acronym{GLR} parser reaches the critical state, it
merely splits into two branches and pursues both syntax rules
simultaneously.  Sooner or later, one of them runs into a parsing
error.  If there is a @samp{..} token before the next
@samp{;}, the rule for enumerated types fails since it cannot
accept @samp{..} anywhere; otherwise, the subrange type rule
fails since it requires a @samp{..} token.  So one of the branches
fails silently, and the other one continues normally, performing
all the intermediate actions that were postponed during the split.

If the input is syntactically incorrect, both branches fail and the parser
reports a syntax error as usual.

The effect of all this is that the parser seems to ``guess'' the
correct branch to take, or in other words, it seems to use more
look-ahead than the underlying @acronym{LALR}(1) algorithm actually allows
for.  In this example, @acronym{LALR}(2) would suffice, but also some cases
that are not @acronym{LALR}(@math{k}) for any @math{k} can be handled this way.

In general, a @acronym{GLR} parser can take quadratic or cubic worst-case time,
and the current Bison parser even takes exponential time and space
for some grammars.  In practice, this rarely happens, and for many
grammars it is possible to prove that it cannot happen.
The present example contains only one conflict between two
rules, and the type-declaration context containing the conflict
cannot be nested.  So the number of
branches that can exist at any time is limited by the constant 2,
and the parsing time is still linear.

Here is a Bison grammar corresponding to the example above.  It
parses a vastly simplified form of Pascal type declarations.

@example
%token TYPE DOTDOT ID

@group
%left '+' '-'
%left '*' '/'
@end group

%%

@group
type_decl : TYPE ID '=' type ';'
     ;
@end group

@group
type : '(' id_list ')'
     | expr DOTDOT expr
     ;
@end group

@group
id_list : ID
     | id_list ',' ID
     ;
@end group

@group
expr : '(' expr ')'
     | expr '+' expr
     | expr '-' expr
     | expr '*' expr
     | expr '/' expr
     | ID
     ;
@end group
@end example

When used as a normal @acronym{LALR}(1) grammar, Bison correctly complains
about one reduce/reduce conflict.  In the conflicting situation the
parser chooses one of the alternatives, arbitrarily the one
declared first.  Therefore the following correct input is not
recognized:

@example
type t = (a) .. b;
@end example

The parser can be turned into a @acronym{GLR} parser, while also telling Bison
to be silent about the one known reduce/reduce conflict, by
adding these two declarations to the Bison input file (before the first
@samp{%%}):

@example
%glr-parser
%expect-rr 1
@end example

@noindent
No change in the grammar itself is required.  Now the
parser recognizes all valid declarations, according to the
limited syntax above, transparently.  In fact, the user does not even
notice when the parser splits.

So here we have a case where we can use the benefits of @acronym{GLR}, almost
without disadvantages.  Even in simple cases like this, however, there
are at least two potential problems to beware.
First, always analyze the conflicts reported by
Bison to make sure that @acronym{GLR} splitting is only done where it is
intended.  A @acronym{GLR} parser splitting inadvertently may cause
problems less obvious than an @acronym{LALR} parser statically choosing the
wrong alternative in a conflict.
Second, consider interactions with the lexer (@pxref{Semantic Tokens})
with great care.  Since a split parser consumes tokens
without performing any actions during the split, the lexer cannot
obtain information via parser actions.  Some cases of
lexer interactions can be eliminated by using @acronym{GLR} to
shift the complications from the lexer to the parser.  You must check
the remaining cases for correctness.

In our example, it would be safe for the lexer to return tokens
based on their current meanings in some symbol table, because no new
symbols are defined in the middle of a type declaration.  Though it
is possible for a parser to define the enumeration
constants as they are parsed, before the type declaration is
completed, it actually makes no difference since they cannot be used
within the same enumerated type declaration.

@node Merging GLR Parses
@subsection Using @acronym{GLR} to Resolve Ambiguities
@cindex @acronym{GLR} parsing, ambiguous grammars
@cindex generalized @acronym{LR} (@acronym{GLR}) parsing, ambiguous grammars
@findex %dprec
@findex %merge
@cindex conflicts
@cindex reduce/reduce conflicts

Let's consider an example, vastly simplified from a C++ grammar.

@example
%@{
  #include <stdio.h>
  #define YYSTYPE char const *
  int yylex (void);
  void yyerror (char const *);
%@}

%token TYPENAME ID

%right '='
%left '+'

%glr-parser

%%

prog :
     | prog stmt   @{ printf ("\n"); @}
     ;

stmt : expr ';'  %dprec 1
     | decl      %dprec 2
     ;

expr : ID               @{ printf ("%s ", $$); @}
     | TYPENAME '(' expr ')'
                        @{ printf ("%s <cast> ", $1); @}
     | expr '+' expr    @{ printf ("+ "); @}
     | expr '=' expr    @{ printf ("= "); @}
     ;

decl : TYPENAME declarator ';'
                        @{ printf ("%s <declare> ", $1); @}
     | TYPENAME declarator '=' expr ';'
                        @{ printf ("%s <init-declare> ", $1); @}
     ;

declarator : ID         @{ printf ("\"%s\" ", $1); @}
     | '(' declarator ')'
     ;
@end example

@noindent
This models a problematic part of the C++ grammar---the ambiguity between
certain declarations and statements.  For example,

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

@noindent
parses as either an @code{expr} or a @code{stmt}
(assuming that @samp{T} is recognized as a @code{TYPENAME} and
@samp{x} as an @code{ID}).
Bison detects this as a reduce/reduce conflict between the rules
@code{expr : ID} and @code{declarator : ID}, which it cannot resolve at the
time it encounters @code{x} in the example above.  Since this is a
@acronym{GLR} parser, it therefore splits the problem into two parses, one for
each choice of resolving the reduce/reduce conflict.
Unlike the example from the previous section (@pxref{Simple GLR Parsers}),
however, neither of these parses ``dies,'' because the grammar as it stands is
ambiguous.  One of the parsers eventually reduces @code{stmt : expr ';'} and
the other reduces @code{stmt : decl}, after which both parsers are in an
identical state: they've seen @samp{prog stmt} and have the same unprocessed
input remaining.  We say that these parses have @dfn{merged.}

At this point, the @acronym{GLR} parser requires a specification in the
grammar of how to choose between the competing parses.
In the example above, the two @code{%dprec}
declarations specify that Bison is to give precedence