|
From: | Sylvain Schmitz |
Subject: | Re: Performance impact of "redundant" rules |
Date: | Mon, 06 Mar 2006 23:14:26 +0100 |
User-agent: | Mozilla/5.0 (Macintosh; U; PPC Mac OS X Mach-O; en-US; rv:1.7) Gecko/20040616 |
Frans Englich wrote:
Sometimes I write grammar constructs like this: StringLiteral: STRING_LITERALand 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.
-- Sylvain
[Prev in Thread] | Current Thread | [Next in Thread] |