一个简单的有限状态自动机实现

/ 0评 / 0

背景:最近为了开发一个串口工具,需要进行序列检测(顺便安利一下自己的GitHub项目SerialPort-Assistant

串口支持两种发送模式:ASCII模式和HEX模式。ASCII模式并不需要什么检测,但是HEX模式需要检查序列是否合法。包括:

  1. 每一个字符,要么是空白符号,要么是十六进制符号。
  2. 每一个十六进制数不可以大于0xFF。

例如,字符串"00 01 f 0a c"是合法的,而"a0b"、"g"是不合法的。同时允许任意多个空白符号,包括但不限于回车、空格、制表符等。

一开始我是想用格式化输入,但是处理起来不是很优雅。参照数电中常用的序列检测器,我想到了有限状态自动机。代码如下:

std::vector<char> wxTextPlus::getHex() const
{
    // Get the correct hexadecimal sequence by a simple deterministic finite automaton
    enum hexDFA {
        IDLE,
        HEX1,
        HEX2,
        SYN_ERR
    }; // define DFA
    hexDFA dfa = IDLE;
    std::vector<char> cbuf;
    wxString str = GetValue() + " "; //  add a additional space to simplify the logic
    char tmp;
    for(auto i: str){
        auto valid = isxdigit(i);
        auto space = isspace(i);
        switch(dfa){
            case IDLE: {
                if(valid) {
                    tmp = c2Hex(i);
                    dfa = HEX1;
                }
                else if(!space) dfa = SYN_ERR;
                break;
            }
            case HEX1: {
                if(valid){
                    tmp = (tmp<<4) | c2Hex(i);
                    dfa = HEX2;
                }
                else if(space){
                    cbuf.push_back(tmp);
                    dfa = IDLE;
                }
                else dfa = SYN_ERR;
                break;
            }
            case HEX2: {
                if(space){
                    cbuf.push_back(tmp);
                    dfa = IDLE;
                }
                else dfa = SYN_ERR;
                break;
            }
            case SYN_ERR: {
                cbuf.clear();
                return cbuf;
            }
        }
    }
    return cbuf;
}

这个文本框继承自wxWidgets自带的文本框类,且这个函数是文本框的附属方法,因此没有很明确的作用域界限。大致流程是:从文本框拉取原始字符串,解析字符串,将字符串中包含的数字用vector返回。如果字符串非法,则弹出一个错误信息。

函数中使用了一个枚举类作为状态指示器,使用GetValue方法获取到字符串,然后用一个C11风格的for循环按顺序O(n)地分析字符串。状态机的核心在于一个switch语句。

状态机包含了几个状态:

  1. 待命
  2. HEX字符1
  3. HEX字符2
  4. 格式错误

待命状态时,缓冲区为空,同时每捕获到一个合法的HEX串,就会回到待命状态。可以将状态机视作一个黑盒,每接收到一个字符就会发生一次状态转移(回环也是一种转移)。状态机被初始化成idle模式,与此同时,一个vector数组和一个1 byte变量被创建以存储和缓存接收到的数据。

状态机对每个输入的字符定义两个属性:空白的、HEX的。在C语言中,可以用函数isspace和isxdigit获取这两个属性。

状态机按照以下规则进行状态转移:

  1. 任何状态下,接收到一个非空白且非HEX的字符,则转移到格式错误状态。
  2. 待命状态下,接收到一个空白字符则不发生跳转(或回环跳转)
  3. 待命状态下,接收到一个合法HEX字符,则转移到HEX1,同时将接收到的字符转换成数字存放到缓冲区tmp
  4. HEX1状态下,接收到空白字符,则将tmp的内容直接追加到vector末尾,并跳转到idle状态
  5. HEX1状态下,接收到HEX字符,则首先将HEX字符转换成数字,并将tmp右移4位再追加到tmp(表达式tmp = (tmp<<4) | c2hex(c) ,其中c2hex是一个将HEX字符转换成HEX数字的函数)
  6. HEX2状态下,接收到HEX字符,则跳转到格式错误状态(不允许发送长度在8bit以上的HEX)
  7. HEX2状态下,接收到空白字符,则将tmp的内容追加到vector

另外,在格式错误状态下,将直接清空vector并返回这个空数组。清空vector的目的是为上层调用者提供“这里发生了错误,不要进行后续操作”的消息(vector::size() == 0)。

可能细心的读者会发现,万一有个字符串以合法的HEX串结尾,则状态机会停留在最后一个状态,最后一个HEX会留在缓冲变量里而不是被返回回去。这里我用了一个小hacker,在获取字符串的同时强行在字符串后追加一个空格。这样无论如何状态机都会在最后处理到一个空格,从而保证能回到idle模式。当然你也可以在返回之前检查一下状态机状态,倘若状态机停在HEX1或HEX2,则对缓冲变量进行正确的处理。


使用有限状态自动机是我突然想到的。因为用C++处理模式串向来是一件蛋疼的事情,而使用状态机则可以优雅且清晰地解决这个过程。另外,我同期也在学习编译原理,其中有限状态自动机是词法分析很重要的部分,因此这也算是一种实践了。

发表评论

邮箱地址不会被公开。 必填项已用*标注