前言
之前在写 gscript时我就在想有没有利用编译原理实现一个更理论工具？毕竟真写一个语言的难度不低，并且也很难真的利用起来。
一次无意间看到有人提起 JSON 解析器，这类工具充斥着咱们的日常开发，使用十分宽泛。
以前我也有思考过它是如何实现的，过程中一旦和编译原理扯上关系就情不自禁的劝退了；但通过这段时间的实际我发现实现一个 JSON 解析器仿佛也不艰难，只是使用到了编译原理前端的局部常识就齐全足够了。
得益于 JSON 的轻量级，同时语法也很简略，所以外围代码大略只用了 800 行便实现了一个语法欠缺的 JSON 解析器。
<!--more-->
首先还是来看看成果：
import "github.com/crossoverJie/gjson"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 := 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"], "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 10SepComma ,String "sex"SepColon :String "girl"EndObject }SepComma ,String "list"SepColon :BeginArray [其实词法解析就是构建一个无限自动机的过程（DFA)，目标是能够生成这样的汇合（token）,只是咱们须要将这些 token进行分类以便后续做语法分析的时候进行解决。
比方 "{" 这样的左花括号就是一个 BeginObject 代表一个对象申明的开始，而 "}" 则是 EndObject 代表一个对象的完结。
其中 "name" 这样的就被认为是 String 字符串，以此类推 "[" 代表 BeginArray
这里我一共定义以下几种 token 类型：
type Token stringconst ( 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 一下就很容易了解：
https://github.com/crossoverJie/gjson/blob/main/token_test.go
以这段 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 10EndObject }提前查看
因为 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/gjson/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.60GHzBenchmarkJsonDecode-12 372298 15506 ns/op 512 B/op 12 allocs/opBenchmarkDecode-12 141482 43516 ns/op 30589 B/op 962 allocs/opPASS同时还有一些根底性能没有实现，比方将解析后的 JSONObject 能够反射生成自定义的 Struct，以及我最终想实现的反对 JSON 的四则运算：
gjson.Get("glossary.age+long*(a.b+a.c)")目前我貌似没有发现有相似的库实现了这个性能，前面真的实现后应该会很有意思，感兴趣的敌人请继续关注。
源码：
https://github.com/crossoverJie/gjson