Re: Performance impact of "redundant" rules

[Frans Englich]

On Monday 06 March 2006 22:14, you wrote:
> Frans Englich wrote:
> > Sometimes I write grammar constructs like this:
> >
> > StringLiteral: STRING_LITERAL
> >
> > and use StringLiteral in subsequent rules, instead of STRING_LITERAL
> > directly. The reason is readability, and to stay consistent with an EBNF
> > specification.
> >
> > I wonder, does this cause a negative performance impact? When I compile
> > the parser with extra debug output I see that it actually performs a
> > STRING_LITERAL --> StringLiteral reduction.
>
> These rules are called "unit rules" in the literature; much effort was
> devoted to wiping them out automatically from LR parsers since they
> account for a non-negligible space and time overhead (an old paper by
> Joliat mentionned a 47% time improvement when getting rid of them).  If
> you want to learn more about these techniques, the chapter on LR
> optimization in Sippu and Soisalon-Soininen's _Parsing_Theory_ seems
> rather exhaustive.

Ok, so Bison do attempt to optimize such grammars to some extent? Is it 
relatively good at it, compared to "other" parsers?


Thanks,

                Frans