Re: LR(1) error recovery in LALR(1)

[Paul Hilfinger]

> Bison --report=all evidently computes the reduction lookahead sets. If I
> have understood this right, then it should be possible, as an option, to
> make a LALR(1) parser that reports an error immediately, as in LR(1). There
> have been a number of questions here, especially in interactive parsers,
> which want to know the lookahead sets, and report entered errors
> immediately.
> 
> So this suggests a feature, where the parser gets an extra table with, for
> each state, these reduction lookahead sets. When, in a state, the $default
> is encountered, the parser checks if the lookahead token is in the lookahead
> set, and if not, immediately reports the error.
> 
> This would make there to be less need for a LR(1) feature, as GLR can handle
> the fact that LALR(1) accepts a smaller grammar set than LR(1).

>   Hans Aberg
> 


AFAIK, Bison always computes the reduction lookahead sets.  Their
removal from the finished tables is the result of the default-
reduction optimization, which in turn is motivated by a desire for
table compression.  The same optimizations could be applied to LR(1)
parsers. In fact, --report=all does NOT seem to report the lookahead
sets in many cases where default reductions are used.

On the other hand, I was just wondering recently about whether table
compression is at all important any more. I mean, a parser with 300
states and 100 tokens has < 30,000 entries in its tables, encodable in
< 60K WITHOUT compression.  Without compression, you have all of the 
lookaheads (and fast error-detection) without any special work.

P. Hilfinger