go語(yǔ)言用八百行代碼實(shí)現(xiàn)一個(gè)JSON解析器
前言
之前在寫(xiě) gscript時(shí)我就在想有沒(méi)有利用編譯原理實(shí)現(xiàn)一個(gè)更實(shí)際工具?畢竟真寫(xiě)一個(gè)語(yǔ)言的難度不低,并且也很難真的應(yīng)用起來(lái)。
一次無(wú)意間看到有人提起 JSON
解析器,這類工具充斥著我們的日常開(kāi)發(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
解析器。
首先還是來(lái)看看效果:
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") }
從這個(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)行讀取,最終可以生成圖中的樹(shù)狀結(jié)構(gòu),也就是一個(gè)JSONObject
。
下面來(lái)重點(diǎn)看看這兩個(gè)步驟具體做了哪些事情。
詞法分析
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ì)象聲明的開(kāi)始,而 "}"
則是 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 一下就很容易理解:
以這段 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 樹(shù)
在討論生成 JSONObject
樹(shù)之前我們先來(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ù)寫(xiě)入當(dāng)前棧頂?shù)?nbsp;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/xjson/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
的文法定義,遞歸的寫(xiě)出算法即可,這樣代碼閱讀起來(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)算:
xjson.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/xjson
以上就是go語(yǔ)言用八百行代碼實(shí)現(xiàn)一個(gè)JSON解析器的詳細(xì)內(nèi)容,更多關(guān)于go語(yǔ)言實(shí)現(xiàn)JSON解析器的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章!
- Go與Rust高性能解析JSON實(shí)現(xiàn)方法示例
- golang解析json數(shù)據(jù)的4種方法總結(jié)
- Golang解析JSON遇到的坑及解決方法
- Go語(yǔ)言學(xué)習(xí)之JSON編碼解析與使用
- Go語(yǔ)言實(shí)現(xiàn)JSON解析的神器詳解
- 一文帶你了解Go語(yǔ)言如何解析JSON
- Go語(yǔ)言JSON解析器gjson使用方法詳解
- Golang實(shí)現(xiàn)解析JSON的三種方法總結(jié)
- golang生成JSON以及解析JSON
- Go?語(yǔ)言?json解析框架與?gjson?詳解
- Go語(yǔ)言實(shí)現(xiàn)JSON解析的方法詳解
- GO中Json解析的幾種方式
相關(guān)文章
Go結(jié)合反射將結(jié)構(gòu)體轉(zhuǎn)換成Excel的過(guò)程詳解
這篇文章主要介紹了Go結(jié)合反射將結(jié)構(gòu)體轉(zhuǎn)換成Excel的過(guò)程詳解,大概思路是在Go的結(jié)構(gòu)體中每個(gè)屬性打上一個(gè)excel標(biāo)簽,利用反射獲取標(biāo)簽中的內(nèi)容,作為表格的Header,需要的朋友可以參考下2022-06-06重學(xué)Go語(yǔ)言之?dāng)?shù)組的具體使用詳解
Go的數(shù)組是一種復(fù)合數(shù)據(jù)類型,在平時(shí)開(kāi)發(fā)中并不常用,更常用的是切片(slice),可以把切片看作是能動(dòng)態(tài)擴(kuò)容的數(shù)組,切片的底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,所以數(shù)組雖不常用,但仍然有必要掌握2023-02-02關(guān)于Golang中for-loop與goroutine的問(wèn)題詳解
這篇文章主要給大家介紹了關(guān)于Golang中for-loop與goroutine問(wèn)題的相關(guān)資料,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家學(xué)習(xí)或者使用golang具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09Golang 實(shí)現(xiàn)插入排序的方法示例(2種)
這篇文章主要介紹了Golang 實(shí)現(xiàn)插入排序的方法示例,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02優(yōu)雅使用GoFrame共享變量Context示例詳解
這篇文章主要為大家介紹了優(yōu)雅使用GoFrame共享變量Context示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-06-06Golang map實(shí)踐及實(shí)現(xiàn)原理解析
這篇文章主要介紹了Golang map實(shí)踐以及實(shí)現(xiàn)原理,Go 語(yǔ)言中,通過(guò)哈希查找表實(shí)現(xiàn) map,用鏈表法解決哈希沖突,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧2022-06-06golang 調(diào)用c語(yǔ)言動(dòng)態(tài)庫(kù)方式實(shí)現(xiàn)
本文主要介紹了golang 調(diào)用c語(yǔ)言動(dòng)態(tài)庫(kù)方式實(shí)現(xiàn),文中通過(guò)示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版)
這篇文章主要介紹了Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版),文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11