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

[Hans Aberg]

At 15:29 -0800 2005/03/01, Paul Hilfinger wrote:
>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.

The funny thing is that the need for the exact LR(1) reduction lookahead set
comes from two types of applications: The first is an interactive parser,
which, for each partial token input, stops, and lists the possible lookahead
tokens. The other application is one which requires exact error detection
and recovery. Then one does not want extra reductions to be performed.

So these two applications suggests one should always have the option to get
the LR(1) reduction tokens listed in a table.

As for the other question, I have come, at least initially, to the same
conclusion as you, that LR(1) without table compression is probably fully
acceptable on todays computers. So I think that Bison should have an LR(1)
option. Bison is now going to get Guile implemented. So perhaps when that
happens, LR(1) might be more quickly implemented using OO-Scheme.

But on the other hand, in view of GLR, the only reason against LALR(1) is
perhaps then that one does not get to know the LR(1) reduction lookahead
sets. So therefore, one can perhaps always use LALR(1) based GLR instead of
LR(1), if the lookahead sets are supplied separately.

It is also a paradox that, as computers get more speed and memory,
compression techniques can be used even more.

  Hans Aberg