[antlr-interest] Re: Parser performance

[lgcraymer]

On 3.0:

Ter's DFA approach will also speed up the parsing engine; interestingly enough, it may also apply to tree walkers and lead to k>1 
support.  AST generation can be significantly optimized (ANTLR 2 does no optimization), and Ter is starting down a path that could 
support that--basically, what you would need is a tree generation (static) analysis pass coupled with some dynamic runtime 
"analysis" (build an tree constructor instruction stream, and edit it on the fly before generating code).  Stay tuned.

--Loring


--- In antlr-interest at yahoogroups.com, Terence Parr <parrt at c...> wrote:
> 
> 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/