Re: Reductions during Bison error handling

[Hans Aberg]

At 20:12 -0700 2002/05/10, Paul Hilfinger wrote:
>I'm not sure we are talking about the same thing here.  When I said
>"default reduction", I was referring to the purely internal device of
>labeling one of the most popular reductions

Yes, I misunderstood this.

Note however, that the default reduction is not internally to Bison,
because under POSIX, it should be the first listed action in the input if
LALR(1) cannot tell which one it should be. Thus, under POSIX, the input is
not a mathematical grammar where the rules are a set, but a well ordered
list.

>Error recovery in Bison is not done as documented in the manual in the
>first place.  In addition, I was pointing out (in effect) that the
>code in question makes even MORE obscure and unpredictable what is
>going on (unnecessarily so).
>
>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.
>
>All nice and clean (although as Corbett and others have pointed out,
>not all that conducive to great error recovery---hence the term "panic
>mode").

I think this sounds reasonable.

>What ACTUALLY happens is that step (1) is replaced with
>
>1'. pop the stack back to the first state that allows *some non-error
>    action OTHER THAN A DEFAULT REDUCTION on* the token `error' (let's
>    say sk),
>
>1.1'. if the indicated action for sk and the error token is a
>    reduction, perform the reduction and proceed normally.
>
>I was basically pointing out that since "default reduction" is not a
>user-visible concept in Bison, the effect of the capitalized clause in
>1.1' is unpredictable from a Bison user's point of view.

So it looks to me as well, when you put it this way. -- I have noticed that
error recovery in Bison is funny (and it becomes funnier because of
LALR(1)), and I could not figure it out how it worked, but I did not think
much about it.

Perhaps it is this change that makes the Bison parser error recovery behave
funny.

>  The effect
>of removing the "#if 0"s around the yyerrdefault code would be to
>convert 1' into something a little more predictable:
>
>1''. pop the stack back to the first state that allows *some non-error
>    action on* the token `error' (let's say sk),
>
>Admittedly, not all that much more predictable, since unfortunately it
>is also hard for a user to understand when Bison will choose to use a
>default reduction for an erroneous token and when it will use an error
>entry (it is always harmless to use a default reduction, since Bison
>normally never shifts past a viable prefix before reporting an error).

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.

  Hans Aberg