[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