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 <criis@ivalde.diku.dk>
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

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