共计 5378 个字符,预计需要花费 14 分钟才能阅读完成。
前言
之前在写 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 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
)
这样的代码读起来也不是很直观,同时容易脱漏语法,只能呈现问题再进行修复。
既然提到了问题那天然也有相应的解决方案,其实就是语法分析中常见的递归降落算法。
咱们只须要依据 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