Re: Q:How to Speedup yacc based parsers? (John McEnerney)
16 Mar 1997 23:06:09 -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: (John McEnerney)
Newsgroups: comp.compilers
Date: 16 Mar 1997 23:06:09 -0500
Organization: Metrowerks, Inc.
References: 97-03-036 97-03-067
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.

: [I would do a little performance measurement before doing any tuning. You'll
: probably find that your lexer takes a lot more time than your parser. -John]

I agree with John here, most of the time is spent in the scanner
unless you've hand-tuned it for performance. If you have already done
that, read on...

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)

Tom cites a speed improvement of about 6.5X on an (early) x86 machine,
with a code size expansion of 2X-4X. At my last job we implemented
this for a 68K machine and found the LALR(1) parser to be nearly as
fast as a hand-coded (assembly-language!) recursive-descent parser. It
requires a little effort to make the interface to the semantic
routines as fast as possible as well. You could probably modify Yacc
to generate something like this with a few weeks' work.

Tom's paper ends with the observation that most of the time spent in a
compiler is spent elsewhere, so it may not be worth the effort to
reduce the parser overhead. Our experience did not support this
theory--turnaround speed was a key factor in the success of our
compiler, so it was mostly run in a non-optimizing mode, and Yacc-like
parsing overhead would have been quite noticeable. (We had already
coded the scanner and symbol-table routines in assembly language for

John McEnerney (

Post a followup to this message

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