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

[Hans Aberg]

On 29 Apr 2007, at 08:08, Joel E. Denny wrote:

> > 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).
>
> Are you (or anyone) aware of any good literature that addresses  
> this issue
> of false completion tokens using LALR or compact LR tables?

It is mentioned in the book by Aho, Sethi & Ullman,  
"Compilers..." ("the dragon book") that a difference between LALR(1)  
and LR(1) is that, when an error token appears in the input, the  
latter reports it immediately, whereas the former may perform some  
additional reductions before it is discovered that the token is  
erroneous. Apparently, the LALR(1) parser must jog through some  
additional states, before the true nature of the token is discovered.  
So this destroys both efficient error handling and the proper set of  
lookahead tokens in such states where this can happen.

I then wasn't aware that the "efficient" LR(1) implementations may  
make use of then same state compaction technique as in LALR(1) - only  
one is not doing it in a way the set of parsable grammars is not cut  
donw, so that one then gets the full lR(1). This was mentioned in one  
of the Bison lists, but without reference.

Some LR(k) links:
  http://pauillac.inria.fr/~fpottier/menhir/menhir.html.en
  http://david.tribble.com/text/honalee.html
I do not know if and how these algorithms compact the states.

The book by Waite & Goose, "Compiler construction", also describes LR 
(k).

  Hans Aberg