Re: Performance impact of "redundant" rules

[Sylvain Schmitz]

Hans Aberg wrote:

> On 7 Mar 2006, at 10:39, Sylvain Schmitz wrote:
>
> > About LR(1), I recently found out menhir
> > <http://pauillac.inria.fr/~fpottier/menhir/menhir.html.en>, which
> > implements LR(1) using Pager's method: even today, the direct generation
> > of a full-blown LR(1) parser is too expensive.
>
> This sounds interesting: Is this a method to cut down on the  generation 
> of the LR(1) parser, without affecting the parser  generated itself? - I 
> thought Bison already had LR(1) in it, and one  should only need to take 
> away the LALR(1) optimizations to get it  implemented.

bison uses an excellent LALR(1) implementation based on DeRemer and
Pennello's work.  It relies solely on the LR(0) automaton; the LR(1)
"stuff" is never computed.


> 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.


> > Anyway, you would need
> > to merge as many LR(1) states as possible if you do not want a  dramatic
> > performance drop in GLR parsing ... My feeling is that LALR(1) is a
> > sensible choice.
>
> 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).
Anyway, this advantage disappears if we start merging states in the
LR(1) automaton ...


> 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.  Thus LR(1) is much more practicable if you merge states.

--
  Sylvain