用C实现有限状态机（FSM）

基本思想：
将有限状态机的对每个状态处理用一个个相同类型的函数（ 定义为FUNCTIONTYPE ）来实现,如：FunState_Start, FunState_1, ....FunState_n, FunState_End, State_Error.这些函数共享一个FUNCTIONTYPE类型的全局的函数指针pNextState并将它的初始值设为FunState_Start.在这些函数的内部，更具不同的输入修改pNextStat的值，使之指向下一个状态对应的函数，来模拟FSM。在实现有先自动机是，设置一个循环：
while( pNextState ！= FunSate_End&&pNextSate != FunState_Error)
｛
( ... )（*pNextState）（ ... ）;
｝

eg：用有限状态机实现的cdecl（解释复杂声明）：
//FSM 实现cdecl，为了简便这里省略了出错状态。
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <stdlib.h>

#pragma warning( disable: 4996 )

#define TOKENLEN 100
#define MAXTK 100
#define STACKSIZE 100


typedef void(*STATE)();
struct TOKEN
{
int Type;
char Content[TOKENLEN];
};

struct TOKEN tkDec[MAXTK];
struct TOKEN tkStack[STACKSIZE];
enum{ TYPE = 1, ID, QUA };

int sp = -1;
int Convertfail = 0;
STATE next = NULL;

struct TOKEN Pop()
{
struct TOKEN ret;
if( sp >= 0 )
return tkStack[sp --];
else
{
printf( "Stack empty" );
ret.Type = -1;
strcpy( ret.Content, "Stack empty" );
return ret;
}
}

void Push( struct TOKEN tk )
{
if( sp >= STACKSIZE -1 )
{
printf( "Stack Full.\n" );
return;
}
tkStack[++sp] = tk;
}

struct TOKEN GetTop()
{
struct TOKEN ret;
if( sp >= 0 )
return tkStack[sp];
else
{
printf( "Stack empty" );
ret.Type = -1;
strcpy( ret.Content, "Stack empty" );
return ret;
}
}




void ConvertSzToTokens( char * szDec )
{
char * c = szDec;
int index = 0;
char Buff[TOKENLEN] = { '\0' };
int BuffIndex = 0;
while( *c != '\0' )
{
while( *c == ' '||*c == '\t'||*c == '\n' )
{
c ++;
}
if( *c == '['|| *c == ']' || *c == '(' ||*c == ')' ||*c == '*'||*c == ',' )
{
(tkDec[index].Content)[0] = *c;
(tkDec[index].Content)[1] = '\0';
tkDec[index ++].Type = *c;
c ++;
continue;
}
while( *c != ' '&&*c != '\t'&&*c != '\n'&&*c != '['&&*c != ']'&&*c != '('&&*c != ')'&&*c != '*'&&*c != '\0'&&*c != ',' )
{
Buff[BuffIndex ++] = *c ++;
}
Buff[BuffIndex] = '\0';
BuffIndex = 0;
strcpy( tkDec[index].Content, Buff );
if( !strcmp( Buff, "int") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "long") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "short") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "unsigned") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "signed") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "float") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "double") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "char") ) tkDec[index].Type = TYPE;
if( !strcmp( Buff, "const") ) tkDec[index].Type = QUA;
if( !strcmp( Buff, "volatile") ) tkDec[index].Type = QUA;
if( (tkDec[index].Type != TYPE )&& (tkDec[index].Type != QUA) )
tkDec[index].Type = ID;
index ++;
}
if( index >= MAXTK )
{
printf( "Too long !\n" );
Convertfail = 1;
return;
}
tkDec[index].Type = -1;
strcpy(tkDec[index].Content, "End");
}

struct TOKEN GetToken( int back, struct TOKEN * ptk )
//传入-1，将ptk指向的TOKEN压入tkDec中，用于下次处理。
//传入0，则从tkDec中取出记号进行处理。
{
static int cur = 0;
if( back == -1 )
{
tkDec[--cur] = *ptk;
return *ptk;
}
return tkDec[cur ++];
}

void S_ARR()//处理数组
{
extern void S_Fun();
struct TOKEN tktemp = GetToken( 0, NULL );
int size = 0;
while( tktemp.Type == '[' )
{
tktemp = GetToken( 0, NULL );
if( tktemp.Type != ']' )
{
size = atoi( tktemp.Content );
printf( "Arr[%d] of ", size );
}
else
{
printf( "Arr of " );
}
tktemp = GetToken( 0, NULL );
}
GetToken( -1, &tktemp );
next = S_Fun;
}

void S_Fun()//处理函数
{
extern void S_PA();
struct TOKEN tktemp = GetToken( 0, NULL );
int paramnum = 0;
if( tktemp.Type == '(' )
{
printf( "fun with " );
tktemp = GetToken( 0, NULL );
if( tktemp.Type != ')' )
{
GetToken( -1, &tktemp );
printf( "param1: " );
++paramnum;
while( tktemp.Type != ')' )
{
tktemp = GetToken( 0, NULL );
if( tktemp.Type == ',' )
{
printf( " param%d : ", ++paramnum );
continue;
}
if( tktemp.Type != ')' )
{
printf( "%s ", tktemp.Content );
}
}
}
else
{
printf( "void param " );
}
printf( " returning " );
}
tktemp = GetToken( 0, NULL );
if( tktemp.Type == '[' )
{
next = S_ARR;
GetToken( -1, &tktemp );
}
else
{
next = S_PA;
GetToken( -1, &tktemp );
}
}

void S_PA()//处理堆栈中的“（”
{
extern void S_PT();
struct TOKEN tktemp;
if( GetTop().Type == '(' )
{
Pop();
tktemp = GetToken( 0, NULL );
while( tktemp.Type != ')' )
{
tktemp = GetToken( 0, NULL );
}
}

tktemp = GetToken( 0, NULL );
if( tktemp.Type == '[' )
{
GetToken( -1, &tktemp );
next = S_ARR;
}
else
{
GetToken( -1, &tktemp );
next = S_PT;
}
}

void S_PT()//处理指针
{
extern void S_TYPE();
int HasQua = 0;
char sztemp[20] = { '\0' };
if( GetTop().Type == QUA )
{
HasQua = 1;
strcpy( sztemp, GetTop().Content );
Pop();
}
if( GetTop().Type == '*' )
{
Pop();
if( HasQua == 1 )
{
printf( "%s pointer to ", sztemp );
}
else
{
printf( "pointer to " );
}
}
if( GetTop().Type == '(' )
{
next = S_PA;
}
else
{
next = S_TYPE;
}
}

void S_TYPE()//处理基本类型
{
extern void S_END();
struct TOKEN tktemp;
while( sp > -1 )
{
tktemp = Pop();
printf( "%s ", tktemp.Content );
}
next = S_END;
}


void S_END()//结束
{
return;
}

int main()
{
STATE states[6] = { S_ARR, S_Fun, S_PA, S_PT, S_TYPE, S_END };
struct TOKEN tk;
char * szDec = "int const * a( int * , int) ";
ConvertSzToTokens( szDec );
tk = GetToken( 0, NULL );
while( tk.Type != ID )
{
Push( tk );
tk = GetToken( 0, NULL );
}
printf( "%s is a ", tk.Content );
for( next = states[0]; next != S_END; )//模拟FSM
{
( *next )();
}
return ( 0 );
}