"Julian V. Noble" <jv*@virginia.eduwrote in message
news:ec**********@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/cla...all01/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/cla...all01/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
