24 Feb 2003 13:51:43 -0500

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) |

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.