[Top][All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

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

From: Paul Hilfinger
Subject: Re: LR(1) error recovery in LALR(1)
Date: Tue, 01 Mar 2005 15:29:32 -0800

> 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

reply via email to

[Prev in Thread] Current Thread [Next in Thread]