[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