# Re: DFA transition table reduction by alphabet reduction.

## Christian Riis <criis@ivalde.diku.dk>9 Mar 2003 17:21:39 -0500

From comp.compilers

Related articles
DFA transition table reduction by alphabet reduction. criis@tyr.diku.dk (Christian Riis) (2003-02-21)
Re: DFA transition table reduction by alphabet reduction. clint@0lsen.net (Clint Olsen) (2003-02-24)
Re: DFA transition table reduction by alphabet reduction. criis@ivalde.diku.dk (Christian Riis) (2003-03-09)
Re: DFA transition table reduction by alphabet reduction. gah@ugcs.caltech.edu (Glen Herrmannsfeldt) (2003-03-14)
| List of all articles for this month |

 From: Christian Riis Newsgroups: comp.compilers Date: 9 Mar 2003 17:21:39 -0500 Organization: Department of Computer Science, University of Copenhagen References: 03-02-106 03-02-138 Keywords: lex, DFA Posted-Date: 09 Mar 2003 17:21:39 EST

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

Post a followup to this message