如何用Go语言实现JSON解析器，方法是什么

之前在写gscript时我就在想有没有利用编译原理实现一个更实际工具？毕竟真写一个语言的难度不低，并且也很难真的应用起来。

一次无意间看到有人提起JSON解析器，这类工具充斥着我们的日常开发，运用非常广泛。

以前我也有思考过它是如何实现的，过程中一旦和编译原理扯上关系就不由自主的劝退了；但经过这段时间的实践我发现实现一个JSON解析器似乎也不困难，只是运用到了编译原理前端的部分知识就完全足够了。

得益于JSON的轻量级，同时语法也很简单，所以核心代码大概只用了 800 行便实现了一个语法完善的JSON解析器。

首先还是来看看效果：

import "github.com/crossoverJie/xjson"
func TestJson(t *testing.T) {

    str := `{

   "glossary": {

       "title": "example glossary",
        "age":1,
        "long":99.99,
        "GlossDiv": {

           "title": "S",
            "GlossList": {

               "GlossEntry": {

                   "ID": "SGML",
                    "SortAs": "SGML",
                    "GlossTerm": "Standard Generalized Markup Language",
                    "Acronym": "SGML",
                    "Abbrev": "ISO 8879:1986",
                    "GlossDef": {

                       "para": "A meta-markup language, used to create markup languages such as DocBook.",
                        "GlossSeeAlso": ["GML", "XML", true, null]
                   }
,
                    "GlossSee": "markup"
               }

           }

       }

   }

}
`
    decode, err := xjson.Decode(str)
    assert.Nil(t, err)
    fmt.Println(decode)
    v := decode.(map[string]interface{
}
)
    glossary := v["glossary"].(map[string]interface{
}
)
    assert.Equal(t, glossary["title"], "example glossary")
    assert.Equal(t, glossary["age"], 1)
    assert.Equal(t, glossary["long"], 99.99)
    glossDiv := glossary["GlossDiv"].(map[string]interface{
}
)
    assert.Equal(t, glossDiv["title"], "S")
    glossList := glossDiv["GlossList"].(map[string]interface{
}
)
    glossEntry := glossList["GlossEntry"].(map[string]interface{
}
)
    assert.Equal(t, glossEntry["ID"], "SGML")
    assert.Equal(t, glossEntry["SortAs"], "SGML")
    assert.Equal(t, glossEntry["GlossTerm"], "Standard Generalized Markup Language")
    assert.Equal(t, glossEntry["Acronym"], "SGML")
    assert.Equal(t, glossEntry["Abbrev"], "ISO 8879:1986")
    glossDef := glossEntry["GlossDef"].(map[string]interface{
}
)
    assert.Equal(t, glossDef["para"], "A meta-markup language, used to create markup languages such as DocBook.")
    glossSeeAlso := glossDef["GlossSeeAlso"].(*[]interface{
}
)
    assert.Equal(t, (*glossSeeAlso)[0], "GML")
    assert.Equal(t, (*glossSeeAlso)[1], "XML")
    assert.Equal(t, (*glossSeeAlso)[2], true)
    assert.Equal(t, (*glossSeeAlso)[3], "")
    assert.Equal(t, glossEntry["GlossSee"], "markup")
}

从这个用例中可以看到支持字符串、布尔值、浮点、整形、数组以及各种嵌套关系。

实现原理

这里简要说明一下实现原理，本质上就是两步：

• 词法解析：根据原始输入的JSON字符串解析出 token，也就是类似于"{ " "obj" "age" "1" "[" "]"这样的标识符，只是要给这类标识符分类。
• 根据生成的一组token集合，以流的方式进行读取，最终可以生成图中的树状结构，也就是一个JSONObject。

下面来重点看看这两个步骤具体做了哪些事情。

词法分析

BeginObject  {

String  "name"
SepColon  :
String  "cj"
SepComma  ,
String  "object"
SepColon  :
BeginObject  {

String  "age"
SepColon  :
Number  10
SepComma  ,
String  "sex"
SepColon  :
String  "girl"
EndObject  }

SepComma  ,
String  "list"
SepColon  :
BeginArray  [

其实词法解析就是构建一个有限自动机的过程（DFA)，目的是可以生成这样的集合（token）,只是我们需要将这些 token进行分类以便后续做语法分析的时候进行处理。

比如"{ "这样的左花括号就是一个BeginObject代表一个对象声明的开始，而"} "则是EndObject代表一个对象的结束。

其中"name"这样的就被认为是String字符串，以此类推"["代表BeginArray

这里我一共定义以下几种 token 类型：

type Token string
const (
    Init        Token = "Init"
    BeginObject       = "BeginObject"
    EndObject         = "EndObject"
    BeginArray        = "BeginArray"
    EndArray          = "EndArray"
    Null              = "Null"
    Null1             = "Null1"
    Null2             = "Null2"
    Null3             = "Null3"
    Number            = "Number"
    Float             = "Float"
    BeginString       = "BeginString"
    EndString         = "EndString"
    String            = "String"
    True              = "True"
    True1             = "True1"
    True2             = "True2"
    True3             = "True3"
    False             = "False"
    False1            = "False1"
    False2            = "False2"
    False3            = "False3"
    False4            = "False4"
    // SepColon :
    SepColon = "SepColon"
    // SepComma ,
    SepComma = "SepComma"
    EndJson  = "EndJson"
)

其中可以看到 true/false/null 会有多个类型，这点先忽略，后续会解释。

以这段JSON为例：{ "age":1} ，它的状态扭转如下图：

总的来说就是依次遍历字符串，然后更新一个全局状态，根据该状态的值进行不同的操作。

部分代码如下：

感兴趣的朋友可以跑跑单例 debug 一下就很容易理解：

以这段 JSON 为例：

func TestInitStatus(t *testing.T) {

    str := `{
"name":"cj", "age":10}
`
    tokenize, err := Tokenize(str)
    assert.Nil(t, err)
    for _, tokenType := range tokenize {

        fmt.Printf("%s  %s\n", tokenType.T, tokenType.Value)
    }

}

最终生成的token集合如下：

BeginObject  {

String  "name"
SepColon  :
String  "cj"
SepComma  ,
String  "age"
SepColon  :
Number  10
EndObject  }
    

提前检查

由于JSON的语法简单，一些规则甚至在词法规则中就能校验。

举个例子：JSON中允许null值，当我们字符串中存在nu nul这类不匹配null的值时，就可以提前抛出异常。

比如当检测到第一个字符串为 n 时，那后续的必须为u-> l-> l不然就抛出异常。

浮点数同理，当一个数值中存在多个 . 点时，依然需要抛出异常。

这也是前文提到true/false/null这些类型需要有多个中间状态的原因。

生成 JSONObject 树

在讨论生成JSONObject树之前我们先来看这么一个问题，给定一个括号集合，判断是否合法。

• [()> ]这样是合法的。
• [()> )而这样是不合法的。

如何实现呢？其实也很简单，只需要利用栈就能完成，如下图所示：

利用栈的特性，依次遍历数据，遇到是左边的符号就入栈，当遇到是右符号时就与栈顶数据匹配，能匹配上就出栈。

当匹配不上时则说明格式错误，数据遍历完毕后如果栈为空时说明数据合法。

其实仔细观察JSON的语法也是类似的：

{

    "name": "cj",
    "object": {

        "age": 10,
        "sex": "girl"
    }
,
    "list": [
        {

            "1": "a"
        }
,
        {

            "2": "b"
        }

    ]
}

BeginObject:{ 与EndObject:} 一定是成对出现的，中间如论怎么嵌套也是成对的。 而对于"age":10这样的数据，: 冒号后也得有数据进行匹配，不然就是非法格式。

所以基于刚才的括号匹配原理，我们也能用类似的方法来解析token集合。

我们也需要创建一个栈，当遇到BeginObject时就入栈一个 Map，当遇到一个String键时也将该值入栈。

当遇到value时，就将出栈一个key,同时将数据写入当前栈顶的map中。

当然在遍历token的过程中也需要一个全局状态，所以这里也是一个有限状态机。

举个例子：当我们遍历到Token类型为String，值为"name"时，预期下一个token应当是 :冒号；

所以我们得将当前的 status 记录为StatusColon，一旦后续解析到 token 为SepColon时，就需要判断当前的 status 是否为StatusColon，如果不是则说明语法错误，就可以抛出异常。

同时值得注意的是这里的status其实是一个集合，因为下一个状态可能是多种情况。

{ "e":[1,[2,3],{ "d":{ "f":"f"} } ]} 比如当我们解析到一个SepColon冒号时，后续的状态可能是value或BeginObject { 或BeginArray [

因此这里就得把这三种情况都考虑到，其他的以此类推。

具体解析过程可以参考源码：

https://github.com/crossoverJie/xjson/blob/main/parse.go

虽然是借助一个栈结构就能将JSON解析完毕，不知道大家发现一个问题没有： 这样非常容易遗漏规则，比如刚才提到的一个冒号后面就有三种情况，而一个BeginArray后甚至有四种情况

StatusArrayValue, StatusBeginArray, StatusBeginObject, StatusEndArray

这样的代码读起来也不是很直观，同时容易遗漏语法，只能出现问题再进行修复。

既然提到了问题那自然也有相应的解决方案，其实就是语法分析中常见的递归下降算法。

我们只需要根据JSON的文法定义，递归的写出算法即可，这样代码阅读起来非常清晰，同时也不会遗漏规则。

完整的JSON语法查看这里：

https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4

我也预计将下个版本改为递归下降算法来实现。

总结

当目前为止其实只是实现了一个非常基础的JSON解析，也没有做性能优化，和官方的JSON包对比性能差的不是一星半点。

cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkJsonDecode-12 372298 15506 ns/op 512 B/op 12 allocs/op
BenchmarkDecode-12 141482 43516 ns/op 30589 B/op 962 allocs/op
PASS

同时还有一些基础功能没有实现，比如将解析后的JSONObject可以反射生成自定义的Struct，以及我最终想实现的支持JSON的四则运算：

xjson.Get("glossary.age+long*(a.b+a.c)")

目前我貌似没有发现有类似的库实现了这个功能，后面真的完成后应该会很有意思，感兴趣的朋友请持续关注。

源码：https://github.com/crossoverJie/xjson

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！