autogen_back

AutoFSM Example

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

Here is a simple example. It decides whether or not the input properly represents a list of value ranges. The input syntax is approximately:


   [[ '!' ] <lo-num>] ['-' [<hi-num>]] \
      [',' [[ '!' ] <lo-num>] ['-' [<hi-num>]] ... ]
If there is no hyphen, then a number must be present. You should not have more than one "bang" operator, but this FSM does not check for that.

This page contains:




The input definitions

See the usage page for a description of the attributes supported.


AutoGen Definitions fsm;

event  = comma, num,  dash, bang, eol;
state  = lonum, dash, hinum;
type   = looping;
method = case;
prefix = ex;
cookie = "void* cookie";

dash   = "-";
bang   = "!";
eol    = "End-Of-Line";
comma  = ",";

/*
 *  Define a transition for every valid transition.
 *  Specify the Transition_STate, the TransitionEVent and
 *  what the NEXT state will be.  A unique transition
 *  enumeration will be produced for each defined transition.
 */
transition = { tst = init; tev = num;  next = lonum; };
transition = { tst = init; tev = bang; next = init;  };
transition = { tst = dash; tev = num;  next = hinum; };

/*
 *  Dash transition.  Always go to 'dash' state, except when we are in
 *  the 'hinum' or 'dash' state.  Then, do the 'invalid' transition.
 */
transition = { tst = "*";   tev = dash; next = dash; },
  { tst = hinum, dash; tev = dash; ttype = invalid; next = invalid; };

/*
 *  Comma transition, other than in 'init'.  You cannot have two
 *  commas together and you cannot start with one.  Transitions out of
 *  "hinum" state require no processing.
 */
transition = { tst = "*";  tev = comma; next = init; },
  { tst = hinum; tev = comma; ttype = noop;    next = init; },
  { tst = init;  tev = comma; ttype = invalid; next = invalid; };

/*
 *  End of line transition, other than in 'init'.
 *  You cannot end with a comma or without any ranges specified.
 */
transition = { tst = "*";  tev = eol; next = done; },
  { tst = hinum; tev = eol; ttype = noop;    next = done; },
  { tst = init;  tev = eol; ttype = invalid; next = invalid; };
back to top


The resulting header file:

#ifndef AUTOFSM_EXAMPLE_FSM_H_GUARD
#define AUTOFSM_EXAMPLE_FSM_H_GUARD

/*
 *  Finite State machine States
 *
 *  Count of non-terminal states.  The generated states INVALID and DONE
 *  are terminal, but INIT is not  :-).
 */
#define EX_STATE_CT  4
typedef enum {
    EX_ST_INIT,    EX_ST_LONUM,   EX_ST_DASH,    EX_ST_HINUM,   EX_ST_INVALID,
    EX_ST_DONE
} te_ex_state;

/*
 *  Finite State machine transition Events.
 *
 *  Count of the valid transition events
 */
#define EX_EVENT_CT 5
typedef enum {
    EX_EV_COMMA,   EX_EV_NUM,     EX_EV_DASH,    EX_EV_BANG,    EX_EV_EOL,
    EX_EV_INVALID
} te_ex_event;

/*
 *  Run the FSM.  Will return EX_ST_DONE or EX_ST_INVALID
 */
extern te_ex_state
ex_run_fsm(
    void* cookie );

#endif /* AUTOFSM_EXAMPLE_FSM_H_GUARD */
back to top


And the associated code file:

#define DEFINE_FSM
#include "example-fsm.h"
#include <stdio.h>

/*
 *  Do not make changes to this file, except between the START/END
 *  comments, or it will be removed the next time it is generated.
 */
/* START === USER HEADERS === DO NOT CHANGE THIS COMMENT */
/* END   === USER HEADERS === DO NOT CHANGE THIS COMMENT */

#ifndef NULL
#  define NULL 0
#endif

/*
 *  Enumeration of the valid transition types
 *  Some transition types may be common to several transitions.
 */
typedef enum {
    EX_TR_DASH_COMMA,
    EX_TR_DASH_EOL,
    EX_TR_DASH_NUM,
    EX_TR_INIT_BANG,
    EX_TR_INIT_DASH,
    EX_TR_INIT_NUM,
    EX_TR_INVALID,
    EX_TR_LONUM_COMMA,
    EX_TR_LONUM_DASH,
    EX_TR_LONUM_EOL,
    EX_TR_NOOP
} te_ex_trans;
#define EX_TRANSITION_CT  11

/*
 *  the state transition handling map
 *  This table maps the state enumeration + the event enumeration to
 *  the new state and the transition enumeration code (in that order).
 *  It is indexed by first the current state and then the event code.
 */
typedef struct ex_transition t_ex_transition;
struct ex_transition {
    te_ex_state  next_state;
    te_ex_trans  transition;
};
static const t_ex_transition
ex_trans_table[ EX_STATE_CT ][ EX_EVENT_CT ] = {

  /* STATE 0:  EX_ST_INIT */
  { { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  , */
    { EX_ST_LONUM, EX_TR_INIT_NUM },                /* EVT:  num */
    { EX_ST_DASH, EX_TR_INIT_DASH },                /* EVT:  - */
    { EX_ST_INIT, EX_TR_INIT_BANG },                /* EVT:  ! */
    { EX_ST_INVALID, EX_TR_INVALID }                /* EVT:  End-Of-Line */
  },


  /* STATE 1:  EX_ST_LONUM */
  { { EX_ST_INIT, EX_TR_LONUM_COMMA },              /* EVT:  , */
    { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  num */
    { EX_ST_DASH, EX_TR_LONUM_DASH },               /* EVT:  - */
    { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  ! */
    { EX_ST_DONE, EX_TR_LONUM_EOL }                 /* EVT:  End-Of-Line */
  },


  /* STATE 2:  EX_ST_DASH */
  { { EX_ST_INIT, EX_TR_DASH_COMMA },               /* EVT:  , */
    { EX_ST_HINUM, EX_TR_DASH_NUM },                /* EVT:  num */
    { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  - */
    { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  ! */
    { EX_ST_DONE, EX_TR_DASH_EOL }                  /* EVT:  End-Of-Line */
  },


  /* STATE 3:  EX_ST_HINUM */
  { { EX_ST_INIT, EX_TR_NOOP },                     /* EVT:  , */
    { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  num */
    { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  - */
    { EX_ST_INVALID, EX_TR_INVALID },               /* EVT:  ! */
    { EX_ST_DONE, EX_TR_NOOP }                      /* EVT:  End-Of-Line */
  }
};


#define ExFsmErr_off     19
#define ExEvInvalid_off  75
#define ExStInit_off     83


static char const zExStrings[127] =
    "** OUT-OF-RANGE **\0"
    "FSM Error:  in state %d (%s), event %d (%s) is invalid\n\0"
    "invalid\0"
    "init\0"
    "lonum\0"
    "dash\0"
    "hinum\0"
    ",\0"
    "num\0"
    "-\0"
    "!\0"
    "End-Of-Line\0";

static const size_t aszExStates[4] = {
    83, 88, 94, 99 };

static const size_t aszExEvents[6] = {
    105, 107, 111, 113, 115, 75 };


#define EX_EVT_NAME(t)   ( (((unsigned)(t)) >= 6) \
    ? zExStrings : zExStrings + aszExEvents[t])

#define EX_STATE_NAME(s) ( (((unsigned)(s)) >= 4) \
    ? zExStrings : zExStrings + aszExStates[s])

#ifndef EXIT_FAILURE
# define EXIT_FAILURE 1
#endif

/* * * * * * * * * THE CODE STARTS HERE * * * * * * * *
 *
 *  Print out an invalid transition message and return EXIT_FAILURE
 */
int
ex_invalid_transition( te_ex_state st, te_ex_event evt )
{
    /* START == INVALID TRANS MSG == DO NOT CHANGE THIS COMMENT */
    fprintf( stderr, zExStrings + ExFsmErr_off, st, EX_STATE_NAME(st),
             evt, EX_EVT_NAME(evt));
    /* END   == INVALID TRANS MSG == DO NOT CHANGE THIS COMMENT */

    return EXIT_FAILURE;
}

/*
 *  Run the FSM.  Will return EX_ST_DONE or EX_ST_INVALID
 */
te_ex_state
ex_run_fsm(
    void* cookie )
{
    te_ex_state ex_state = EX_ST_INIT;
    te_ex_event trans_evt;
#ifdef DEBUG
    te_ex_state firstNext;
#endif
    te_ex_state nxtSt;
    te_ex_trans trans;

    while (ex_state < EX_ST_INVALID) {

        /* START == FIND TRANSITION == DO NOT CHANGE THIS COMMENT */
        trans_evt = GET_NEXT_TRANS();
        /* END   == FIND TRANSITION == DO NOT CHANGE THIS COMMENT */

        if (trans_evt >= EX_EV_INVALID) {
            nxtSt = EX_ST_INVALID;
            trans = EX_TR_INVALID;
        } else {
            const t_ex_transition* pTT =
            ex_trans_table[ ex_state ] + trans_evt;
#ifdef DEBUG
            firstNext = /* next line */
#endif
            nxtSt = pTT->next_state;
            trans = pTT->transition;
        }

#ifdef DEBUG
        printf( "in state %s(%d) step %s(%d) to %s(%d)\n",
            EX_STATE_NAME( ex_state ), ex_state,
            EX_EVT_NAME( trans_evt ), trans_evt,
            EX_STATE_NAME( nxtSt ), nxtSt );
#endif

        switch (trans) {
        case EX_TR_DASH_COMMA:
            /* START == DASH_COMMA == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_DASH_COMMA();
            /* END   == DASH_COMMA == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_DASH_EOL:
            /* START == DASH_EOL == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_DASH_EOL();
            /* END   == DASH_EOL == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_DASH_NUM:
            /* START == DASH_NUM == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_DASH_NUM();
            /* END   == DASH_NUM == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_INIT_BANG:
            /* START == INIT_BANG == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_INIT_BANG();
            /* END   == INIT_BANG == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_INIT_DASH:
            /* START == INIT_DASH == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_INIT_DASH();
            /* END   == INIT_DASH == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_INIT_NUM:
            /* START == INIT_NUM == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_INIT_NUM();
            /* END   == INIT_NUM == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_INVALID:
            /* START == INVALID == DO NOT CHANGE THIS COMMENT */
            exit( ex_invalid_transition( ex_state, trans_evt ));
            /* END   == INVALID == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_LONUM_COMMA:
            /* START == LONUM_COMMA == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_LONUM_COMMA();
            /* END   == LONUM_COMMA == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_LONUM_DASH:
            /* START == LONUM_DASH == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_LONUM_DASH();
            /* END   == LONUM_DASH == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_LONUM_EOL:
            /* START == LONUM_EOL == DO NOT CHANGE THIS COMMENT */
            nxtSt = HANDLE_LONUM_EOL();
            /* END   == LONUM_EOL == DO NOT CHANGE THIS COMMENT */
            break;


        case EX_TR_NOOP:  break;
        default:
            /* START == BROKEN MACHINE == DO NOT CHANGE THIS COMMENT */
            exit( ex_invalid_transition( ex_state, trans_evt ));
            /* END   == BROKEN MACHINE == DO NOT CHANGE THIS COMMENT */
        }
#ifdef DEBUG
        if (nxtSt != firstNext)
            printf( "transition code changed destination state to %s(%d)\n",
                EX_STATE_NAME( nxtSt ), nxtSt );
#endif
        ex_state = nxtSt;
    }
    return ex_state;
}

And a PDF state diagram

This PDF file was derived utilizing the att-fsm.tpl template. That template produces the FSM definitions used by the AT&T Research FSM tools. One of those programs will produce a PostScript drawing and ps2pdf can be used to produce this output:
    autogen -L ~/ag/autofsm -Tatt-fsm example.def
    arcopt='-i example-att.arc -o example-att.arc'
    fsmcompile ${arcopt} -S example-att.ste example-att.fsm | \
      fsmdraw ${arcopt} -s example-att.ste > example.dot
    dot -Tps example.dot > example.ps
    ps2pdf example.ps example.pdf
The "/1" appearing in the output are default transition costs. You can get different costs by specifying a cost attribute for each transition. For example:
   cost = 0.123;
This template is not part of the AutoGen distribution. It is available within the separately downloadable package: AutoFSM.

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:18 PDT 2006