autogen_back

AutoFSM - Automated Finite State Machine

Main
AutoGen
Pages

Home
Announce
FAQ
docs
XML Defs
testimonials
downloads

Automated
Options

AutoOpts
Comparison
Man example
Redistribute
Licensing
local use
using getopt

GCC's
Fixincludes

fixincludes

Automated
FSM

description
example
usagefsm

Addons
addon

Project GNU
Home Page

Automated
XDR

xdr project

i

AutoFSM is an add-on package to AutoGen. AutoGen actually includes AutoFSM because it uses its functionality itself. When you install AutoGen, the Finite State Machine templates will be installed in ${datadir}/autogen/fsm*.tpl.

Finite state machines can be constructed in a variety of ways. Some of them can be assisted with generated text and others cannot. Or, at least, they cannot be generated very well. What can be generated very well are the transition tables derived from the machine definition.

Here is the list of attributes that various flavors of software finite state machines may have.

Transition Event Detection
There is no way to select among these detection methods. ``state-independent'' is assumed, but you have ``adjustments'' available to you when your transition handling code is invoked.
state-independent
If the transition event can be recognized without reference to the current machine state, it is state-independent. If you cannot determine the next transition event without knowing the state, then it is state-dependent.
state-dependent
Generally, transition tables are not very helpful for a state-dependent machine.
combination
Very often, you can mostly determine the transition event independently of the current state. For these occasions, this Finite State Machine generator will allow you to ``adjust'' the state during transition processing.

FSM Type
The finite state machine may be either the master, driving the other parts of the program, or act as a subroutine keeping track of state between calls. Consequently, the type attribute may be set to:
looping
If the machine processes transitions until it reaches a terminal state (error or done).
stepping
If the FSM code must only process a single transition and then return.
reentrant
If the application must run the FSM from multiple independent threads and the FSM code must only process a single transition and then return.

implementation method
AutoFSM gives you a choice of implementations. You can specify which with the method attribute. If you omit the attribute or specify ``none'', then only a header file containing a transition table will be produced.
callout
This method will use a callout table instead of a switch statement to implement the machine.
case
This is the alternate implementation method.
none
Choosing this method suppresses the prototype implementation.


AutoFSM supports all four variations of the state-independent or nearly-state-independent transition machines, plus the transition table only output. To use this, you must set up a Finite State Machine AutoGen definitions file that defines:

  • a list of events,
  • a list of states, and
  • a list of transitions.

The events and states are simply names you provide for the transition types and processing states. The transition entries are entries that specify an initial state, the result state and a transition type. By default, the transition type is named after the original state and the transition event. However, you may also specify a name in order to allow several different transitions to be handled with the same code.

The output is currently a set of defines, a transition table suitable for compiling into a C or C++ program, and, optionally, a prototype implementation. There is nothing to restrict output in another language, there just happens not to be any templates to produce other languages at the moment. Watch this space if you have interest in finite state machines in other languages.

Here is an example of a case method machine, and a usage page for a description of the FSM attributes. AutoGen itself uses AutoFSM for three parsing functions. Only the two .c files are linked to here as the generated .h header files are not archived under CVS:


agen5/cgi.def  produces cgi-fsm.c and cgi-fsm.h. These are used to scan CGI script values for conversion into AutoGen definitions.
pseudo.def  produces pseudo-fsm.h, which is used in the file loadPseudo.c. That FSM does not produce any code. The table produced is used to parse the pseudo macro at the start of a template.
defParse.def  produces defParse-fsm.c and defParse-fsm.h. This code drives the parsing of the definition files.

top  Viewable With Any Browser  Valid XHTML 1.0!


AutoGen, AutoOpts, columns, getdefs, AutoFSM, AutoXDR and these web pages copyright (c) 1999-2002 Bruce Korb, all rights reserved.

Return to GNU's home page.

Please send FSF & GNU inquiries & questions to gnu@gnu.org. There are also other ways to contact the FSF.

Please send comments on these web pages to webmasters@www.gnu.org, send other questions to gnu@gnu.org.

This article, Copyright © 2000-2002 by Bruce Korb

Verbatim copying and distribution of this entire article is permitted in any medium, provided this notice is preserved. Last modified: Sun Oct 1 12:59:14 PDT 2006