前言之前在写gscript的时候，就在想有没有更实用的利用编译原理的工具？毕竟真正写出一门语言并不难，真正应用起来也难。有一次无意中看到有人提到JSON解析器。这类工具充斥在我们的日常开发中，被广泛使用。之前也想过是怎么实现的，一旦和编译原理有关系，就忍不住劝说；但是经过这段时间的实践，我发现实现一个JSON解析器并不难，只是应用于编译原理前端的一些知识就完全足够了。得益于JSON的轻量级和简单语法，核心代码仅需800行左右即可实现一个语法完美的JSON解析器。首先还是来看效果：import"github.com/crossoverJie/gjson"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":"一种元标记语言，用于创建标记语言，例如DocBook.","GlossSeeAlso":["GML","XML",true,null]},"GlossSee":"markup"}}}}}`decode,err:=gjson.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[字符串]接口{})glossEntry:=glossList["GlossEntry"].(map[字符串]接口{})assert.Equal(t,glossEntry["ID"],"SGML")assert.Equal(t,glossEntry["SortAs"],"SGML")assert.Equal(t,glossEntry["GlossTerm"],"标准通用标记语言")assert.Equal(t,glossEntry["Acronym"],"SGML")assert.Equal(t,glossEntry["Abbrev"],"ISO8879:1986")glossDef:=glossEntry["GlossDef"].(map[string]interface{})assert.Equal(t,glossDef["para"],"一种元标记语言，用于创建标记语言，例如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:Number10SepComma,String"sex"SepColon:String"girl"EndObject}SepComma,String"list"SepColon:BeginArray[词法分析其实就是构造一个有限自动机（DFA）的过程，目的就是生成这样一个集合（token），但是我们在做语法分析的时候需要对这些token进行分类，以便后续处理。例如，左花括号“{”是一个BeginObject，表示一个对象声明的开始，而“}”是一个EndObject，表示一个对象的结束。其中，“name”被认为是一个String字符串，以此类推“[”代表BeginArray这里我定义了以下token类型：typeTokenstringconst(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}，它的状态反转如下图：一般来说就是依次遍历字符串，然后更新一个全局状态，进行不同的操作根据国家的价值。部分代码如下：有兴趣的朋友可以运行singletondebug来轻松理解：https://github.com/crossoverJie/gjson/blob/main/token_test.go以这个JSON为例：funcTestInitStatus(t*testing.T){str:=`{"name":"cj","age":10}`tokenize,err:=Tokenize(str)assert.Nil(t,err)for_,tokenType:=range标记化{fmt.Printf("%s%s\n",tokenType.T,tokenType.Value)}}最终生成的token集合如下：BeginObject{String"name"SepColon:String"cj"SepComma,String"age"SepColon:Number10EndObject}早期检查由于JSON语法简单，一些规则甚至可以在词法规则中进行验证。例如：JSON允许空值，当我们的字符串中有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应该是：一个冒号；所以我们要记录当前状态为StatusColon，一旦token后续被解析为AtSepColon，就需要判断当前状态是否为StatusColon，如果不是，说明语法错误，可以抛出异常抛出。同时值得注意的是这里的status其实是一个集合，因为下一个status可能是多种情况。{"e":[1,[2,3],{"d":{"f":"f"}}]}比如我们解析到一个SepColon冒号时，后续状态可能是value或BeginObject{或BeginArray[所以这里我们必须考虑所有三种情况，依此类推。具体解析过程可以参考源码：https://github.com/crossoverJie/gjson/blob/main/parse.go知道你是否发现了一个问题：这是很容易错过的规则。比如刚才说的一个冒号后面是三个case，一个BeginArray(StatusArrayValue,StatusBeginArray,StatusBeginObject,StatusEndArray)后面甚至还有四个case。这样的代码读起来不是很直观，而且容易漏语法，有问题只能修复。既然提到了问题，自然就有对应的解决方案，其实就是句法分析中常见的递归下降算法。我们只需要按照JSON语法定义递归地编写算法，这样代码就可以看得很清楚，不会漏掉规则。在这里查看完整的JSON语法：https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4我也希望将下一个版本更改为递归下降算法。总结一下，到目前为止，它只是实现了一个很基础的JSON解析，并没有做性能优化。和官方的json包相比，性能差的不是一点半点。cpu:Intel(R)Core(TM)i7-9750HCPU@2.60GHzBenchmarkJsonDecode-1237229815506ns/op512B/op12allocs/opBenchmarkDecode-1214148243516ns/op30589B/op962allocs/opPASS一些基本功能还没有实现，比如解析出来的JSONObject可以反射生成自定义的Struct，最后想实现支持JSON的四种操作：gjson.Get("glossary.age+long*(a.b+a.c)")源代码：https://github.com/crossoverJie/gjson
