您现在的位置是：亿华云 > 系统运维

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

亿华云2025-10-04 03:27:18【系统运维】7人已围观

简介前言之前在写 gscript 时我就在想有没有利用编译原理实现一个更实际工具？毕竟真写一个语言的难度不低，并且也很难真的应用起来。一次无意间看到有人提起JSON解析器，这类工具充斥着我们的日常开发，运

前言

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

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

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

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

首先还是析器来看看效果：

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 10

SepComma ,

String "sex"

SepColon :

String "girl"

EndObject }

SepComma ,

String "list"

SepColon :

BeginArray [

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

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

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

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

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}，它的状态扭转如下图：

总的来说就是依次遍历字符串，然后更新一个全局状态，根据该状态的值进行不同的操作。

部分代码如下：

感兴趣的朋友可以跑跑单例 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 10

EndObject }提前检查

由于 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）

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

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