go语言用八百行代码实现一个JSON解析器

第go语言用八百行代码实现一个JSON解析器目录前言实现原理词法分析提前检查生成JSONObject树总结

前言

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

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

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

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

首先还是来看看效果：

import"/crossoverJie/xjson"

funcTestJson(t*testing.T){

str:=`{

"glossary":{

"title":"exampleglossary",

"age":1,

"long":99.99,

"GlossDiv":{

"title":"S",

"GlossList":{

"GlossEntry":{

"ID":"SGML",

"SortAs":"SGML",

"GlossTerm":"StandardGeneralizedMarkupLanguage",

"Acronym":"SGML",

"Abbrev":"ISO8879:1986",

"GlossDef":{

"para":"Ameta-markuplanguage,usedtocreatemarkuplanguagessuchasDocBook.",

"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"],"exampleglossary")

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"],"StandardGeneralizedMarkupLanguage")

assert.Equal(t,glossEntry["Acronym"],"SGML")

assert.Equal(t,glossEntry["Abbrev"],"ISO8879:1986")

glossDef:=glossEntry["GlossDef"].(map[string]interface{})

assert.Equal(t,glossDef["para"],"Ameta-markuplanguage,usedtocreatemarkuplanguagessuchasDocBook.")

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，也就是类似于{objage1[]这样的标识符，只是要给这类标识符分类。根据生成的一组token集合，以流的方式进行读取，最终可以生成图中的树状结构，也就是一个JSONObject。

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

词法分析

BeginObject{

String"name"

SepColon:

String"cj"

SepComma,

String"object"

SepColon:

BeginObject{

String"age"

SepColon:

Number10

SepComma,

String"sex"

SepColon:

String"girl"

EndObject}

SepComma,

String"list"

SepColon:

BeginArray[

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

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

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

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

typeTokenstring

const(

InitToken="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为例：

funcTestInitStatus(t*testing.T){

str:=`{"name":"cj","age":10}`

tokenize,err:=Tokenize(str)

assert.Nil(t,err)

for_,tokenType:=rangetokenize{

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

最终生成的token集合如下：

BeginObject{

String"name"

SepColon:

String"cj"

SepComma,

String"age"

SepColon:

Number10

EndObject}

提前检查

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

举个例子：JSON中允许null值，当我们字符串中存在nunul这类不匹配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[

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

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

/crossoverJie/xjson/blob/main/parse.go

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

StatusArrayValue,StatusBeginArray,StatusBeginObject,StatusEndArray

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

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

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

完整的JSON语法查看这里：