有限状态机解析json

前段时间看了篇博客，了解了有限状态机这么个概念。于是有了个想法想实验一下

基础知识

首先一些基础概念可以参见这篇博文。

状态机就是接收一个输入，根据输入决定下一个状态应该是什么，然后继续接收输入，判断状态是否正确。

继续抽象输入为一个Token，状态机有一个初始状态。状态机每接收一个token，就判断是否符合期望，符合则转换到下一个状态。

伪代码如下：

expect_status = init_status;

while (hasToken()){

    if(token()==1){
        if( expect_status == token_status){
            expect_status = new_except_status;
        }
    }


}

---

回到json解析。

首先我参考了这篇博客

文章中对于细节没有过多描述，我再做一些补充。

Token

token代表一种输入，是对字符或者字节的抽象。token和状态并非一种固定的对应关系。

json中可以定义token如下：

• DOCUMENT_START,
• DOCUMENT_END,
• OBJECT_START,
• OBJECT_END,
• ARRAY_START,
• ARRAY_END,
• BOOLEAN,
• SEP_COLON,
• SEP_COMMA,
• TEXT,
• NUMBER,
• NULL,
• ILL, //非法

状态

为了编码方便，状态实际上是在指代期望的下一个状态。例如读取到一个 “ ，那期望就是一个字符串，当然这个字符串可能用在不同的位置，例如OBJECT-KEY，ARRAY-VALUE之类的

可以定义状态如下

• EXPECT_DOCUMENT_START
• EXPECT_DOCUMENT_END
• EXPECT_OBJECT_START
• EXPECT_OBJECT_END
• EXPECT_ARRAY_START
• EXPECT_ARRAY_END
• EXPECT_OBJECT_KEY
• EXPECT_OBJECT_VALUE
• EXPECT_ARRAY_VALUE
• EXPECT_COMMA

要注意，状态可能处于复合状态，同时期待多个状态，所以使用二的幂指数和位运算来处理状态

实现

最终实现位于https://github.com/inkroom/json