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

Terence Parr parrt at cs.usfca.edu
Mon May 22 16:02:01 PDT 2006


On May 22, 2006, at 3:47 PM, Prashant Deva wrote:

> 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 :)

It comes down to

a : A
   | B
   ;

When building a DFA, you have 3 states

s1 -A-> s2
s1 -B-> s3

where s2, s3 are accept states and predict alt 1, 2 respectively.   
The point is that s2 and s3 are not going to lead to any other  
states..ever.  They uniquely predict alts 1 and 2.  Do not compute  
closure on these as there is no need.  Worse, it amounts to computing  
FOLLOW(a), which will find all refs to rule a and then do a closure  
on every state that can follow that state etc...

Saves a lot apparently ;)

Ter


More information about the antlr-interest mailing list