Re: Reductions during Bison error handling

[Hans Aberg]

At 14:09 -0700 2002/05/13, Paul Hilfinger wrote:
> > I realized this when you say it. This "default reduction" is tied to
> > LALR(1), if one changes to LR(1) or something else, it might not even
> > exist, right?
...
>The whole idea of default reductions is based on two observations:
>
>a. A row of a table most of whose members are the same can be overlaid
>   on other rows by the "yycheck trick", and
>
>b. It is always safe to substitute any reduction that is legal in a state
>   for some lookahead for all error entries for that state.
>
>Point (b) is true for both LR and LALR parsers (because both exhibit
>the viable prefix property---they never shift past a legal prefix).

This overlaying of states distort the LR(1) parsing in that before an error
is detected, some additional reductions may take place.

Are you sure this does not distort the error recovery scheme so that
LALR(1) is unsuitable? -- It might be better to use LR(1) with a table
compression scheme that does not distort the parsing during error recovery
(i.e. does not apply possibly extra reductions).

>HA > And that this might have been too difficult to achieve with the current
>HA > "error" implementation that relies on a simple error recovery routine in
>HA > the parser implementation.
>
>I don't think so.  In fact, I have implemented the documented error
>recovery for GLR, and didn't trip over anything.

So GLR is just LR with non-deterministic parsing, but it should behave in
each thread as LR during error recovery. Thus simpler than LALR(1).

>  In fact, I think
>that bison.simple's current method is slightly more complex than the
>documented method---it allows additional reductions after an error is
>detected, but before 'error' is shifted.  In essense, my comment was
>that this makes things even more confusing for the user and, with the
>use of default reductions, nearly unpredictable.

But it would be great to have a good approximation of true LR(1) error
recovery, plus a description of what is actually happening.

>HA> -- Perhaps a better error recovery can be achieved by implicitly
>sprinkling
>HA> the input grammar with "error_k" tokens, somehow (I do not see the details
>HA> of this idea, though).
>
>Actually, there are couple of experiments that might be interesting
>(although I have a sneaking suspicion that papers have already been
>written about them):
>
>1. What would be the effect on table size and error-recovery behavior
>   if Bison were always to use 'error' as the default reduction (so
>   that yydefact could be eliminated entirely and
>   yypact[yystate] == YYFLAG only for accepting state).
>
>2. What would be the effect on table size and error-recovery behavior
>   if Bison were to use default reductions only for consistent LALR
>   states (in current Bison terms, only use the default when
>   yypact[yystate] == YYFLAG) and make 'error' the default everywhere
>   else.
>
>The intent (besides a slight simplification of the parser) is to cause
>Bison to detect parsing errors as soon as the offending token was
>consulted (without performing any reductions first).

Yes, this is what LR does; LALR does not do that because of its
(intentional) table compression flaw. -- I suspect one should use LR for
good error recovery.

One idea that I have is to allow errors be put on a hierarchy (a directed
tree, like in C++ derived classes). The error recovery token would only
pick up it and derived errors (lower down in the tree hierarchy). Then one
can throw more accurate error when detected, providing a more exact error
recovery.

  Hans Aberg