Re: Compress the finite state machine

Chris F Clark <cfc@world.std.com>
4 Mar 1999 12:10:12 -0500

          From comp.compilers

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]
| List of all articles for this month |

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.