Re: Are Google summer of code 2006 ideas still available?

[Hans Aberg]

On 1 Apr 2007, at 20:17, Joel E. Denny wrote:

> > If there is a choice. And which variation of LR(1) would you  
> > prefer, if there
> > now is a difference: One that compacts the states and still has  
> > the same
> > problem as LALR(1) that when an error token comes by, some actions  
> > can be
> > performed before the error is being reported plus it cannot be  
> > used in
> > interactive scanners to report possible token completions,
>
> I'm focusing on that one.
>
> > or one that does
> > not have those flaws, but takes up perhaps much more space?
>
> I'm thinking there could be an option to modify the definition of  
> state
> compatibility so that Bison can generate either canonical or  
> compact LR(1)
> tables.  Assuming the compact LR(1) works out as I hope, canonical  
> LR(1)
> would be interesting to me purely for an efficiency comparison.

Since a problem with LALR(1) is poor error handling, I think one  
should be able to turn state merging off. This will also be required  
if one wants each state to tell the correct set of possible  
completion tokens, as in some interactive parsers. The latter was  
discussed on some Bison list (perhaps for GNU readline).

> I'm very much still in the planning stages, so don't hold me to any of
> this.

There is also a dynamic variation: One sets a maximum of states. If  
the number of states does not exceed that, one gets a static  
implementation. If they exceed that limit, one instead implements a  
parser able to compute new states on the fly.

It is mentioned in the book by Aho, Sethi & Ullman,  
"Compilers..." (the "dragon book"), that for a NFA to DFA  
translation, such a dynamic translation can avoid the exponentiality  
that may happen in a static compilation. Since LR(1) proper can also  
generate exponential amounts of states, this might be something  
consider as an alternative to state merging. I do not know the theory  
of it. I just mention this "just in case".

  Hans Aberg