Re: Performance impact of "redundant" rules

[Akim Demaille]

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

Menhir has many interesting features, and its algorithm, even if it
is more expensive than De Remer's, offers the significant advantage
to be able to explain nicely conflicts.  It would be nice for Bison
to also implement this algorithm.  It might also be sensible for
Bison to generate non-compressed parser tables.

The only problem is finding someone willing to do it :)