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

之前在写 gscript 时我就在想有没有利用编译原理实现一个更实际工具？毕竟真写一个语言的难度不低，并且也很难真的应用起来。,一次无意间看到有人提起 JSON 解析器，这类工具充斥着我们的日常开发，运用非常广泛。,以前我也有思考过它是如何实现的，过程中一旦和编译原理扯上关系就不由自主的劝退了；但经过这段时间的实践我发现实现一个 JSON 解析器似乎也不困难，只是运用到了编译原理前端的部分知识就完全足够了。,得益于 JSON​ 的轻量级，同时语法也很简单，所以核心代码大概只用了 800 行便实现了一个语法完善的 JSON 解析器。,首先还是来看看效果：,从这个用例中可以看到支持字符串、布尔值、浮点、整形、数组以及各种嵌套关系。,,这里简要说明一下实现原理，本质上就是两步：,其实词法解析就是构建一个有限自动机的过程（DFA)，目的是可以生成这样的集合（token）,只是我们需要将这些 token进行分类以便后续做语法分析的时候进行处理。,比如 "{"​ 这样的左花括号就是一个 BeginObject​ 代表一个对象声明的开始，而 "}"​ 则是 EndObject 代表一个对象的结束。,其中 "name"​ 这样的就被认为是 String​ 字符串，以此类推 "["​ 代表 BeginArray,这里我一共定义以下几种 token 类型：,其中可以看到  true/false/null 会有多个类型，这点先忽略，后续会解释。,以这段 JSON​ 为例：{"age":1}​，它的状态扭转如下图：,,总的来说就是依次遍历字符串，然后更新一个全局状态，根据该状态的值进行不同的操作。,部分代码如下：,,,感兴趣的朋友可以跑跑单例 debug 一下就很容易理解：,https://github.com/crossoverJie/gjson/blob/main/token_test.go,以这段 JSON 为例：,最终生成的 token 集合如下：,由于 JSON 的语法简单，一些规则甚至在词法规则中就能校验。,举个例子：JSON​ 中允许 null​ 值，当我们字符串中存在 nu nul​ 这类不匹配 null​ 的值时，就可以提前抛出异常。,,比如当检测到第一个字符串为 n 时，那后续的必须为 ​u->l->l 不然就抛出异常。,浮点数同理，当一个数值中存在多个 . 点时，依然需要抛出异常。,,这也是前文提到 true/false/null 这些类型需要有多个中间状态的原因。,在讨论生成 JSONObject 树之前我们先来看这么一个问题，给定一个括号集合，判断是否合法。,如何实现呢？其实也很简单，只需要利用栈就能完成，如下图所示：,,利用栈的特性，依次遍历数据，遇到是左边的符号就入栈，当遇到是右符号时就与栈顶数据匹配，能匹配上就出栈。,当匹配不上时则说明格式错误，数据遍历完毕后如果栈为空时说明数据合法。,其实仔细观察 JSON 的语法也是类似的：,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 包对比性能差的不是一星半点。,同时还有一些基础功能没有实现，比如将解析后的 JSONObject​ 可以反射生成自定义的 Struct​，以及我最终想实现的支持 JSON 的四则运算：,源码：https://github.com/crossoverJie/gjson