狀态機系列學習筆記01

有限狀态機（FSM）概念

定義

總的來說，有限狀态機系統，是指在不同階段會呈現出不同的運作狀态的系統，這些狀态是有限的、不重疊的。這樣的系統在某一時刻一定會處于其所有狀态中的一個狀态，此時它接受一部分允許的輸入，産生一部分可能的響應，并且遷移到一部分可能的狀态。

要素

狀态（State）

狀态，就是一個系統在其生命周期中某一時刻的運作情況，此時，系統會執行一些動作，或者等待一些外部輸入。

條件（Guard）

狀态機對外部消息進行響應的時候，除了需要判斷目前的狀态，還要判斷跟這個狀态相關的一些條件是否成立。這種判斷稱為Guard（”條件“）。Guard通過允許或禁止某些操作來影響狀态機的行為。

事件（Event）

Event（”事件“），就是在一定的時間和空間上發生的對系統有意義的事情。

動作（Action）

當一個Event被狀态機系統分發的時候，狀态機用Action（”動作“）來進行響應，比如修改一下變量的值、進行輸入輸出、産生另外一個Event或者遷移到另外一個狀态等等。

遷移（Transition）

從一個狀态切換到另一個狀态被稱為Transition（”遷移“）。引起狀态遷移的事件被稱為triggering event（”觸發事件“），或者被簡稱為trigger（”觸發“）。

FSM設計方法

C Parser（注釋分析程式）

假如需要設計一個統計.C檔案中注釋字元的個數的程式，這個程式需要分析出一個.C檔案中C風格的注釋字元（/.../）的個數。”/.../“之外的字元統一認為是code（不考慮”//“作為注釋的情況）。

分析如下：

（1） 首先，我們可以假設一段輸入字元，比如：

a = b * c / d;/* calc expression is b*c/d. **/

（2） 因為Event比較清晰，可以先确定下來：

CHAR，表示字元。即除了斜杠和星号之外的所有字元。

SLASH，表示斜杠。

STAR，表示星号。

（3） 确定Initial Transition：

确定初始狀态為code态。（或者增加一個idle态，根據第一字元再判斷。不過這個例子中不需要，因為不用計算code的個數。）

（4） 确定所有的state和transition。

在code态，如果輸入是CHAR或者STAR，仍然處于code狀态。當輸入SLASH以後，則認為這個SLASH有可能是注釋的開始，進入新的狀态叫slash。

在slash狀态，檢查後面的輸入是否是STAR，如果是STAR，說明這個是注釋的開始部分，轉入comment狀态，如果是CHAR或者SLASH，則認為前面輸入的SLASH和目前輸入的字元仍然是code，傳回code态。

同樣，comment态的思路跟code态類似。star态的思路跟slash态類似。

FSM實作

nestted switch statement（嵌套switch）

Cparser1.h

enum Signal {                 /* enumeration for CParser signals */
    CHAR_SIG, STAR_SIG, SLASH_SIG
};
enum State {                  /* enumeration for CParser states */
    CODE, SLASH, COMMENT, STAR
};

struct CParser1 {
    enum State state__;            /* the scalar state-variable */
    long commentCtr__;             /* comment character counter */
    /* ... */                      /* other CParser1 attributes */
};

#define CParser1Tran(me_, target_)    ((me_)->state__ = target_)           

Cparser1.c

void CParser1Dispatch(CParser1 *me, unsigned const sig) {
    switch (me->state__) {
    case CODE:
        switch (sig) {
        case SLASH_SIG:
            CParser1Tran(me, SLASH);        /* transition to "slash" */
            break;
        }
        break;
    case SLASH:
        switch (sig) {
        case STAR_SIG:
            me->commentCtr__ += 2;          /* SLASH-STAR count as comment */
            CParser1Tran(me, COMMENT);      /* transition to "comment" */
            break;
        case CHAR_SIG:
            CParser1Tran(me, CODE);         /* go back to "code" */
            break;
        }
        break;
    case COMMENT:
        switch (sig) {
        case STAR_SIG:
            CParser1Tran(me, STAR);         /* transition to "star" */
            break;
        case CHAR_SIG:
        case SLASH_SIG:
            ++me->commentCtr__;             /* count the comment char */
            break;
        }
        break;
    case STAR:
        switch (sig) {
        case STAR_SIG:
            ++me->commentCtr__;             /* count STAR as coment */
            break;
        case SLASH_SIG:
            me->commentCtr__ += 2;          /* count STAR-SLASH as comment */
            CParser1Tran(me, CODE);         /* transition to "code" */
            break;
        case CHAR_SIG:
            me->commentCtr__ += 2;          /* count STAR-? as comment */
            CParser1Tran(me, COMMENT);      /* go back to "comment" */
            break;
        }
        break;
    }
}