[antlr-interest] new DFA implementation for generated v3 recognizers

Terence Parr parrt at cs.usfca.edu
Sat Mar 25 23:11:14 PST 2006


On Mar 25, 2006, at 6:24 PM, Jeff Barnes wrote:
>> I'd waste all the space in between.  This
>> will waste 64k ints
>> for any state that does that, but naturally, I'll
>> push that to a
>> "special" state.
>>
>
> So you'll have varying degrees of optimity in the time
> domain, with no optimity in the space domain...

Well, for ascii and all unicode states with only a few edges, I'm as  
close to optimal in time/space as you can expect.  What I'm doing is  
fairly typical for the old ascii-based dfa-based lexer generators  
like lex.  I could even optimize the size of the elements to char  
from int for state numbers etc...  I'll try it out and see what we get.

> How are you constructing the "special" states?

switch on char or if-then-else depending on the edges.  If  
predicates, it's perforce if-then-else.

Got another suggestion?  I'm all ears!

Ter


More information about the antlr-interest mailing list