RE: Why are LR parsers faster than using if conditions

Quinn Tyler Jackson <quinn-j@shaw.ca>
21 Jun 2004 23:40:18 -0400

          From comp.compilers

Related articles
Re: Why are LR parsers faster than using if conditions cdc@maxnet.co.nz (Carl Cerecke) (2004-06-15)
RE: Why are LR parsers faster than using if conditions quinn-j@shaw.ca (Quinn Tyler Jackson) (2004-06-21)
Re: Why are LR parsers faster than using if conditions cdc@maxnet.co.nz (Carl Cerecke) (2004-06-21)
RE: Why are LR parsers faster than using if conditions quinn-j@shaw.ca (Quinn Tyler Jackson) (2004-06-30)
| List of all articles for this month |

From: Quinn Tyler Jackson <quinn-j@shaw.ca>
Newsgroups: comp.compilers
Date: 21 Jun 2004 23:40:18 -0400
Organization: Compilers Central
References: 04-06-072
Keywords: parse, performance
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++.)


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


Post a followup to this message

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