go語言用八百行代碼實現(xiàn)一個JSON解析器
之前在寫gscript時我就在想有沒有利用編譯原理實現(xiàn)一個更實際工具？畢竟真寫一個語言的難度不低，并且也很難真的應(yīng)用起來。
一次無意間看到有人提起JSON解析器，這類工具充斥著我們的日常開發(fā)，運用非常廣泛。
以前我也有思考過它是如何實現(xiàn)的，過程中一旦和編譯原理扯上關(guān)系就不由自主的勸退了；但經(jīng)過這段時間的實踐我發(fā)現(xiàn)實現(xiàn)一個JSON解析器似乎也不困難，只是運用到了編譯原理前端的部分知識就完全足夠了。
得益于JSON的輕量級，同時語法也很簡單，所以核心代碼大概只用了 800 行便實現(xiàn)了一個語法完善的JSON解析器。
首先還是來看看效果：
import "github.com/crossoverJie/xjson"
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 := xjson.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")
}
從這個用例中可以看到支持字符串、布爾值、浮點、整形、數(shù)組以及各種嵌套關(guān)系。
實現(xiàn)原理
這里簡要說明一下實現(xiàn)原理，本質(zhì)上就是兩步：
- 詞法解析：根據(jù)原始輸入的
JSON字符串解析出 token，也就是類似于"{" "obj" "age" "1" "[" "]"這樣的標(biāo)識符，只是要給這類標(biāo)識符分類。 - 根據(jù)生成的一組
token集合，以流的方式進(jìn)行讀取，最終可以生成圖中的樹狀結(jié)構(gòu)，也就是一個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 [
其實詞法解析就是構(gòu)建一個有限自動機(jī)的過程（DFA)，目的是可以生成這樣的集合（token）,只是我們需要將這些 token進(jìn)行分類以便后續(xù)做語法分析的時候進(jìn)行處理。
比如"{"這樣的左花括號就是一個BeginObject代表一個對象聲明的開始，而"}"則是EndObject代表一個對象的結(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 會有多個類型，這點先忽略，后續(xù)會解釋。
以這段JSON為例：{"age":1}，它的狀態(tài)扭轉(zhuǎn)如下圖：
總的來說就是依次遍歷字符串，然后更新一個全局狀態(tài)，根據(jù)該狀態(tài)的值進(jìn)行不同的操作。
部分代碼如下：
感興趣的朋友可以跑跑單例 debug 一下就很容易理解：
以這段 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的語法簡單，一些規(guī)則甚至在詞法規(guī)則中就能校驗。
舉個例子：JSON中允許null值，當(dāng)我們字符串中存在nu nul這類不匹配null的值時，就可以提前拋出異常。
比如當(dāng)檢測到第一個字符串為 n 時，那后續(xù)的必須為u->l->l不然就拋出異常。
浮點數(shù)同理，當(dāng)一個數(shù)值中存在多個 . 點時，依然需要拋出異常。
這也是前文提到true/false/null這些類型需要有多個中間狀態(tài)的原因。
生成 JSONObject 樹
在討論生成JSONObject樹之前我們先來看這么一個問題，給定一個括號集合，判斷是否合法。
[<()>]這樣是合法的。[<()>)而這樣是不合法的。
如何實現(xiàn)呢？其實也很簡單，只需要利用棧就能完成，如下圖所示：
利用棧的特性，依次遍歷數(shù)據(jù)，遇到是左邊的符號就入棧，當(dāng)遇到是右符號時就與棧頂數(shù)據(jù)匹配，能匹配上就出棧。
當(dāng)匹配不上時則說明格式錯誤，數(shù)據(jù)遍歷完畢后如果棧為空時說明數(shù)據(jù)合法。
其實仔細(xì)觀察JSON的語法也是類似的：
{
"name": "cj",
"object": {
"age": 10,
"sex": "girl"
},
"list": [
{
"1": "a"
},
{
"2": "b"
}
]
}
BeginObject:{與EndObject:}一定是成對出現(xiàn)的，中間如論怎么嵌套也是成對的。 而對于"age":10這樣的數(shù)據(jù)，: 冒號后也得有數(shù)據(jù)進(jìn)行匹配，不然就是非法格式。
所以基于剛才的括號匹配原理，我們也能用類似的方法來解析token集合。
我們也需要創(chuàng)建一個棧，當(dāng)遇到BeginObject時就入棧一個 Map，當(dāng)遇到一個String鍵時也將該值入棧。
當(dāng)遇到value時，就將出棧一個key,同時將數(shù)據(jù)寫入當(dāng)前棧頂?shù)?code>map中。
當(dāng)然在遍歷token的過程中也需要一個全局狀態(tài)，所以這里也是一個有限狀態(tài)機(jī)。
舉個例子：當(dāng)我們遍歷到Token類型為String，值為"name"時，預(yù)期下一個token應(yīng)當(dāng)是 :冒號；
所以我們得將當(dāng)前的 status 記錄為StatusColon，一旦后續(xù)解析到 token 為SepColon時，就需要判斷當(dāng)前的 status 是否為StatusColon，如果不是則說明語法錯誤，就可以拋出異常。
同時值得注意的是這里的status其實是一個集合，因為下一個狀態(tài)可能是多種情況。
{"e":[1,[2,3],{"d":{"f":"f"}}]}比如當(dāng)我們解析到一個SepColon冒號時，后續(xù)的狀態(tài)可能是value或BeginObject {或BeginArray [
因此這里就得把這三種情況都考慮到，其他的以此類推。
具體解析過程可以參考源碼：
https://github.com/crossoverJie/xjson/blob/main/parse.go
雖然是借助一個棧結(jié)構(gòu)就能將JSON解析完畢，不知道大家發(fā)現(xiàn)一個問題沒有： 這樣非常容易遺漏規(guī)則，比如剛才提到的一個冒號后面就有三種情況，而一個BeginArray后甚至有四種情況
StatusArrayValue, StatusBeginArray, StatusBeginObject, StatusEndArray
這樣的代碼讀起來也不是很直觀，同時容易遺漏語法，只能出現(xiàn)問題再進(jìn)行修復(fù)。
既然提到了問題那自然也有相應(yīng)的解決方案，其實就是語法分析中常見的遞歸下降算法。
我們只需要根據(jù)JSON的文法定義，遞歸的寫出算法即可，這樣代碼閱讀起來非常清晰，同時也不會遺漏規(guī)則。
完整的JSON語法查看這里：
https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4
我也預(yù)計將下個版本改為遞歸下降算法來實現(xiàn)。
總結(jié)
當(dāng)目前為止其實只是實現(xiàn)了一個非常基礎(chǔ)的JSON解析，也沒有做性能優(yōu)化，和官方的JSON包對比性能差的不是一星半點。
cpu: Intel(R) Core(TM) i7-9750H CPU @ 2.60GHz
BenchmarkJsonDecode-12372298 15506 ns/op 512 B/op 12 allocs/op
BenchmarkDecode-12 141482 43516 ns/op30589 B/op 962 allocs/op
PASS
同時還有一些基礎(chǔ)功能沒有實現(xiàn)，比如將解析后的JSONObject可以反射生成自定義的Struct，以及我最終想實現(xiàn)的支持JSON的四則運算：
xjson.Get("glossary.age+long*(a.b+a.c)")
目前我貌似沒有發(fā)現(xiàn)有類似的庫實現(xiàn)了這個功能，后面真的完成后應(yīng)該會很有意思，感興趣的朋友請持續(xù)關(guān)注。
源碼：https://github.com/crossoverJie/xjson
以上就是go語言用八百行代碼實現(xiàn)一個JSON解析器的詳細(xì)內(nèi)容，更多關(guān)于go語言實現(xiàn)JSON解析器的資料請關(guān)注本站其它相關(guān)文章！
版權(quán)聲明：本站文章來源標(biāo)注為YINGSOO的內(nèi)容版權(quán)均為本站所有，歡迎引用、轉(zhuǎn)載，請保持原文完整并注明來源及原文鏈接。禁止復(fù)制或仿造本網(wǎng)站，禁止在非maisonbaluchon.cn所屬的服務(wù)器上建立鏡像，否則將依法追究法律責(zé)任。本站部分內(nèi)容來源于網(wǎng)友推薦、互聯(lián)網(wǎng)收集整理而來，僅供學(xué)習(xí)參考，不代表本站立場，如有內(nèi)容涉嫌侵權(quán)，請聯(lián)系alex-e#qq.com處理。
關(guān)注官方微信