Mon, 01 Oct 2007 15:07:29 GMT

Related articles |
---|

Perfecting State Elimination bjoern@hoehrmann.de (Bjoern Hoehrmann) (2007-10-01) |

Re: Perfecting State Elimination anton@mips.complang.tuwien.ac.at (2007-10-01) |

Re: Perfecting State Elimination bjoern@hoehrmann.de (Bjoern Hoehrmann) (2007-10-01) |

From: | anton@mips.complang.tuwien.ac.at (Anton Ertl) |

Newsgroups: | comp.compilers |

Date: | Mon, 01 Oct 2007 15:07:29 GMT |

Organization: | Institut fuer Computersprachen, Technische Universitaet Wien |

References: | 07-10-006 |

Keywords: | DFA, lex, optimize |

Bjoern Hoehrmann <bjoern@hoehrmann.de> writes:

*> I am trying to find a method that will make regular expressions as*

*>short as possible (say, using only concatenation, alternation, zero or*

*>more repetition, characters and epsilon, I want to minimize the number*

*>of characters) given limited resources. I could not find much material*

*>on the problem on the web, except that I can turn the expression into*

*>a minimal DFA and the DFA into a regular expression using state elimi-*

*>nation, and that some removal sequences are better than others.*

My feeling is that that approach is wrong, because a regexp

corresponds to an NFA, and a DFA can be much larger than an equivalent

NFA, so a regexp generated from the DFA is likely to be suboptimal,

unless the DFA->regexp step reintroduces nondeterminism.

- anton

--

M. Anton Ertl

anton@mips.complang.tuwien.ac.at

http://www.complang.tuwien.ac.at/anton/

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.