欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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

 更新時間:2022年07月14日 14:31:47   作者:crossoverJie  
這篇文章主要為大家介紹了go語言用八百行代碼實現(xiàn)一個JSON解析器實例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪

前言

之前在寫 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ù)?nbsp;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)了一個非?;A(chǔ)的 JSON 解析,也沒有做性能優(yōu)化,和官方的 JSON 包對比性能差的不是一星半點。

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

同時還有一些基礎(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)文章!

相關(guān)文章

  • Go結(jié)合反射將結(jié)構(gòu)體轉(zhuǎn)換成Excel的過程詳解

    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ù)組的具體使用詳解

    重學(xué)Go語言之?dāng)?shù)組的具體使用詳解

    Go的數(shù)組是一種復(fù)合數(shù)據(jù)類型,在平時開發(fā)中并不常用,更常用的是切片(slice),可以把切片看作是能動態(tài)擴(kuò)容的數(shù)組,切片的底層數(shù)據(jù)結(jié)構(gòu)就是數(shù)組,所以數(shù)組雖不常用,但仍然有必要掌握
    2023-02-02
  • 從零開始學(xué)Golang的接口

    從零開始學(xué)Golang的接口

    本文主要介紹了從零開始學(xué)Golang的接口,原文中根據(jù)實例編碼詳細(xì)介紹的十分詳盡,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-03-03
  • 詳解如何讓Go語言中的反射加快

    詳解如何讓Go語言中的反射加快

    這篇文章主要為大家詳細(xì)介紹了如何讓Go語言中的反射加快的方法,文中的示例代碼講解詳細(xì),對我們學(xué)習(xí)Go語言有一定幫助,需要的可以參考一下
    2022-08-08
  • 關(guān)于Golang中for-loop與goroutine的問題詳解

    關(guān)于Golang中for-loop與goroutine的問題詳解

    這篇文章主要給大家介紹了關(guān)于Golang中for-loop與goroutine問題的相關(guān)資料,文中通過示例代碼介紹的非常詳細(xì),對大家學(xué)習(xí)或者使用golang具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧。
    2017-09-09
  • Golang 實現(xiàn)插入排序的方法示例(2種)

    Golang 實現(xiàn)插入排序的方法示例(2種)

    這篇文章主要介紹了Golang 實現(xiàn)插入排序的方法示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-02-02
  • 優(yōu)雅使用GoFrame共享變量Context示例詳解

    優(yōu)雅使用GoFrame共享變量Context示例詳解

    這篇文章主要為大家介紹了優(yōu)雅使用GoFrame共享變量Context示例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-06-06
  • Golang map實踐及實現(xiàn)原理解析

    Golang map實踐及實現(xiàn)原理解析

    這篇文章主要介紹了Golang map實踐以及實現(xiàn)原理,Go 語言中,通過哈希查找表實現(xiàn) map,用鏈表法解決哈希沖突,本文結(jié)合實例代碼給大家介紹的非常詳細(xì),需要的朋友參考下吧
    2022-06-06
  • golang 調(diào)用c語言動態(tài)庫方式實現(xiàn)

    golang 調(diào)用c語言動態(tài)庫方式實現(xiàn)

    本文主要介紹了golang 調(diào)用c語言動態(tài)庫方式實現(xiàn),文中通過示例代碼介紹的非常詳細(xì),具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2021-12-12
  • Golang實現(xiàn)拓?fù)渑判?DFS算法版)

    Golang實現(xiàn)拓?fù)渑判?DFS算法版)

    這篇文章主要介紹了Golang實現(xiàn)拓?fù)渑判?DFS算法版),文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-11-11

最新評論