Re: Reductions during Bison error handling

[Hans Aberg]

At 19:44 -0700 2002/05/13, Paul Hilfinger wrote:
>Again, Bison has, in effect, TWO information-losing table compression
>tricks vs. pure LR:
>
>1. States differing only in lookahead symbols are merged (the LALR
>   optimization).
>
>2. Erroneous lookaheads are not distinguished from lookaheads for the
>   most common reduction (an optimization that could apply equally
>   well to LR(1) and LALR(1) parsers, as described in ASU, pp 244-245).
>   This is the one I've been talking about here; it is orthogonal to
>   the compression effected by the LALR construction.

I was under the impression that Bison only uses 2 to present the parser,
but it wasn't used in the actual parser implementation: The Bison parser
would need a table with (token, action) pairs to be searched, and that does
not seem the case.

But you are right, also this compression scheme may add some reductions
before an error is detected.

> > 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.
>
>To be honest, however bad panic-mode syntactic error recovery might be
>in Bison, in practice it doesn't seem so terrible *given how it is now
>used.*   Back in the good old days when I had to wait quite a while
>for a compilation, good error recovery was extremely useful, since it
>allowed me to get more errors per run, and therefore significantly
>affected productivity.  The way I work now, and with the speed of
>modern computers, the "compile to the first syntax error, fix, and repeat"
>technique has become increasingly viable over the years.

I have noticed the same, even though I did not think of that the reason for
extensive error recovery schemes in the past was dictated by the long
compile times. (I did some punch-card programming in the seventies with,
with the compile returned perhaps in a couple of hours or the next day so I
know by personal experience what you are speaking about.)

In addition, I have noticed another factor that promotes the "compile to
the first syntax error, fix, and repeat" method: Humans are good at
identifying context, which computers are not. More structured computer
languages, like C++, depend a lot more on context information, but it makes
it more difficult for  their compilers to handle error recovery. Typically,
some declaration is wrong, and it generates hundreds of errors, the
compiler getting out of synch, generating even more errors.

So I think the efficient error recovery must include semantic information;
perhaps computer languages needs to be redesigned as well, in order to
encapsulate contexts better.

>If you do want to implement your idea or something more ambitious, do
>be sure to check the literature (Corbett's dissertation has quite a
>few pointers, plus caveats about some of the apparently attractive
>techniques).

Oh, I just thought of something more modest: Having access to the parsing
equivalent of C++ exceptions. One also needs to know whether it is useful.

  Hans Aberg