|Q:How to Speedup yacc based parsers? Venkateswara.Rao@cho.ge.com (Venkateswara Rao) (1997-03-07)|
|Re: Q:How to Speedup yacc based parsers? john_reiser@MENTORG.COM (1997-03-14)|
|Re: Q:How to Speedup yacc based parsers? email@example.com (1997-03-16)|
|Re: Q:How to Speedup yacc based parsers? firstname.lastname@example.org (John Lilley) (1997-03-16)|
|Re: Q:How to Speedup yacc based parsers? email@example.com (Alexander Krotoff) (1997-03-16)|
|Re: Q:How to Speedup yacc based parsers? firstname.lastname@example.org (Scott Stanchfield) (1997-03-18)|
|Re: Q:How to Speedup yacc based parsers? email@example.com (Carl Cerecke) (1997-03-21)|
|From:||Carl Cerecke <firstname.lastname@example.org>|
|Date:||21 Mar 1997 10:16:27 -0500|
|References:||97-03-036 97-03-067 97-03-069|
|Keywords:||parse, yacc, performance|
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
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
|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.
Return to the
Search the comp.compilers archives again.