Re: DFA transition table reduction by alphabet reduction.

Clint Olsen <clint@0lsen.net> writes:


> Christian Riis wrote:
> > I'm writing a project about a certain scheme to reduce the size of DFA
> > transition tables. The idea is to make transtions on only a certain
> > number of the bits (half the bits for instance) in the letters in the
> > alfabet of a given DFA to an intermediate state and from there make
> > transitions on the rest of the bits. If one splits the transitions up in
> > two halves of equal size, the number of letters in the resulting alfabet
> > will of course have as many letters as the square root of the number of
> > letters in the original alfabet. What I'm hoping is, that the number of
> > states will increase less than the decrease of letters.
>
> I don't see why you absolutely need to use transition tables. If you
> use the directly executable method of this using explicit character
> range tests, the transitions should be quite compact. Re2c uses this
> technique. If there are a lot of transitions out of a particular
> state it splits the ranges using a binary search technique to minimize
> the number of tests.


Yes well, I'm writing a project about the method I have described
above. As such I don't care much how well it performs but in the
theoretical "virtues" of the method I have selected. It could
revolutionize the world of lexer generation og suck immensely and it
would all be the same to me, although I would prefer the former
alternative. :) As far as I can see re2c bears only a slight
resemblence to what I'm interested in (i.e. the part about range
tests). It appears to me to be a relatively straightforward lexer
generator whose strength lies in generality.


Regards.
Christian

Return to the comp.compilers page.
Search the comp.compilers archives again.