Re: Performance impact of "redundant" rules

[Hans Aberg]

On 6 Mar 2006, at 23:32, Frans Englich wrote:

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

Bison just applies the LALR(1) algorithm straight off, without any  
optimizations. Nor is there any point with such optimizations, as a  
typical compiler spends most time in its actions and the lexer,  
making parser efficiency not very important.

So for that reason, when developing your program, I suggest not  
bothering about it.

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

  Hans Aberg