几百行代码实现一个 JSON 解析器

crossoverJie · · 1628 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3m5tef1rzj218a0u07ju.jpg) # 前言 之前在写 [gscript](https://crossoverjie.top/2022/05/30/gscript/gscript01/)时我就在想有没有利用编译原理实现一个更实际工具?毕竟真写一个语言的难度不低,并且也很难真的应用起来。 一次无意间看到有人提起 `JSON` 解析器,这类工具充斥着我们的日常开发,运用非常广泛。 以前我也有思考过它是如何实现的,过程中一旦和编译原理扯上关系就不由自主的劝退了;但经过这段时间的实践我发现实现一个 `JSON` 解析器似乎也不困难,只是运用到了编译原理前端的部分知识就完全足够了。 得益于 `JSON` 的轻量级,同时语法也很简单,所以核心代码大概只用了 800 行便实现了一个语法完善的 `JSON` 解析器。 <!--more--> 首先还是来看看效果: ```go 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") } ``` 从这个用例中可以看到支持字符串、布尔值、浮点、整形、数组以及各种嵌套关系。 # 实现原理 ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3mz1xo687j20iw0evt9f.jpg) 这里简要说明一下实现原理,本质上就是两步: 1. **词法解析**:根据原始输入的 `JSON` 字符串解析出 token,也就是类似于 `"{" "obj" "age" "1" "[" "]"` 这样的标识符,只是要给这类标识符分类。 2. 根据生成的一组 `token` 集合,以流的方式进行读取,最终可以生成图中的树状结构,也就是一个 `JSONObject` 。 下面来重点看看这两个步骤具体做了哪些事情。 ## 词法分析 ```shell 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 类型: ```go 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}`,它的状态扭转如下图: ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n83xkv82j21360i0t9r.jpg) 总的来说就是依次遍历字符串,然后更新一个全局状态,根据该状态的值进行不同的操作。 部分代码如下: ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n866cfqfj20u01jyjxt.jpg) ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n86kgy9qj20u012kadx.jpg) 感兴趣的朋友可以跑跑单例 debug 一下就很容易理解: [https://github.com/crossoverJie/xjson/blob/main/token_test.go](https://github.com/crossoverJie/xjson/blob/main/token_test.go) 以这段 JSON 为例: ```go 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` 集合如下: ```shell BeginObject { String "name" SepColon : String "cj" SepComma , String "age" SepColon : Number 10 EndObject } ``` ### 提前检查 由于 `JSON` 的语法简单,一些规则甚至在词法规则中就能校验。 举个例子: `JSON` 中允许 `null` 值,当我们字符串中存在 `nu nul` 这类不匹配 `null` 的值时,就可以提前抛出异常。 ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n8dt7d1aj211w0tigpa.jpg) 比如当检测到第一个字符串为 n 时,那后续的必须为 `u->l->l` 不然就抛出异常。 浮点数同理,当一个数值中存在多个 . 点时,依然需要抛出异常。 ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n8fk2xsbj20u010hgp2.jpg) 这也是前文提到 `true/false/null` 这些类型需要有多个中间状态的原因。 ## 生成 JSONObject 树 在讨论生成 `JSONObject` 树之前我们先来看这么一个问题,给定一个括号集合,判断是否合法。 - `[<()>]` 这样是合法的。 - `[<()>)` 而这样是不合法的。 如何实现呢?其实也很简单,只需要利用栈就能完成,如下图所示: ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n8u1brbbj216u0rsgp1.jpg) 利用栈的特性,依次遍历数据,遇到是左边的符号就入栈,当遇到是右符号时就与栈顶数据匹配,能匹配上就出栈。 当匹配不上时则说明格式错误,数据遍历完毕后如果栈为空时说明数据合法。 其实仔细观察 `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` ,如果不是则说明语法错误,就可以抛出异常。 ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n9ilzooqj20u00u442z.jpg) ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n9j1iex0j21bc09q0uj.jpg) 同时值得注意的是这里的 `status` 其实是一个`集合`,因为下一个状态可能是多种情况。 `{"e":[1,[2,3],{"d":{"f":"f"}}]}` 比如当我们解析到一个 `SepColon` 冒号时,后续的状态可能是 `value` 或 `BeginObject {` 或 `BeginArray [` ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n9pwpspuj21hg09q76e.jpg) 因此这里就得把这三种情况都考虑到,其他的以此类推。 具体解析过程可以参考源码: [https://github.com/crossoverJie/xjson/blob/main/parse.go](https://github.com/crossoverJie/xjson/blob/main/parse.go) --- 虽然是借助一个栈结构就能将 `JSON` 解析完毕,不知道大家发现一个问题没有: 这样非常容易遗漏规则,比如刚才提到的一个冒号后面就有三种情况,而一个 `BeginArray` 后甚至有四种情况(`StatusArrayValue, StatusBeginArray, StatusBeginObject, StatusEndArray`) 这样的代码读起来也不是很直观,同时容易遗漏语法,只能出现问题再进行修复。 既然提到了问题那自然也有相应的解决方案,其实就是语法分析中常见的递归下降算法。 ![](https://tva1.sinaimg.cn/large/e6c9d24ely1h3n9vzwepij20u01ecwgy.jpg) 我们只需要根据 `JSON` 的文法定义,递归的写出算法即可,这样代码阅读起来非常清晰,同时也不会遗漏规则。 完整的 `JSON` 语法查看这里: [https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4](https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4) 我也预计将下个版本改为递归下降算法来实现。 # 总结 当目前为止其实只是实现了一个非常基础的 `JSON` 解析,也没有做性能优化,和官方的 `JSON` 包对比性能差的不是一星半点。 ```shell 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` 的四则运算: ```json xjson.Get("glossary.age+long*(a.b+a.c)") ``` 目前我貌似没有发现有类似的库实现了这个功能,后面真的完成后应该会很有意思,感兴趣的朋友请持续关注。 源码: [https://github.com/crossoverJie/xjson](https://github.com/crossoverJie/xjson)

有疑问加站长微信联系(非本文作者))

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1628 次点击  ∙  1 赞  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传