[antlr-interest] Re: [antlr-dev] holy crap! optimization from allah!

[Prashant Deva]

You should write a blog entry about it.
This way all of us who are not following the code changes itself can find
out what the super optimization was, too :)

On 5/23/06, Terence Parr <parrt at cs.usfca.edu> wrote:
>
> You know how somedays things just go right?  Well I have been trying
> to solve a problem with the ASN grammar as submitted to me by Magne
> Rasmussen...at first I thought it was a bug but now I think it is
> just hitting an exponentiality in the algorithm.  So I started
> thinking again about how to speed the analysis up...I have spent
> hours thinking and thinking about how the algorithm works, which is
> how I decided it was still solid.  I did think of one minor
> optimization...when I added it (1 IF statement!), analysis dropped by
> 90% or so!!!  Hooray!  Analysis is now down to about 10% of total
> time from 1/3. :)
>
> The optimization avoid computing the closure operation on states that
> are only capable of predicting a single alternative (as analysis will
> stop with that state); no point in computing closure, which is very
> expensive.
>
> Magne: still hitting landmines in the grammar, but I am still working
> on it!
>
> Ter
> _______________________________________________
> antlr-dev mailing list
> antlr-dev at antlr.org
> http://www.antlr.org/mailman/listinfo/antlr-dev
>



-- 
Prashant Deva
Creator, ANTLR Studio
Founder, Placid Systems, www.placidsystems.com
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.antlr.org/pipermail/antlr-interest/attachments/20060523/eec37ec0/attachment.html