[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