作者：CppExplore 網(wǎng)址：http://www.shnenglu.com/CppExplore/
一、狀態(tài)機描述
狀態(tài)機理論最初的發(fā)展在數(shù)字電路設(shè)計領(lǐng)域。在數(shù)字電路方面，根據(jù)輸出是否與輸入信號有關(guān)，狀態(tài)機可以劃分為Mealy型和Moore型狀態(tài)機；根據(jù)輸出是否與輸入信號同步，狀態(tài)機可以劃分為異步和同步狀態(tài)機。而在軟件設(shè)計領(lǐng)域，狀態(tài)機設(shè)計的理論儼然已經(jīng)自成一體。Moore型狀態(tài)機的輸出只和當前狀態(tài)有關(guān)，和輸入無關(guān)，如果在軟件設(shè)計領(lǐng)域設(shè)計出這種類型的狀態(tài)機，則該狀態(tài)機接受的事件都是無內(nèi)蘊信息的事件（輸入）。Mealy型狀態(tài)機的輸入是由當前狀態(tài)和輸入共同決定，對應(yīng)到軟件設(shè)計領(lǐng)域，則該狀態(tài)機接收的事件含有內(nèi)蘊信息，并且影響狀態(tài)機的輸出。顯然，這種劃分在軟件設(shè)計領(lǐng)域毫無意義。雖然軟件設(shè)計領(lǐng)域的狀態(tài)機也有同步和異步的劃分，但和數(shù)字電路方面的同步異步已經(jīng)不同。
除了《數(shù)字電路》，涉及到狀態(tài)機的課程就是《編譯原理》了（本人屬計算機專業(yè)，其它專業(yè)是否涉及到狀態(tài)機就不清楚了）。下面簡單回顧一下《編譯原理》里有關(guān)有限狀態(tài)機的描述。在編譯原理課程里面，對有限狀態(tài)機的描述僅限在編譯領(lǐng)域，特定狀態(tài)，針對輸入字符，發(fā)生狀態(tài)改變，沒有額外的行為，另編譯原理里有限狀態(tài)機的構(gòu)成要素，還包含唯一的初始狀態(tài)和一個終態(tài)集。數(shù)學(xué)語言描述如下：一個有限狀態(tài)機M是一個五元組，M=(K,E,T,S,Z)。其中（1)K是一個有窮集，其中的每個元素稱為狀態(tài)(2)E是一個有窮字母表，它的每個元素稱為一個輸入字符（3）T是轉(zhuǎn)換函數(shù)，是K×E->K上的映射(4)S是K中的元素，是唯一的一個初態(tài)（5） Z是K的一個子集，是一個終態(tài)集，或者叫結(jié)束集。很明顯，狀態(tài)機在編譯原理里的講解已經(jīng)特化，輸入被定位為字符集，狀態(tài)改變的時候沒有額外動作發(fā)生。
與編譯原理中的狀態(tài)機不同，軟件設(shè)計領(lǐng)域中通用狀態(tài)機的輸入不是字符集，而是被稱作事件的結(jié)構(gòu)（可以是結(jié)構(gòu)體，也可以是類對象），并且特定的狀態(tài)下，針對發(fā)生的事件，不僅發(fā)生狀態(tài)改變，而且產(chǎn)生動作。借鑒編譯原理中狀態(tài)機的初始狀態(tài)和終態(tài)，通用狀態(tài)機的數(shù)學(xué)語言描述如下：一個通用有限狀態(tài)機M是一個七元組，M={K,E,T,M,F,S,Z}。其中（1）K是一個有窮集，其中的每個元素稱為狀態(tài)(2)E是一個有窮集，它的每個元素稱為一個事件（3）T是轉(zhuǎn)換函數(shù)，是K×E->K上的映射（4）M是一個有窮集，它的每個元素稱為動作（5）F是動作映射函數(shù)，是K×E->M上的映射（6)S是K中的元素，是唯一的一個初態(tài)（7） Z是K的一個子集，是一個終態(tài)集，或者叫結(jié)束集。實用的狀態(tài)機可以做進一步的優(yōu)化，首先，可以把 （3）（5）整合在一起，做一個K×E->{K,M}的映射，其次從實用性的角度出發(fā)，禁止狀態(tài)接收空事件（無輸入的情況下，狀態(tài)發(fā)生改變），作為彌補，為每個狀態(tài)增加進入動作和離開動作，第三，鑒于定時器在系統(tǒng)中，尤其是在狀態(tài)機中的重要性，可以為每個狀態(tài)增加定時器以及超時后的狀態(tài)轉(zhuǎn)換。本文后面的講述以及實現(xiàn)暫不考慮把定時器特化，如果需要，可以在狀態(tài)的進入動作中初始化定時器（另：關(guān)于定時器，以后會寫文章《系統(tǒng)設(shè)計之 定時器》）。
二、狀態(tài)機分類（后文中如無特別說明，則狀態(tài)機指軟件設(shè)計領(lǐng)域的通用有限狀態(tài)機）
依據(jù)狀態(tài)之間是否有包含關(guān)系，分以下兩種
（1）常規(guī)狀態(tài)機。狀態(tài)機中的所有狀態(tài)是不相交的、互斥的。
（2）層次狀態(tài)機。狀態(tài)機中的狀態(tài)之間要么是互斥的，要么是真包含的，可以用樹性結(jié)構(gòu)來描述這些狀態(tài)集，包含其它狀態(tài)的狀態(tài)稱為枝節(jié)點，不包含其它狀態(tài)的狀態(tài)稱為葉節(jié)點，為方便單樹描述，總是設(shè)計一個狀態(tài)包含所有的狀態(tài)節(jié)點，稱為根節(jié)點。狀態(tài)機的狀態(tài)只能停留在葉節(jié)點，而不能停留在枝節(jié)點，每個枝節(jié)點需要指定一個子節(jié)點為它的默認子節(jié)點，以便狀態(tài)機進入枝節(jié)點的時候能夠停留到葉節(jié)點。
三、狀態(tài)機實現(xiàn)
（1）switch/case if/else方式實現(xiàn)。用于少量狀態(tài)（3個及其以下）的時候，不需要引入專門的狀態(tài)機模塊。這種方式不能編寫通用的狀態(tài)機模塊，不再多說。
（2）面向過程方式：宏是實現(xiàn)面向過程方式的通用方式。雖然在狀態(tài)機層面還是可以用面向?qū)ο蟮姆绞椒庋b，這里還是把它稱為面向過程的方式。
1.常規(guī)狀態(tài)機模塊實現(xiàn)。這個狀態(tài)機涉及到機構(gòu)由上而下為：
頂層結(jié)構(gòu)是狀態(tài)機：當前狀態(tài)id，缺省操作，狀態(tài)表，
狀態(tài)表：狀態(tài)數(shù)組
狀態(tài)結(jié)構(gòu)：狀態(tài)id，狀態(tài)名，進入操作，退出操作，缺省操作，狀態(tài)事件表（數(shù)組）
狀態(tài)事件結(jié)構(gòu)：操作，事件，下一狀態(tài)的id
狀態(tài)機的算法是由狀態(tài)機的結(jié)構(gòu)決定的。實現(xiàn)如下：
#define SINGLE_STATE_MAX_EVENT 10
typedef int FSM_EVENT_ID;
typedef struct event_param_st
{
FSM_EVENT_ID id;
union{
int i;
}data;
}FSM_EVENT;
typedef int FSM_STATE_ID;
typedef void (*FSM_FUNC)(FSM_EVENT *);
typedef struct state_event_st
{
FSM_FUNC func;
FSM_EVENT_ID event;
FSM_STATE_ID state;
}FSM_STATE_EVENT;
typedef struct state_st
{
FSM_STATE_ID id;
char *name;
FSM_FUNC enter_func;
FSM_FUNC exit_func;
FSM_FUNC default_func;
FSM_STATE_EVENT event_table[SINGLE_STATE_MAX_EVENT];
}FSM_STATE;
typedef FSM_STATE STATE_TABLE[];
typedef FSM_STATE * PTR_STATE_TABLE;
#define END_EVENT_ID -1
#define END_STATE_ID -1
#define BEGIN_FSM_STATE_TABLE(state_stable) static STATE_TABLE state_stable={
#define BEGIN_STATE(id,name,enter_func,exit_func,default_func) {id,name,enter_func,exit_func,default_func,{
#define STATE_EVENT_ITEM(func,event,state) {func,event,state},
#define END_STATE(id) {NULL,END_EVENT_ID,END_STATE_ID}}},
#define END_FSM_STATE_TABLE(state_stable) {END_STATE_ID,NULL,NULL,NULL,NULL,NULL}};
typedef struct fsm_st
{
FSM_STATE_ID state_id;
FSM_FUNC default_func;
PTR_STATE_TABLE state_tables;
}FSM;
void fsm_do_event(FSM &fsm, FSM_EVENT &event)
{
FSM_STATE *state=&(fsm.state_tables[fsm.state_id]);
int i=0;
while(state->event_table[i].event!=END_EVENT_ID)
{
if(state->event_table[i].event==event.id)
break;
i++;
}
if(state->event_table[i].event!=END_EVENT_ID)
{
if(state->id!=state->event_table[i].state)
{
if(state->exit_func )
state->exit_func(&event);
}
if(state->event_table[i].func)
state->event_table[i].func(&event);
if(state->id!=state->event_table[i].state)
{
if(fsm.state_tables[state->event_table[i].state].enter_func)
fsm.state_tables[state->event_table[i].state].enter_func(&event);
fsm.state_id=state->event_table[i].state;
}
}
else
{
if(state->default_func)
state->default_func(&event);
else
{
if(fsm.default_func)
fsm.default_func(&event);
}
}
}以上說明實現(xiàn)原理，有特殊需要的話可以自己定制狀態(tài)機，比如上面的狀態(tài)事件表數(shù)組的上限取的是單個狀態(tài)中事件項的最大值，也可以定義為所有事件的個數(shù)，這樣的話事件也不需要查詢，可以象狀態(tài)樣直接定位，只是狀態(tài)事件表會浪費一些存儲空間。上面的FSM_EVENT僅僅是個例子，實際開發(fā)根據(jù)需要定義不同的union。上面的算法也是假定狀態(tài)表的狀態(tài)定義是從0開始，順序遞增的。
對外部調(diào)用而言，最后的狀態(tài)機結(jié)構(gòu)和事件執(zhí)行的方法可以封裝為對象。下面舉例說明狀態(tài)機的定義(事件和狀態(tài)都應(yīng)該是enum類型，這里直接使用數(shù)字，僅為說明問題而已)。
BEGIN_FSM_STATE_TABLE(my_state_table)
BEGIN_STATE(0,"first",enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm,1,1)
STATE_EVENT_ITEM(func_fsm,2,2)
END_STATE(0)
BEGIN_STATE(1,"second",enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm,1,2)
STATE_EVENT_ITEM(func_fsm,2,0)
END_STATE(1)
BEGIN_STATE(2,"third",enter_fsm,exit_fsm,defualt_fsm)
STATE_EVENT_ITEM(func_fsm,1,0)
STATE_EVENT_ITEM(func_fsm,2,1)
END_STATE(2)
END_FSM_STATE_TABLE(my_state_table)
void enter_fsm(FSM_EVENT * event)
{
printf("enter me\n");
}
void exit_fsm(FSM_EVENT * event)
{
printf("exit me\n");
}
void defualt_fsm(FSM_EVENT * event)
{
printf("i am defualt_fsm\n");
}
void func_fsm(FSM_EVENT * event)
{
printf("i am func_fsm\n");
}
int main()
{
printf("i am main\n");
FSM fsm={0,defualt_fsm,my_state_table};
printf("state[%d],name[%s]\n",fsm.state_id,fsm.state_tables[fsm.state_id].name);
FSM_EVENT event;
event.id=1;
event.data.i=1;
fsm_do_event(fsm,event);
printf("state[%d],name[%s]\n",fsm.state_id,fsm.state_tables[fsm.state_id].name);
}