概念

状态机是软件编程中的一个重要概念。比这个概念更重要的是对它的灵活应用。在一个思路清晰而且高效的程序中,必然有状态机的身影浮现。

比如说一个按键命令解析程序,就可以被看做状态机:本来在A状态下,触发一个按键后切换到了B状态;再触发另一个键后切换到C状态,或者返回到A状态。这就是最简单的按键状态机例子。进一步看,击键动作本身也可以看做一个状态机。一个细小的击键动作包含了:释放、抖动、闭合、抖动和重新释放等状态。

程序其实就是状态机

要素

状态机可归纳为4个要素,即现态条件动作次态。这样的归纳,主要是出于对状态机的内在因果关系的考虑。“现态”和“条件”是因,“动作”和“次态”是果。详解如下:

  1. 现态:是指当前所处的状态。
  2. 条件:又称为“事件”。当一个条件被满足,将会触发一个动作,或者执行一次状态的迁移。
  3. 动作:条件满足后执行的动作。动作执行完毕后,可以迁移到新的状态,也可以仍旧保持原状态。动作不是必需的,当条件满足后,也可以不执行任何动作,直接迁移到新状态。
    4.次态:条件满足后要迁往的新状态。“次态”是相对于“现态”而言的,“次态”一旦被激活,就转变成新的“现态”了。

如果我们进一步归纳,把“现态”和“次态”统一起来,而把“动作”忽略(降格处理),则只剩下两个最关键的要素,即:状态迁移条件

表示

状态机的表示方法有许多种,我们可以用文字、图形或表格的形式来表示一个状态机。
纯粹用文字描述是很低效的,所以就不介绍了。接下来先介绍图形的方式。

状态迁移图(STD)

状态迁移图(STD),是一种描述系统的状态、以及相互转化关系的图形方式。状态迁移图的画法有许多种,不过一般都大同小异。我们结合一个例子来说明一下它的画法,如图1所示。

  1. 状态框:用方框表示状态,包括所谓的“现态”和“次态”。
  2. 条件及迁移箭头:用箭头表示状态迁移的方向,并在该箭头上标注触发条件。
  3. 节点圆圈:当多个箭头指向一个状态时,可以用节点符号(小圆圈)连接汇总。
  4. 动作框:用椭圆框表示。
  5. 附加条件判断框:用六角菱形框表示。

状态迁移图和我们常见的流程图相比有着本质的区别,具体体现为:在流程图中,箭头代表了程序PC指针的跳转;而在状态迁移图中,箭头代表的是状态的改变

实践

利用状态机实现去除C/C++代码中的注释

思路

首先想象一下处理过程,一个字符一个字符的读取输入文件,如果是一般字符,原样输出;如果是特殊字符 /, *, ", /, \n 特殊处理。比如遇到一个 / 字符,则需要看下一个字符是否是 /,如果是就找到了单行注释的开头,接下来找换行符 \n,该行不输出;如果下一个字符是*,则找到了多行注释的开头,接下来需要找匹配的 */;如果是遇到了双引号",则再遇到下一个"之前,要忽略掉这之间的注释。。

状态机迁移图

0_1307697618HQRY.gif

各状态解析

  • state 0: 正在分析,在这个状态下,读到什么,输出什么。
  • state 1: 读到第一个/
  • state 2: 读到第二个/。(//...)
  • state 3: 读到第一个。(/
  • state 4: 读到第二个。(/...*)
  • state 5: 读到第一个双引号"
  • state 6: 读到转义字符(转义字符后面的双引号不用来配对的)
  • state 7: 读到//后面的行连接符\。 (//......\)
  • state 8: 读到//后面的行连接符\后,继续处理
  • state 9: 和state0是等价状态,分出这个状态可以做一些操作,比如删除注释。

代码

#include <cstdio>
#include <cstring>
#include <string>

unsigned char fsm[10][256];

void Initfsm()
{
    const int line_len = sizeof(char) * 256;
    memset(fsm[0], 0, line_len);
    memset(fsm[1], 0, line_len);
    memset(fsm[2], 2, line_len);
    memset(fsm[3], 3, line_len);
    memset(fsm[4], 3, line_len);
    memset(fsm[5], 5, line_len);
    memset(fsm[6], 5, line_len);
    memset(fsm[7], 2, line_len);
    memset(fsm[8], 8, line_len);
    memset(fsm[9], 0, line_len);

    fsm[0]['/'] = 1;
    fsm[0]['"'] = 5;
    fsm[1]['/'] = 2;
    fsm[1]['*'] = 3;
    fsm[1]['"'] = 5;
    fsm[2]['\n'] = 9;
    fsm[2]['\\'] = 7;
    fsm[3]['*'] = 4;
    fsm[4]['/'] = 9;
    fsm[4]['*'] = 4;
    fsm[5]['"'] = 0;
    fsm[5]['\\'] = 6;
    fsm[7]['\\'] = 7;
    fsm[7]['\n'] = 8;
    fsm[8]['\n'] = 9;
    fsm[8]['\\'] = 7;
    fsm[9]['/'] = 1;
    fsm[9]['"'] = 5;
}

int main(int argc, char* argv[])
{
    int state = 0;
    unsigned char c;
    std::string outStr;

    FILE *fin = fopen(argv[1],"r");
    if (fin == NULL)
    {
        printf("Fail to open input file!");
        return 0;
    }

    FILE *fout = fopen(argv[2],"w");

    Initfsm();

    while(fscanf(fin,"%c",&c)!=EOF)
    {
        state = fsm[state][c];
        outStr += c;

        switch(state)
        {
        case 0:
            fprintf(fout, "%s", outStr.c_str());
            outStr = "";
            break;
        case 9:
            outStr = "";
            if(c == '\n')
            {
                fputc(c, fout);
            }
            break;
        }
    }

    fclose(fin);
    fclose(fout);

    return 0;
}

参考链接