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.


: [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
speed)


--
John McEnerney (mcenerney@metrowerks.com)
--

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