Re: DFA transition table reduction by alphabet reduction.

Clint Olsen <clint@0lsen.net>
24 Feb 2003 13:51:43 -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: Clint Olsen <clint@0lsen.net>
Newsgroups: comp.compilers
Date: 24 Feb 2003 13:51:43 -0500
Organization: AT&T Broadband
References: 03-02-106
Keywords: lex, performance
Posted-Date: 24 Feb 2003 13:51:43 EST

  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.


I can't get to the re2c homepage now, but I believe it's at:


http://www.tildeslash.org/re2c


-Clint


Post a followup to this message

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