狀態(tài)機(jī)之C++解析

1、狀態(tài)機(jī)之C+解析 2008-11-18 作者：CppExplore 來(lái)源： 一、狀態(tài)機(jī)描述狀態(tài)機(jī)理論最初的發(fā)展在數(shù)字電路設(shè)計(jì)領(lǐng)域。在數(shù)字電路方面，根據(jù)輸出是否與輸入信號(hào)有關(guān)，狀態(tài)機(jī)可以劃分為Mealy型和Moore型狀態(tài)機(jī)；根據(jù)輸出是否與輸入信號(hào)同步，狀態(tài)機(jī)可以劃分為異步和同步狀態(tài)機(jī)。而在軟件設(shè)計(jì)領(lǐng)域，狀態(tài)機(jī)設(shè)計(jì)的理論儼然已經(jīng)自成一體。Moore型狀態(tài)機(jī)的輸出只和當(dāng)前狀態(tài)有關(guān)，和輸入無(wú)關(guān)，如果在軟件設(shè)計(jì)領(lǐng)域設(shè)計(jì)出這種類型的狀態(tài)機(jī)，則該狀態(tài)機(jī)接受的事件都是無(wú)內(nèi)蘊(yùn)信息的事件（輸入）。Mealy型狀態(tài)機(jī)的輸入是由當(dāng)前狀態(tài)和輸入共同決定，對(duì)應(yīng)到軟件設(shè)計(jì)領(lǐng)域，則該狀態(tài)機(jī)接收的事件含有

2、內(nèi)蘊(yùn)信息，并且影響狀態(tài)機(jī)的輸出。顯然，這種劃分在軟件設(shè)計(jì)領(lǐng)域毫無(wú)意義。雖然軟件設(shè)計(jì)領(lǐng)域的狀態(tài)機(jī)也有同步和異步的劃分，但和數(shù)字電路方面的同步異步已經(jīng)不同。除了數(shù)字電路，涉及到狀態(tài)機(jī)的課程就是編譯原理了（本人屬計(jì)算機(jī)專業(yè)，其它專業(yè)是否涉及到狀態(tài)機(jī)就不清楚了）。下面簡(jiǎn)單回顧一下編譯原理里有關(guān)有限狀態(tài)機(jī)的描述。在編譯原理課程里面，對(duì)有限狀態(tài)機(jī)的描述僅限在編譯領(lǐng)域，特定狀態(tài)，針對(duì)輸入字符，發(fā)生狀態(tài)改變，沒有額外的行為，另編譯原理里有限狀態(tài)機(jī)的構(gòu)成要素，還包含唯一的初始狀態(tài)和一個(gè)終態(tài)集。數(shù)學(xué)語(yǔ)言描述如下：一個(gè)有限狀態(tài)機(jī)M是一個(gè)五元組，M=(K,E,T,S,Z)。其中（1)K是一個(gè)有窮集，其中的每個(gè)元素稱為

3、狀態(tài)(2)E是一個(gè)有窮字母表，它的每個(gè)元素稱為一個(gè)輸入字符（3）T是轉(zhuǎn)換函數(shù)，是K×E->K上的映射(4)S是K中的元素，是唯一的一個(gè)初態(tài)（5） Z是K的一個(gè)子集，是一個(gè)終態(tài)集，或者叫結(jié)束集。很明顯，狀態(tài)機(jī)在編譯原理里的講解已經(jīng)特化，輸入被定位為字符集，狀態(tài)改變的時(shí)候沒有額外動(dòng)作發(fā)生。與編譯原理中的狀態(tài)機(jī)不同，軟件設(shè)計(jì)領(lǐng)域中通用狀態(tài)機(jī)的輸入不是字符集，而是被稱作事件的結(jié)構(gòu)（可以是結(jié)構(gòu)體，也可以是類對(duì)象），并且特定的狀態(tài)下，針對(duì)發(fā)生的事件，不僅發(fā)生狀態(tài)改變，而且產(chǎn)生動(dòng)作。借鑒編譯原理中狀態(tài)機(jī)的初始狀態(tài)和終態(tài)，通用狀態(tài)機(jī)的數(shù)學(xué)語(yǔ)言描述如下：一個(gè)通用有限狀態(tài)機(jī)M是一個(gè)七元組，M=K,

4、E,T,M,F,S,Z。其中（1）K是一個(gè)有窮集，其中的每個(gè)元素稱為狀態(tài)(2)E是一個(gè)有窮集，它的每個(gè)元素稱為一個(gè)事件（3）T是轉(zhuǎn)換函數(shù)，是K×E->K上的映射（4）M是一個(gè)有窮集，它的每個(gè)元素稱為動(dòng)作（5）F是動(dòng)作映射函數(shù)，是K×E->M上的映射（6)S是K中的元素，是唯一的一個(gè)初態(tài)（7） Z是K的一個(gè)子集，是一個(gè)終態(tài)集，或者叫結(jié)束集。實(shí)用的狀態(tài)機(jī)可以做進(jìn)一步的優(yōu)化，首先，可以把 （3）（5）整合在一起，做一個(gè)K×E->K,M的映射，其次從實(shí)用性的角度出發(fā)，禁止?fàn)顟B(tài)接收空事件（無(wú)輸入的情況下，狀態(tài)發(fā)生改變），作為彌補(bǔ)，為每個(gè)狀態(tài)增加進(jìn)入動(dòng)作和離

5、開動(dòng)作，第三，鑒于定時(shí)器在系統(tǒng)中，尤其是在狀態(tài)機(jī)中的重要性，可以為每個(gè)狀態(tài)增加定時(shí)器以及超時(shí)后的狀態(tài)轉(zhuǎn)換。本文后面的講述以及實(shí)現(xiàn)暫不考慮把定時(shí)器特化，如果需要，可以在狀態(tài)的進(jìn)入動(dòng)作中初始化定時(shí)器（另：關(guān)于定時(shí)器，以后會(huì)寫文章系統(tǒng)設(shè)計(jì)之 定時(shí)器）。二、狀態(tài)機(jī)分類（后文中如無(wú)特別說(shuō)明，則狀態(tài)機(jī)指軟件設(shè)計(jì)領(lǐng)域的通用有限狀態(tài)機(jī)）依據(jù)狀態(tài)之間是否有包含關(guān)系，分以下兩種（1）常規(guī)狀態(tài)機(jī)。狀態(tài)機(jī)中的所有狀態(tài)是不相交的、互斥的。（2）層次狀態(tài)機(jī)。狀態(tài)機(jī)中的狀態(tài)之間要么是互斥的，要么是真包含的，可以用樹性結(jié)構(gòu)來(lái)描述這些狀態(tài)集，包含其它狀態(tài)的狀態(tài)稱為枝節(jié)點(diǎn)，不包含其它狀態(tài)的狀態(tài)稱為葉節(jié)點(diǎn)，為方便單樹描述，總是設(shè)計(jì)

6、一個(gè)狀態(tài)包含所有的狀態(tài)節(jié)點(diǎn)，稱為根節(jié)點(diǎn)。狀態(tài)機(jī)的狀態(tài)只能停留在葉節(jié)點(diǎn)，而不能停留在枝節(jié)點(diǎn)，每個(gè)枝節(jié)點(diǎn)需要指定一個(gè)子節(jié)點(diǎn)為它的默認(rèn)子節(jié)點(diǎn)，以便狀態(tài)機(jī)進(jìn)入枝節(jié)點(diǎn)的時(shí)候能夠停留到葉節(jié)點(diǎn)。三、狀態(tài)機(jī)實(shí)現(xiàn)（1）switch/case if/else方式實(shí)現(xiàn)。用于少量狀態(tài)（3個(gè)及其以下）的時(shí)候，不需要引入專門的狀態(tài)機(jī)模塊。這種方式不能編寫通用的狀態(tài)機(jī)模塊，不再多說(shuō)。（2）面向過程方式：宏是實(shí)現(xiàn)面向過程方式的通用方式。雖然在狀態(tài)機(jī)層面還是可以用面向?qū)ο蟮姆绞椒庋b，這里還是把它稱為面向過程的方式。1.常規(guī)狀態(tài)機(jī)模塊實(shí)現(xiàn)。這個(gè)狀態(tài)機(jī)涉及到機(jī)構(gòu)由上而下為：· 頂層結(jié)構(gòu)是狀態(tài)機(jī)：當(dāng)前狀態(tài)id，缺省操作，狀

7、態(tài)表，· 狀態(tài)表：狀態(tài)數(shù)組· 狀態(tài)結(jié)構(gòu)：狀態(tài)id，狀態(tài)名，進(jìn)入操作，退出操作，缺省操作，狀態(tài)事件表（數(shù)組）· 狀態(tài)事件結(jié)構(gòu)：操作，事件，下一狀態(tài)的id狀態(tài)機(jī)的算法是由狀態(tài)機(jī)的結(jié)構(gòu)決定的。實(shí)現(xiàn)如下：窗體頂端#define SINGLE_STATE_MAX_EVENT 10typedef int FSM_EVENT_ID;typedef struct event_param_st    FSM_EVENT_ID id;   

8、60;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;    

9、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_fu

10、nc;    FSM_FUNC default_func;    FSM_STATE_EVENT event_tableSINGLE_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&#

11、160;-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 

12、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

13、_STATE_TABLE state_tables;    FSM;void fsm_do_event(FSM &fsm, FSM_EVENT &event)    FSM_STATE *state=&(fsm.state_tablesfsm.state_id);    int i=0;    while(state->event_tab

14、lei.event!=END_EVENT_ID)            if(state->event_tablei.event=event.id)            break;        i+;     

15、0;  if(state->event_tablei.event!=END_EVENT_ID)            if(state->id!=state->event_tablei.state)                    if

16、(state->exit_func )                 state->exit_func(&event);                if(state->event_tablei.func)  

17、          state->event_tablei.func(&event);        if(state->id!=state->event_tablei.state)                 

18、0;  if(fsm.state_tablesstate->event_tablei.state.enter_func)                 fsm.state_tablesstate->event_tablei.state.enter_func(&event);         

19、60;  fsm.state_id=state->event_tablei.state;                else            if(state->default_func)       

20、60;    state->default_func(&event);        else                    if(fsm.default_func)       

21、0;        fsm.default_func(&event);            窗體底端窗體頂端以上說(shuō)明實(shí)現(xiàn)原理，有特殊需要的話可以自己定制狀態(tài)機(jī)，比如上面的狀態(tài)事件表數(shù)組的上限取的是單個(gè)狀態(tài)中事件項(xiàng)的最大值，也可以定義為所有事件的個(gè)數(shù)，這樣的話事件也不需要查詢，可以象狀態(tài)樣直接定位，只是狀態(tài)事件表會(huì)浪費(fèi)一些存儲(chǔ)空間。上面的FSM_EVENT僅僅是個(gè)例子，實(shí)際開發(fā)根據(jù)需要定義

22、不同的union。上面的算法也是假定狀態(tài)表的狀態(tài)定義是從0開始，順序遞增的。對(duì)外部調(diào)用而言，最后的狀態(tài)機(jī)結(jié)構(gòu)和事件執(zhí)行的方法可以封裝為對(duì)象。下面舉例說(shuō)明狀態(tài)機(jī)的定義(事件和狀態(tài)都應(yīng)該是enum類型，這里直接使用數(shù)字，僅為說(shuō)明問題而已)。BEGIN_FSM_STATE_TABLE(my_state_table)    BEGIN_STATE(0,"first",enter_fsm,exit_fsm,defualt_fsm)        STATE_EVEN

23、T_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_

24、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)        STA

25、TE_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 men");void exit_fsm(FSM_EVENT *