Re: Performance impact of "redundant" rules

[Hans Aberg]

On 7 Mar 2006, at 18:42, Sylvain Schmitz wrote:

> bison uses an excellent LALR(1) implementation based on DeRemer and
> Pennello's work.

This reference is mentioned in the Aho et al. "Compilers..." book,  
but it does not say if it is what is described in its text.

> It relies solely on the LR(0) automaton; the LR(1)
> "stuff" is never computed.

OK.

> > But you seem to say, that parser generation phase might  then  
> > become too big.
>
> I think it's big, and the menhir implementors seem to agree.

OK. That is something to look up, would Bison be given an LR(1) option.

> > LR(1) becomes interesting from unexpected corners: efficient  
> > error  generation and parser that need to display token  
> > lookaheads, which  LALR(1) deliberately both corrupts in its  
> > optimizations.
>
> I'm not fully convinced of the interest of the "valid prefix +
> lookahead" property of LR(1) versus the simple "valid prefix" of LR 
> (0).

It is just a question of being able to capture all the LALR(1)  
grammars at least.

> Anyway, this advantage disappears if we start merging states in the
> LR(1) automaton ...

Right. One can though think of a LALR(1) that somehow records the  
proper LR(1) tokens just for such purposes.

> > What is the reason  performance drops especially in GLR?
>
> Too many states means less chances of merging concurrent stacks.  One
> could also point out that less inadequate states means less branching,
> but the number of inadequate states avoided when using LR(1)  
> instead of
> LALR(1) is not very big, whereas the difference in automaton size is
> exponential.

I am not aware of this exponentiality: The Aho [loc.cit.] just gives  
a percentage on typical parsers.

> Thus LR(1) is much more practicable if you merge states.

The question will be to find compaction methods that does not destroy  
the immediate reaction to wrong tokens, and can provide the proper  
set of valid lookahead tokens.

  Hans Aberg