3

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

 1 year ago
source link: https://www.cnblogs.com/crossoverJie/p/16419004.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

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

e6c9d24ely1h3m5tef1rzj218a0u07ju.jpg

之前在写 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")
}

从这个用例中可以看到支持字符串、布尔值、浮点、整形、数组以及各种嵌套关系。

e6c9d24ely1h3mz1xo687j20iw0evt9f.jpg

这里简要说明一下实现原理，本质上就是两步：

  1. 词法解析：根据原始输入的 JSON 字符串解析出 token，也就是类似于 "{" "obj" "age" "1" "[" "]" 这样的标识符，只是要给这类标识符分类。
  2. 根据生成的一组 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}，它的状态扭转如下图：

e6c9d24ely1h3n83xkv82j21360i0t9r.jpg

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

部分代码如下：

e6c9d24ely1h3n866cfqfj20u01jyjxt.jpg
e6c9d24ely1h3n86kgy9qj20u012kadx.jpg

感兴趣的朋友可以跑跑单例 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 的值时，就可以提前抛出异常。

e6c9d24ely1h3n8dt7d1aj211w0tigpa.jpg

比如当检测到第一个字符串为 n 时，那后续的必须为 u->l->l 不然就抛出异常。

浮点数同理，当一个数值中存在多个 . 点时，依然需要抛出异常。

e6c9d24ely1h3n8fk2xsbj20u010hgp2.jpg

这也是前文提到 true/false/null 这些类型需要有多个中间状态的原因。

生成 JSONObject 树

在讨论生成 JSONObject 树之前我们先来看这么一个问题，给定一个括号集合，判断是否合法。

  • [<()>] 这样是合法的。
  • [<()>) 而这样是不合法的。

如何实现呢？其实也很简单，只需要利用栈就能完成，如下图所示：

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 ，如果不是则说明语法错误，就可以抛出异常。

e6c9d24ely1h3n9ilzooqj20u00u442z.jpg
e6c9d24ely1h3n9j1iex0j21bc09q0uj.jpg

同时值得注意的是这里的 status 其实是一个集合，因为下一个状态可能是多种情况。

{"e":[1,[2,3],{"d":{"f":"f"}}]}
比如当我们解析到一个 SepColon 冒号时，后续的状态可能是 value 或 BeginObject { 或 BeginArray [

e6c9d24ely1h3n9pwpspuj21hg09q76e.jpg

因此这里就得把这三种情况都考虑到，其他的以此类推。

具体解析过程可以参考源码：
https://github.com/crossoverJie/gjson/blob/main/parse.go

虽然是借助一个栈结构就能将 JSON 解析完毕，不知道大家发现一个问题没有：
这样非常容易遗漏规则，比如刚才提到的一个冒号后面就有三种情况，而一个 BeginArray 后甚至有四种情况（StatusArrayValue, StatusBeginArray, StatusBeginObject, StatusEndArray）

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

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

e6c9d24ely1h3n9vzwepij20u01ecwgy.jpg

我们只需要根据 JSON 的文法定义，递归的写出算法即可，这样代码阅读起来非常清晰，同时也不会遗漏规则。

完整的 JSON 语法查看这里：
https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4

我也预计将下个版本改为递归下降算法来实现。

当目前为止其实只是实现了一个非常基础的 JSON 解析，也没有做性能优化，和官方的 JSON 包对比性能差的不是一星半点。

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 的四则运算：

gjson.Get("glossary.age+long*(a.b+a.c)")

目前我貌似没有发现有类似的库实现了这个功能，后面真的完成后应该会很有意思，感兴趣的朋友请持续关注。

源码：
https://github.com/crossoverJie/gjson


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK