[antlr-interest] open-ended speed question: order of magnitude comparison?

John D. Mitchell johnm-antlr at non.net
Mon Nov 24 20:14:43 PST 2003


'netiquette nanny says: Top posting is Evil(tm)!

>>>>> "Terence" == Terence Parr <parrt at cs.usfca.edu> writes:
[...]

> is this: the theoretical complexity is linear for ANTLR's basic LL and
> yacc-n-friends LR-based stuff.  So, the thing you're fighting is the
> constant on the front.  That is, how fast can you spin in a for-loop or
> walk thru a state-machine.  Back in the 80's, tom pennello who works with
> deremer (inventor of LALR) did an LALR to x86 machine code generator.
> That damn thing was FAST!

I was tangentially involved with an assembler a long time ago.  It was a
multi-pass macro-assembler for x86 assembly language written in yacc/bison.
It wasn't as fast as we liked (since we had millions of lines of x86
assembly language code -- an entire OS and application suite :-)) so it was
profiled.  Putting in a special case in the read I/O routine so that it
understood and discarded comments all by itself (which, of course, is a
major hack).  Modifying that "constant factor" made the entire translation
on the order of 50% faster (and that was after tuning the base I/O routines
:-).

Take care,
	John

 

Your use of Yahoo! Groups is subject to http://docs.yahoo.com/info/terms/ 




More information about the antlr-interest mailing list