Re: Q:How to Speedup yacc based parsers?

Carl Cerecke <>
21 Mar 1997 10:16:27 -0500

          From comp.compilers

Related articles
Q:How to Speedup yacc based parsers? (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? (1997-03-16)
Re: Q:How to Speedup yacc based parsers? (John Lilley) (1997-03-16)
Re: Q:How to Speedup yacc based parsers? (Alexander Krotoff) (1997-03-16)
Re: Q:How to Speedup yacc based parsers? (Scott Stanchfield) (1997-03-18)
Re: Q:How to Speedup yacc based parsers? (Carl Cerecke) (1997-03-21)
| List of all articles for this month |

From: Carl Cerecke <>
Newsgroups: comp.compilers
Date: 21 Mar 1997 10:16:27 -0500
Organization: Compilers Central
References: 97-03-036 97-03-067 97-03-069
Keywords: parse, yacc, performance

Venkateswara Rao ( 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.

Post a followup to this message

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