状态机系列学习笔记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;
    }
}