Re: Performance impact of "redundant" rules

[Sylvain Schmitz]

Hans Aberg wrote:

> As for the optimizations mentioned, I suspect they are old; they  
> probably seemed important in older times, when computing time and space 
> was very expensive.

It's true they are getting old, and bison is already pretty fast.
Except in some specific cases, I also doubt anyone needs much
faster.

> The LALR(1) algorithm that Bison uses, was  
> developed in this vein; Bison probably ought to also have LR(1) these  
> days, which may expand the parser size several times, but would not  
> matter on todays computers.

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

--
Regards,

  Sylvain