Re: Why are LR parsers faster than using if conditions

Carl Cerecke <cdc@maxnet.co.nz>
21 Jun 2004 23:53:06 -0400

          From comp.compilers

Related articles
Why are LR parsers faster than using if conditions shripal.meghani@philips.com (2004-06-06)
Re: Why are LR parsers faster than using if conditions torbenm@diku.dk (2004-06-09)
Re: Why are LR parsers faster than using if conditions alexc@std.com (Alex Colvin) (2004-06-11)
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 t.zielonka@zodiac.mimuw.edu.pl (Tomasz Zielonka) (2004-06-25)
Re: Why are LR parsers faster than using if conditions haberg@matematik.su.se (Hans Aberg) (2004-06-26)
Re: Why are LR parsers faster than using if conditions haberg@matematik.su.se (Hans Aberg) (2004-06-28)
Re: Why are LR parsers faster than using if conditions clint@0lsen.net (Clint Olsen) (2004-06-28)
Re: Why are LR parsers faster than using if conditions tmoog@panix.com (2004-06-30)
Re: Why are LR parsers faster than using if conditions haberg@matematik.su.se (Hans Aberg) (2004-06-30)
[3 later articles]
| List of all articles for this month |

From: Carl Cerecke <cdc@maxnet.co.nz>
Newsgroups: comp.compilers
Date: 21 Jun 2004 23:53:06 -0400
Organization: Compilers Central
References: 04-06-072 04-06-081
Keywords: parse, performance
Posted-Date: 21 Jun 2004 23:53:05 EDT

Quinn Tyler Jackson wrote:
> 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.


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


Interesting. But, the point I made was about *hard-coded* LR parsers in
particular. It's not just the reduction code that is hard-coded, but the
*entire* parsing automata is hard-coded.
These have a claimed speedup of 2.5-6.5 times over table-drive LR
parsers. This is without any semantic checks, I think. Their code was
based on bison 1.22; there is a Tech report:
http://www.cs.arizona.edu/research/reports.html. The title is "Very fast
YACC compatible parsers (for very little effort)"


I appear to be the only one with the source code from this Tech report.
I was emailed just this week by someone looking for it. It's very
alpha-quality though - be warned. The authors are difficult to contact
and have hidden their email addresses from the internet (which sounds
like a good thing, seeing as I got 400+ spam overnight). The guy who
actually did the work (well, he wrote the code) is Achyutram Bhamidipaty.


Cheers,
Carl Cerecke
x


Post a followup to this message

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