RE: Why are LR parsers faster than using if conditions

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


c17: <c:\dev\Misc\Test\Foo_m8192.cpp>


File size: 13813779 bytes
M-S -> 1994.2 : 6926961
LR(1) -> 2366.41 : 5837431
119%


The test case has 8192 C++ classes, each with a ctor, dtor, and 14
member functions. Neither parser accepts:


class Foo
{
public:


void bar(void);
};


int Foo::quux(void)
{
}


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.


--
Quinn

Return to the comp.compilers page.
Search the comp.compilers archives again.