Nested FSM implementation
Polomora
I've done a bit of searching here on c.l.c, and I also checked out SMC at
soureforge, but haven't been able to find what I'l looking for.
I've got two FSMs: A and B, where I want to embed B inside one of A's
states. Plus I want to be able to use FSM B separately. Can anyone think of
an elegant way to this using C code.
SMC looked promising, however, it doesn't support nested FSMs.
Many thanks,
Paul
Kenny McCormack
jacob navia
Acronyms are a plague
if (FSM == "Finite State Machine") {
printf("Off topic in this newsgroup\n");
printf("Use another newsgroup\n");
}
else
{
printf("What is a \"FSM\"\n");
}
Julian V. Noble
Think of a deterministic FSM as a 2-dim table. The row labels are
states, the column labels are inputs. The table entries have two
parts: an action and a transition to the appropriate state following
that action.
The FSM must have a place to keep the current state. Before you
enter the FSM you must initialize the state to 0. You also need
a function that translates your input data to a column label. To
get to the appropriate table entry you compute an offset from
the base address:
offset_in_address_units = column# + row# * width
where width is the number of cells in a row.
Perhaps a struct would be the best way to program this, with each
cell holding two function addresses, one for the action and one
for the next state transition. Alternatively you might represent
the FSM as a giant switch construct.
I don't know any elegant way to do this in C. It would probably
be easier in an object-oriented language like C++ where you can
package code with the data structure. I have only done it in Forth
where it was also relatively easy.
You might try to devise a mini-language for constructing FSMs and
implementing its translation to C with YACC.
Once you have done this, however, and represented the FSM as a
function, you can easily embed that function as an action in
another FSM.
Finally, I have an online article on FSMs that mentions some
C software tools that were available several years ago:
http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html
You might try to see whether some of these are still available
before trying to roll your own.
--
Julian V. Noble
Professor Emeritus of Physics
University of Virginia
Rod Pemberton
"Julian V. Noble" <j...@virginia.edu> wrote in message
news:ecciju$spq$1...@murdoch.acc.Virginia.EDU...
> Think of a deterministic FSM as a 2-dim table. The row labels are
> states, the column labels are inputs. The table entries have two
> parts: an action and a transition to the appropriate state following
> that action.
>
> The FSM must have a place to keep the current state. Before you
> enter the FSM you must initialize the state to 0. You also need
> a function that translates your input data to a column label. To
> get to the appropriate table entry you compute an offset from
> the base address:
>
> offset_in_address_units = column# + row# * width
>
> where width is the number of cells in a row.
>
> Perhaps a struct would be the best way to program this, with each
> cell holding two function addresses, one for the action and one
> for the next state transition. Alternatively you might represent
> the FSM as a giant switch construct.
>
Using a struct eliminates any correlation with the data in the FSM table.
Also, alignment issues and padding problems may slow the code down. I would
recommend creating two 2-dim tables ("arrays" in C).
> Finally, I have an online article on FSMs
<snip>
>
> http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html
>
> I don't know any elegant way to do this in C. It would probably
> be easier in an object-oriented language like C++ where you can
> package code with the data structure. I have only done it in Forth
> where it was also relatively easy.
>
I found your article to be interesting, so here is a Public Domain C version
of the example on your web-page. Unfortunately, in C there is no portable
way to get a character without echoing it to the screen. C always combines
FORTH's KEY and EMIT. Since this is necessary for your FSM example, the
code has some DOS specific code which should be easy to modify for other
OS's such as Linux.
/* port of a FORTH Finite State Machine by JV Noble */
/* C version by Rod Pemberton */
/* released to the Public Domain */
/* September 8th, 2006 */
#if 0
http://galileo.phys.virginia.edu/classes/551.jvn.fall01/fsm.html
#endif
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h> /* for non-echo get() */
void getstate(unsigned char *ch)
{
/* These two commented out are ISO, */
/* but they echo which we don't want... */
/* *ch=getchar(); */
/* scanf("%c",ch); */
/* non-ISO, non-echo getc() */
/* this will need to be modified */
/* to work for non-DOS systems */
while(!kbhit());
*ch=getch();
if(*ch==0x1a) /* ctrl-Z for EOF */
exit(EXIT_SUCCESS);
}
void echo(unsigned char ch)
{
printf("%c",ch);
fflush(stdout);
}
int other(unsigned char ch)
{
int result=0;
/* empty */
return(result);
}
int digit(unsigned char ch)
{
int result=0;
/* isdigit() is fine too... */
if(strchr("0123456789",ch)!=NULL)
result=1;
return(result);
}
int minus(unsigned char ch)
{
int result=0;
if(ch=='-')
result=1;
return(result);
}
int dp(unsigned char ch)
{
int result=0;
if(ch=='.')
result=1;
return(result);
}
#define MAXSTATES 3
#define MAXINPUTS 4
int main(void)
{
unsigned char state=0,input=0,mystate;
/* RP chose to use two arrays instead */
/* of a struct with pointers to functions */
/* to keep the initialization similar to */
/* JV Noble's FORTH FSM tables */
unsigned char action[MAXSTATES][MAXINPUTS]
={
{'X','E','E','E'},
{'X','E','X','E'},
{'X','E','X','X'} /* no comma */
};
unsigned char transition[MAXSTATES][MAXINPUTS]
={
{0,1,1,2},
{1,1,1,2},
{2,2,2,2} /* no comma */
};
while(1)
{
getstate(&mystate);
input=0*other(mystate)
+1*digit(mystate)
+2*minus(mystate)
+3*dp(mystate);
switch(action[state][input])
{
case 'X': /* no action */
break;
case 'E': echo(mystate);
break;
}
state=transition[state][input];
}
}
Sincerely,
Rod Pemberton
webs...@gmail.com
I've never used any kind of infrastructure for implementing a finite
state machine (though I have heard of Teja). I just usually code them
up directly. But it seems to me that you can always have multiply
declared states, and transition through them easily, and that nesting
should not be a problem. I would say that an infrastructure that
didn't allow nesting is pretty weak and not really adding any value at
all versus just straight coding it (presumably a useful infrastructure
would make the nesting itself comparably useful.)
Unfortunately, I don't really have anything insightful to add, except
to say -- is just coding it directly really that bad?
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
EventHelix.com
I would recommend moving over to C++. The following articles would
help:
http://www.eventhelix.com/RealtimeMantra/HierarchicalStateMachine.htm
--
EventStudio 2.5 - http://www.EventHelix.com/EventStudio
Model in Plain Text; Generate Call Flow Diagrams in PDF/Word