社區(qū)精選 | 幾百行代碼實(shí)現(xiàn)一個(gè) JSON 解析器
本期為大家推薦的是社區(qū)作者 crossoverJie 的文章 ，在這篇文章中作者經(jīng)過(guò)實(shí)踐發(fā)現(xiàn)只運(yùn)用編譯原理前端的部分知識(shí)，就可以實(shí)現(xiàn)一個(gè) JSON 解析器。到底如何操作呢？
話不多說(shuō)，馬上進(jìn)入正文學(xué)習(xí)啦！
前言
之前在寫 gscript時(shí)我就在想有沒(méi)有利用編譯原理實(shí)現(xiàn)一個(gè)更實(shí)際工具？畢竟真寫一個(gè)語(yǔ)言的難度不低，并且也很難真的應(yīng)用起來(lái)。
一次無(wú)意間看到有人提起 JSON 解析器，這類工具充斥著我們的日常開發(fā)，運(yùn)用非常廣泛。
以前我也有思考過(guò)它是如何實(shí)現(xiàn)的，過(guò)程中一旦和編譯原理扯上關(guān)系就不由自主的勸退了；但經(jīng)過(guò)這段時(shí)間的實(shí)踐我發(fā)現(xiàn)實(shí)現(xiàn)一個(gè) JSON 解析器似乎也不困難，只是運(yùn)用到了編譯原理前端的部分知識(shí)就完全足夠了。
得益于 JSON 的輕量級(jí)，同時(shí)語(yǔ)法也很簡(jiǎn)單，所以核心代碼大概只用了 800 行便實(shí)現(xiàn)了一個(gè)語(yǔ)法完善的 JSON 解析器。
<!--more-->
首先還是來(lái)看看效果：
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")
}
從這個(gè)用例中可以看到支持字符串、布爾值、浮點(diǎn)、整形、數(shù)組以及各種嵌套關(guān)系。
實(shí)現(xiàn)原理
這里簡(jiǎn)要說(shuō)明一下實(shí)現(xiàn)原理，本質(zhì)上就是兩步：
詞法解析：根據(jù)原始輸入的 JSON 字符串解析出 token，也就是類似于 "{" "obj" "age" "1" "[" "]" 這樣的標(biāo)識(shí)符，只是要給這類標(biāo)識(shí)符分類。
根據(jù)生成的一組 token 集合，以流的方式進(jìn)行讀取，最終可以生成圖中的樹狀結(jié)構(gòu)，也就是一個(gè) 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 [
其實(shí)詞法解析就是構(gòu)建一個(gè)有限自動(dòng)機(jī)的過(guò)程（DFA)，目的是可以生成這樣的集合（token）,只是我們需要將這些 token進(jìn)行分類以便后續(xù)做語(yǔ)法分析的時(shí)候進(jìn)行處理。
比如 "{" 這樣的左花括號(hào)就是一個(gè) BeginObject 代表一個(gè)對(duì)象聲明的開始，而 "}" 則是 EndObject 代表一個(gè)對(duì)象的結(jié)束。
其中 "name" 這樣的就被認(rèn)為是 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 會(huì)有多個(gè)類型，這點(diǎn)先忽略，后續(xù)會(huì)解釋。
以這段 JSON 為例：{"age":1}，它的狀態(tài)扭轉(zhuǎn)如下圖：
總的來(lái)說(shuō)就是依次遍歷字符串，然后更新一個(gè)全局狀態(tài)，根據(jù)該狀態(tài)的值進(jìn)行不同的操作。
部分代碼如下：
感興趣的朋友可以跑跑單例 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 的語(yǔ)法簡(jiǎn)單，一些規(guī)則甚至在詞法規(guī)則中就能校驗(yàn)。
舉個(gè)例子：
JSON 中允許 null 值，當(dāng)我們字符串中存在 nu nul 這類不匹配 null 的值時(shí)，就可以提前拋出異常。
比如當(dāng)檢測(cè)到第一個(gè)字符串為 n 時(shí)，那后續(xù)的必須為 u->l->l 不然就拋出異常。
浮點(diǎn)數(shù)同理，當(dāng)一個(gè)數(shù)值中存在多個(gè) . 點(diǎn)時(shí)，依然需要拋出異常。
這也是前文提到 true/false/null 這些類型需要有多個(gè)中間狀態(tài)的原因。
生成 JSONObject 樹
在討論生成 JSONObject 樹之前我們先來(lái)看這么一個(gè)問(wèn)題，給定一個(gè)括號(hào)集合，判斷是否合法。
[<()>] 這樣是合法的。
[<()>) 而這樣是不合法的。
如何實(shí)現(xiàn)呢？其實(shí)也很簡(jiǎn)單，只需要利用棧就能完成，如下圖所示：
利用棧的特性，依次遍歷數(shù)據(jù)，遇到是左邊的符號(hào)就入棧，當(dāng)遇到是右符號(hào)時(shí)就與棧頂數(shù)據(jù)匹配，能匹配上就出棧。
當(dāng)匹配不上時(shí)則說(shuō)明格式錯(cuò)誤，數(shù)據(jù)遍歷完畢后如果棧為空時(shí)說(shuō)明數(shù)據(jù)合法。
其實(shí)仔細(xì)觀察 JSON 的語(yǔ)法也是類似的：
{
"name": "cj",
"object": {
"age": 10,
"sex": "girl"
},
"list": [
{
"1": "a"
},
{
"2": "b"
}
]
}
BeginObject:{ 與 EndObject:} 一定是成對(duì)出現(xiàn)的，中間如論怎么嵌套也是成對(duì)的。
而對(duì)于 "age":10 這樣的數(shù)據(jù)，: 冒號(hào)后也得有數(shù)據(jù)進(jìn)行匹配，不然就是非法格式。
所以基于剛才的括號(hào)匹配原理，我們也能用類似的方法來(lái)解析 token 集合。
我們也需要?jiǎng)?chuàng)建一個(gè)棧，當(dāng)遇到 BeginObject 時(shí)就入棧一個(gè) Map，當(dāng)遇到一個(gè) String 鍵時(shí)也將該值入棧。
當(dāng)遇到 value 時(shí)，就將出棧一個(gè) key,同時(shí)將數(shù)據(jù)寫入當(dāng)前棧頂?shù)?map 中。
當(dāng)然在遍歷 token 的過(guò)程中也需要一個(gè)全局狀態(tài)，所以這里也是一個(gè)有限狀態(tài)機(jī)。
舉個(gè)例子：當(dāng)我們遍歷到 Token 類型為 String，值為 "name" 時(shí)，預(yù)期下一個(gè) token 應(yīng)當(dāng)是 :冒號(hào)；
所以我們得將當(dāng)前的 status 記錄為 StatusColon，一旦后續(xù)解析到 token 為 SepColon 時(shí)，就需要判斷當(dāng)前的 status 是否為 StatusColon ，如果不是則說(shuō)明語(yǔ)法錯(cuò)誤，就可以拋出異常。
同時(shí)值得注意的是這里的 status 其實(shí)是一個(gè)集合，因?yàn)橄乱粋€(gè)狀態(tài)可能是多種情況。
{"e":[1,[2,3],{"d":{"f":"f"}}]}
比如當(dāng)我們解析到一個(gè) SepColon 冒號(hào)時(shí)，后續(xù)的狀態(tài)可能是 value 或 BeginObject { 或 BeginArray [
因此這里就得把這三種情況都考慮到，其他的以此類推。
具體解析過(guò)程可以參考源碼：
https://github.com/crossoverJie/gjson/blob/main/parse.go
雖然是借助一個(gè)棧結(jié)構(gòu)就能將 JSON 解析完畢，不知道大家發(fā)現(xiàn)一個(gè)問(wèn)題沒(méi)有：
這樣非常容易遺漏規(guī)則，比如剛才提到的一個(gè)冒號(hào)后面就有三種情況，而一個(gè) BeginArray 后甚至有四種情況（StatusArrayValue, StatusBeginArray, StatusBeginObject, StatusEndArray）
這樣的代碼讀起來(lái)也不是很直觀，同時(shí)容易遺漏語(yǔ)法，只能出現(xiàn)問(wèn)題再進(jìn)行修復(fù)。
既然提到了問(wèn)題那自然也有相應(yīng)的解決方案，其實(shí)就是語(yǔ)法分析中常見(jiàn)的遞歸下降算法。
我們只需要根據(jù) JSON 的文法定義，遞歸的寫出算法即可，這樣代碼閱讀起來(lái)非常清晰，同時(shí)也不會(huì)遺漏規(guī)則。
完整的 JSON 語(yǔ)法查看這里：
https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4
我也預(yù)計(jì)將下個(gè)版本改為遞歸下降算法來(lái)實(shí)現(xiàn)。
總結(jié)
當(dāng)目前為止其實(shí)只是實(shí)現(xiàn)了一個(gè)非?；A(chǔ)的 JSON 解析，也沒(méi)有做性能優(yōu)化，和官方的 JSON 包對(duì)比性能差的不是一星半點(diǎn)。
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
同時(shí)還有一些基礎(chǔ)功能沒(méi)有實(shí)現(xiàn)，比如將解析后的 JSONObject 可以反射生成自定義的 Struct，以及我最終想實(shí)現(xiàn)的支持 JSON 的四則運(yùn)算：
gjson.Get("glossary.age+long*(a.b+a.c)")
目前我貌似沒(méi)有發(fā)現(xiàn)有類似的庫(kù)實(shí)現(xiàn)了這個(gè)功能，后面真的完成后應(yīng)該會(huì)很有意思，感興趣的朋友請(qǐng)持續(xù)關(guān)注。
源碼：
https://github.com/crossoverJie/gjson
SegmentFault 思否社區(qū)小編說(shuō)
自 2022-07-01 起 SegmentFault 思否公眾號(hào)改版啦！之后將陸續(xù)推出新的欄目和大家見(jiàn)面?。ㄕ?qǐng)拭目以待呀~?）
在「社區(qū)精選」欄目中，我們將為廣大開發(fā)者推薦來(lái)自 SegmentFault 思否開發(fā)者社區(qū)的優(yōu)質(zhì)技術(shù)文章，這些文章全部出自社區(qū)中充滿智慧的技術(shù)創(chuàng)作者哦!
希望通過(guò)這一欄目，大家可以共同學(xué)習(xí)技術(shù)干貨，GET 新技能和各種花式技術(shù)小 Tips。
歡迎越來(lái)越多的開發(fā)者加入創(chuàng)作者的行列，我們將持續(xù)甄選出社區(qū)中優(yōu)質(zhì)的內(nèi)容推介給更多人，讓閃閃發(fā)光的技術(shù)創(chuàng)作者們走到聚光燈下，被更多人認(rèn)識(shí)。
「社區(qū)精選」投稿郵箱：[email protected]
投稿請(qǐng)附上社區(qū)文章地址
