Re: Compress the finite state machine

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

Return to the comp.compilers page.
Search the comp.compilers archives again.