go語言用八百行代碼實(shí)現(xiàn)一個JSON解析器
前言
之前在寫 gscript時(shí)我就在想有沒有利用編譯原理實(shí)現(xiàn)一個更實(shí)際工具?畢竟真寫一個語言的難度不低,并且也很難真的應(yīng)用起來。
一次無意間看到有人提起 JSON
解析器,這類工具充斥著我們的日常開發(fā),運(yùn)用非常廣泛。
以前我也有思考過它是如何實(shí)現(xiàn)的,過程中一旦和編譯原理扯上關(guān)系就不由自主的勸退了;但經(jīng)過這段時(shí)間的實(shí)踐我發(fā)現(xiàn)實(shí)現(xiàn)一個 JSON
解析器似乎也不困難,只是運(yùn)用到了編譯原理前端的部分知識就完全足夠了。
得益于 JSON
的輕量級,同時(shí)語法也很簡單,所以核心代碼大概只用了 800 行便實(shí)現(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") }
從這個用例中可以看到支持字符串、布爾值、浮點(diǎn)、整形、數(shù)組以及各種嵌套關(guān)系。
實(shí)現(xiàn)原理
這里簡要說明一下實(shí)現(xiàn)原理,本質(zhì)上就是兩步:
- 詞法解析:根據(jù)原始輸入的
JSON
字符串解析出 token,也就是類似于"{" "obj" "age" "1" "[" "]"
這樣的標(biāo)識符,只是要給這類標(biāo)識符分類。 - 根據(jù)生成的一組
token
集合,以流的方式進(jìn)行讀取,最終可以生成圖中的樹狀結(jié)構(gòu),也就是一個JSONObject
。
下面來重點(diǎn)看看這兩個步驟具體做了哪些事情。
詞法分析
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)建一個有限自動機(jī)的過程(DFA
),目的是可以生成這樣的集合(token),只是我們需要將這些 token進(jìn)行分類以便后續(xù)做語法分析的時(shí)候進(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 會有多個類型,這點(diǎn)先忽略,后續(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ī)則中就能校驗(yàn)。
舉個例子: JSON
中允許 null
值,當(dāng)我們字符串中存在 nu nul
這類不匹配 null
的值時(shí),就可以提前拋出異常。
比如當(dāng)檢測到第一個字符串為 n 時(shí),那后續(xù)的必須為 u->l->l
不然就拋出異常。
浮點(diǎn)數(shù)同理,當(dāng)一個數(shù)值中存在多個 . 點(diǎn)時(shí),依然需要拋出異常。
這也是前文提到 true/false/null
這些類型需要有多個中間狀態(tài)的原因。
生成 JSONObject 樹
在討論生成 JSONObject
樹之前我們先來看這么一個問題,給定一個括號集合,判斷是否合法。
[<()>]
這樣是合法的。[<()>)
而這樣是不合法的。
如何實(shí)現(xiàn)呢?其實(shí)也很簡單,只需要利用棧就能完成,如下圖所示:
利用棧的特性,依次遍歷數(shù)據(jù),遇到是左邊的符號就入棧,當(dāng)遇到是右符號時(shí)就與棧頂數(shù)據(jù)匹配,能匹配上就出棧。
當(dāng)匹配不上時(shí)則說明格式錯誤,數(shù)據(jù)遍歷完畢后如果棧為空時(shí)說明數(shù)據(jù)合法。
其實(shí)仔細(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
時(shí)就入棧一個 Map,當(dāng)遇到一個 String
鍵時(shí)也將該值入棧。
當(dāng)遇到 value
時(shí),就將出棧一個 key
,同時(shí)將數(shù)據(jù)寫入當(dāng)前棧頂?shù)?nbsp;map
中。
當(dāng)然在遍歷 token
的過程中也需要一個全局狀態(tài),所以這里也是一個有限狀態(tài)機(jī)。
舉個例子:當(dāng)我們遍歷到 Token
類型為 String
,值為 "name"
時(shí),預(yù)期下一個 token
應(yīng)當(dāng)是 :冒號;
所以我們得將當(dāng)前的 status 記錄為 StatusColon
,一旦后續(xù)解析到 token 為 SepColon
時(shí),就需要判斷當(dāng)前的 status 是否為 StatusColon
,如果不是則說明語法錯誤,就可以拋出異常。
同時(shí)值得注意的是這里的 status
其實(shí)是一個集合,因?yàn)橄乱粋€狀態(tài)可能是多種情況。
{"e":[1,[2,3],{"d":{"f":"f"}}]}
比如當(dāng)我們解析到一個 SepColon
冒號時(shí),后續(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
這樣的代碼讀起來也不是很直觀,同時(shí)容易遺漏語法,只能出現(xiàn)問題再進(jìn)行修復(fù)。
既然提到了問題那自然也有相應(yīng)的解決方案,其實(shí)就是語法分析中常見的遞歸下降算法。
我們只需要根據(jù) JSON
的文法定義,遞歸的寫出算法即可,這樣代碼閱讀起來非常清晰,同時(shí)也不會遺漏規(guī)則。
完整的 JSON
語法查看這里:
https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4
我也預(yù)計(jì)將下個版本改為遞歸下降算法來實(shí)現(xiàn)。
總結(jié)
當(dāng)目前為止其實(shí)只是實(shí)現(xiàn)了一個非?;A(chǔ)的 JSON
解析,也沒有做性能優(yōu)化,和官方的 JSON
包對比性能差的不是一星半點(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ǔ)功能沒有實(shí)現(xiàn),比如將解析后的 JSONObject
可以反射生成自定義的 Struct
,以及我最終想實(shí)現(xiàn)的支持 JSON
的四則運(yùn)算:
xjson.Get("glossary.age+long*(a.b+a.c)")
目前我貌似沒有發(fā)現(xiàn)有類似的庫實(shí)現(xiàn)了這個功能,后面真的完成后應(yīng)該會很有意思,感興趣的朋友請持續(xù)關(guān)注。
源碼:https://github.com/crossoverJie/xjson
以上就是go語言用八百行代碼實(shí)現(xiàn)一個JSON解析器的詳細(xì)內(nèi)容,更多關(guān)于go語言實(shí)現(xiàn)JSON解析器的資料請關(guān)注腳本之家其它相關(guān)文章!
- Go與Rust高性能解析JSON實(shí)現(xiàn)方法示例
- golang解析json數(shù)據(jù)的4種方法總結(jié)
- Golang解析JSON遇到的坑及解決方法
- Go語言學(xué)習(xí)之JSON編碼解析與使用
- Go語言實(shí)現(xiàn)JSON解析的神器詳解
- 一文帶你了解Go語言如何解析JSON
- Go語言JSON解析器gjson使用方法詳解
- Golang實(shí)現(xiàn)解析JSON的三種方法總結(jié)
- golang生成JSON以及解析JSON
- Go?語言?json解析框架與?gjson?詳解
- Go語言實(shí)現(xiàn)JSON解析的方法詳解
- GO中Json解析的幾種方式
相關(guān)文章
Go結(jié)合反射將結(jié)構(gòu)體轉(zhuǎn)換成Excel的過程詳解
這篇文章主要介紹了Go結(jié)合反射將結(jié)構(gòu)體轉(zhuǎn)換成Excel的過程詳解,大概思路是在Go的結(jié)構(gòu)體中每個屬性打上一個excel標(biāo)簽,利用反射獲取標(biāo)簽中的內(nèi)容,作為表格的Header,需要的朋友可以參考下2022-06-06重學(xué)Go語言之?dāng)?shù)組的具體使用詳解
Go的數(shù)組是一種復(fù)合數(shù)據(jù)類型,在平時(shí)開發(fā)中并不常用,更常用的是切片(slice),可以把切片看作是能動態(tài)擴(kuò)容的數(shù)組,切片的底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,所以數(shù)組雖不常用,但仍然有必要掌握2023-02-02關(guān)于Golang中for-loop與goroutine的問題詳解
這篇文章主要給大家介紹了關(guān)于Golang中for-loop與goroutine問題的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用golang具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。2017-09-09Golang 實(shí)現(xiàn)插入排序的方法示例(2種)
這篇文章主要介紹了Golang 實(shí)現(xiàn)插入排序的方法示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(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 語言中,通過哈希查找表實(shí)現(xiàn) map,用鏈表法解決哈希沖突,本文結(jié)合實(shí)例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧2022-06-06golang 調(diào)用c語言動態(tài)庫方式實(shí)現(xiàn)
本文主要介紹了golang 調(diào)用c語言動態(tài)庫方式實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下2021-12-12Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版)
這篇文章主要介紹了Golang實(shí)現(xiàn)拓?fù)渑判?DFS算法版),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-11-11