9 Mar 2003 17:21:39 -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: | 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.