Re: Why are LR parsers faster than using if conditions

Torben Ęgidius Mogensen wrote:


> LR parsers are a bit slower than well-written recursive descent
> parsers,


OK. I'll bite.


A hard-coded LR parser will be substantially faster than a table-driven
LR parser (2.5-6.5 times, according to Todd Proebsting and co. IIRC).


Basically, "hard-coded" means that the LR state machine is expanded out
into code, and shifts are coded as gotos between the code chunks. This
works well for C, but not so good for Java or python, which don't have
gotos (See! There *is* a reason for having gotos in a language!).
Another downside is that, for large grammars, this produces a *very*
large C function that some compilers can choke on.


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.


Of course, parsing isn't usually a bottleneck anymore, so go with what
you understand/feel comfortable with. For most, I suspect that's
recursive descent.


Cheers,
Carl Cerecke

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