Re: Q:How to Speedup yacc based parsers?

Venkateswara Rao (Venkateswara.Rao@cho.ge.com) wrote:
: I am working on a large parser (yacc based). I was wondering whether I
: can get some tips from the old hands in the group to improve on speed.
: I am using Abraxas PCYACC and Visual C++ 4.1 on NT4.0, if it matters.


John McEnerney wrote:
> If you don't mind getting your hands a little dirty, check out Tom
> Pennello's paper in the SIGPLAN '86 Symposium on Compiler Construction
> entitiled "Very Fast LR Parsers" The basic trick is to implement the
> states of the parser as labels in an assembly-language program, the
> transitions as conditional or unconditional branches, and the stacked
> set of states as return addresses. (These are usually called
> "direct-executable parsers)


[stuff on Tom Penello's paper snipped]


Another paper (actually a Tech report), entitled "Very Fast
YACC-Compatible Parsers (For Very Little Effort)" by Achyutram
Bhamidipaty and Todd A. Proebsting, discusses their contribution to
hard-coded parsers. They call their system mule (yacc -> bison ->
mule, hahaha), and claim speedups of 2.5 to 6.5 times over yacc or
bison. Some of the improvements over Tom's system that they claim are:
mule generates ANSI C, always checks for stack overflow, accepts yacc
grammars, maintains a semantic stack, and implements yacc-style error
recovery.


I obtained a copy of their code from the authors, and it seems like
I'm the only one to have asked for it. This `disclaimer' came from
Achyutram:


|Note, however, the code is FAR from rebust and in fact has several
|rather nasty kludges in it. Also there is absolutely no documentation
|at all. On the other hand, the intended behavior of the code is described
|in the tech report (which you must have since you know about mule!).


When I got mule working (which was less effort than I expected, but
did require hand insertion of code for some states) it produced
parsers which were at the top end of the claimed speedup, about 6
times faster than bison.


All-in-all I thought it was quite a nifty idea.
Cheers,
cdc
--

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