go語言用八百行代碼實(shí)現(xiàn)一個(gè)JSON解析器

第go語言用八百行代碼實(shí)現(xiàn)一個(gè)JSON解析器目錄前言實(shí)現(xiàn)原理詞法分析提前檢查生成JSONObject樹總結(jié)

前言

之前在寫gscript時(shí)我就在想有沒有利用編譯原理實(shí)現(xiàn)一個(gè)更實(shí)際工具？畢竟真寫一個(gè)語言的難度不低，并且也很難真的應(yīng)用起來。

一次無意間看到有人提起JSON解析器，這類工具充斥著我們的日常開發(fā)，運(yùn)用非常廣泛。

以前我也有思考過它是如何實(shí)現(xiàn)的，過程中一旦和編譯原理扯上關(guān)系就不由自主的勸退了；但經(jīng)過這段時(shí)間的實(shí)踐我發(fā)現(xiàn)實(shí)現(xiàn)一個(gè)JSON解析器似乎也不困難，只是運(yùn)用到了編譯原理前端的部分知識(shí)就完全足夠了。

得益于JSON的輕量級(jí)，同時(shí)語法也很簡(jiǎn)單，所以核心代碼大概只用了800行便實(shí)現(xiàn)了一個(gè)語法完善的JSON解析器。

首先還是來看看效果：

import"/crossoverJie/xjson"

funcTestJson(t*testing.T){

str:=`{

"glossary":{

"title":"exampleglossary",

"age":1,

"long":99.99,

"GlossDiv":{

"title":"S",

"GlossList":{

"GlossEntry":{

"ID":"SGML",

"SortAs":"SGML",

"GlossTerm":"StandardGeneralizedMarkupLanguage",

"Acronym":"SGML",

"Abbrev":"ISO8879:1986",

"GlossDef":{

"para":"Ameta-markuplanguage,usedtocreatemarkuplanguagessuchasDocBook.",

"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"],"exampleglossary")

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"],"StandardGeneralizedMarkupLanguage")

assert.Equal(t,glossEntry["Acronym"],"SGML")

assert.Equal(t,glossEntry["Abbrev"],"ISO8879:1986")

glossDef:=glossEntry["GlossDef"].(map[string]interface{})

assert.Equal(t,glossDef["para"],"Ameta-markuplanguage,usedtocreatemarkuplanguagessuchasDocBook.")

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)要說明一下實(shí)現(xiàn)原理，本質(zhì)上就是兩步：

詞法解析：根據(jù)原始輸入的JSON字符串解析出token，也就是類似于{objage1[]這樣的標(biāo)識(shí)符，只是要給這類標(biāo)識(shí)符分類。根據(jù)生成的一組token集合，以流的方式進(jìn)行讀取，最終可以生成圖中的樹狀結(jié)構(gòu)，也就是一個(gè)JSONObject。

下面來重點(diǎn)看看這兩個(gè)步驟具體做了哪些事情。

詞法分析

BeginObject{

String"name"

SepColon:

String"cj"

SepComma,

String"object"

SepColon:

BeginObject{

String"age"

SepColon:

Number10

SepComma,

String"sex"

SepColon:

String"girl"

EndObject}

SepComma,

String"list"

SepColon:

BeginArray[

其實(shí)詞法解析就是構(gòu)建一個(gè)有限自動(dòng)機(jī)的過程（DFA)，目的是可以生成這樣的集合（token）,只是我們需要將這些token進(jìn)行分類以便后續(xù)做語法分析的時(shí)候進(jìn)行處理。

比如{這樣的左花括號(hào)就是一個(gè)BeginObject代表一個(gè)對(duì)象聲明的開始，而}則是EndObject代表一個(gè)對(duì)象的結(jié)束。

其中name這樣的就被認(rèn)為是String字符串，以此類推[代表BeginArray

這里我一共定義以下幾種token類型：

typeTokenstring

const(

InitToken="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)如下圖：

總的來說就是依次遍歷字符串，然后更新一個(gè)全局狀態(tài)，根據(jù)該狀態(tài)的值進(jìn)行不同的操作。

部分代碼如下：

感興趣的朋友可以跑跑單例debug一下就很容易理解：

以這段JSON為例：

funcTestInitStatus(t*testing.T){

str:=`{"name":"cj","age":10}`

tokenize,err:=Tokenize(str)

assert.Nil(t,err)

for_,tokenType:=rangetokenize{

fmt.Printf("%s%s\n",tokenType.T,tokenType.Value)

最終生成的token集合如下：

BeginObject{

String"name"

SepColon:

String"cj"

SepComma,

String"age"

SepColon:

Number10

EndObject}

提前檢查

由于JSON的語法簡(jiǎn)單，一些規(guī)則甚至在詞法規(guī)則中就能校驗(yàn)。

舉個(gè)例子：JSON中允許null值，當(dāng)我們字符串中存在nunul這類不匹配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樹之前我們先來看這么一個(gè)問題，給定一個(gè)括號(hào)集合，判斷是否合法。

[()]這樣是合法的。[())而這樣是不合法的。

如何實(shí)現(xiàn)呢？其實(shí)也很簡(jiǎn)單，只需要利用棧就能完成，如下圖所示：

利用棧的特性，依次遍歷數(shù)據(jù)，遇到是左邊的符號(hào)就入棧，當(dāng)遇到是右符號(hào)時(shí)就與棧頂數(shù)據(jù)匹配，能匹配上就出棧。

當(dāng)匹配不上時(shí)則說明格式錯(cuò)誤，數(shù)據(jù)遍歷完畢后如果棧為空時(shí)說明數(shù)據(jù)合法。

其實(shí)仔細(xì)觀察JSON的語法也是類似的：

{

"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)匹配原理，我們也能用類似的方法來解析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ù)膍ap中。

當(dāng)然在遍歷token的過程中也需要一個(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，如果不是則說明語法錯(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[

因此這里就得把這三種情況都考慮到，其他的以此類推。

具體解析過程可以參考源碼：

/crossoverJie/xjson/blob/main/parse.go

雖然是借助一個(gè)棧結(jié)構(gòu)就能將JSON解析完畢，不知道大家發(fā)現(xiàn)一個(gè)問題沒有：這樣非常容易遺漏規(guī)則，比如剛才提到的一個(gè)冒號(hào)后面就有三種情況，而一個(gè)BeginArray后甚至有四種情況

StatusArrayValue,StatusBeginArray,StatusBeginObject,StatusEndArray

這樣的代碼讀起來也不是很直觀，同時(shí)容易遺漏語法，只能出現(xiàn)問題再進(jìn)行修復(fù)。

既然提到了問題那自然也有相應(yīng)的解決方案，其實(shí)就是語法分析中常見的遞歸下降算法。

我們只需要根據(jù)JSON的文法定義，遞歸的寫出算法即可，這樣代碼閱讀起來非常清晰，同時(shí)也不會(huì)遺漏規(guī)則。

完整的JSON語法查看這里：