Re: Reductions during Bison error handling

[Hans Aberg]

At 16:46 -0700 2002/05/12, Paul Hilfinger wrote:
>Yeesh; you are demonstrating to me how many different uses of the word
>"default" there are in this system!

Somebody said that it is hard to make something foolproof, because fools
are so innovative. :-)

>  This is in fact another example
>of what I was NOT talking about.  The default reduction in Bison's
>table is the *most common* reduction among all the actions in a
>particular state

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?

-- Bison may change, making use different parsing algorithms (even though
POSIX requires LALR(1)).

Then one needs error recovery tied to the grammar description of a language
(that is, independent of the parsing algorithm used).

> > Perhaps a better error recovery procedure requires the "error" token to be
> > better integrated into the grammar, and then passed through the LALR(1)
> > algorithm: Right now, I suspect that the LALR algorithm tells what should
> > constitute an error, and then the written parser hooks a simplistic error
> > recovery scheme onto that. This then sets some severe limitations on how
> > the error recovery might act.
>
>Well, actually, I think you'll find that the machine generated by
>Bison treats 'error' as a perfectly ordinary token.

Actually, I know this; I should perhaps have let some experts providing the
replies (but perhaps I learnt something :-) ).

>  I only see one
>slight adjustment---states that shift the error token don't use a
>default reduction (in my sense).  I believe this is to allow parse
>errors to be caught a little earlier than they might otherwise be, but
>I am not sure how effective it is at that.
>
>The whole algorithm is really rather elegant (at least the official one, as
>described in the documentation); it is a pity that it has various
>undesirable properties (including a tendency to throw away more text
>than necessary).  But I suppose that is simply an example of TANSTAAFL
>("There ain't no such thing as a free lunch").

I thought you opted for:

>The documentation says that when I am in this situation:
>
>    Parse Stack:  s1  s2 ... sk ... sn  <-top   Lookahead: X
>
>and the action for lookahead X in sn is "parsing error", then we are
>supposed to
>
>1. pop the stack back to the first state that allows shifting
>   the token `error' (let's say sk),
>2. shift 'error' (giving, let's say, state sk'),
>3. delete tokens until we have a new lookahead (Y) that is legal for
>   state sk',
>4. Proceed normally.

And that this might have been too difficult to achieve with the current
"error" implementation that relies on a simple error recovery routine in
the parser implementation.

-- Perhaps a better error recovery can be achieved by implicitly sprinkling
the input grammar with "error_k" tokens, somehow (I do not see the details
of this idea, though).

  Hans Aberg