[antlr-interest] Parser performance

Terence Parr parrt at cs.usfca.edu
Mon Mar 22 10:55:33 PST 2004


On Mar 22, 2004, at 10:37 AM, Donovan, Bob wrote:

> Terence,
>
> Are you saying we should see a performance improvement in antlr 3.0?

Hi Bob,

Yes.  A huge weakness in ANTLR 2 is the speed of the lexers.  There are 
two main reasons: huge overhead and (I'm guessing) poor prediction 
speed between rules.

ANTLR 3.0 will derive its speed partially from an improved prediction 
algorithm that is not only faster but also much more powerful.  
Essentially, k-token lookahead can be seen as a DFA acyclic prediction 
machine of depth k.  Allow lookahead DFA cycles and all of a sudden you 
allow k to vary arbitrarily :)  It degenerates to fixed lookahead when 
necessary, but predicts which alt to match in one shot rather than in 
successive testing (if-then-else sequences) as it does now.  The other 
benefit is that only a single symbol of lookahead is required at any 
point, dramatically reducing the infrastructure from a window of tokens 
to essentially:

int tokenType;

or

int c;

for characters.

<snicker>

> I looked on the website for info about when 3.0 is due out, but I 
> didn't see anything. Any thoughts on a release date?

I hope to have the core parsing engine done this summer and then I must 
study the user-level semantics like attributes, tree construction 
etc...  Loring, Monty and I have discussed this stuff at length, but I 
must propose stuff, get it past you folks, and then implement it! ;)  
Don't expect 3.0 any time soon.  It may be useful to people in the Fall 
if they don't need much in the way of support such as trees.  I'm first 
focusing on the core analysis and code gen portions.

In its full glory, 3.0 won't be ready for quite a while, though I 
expect to release multiple completion levels on my way up to full 3.0 
functionality :)

Ter
--
Professor Comp. Sci., University of San Francisco
Creator, ANTLR Parser Generator, http://www.antlr.org
Cofounder, http://www.jguru.com
Cofounder, http://www.knowspam.net enjoy email again!
Cofounder, http://www.peerscope.com pure link sharing





 
Yahoo! Groups Links

<*> To visit your group on the web, go to:
     http://groups.yahoo.com/group/antlr-interest/

<*> To unsubscribe from this group, send an email to:
     antlr-interest-unsubscribe at yahoogroups.com

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



More information about the antlr-interest mailing list