|Re: Why are LR parsers faster than using if conditions email@example.com (Carl Cerecke) (2004-06-15)|
|RE: Why are LR parsers faster than using if conditions firstname.lastname@example.org (Quinn Tyler Jackson) (2004-06-21)|
|Re: Why are LR parsers faster than using if conditions email@example.com (Carl Cerecke) (2004-06-21)|
|RE: Why are LR parsers faster than using if conditions firstname.lastname@example.org (Quinn Tyler Jackson) (2004-06-30)|
|From:||Quinn Tyler Jackson <email@example.com>|
|Date:||21 Jun 2004 23:40:18 -0400|
|Posted-Date:||21 Jun 2004 23:40:18 EDT|
Carl Cerecke said:
> But, if we are talking about speed, I suspect a hard-coded LR parser
> will leave even a well written recursive descent parser in its dust.
Not necessarily. Some years back, as a way of having something to test
the timing of an adaptive recursive-descent parser against a
"traditional" parser, I asked a parser-generator author to write a
grammar against which I would time my parsing engine.
Over the years, I optimized the engine so that it would show
progressively better times against the reference grammar. (Both accept
the same subset of C++.)
File size: 13813779 bytes
M-S -> 1994.2 : 6926961
LR(1) -> 2366.41 : 5837431
The test case has 8192 C++ classes, each with a ctor, dtor, and 14
member functions. Neither parser accepts:
That is to say, both grammars fail on the above because quux is not
declared in Foo.
The Meta-S engine (byte-code interpreted recursive descent, generated
from a grammar specification only, with semantic checks in the
grammar), parses on my box at about 6.1 megs/second. The LR(1) engine
(compiled bottom-up, semantic checks done in reduction code using fast
hash lookups), parses on my box at about 5.7 megs/second.
Because many of the optimizations made in order to get these test case
results carried into "many grammars in general", the recursive descent
parser in Meta-S "holds its own" against the bottom-up family quite
nicely in many cases.
Return to the
Search the comp.compilers archives again.