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
_______________________________________________
[email protected] http://lists.gnu.org/mailman/listinfo/help-bison
