Re: Why are LR parsers faster than using if conditions

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

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