4 Mar 1999 12:10:12 -0500

Related articles |
---|

Compress the finite state machine felixmish@usa.net (Felix Mish) (1999-03-02) |

Re: Compress the finite state machine cfc@world.std.com (Chris F Clark) (1999-03-04) |

Re: Compress the finite state machine torbenm@diku.dk (Torben Mogensen) (1999-03-04) |

Re: Compress the finite state machine jes6@eecs.lehigh.edu (James E. Stine) (1999-03-04) |

Re: Compress the finite state machine allanmac@blueprint.com (Allan MacKinnon) (1999-03-04) |

Re: Compress the finite state machine hunk@alpha1.csd.uwm.edu (1999-03-04) |

Re: Compress the finite state machine stans@lucent.com (Sicco Tans) (1999-03-10) |

Re: Compress the finite state machine torbenm@diku.dk (Torben Mogensen) (1999-03-22) |

[1 later articles] |

From: | Chris F Clark <cfc@world.std.com> |

Newsgroups: | comp.compilers |

Date: | 4 Mar 1999 12:10:12 -0500 |

Organization: | The World Public Access UNIX, Brookline, MA |

References: | 99-03-010 |

Keywords: | DFA |

Felix Mish wrote:

*> I am evaluating the ways to compress the finite state machine.*

*> Is there anyone be kind enough to provide some possible solutions?*

If you mean "compress the representation of the states of an FSA (as a

table)", I would recommend you read:

@article{table-optim,

author = {P. Dencker and K. D{\"{u}}rre and J. Heuft},

title = {{O}ptimization of {P}arser {T}ables for {P}ortable {C}ompilers},

journal = "TOPLAS",

volume = 6,

number = 4,

pages = "546--572",

year = 1984,

*}*

The article essentially covers every packing algorithm which might be

applied to a state table. The only algorithm I know of that they

don't cover is constructing "tunnel automatons". However, one of

their row or column packing algorithms can be modified to have

essentially the same effect. For more info on "tunnel automatons",

see:

@article{tunnel,

author = "J. Grosch",

title = {{E}fficient {G}eneration of {L}exical {A}nalysers},

journal = "Software--Practice and Experience",

volume = "19",

number = "11",

pages = "1089--1103",

month = "November",

year = "1989",

*}*

If you mean to "optimize the finite state machine so that it has fewer

states", I don't have any recommendations. I vaguely recall that

there might be an algorithm in the dragon book that works by creating

equivalence classes.

(As you might guess, I have on several occassions done the former and

never done the later.)

Hope this helps,

-Chris

*****************************************************************************

Chris Clark Internet : cfc@world.std.com

Compiler Resources, Inc. CompuServe : 74252,1375

3 Proctor Street voice : (508) 435-5016

Hopkinton, MA 01748 USA fax : (508) 435-4847 (24 hours)

------------------------------------------------------------------------------

Web Site in Progress: Web Site : http://world.std.com/~compres

Post a followup to this message

Return to the
comp.compilers page.

Search the
comp.compilers archives again.