[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Performance impact of "redundant" rules
From: |
Frans Englich |
Subject: |
Re: Performance impact of "redundant" rules |
Date: |
Mon, 6 Mar 2006 22:32:14 +0000 |
User-agent: |
KMail/1.8.50 |
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
- Performance impact of "redundant" rules, Frans Englich, 2006/03/06
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/06
- Re: Performance impact of "redundant" rules,
Frans Englich <=
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/07
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/07
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/07
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/07
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/11
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/14
- Re: Performance impact of "redundant" rules, Sylvain Schmitz, 2006/03/14
- Re: Performance impact of "redundant" rules, Hans Aberg, 2006/03/15
- Re: Performance impact of "redundant" rules, Akim Demaille, 2006/03/08