我的编程空间,编程开发者的网络收藏夹
学习永远不晚

go语言用八百行代码实现一个JSON解析器

短信预约 -IT技能 免费直播动态提醒
省份

北京

  • 北京
  • 上海
  • 天津
  • 重庆
  • 河北
  • 山东
  • 辽宁
  • 黑龙江
  • 吉林
  • 甘肃
  • 青海
  • 河南
  • 江苏
  • 湖北
  • 湖南
  • 江西
  • 浙江
  • 广东
  • 云南
  • 福建
  • 海南
  • 山西
  • 四川
  • 陕西
  • 贵州
  • 安徽
  • 广西
  • 内蒙
  • 西藏
  • 新疆
  • 宁夏
  • 兵团
手机号立即预约

请填写图片验证码后获取短信验证码

看不清楚,换张图片

免费获取短信验证码

go语言用八百行代码实现一个JSON解析器

前言

之前在写 gscript时我就在想有没有利用编译原理实现一个更实际工具?毕竟真写一个语言的难度不低,并且也很难真的应用起来。

一次无意间看到有人提起 JSON 解析器,这类工具充斥着我们的日常开发,运用非常广泛。

以前我也有思考过它是如何实现的,过程中一旦和编译原理扯上关系就不由自主的劝退了;但经过这段时间的实践我发现实现一个 JSON 解析器似乎也不困难,只是运用到了编译原理前端的部分知识就完全足够了。

得益于 JSON 的轻量级,同时语法也很简单,所以核心代码大概只用了 800 行便实现了一个语法完善的 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")
}

从这个用例中可以看到支持字符串、布尔值、浮点、整形、数组以及各种嵌套关系。

实现原理

这里简要说明一下实现原理,本质上就是两步:

  • 词法解析:根据原始输入的 JSON 字符串解析出 token,也就是类似于 "{" "obj" "age" "1" "[" "]" 这样的标识符,只是要给这类标识符分类。
  • 根据生成的一组 token 集合,以流的方式进行读取,最终可以生成图中的树状结构,也就是一个 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  [

其实词法解析就是构建一个有限自动机的过程(DFA),目的是可以生成这样的集合(token),只是我们需要将这些 token进行分类以便后续做语法分析的时候进行处理。

比如 "{" 这样的左花括号就是一个 BeginObject 代表一个对象声明的开始,而 "}" 则是 EndObject 代表一个对象的结束。

其中 "name" 这样的就被认为是 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 会有多个类型,这点先忽略,后续会解释。

以这段 JSON 为例:{"age":1},它的状态扭转如下图:

总的来说就是依次遍历字符串,然后更新一个全局状态,根据该状态的值进行不同的操作。

部分代码如下:

感兴趣的朋友可以跑跑单例 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 的语法简单,一些规则甚至在词法规则中就能校验。

举个例子: JSON 中允许 null 值,当我们字符串中存在 nu nul 这类不匹配 null 的值时,就可以提前抛出异常。

比如当检测到第一个字符串为 n 时,那后续的必须为 u->l->l 不然就抛出异常。

浮点数同理,当一个数值中存在多个 . 点时,依然需要抛出异常。

这也是前文提到 true/false/null 这些类型需要有多个中间状态的原因。

生成 JSONObject 树

在讨论生成 JSONObject 树之前我们先来看这么一个问题,给定一个括号集合,判断是否合法。

  • [<()>] 这样是合法的。
  • [<()>) 而这样是不合法的。

如何实现呢?其实也很简单,只需要利用栈就能完成,如下图所示:

利用栈的特性,依次遍历数据,遇到是左边的符号就入栈,当遇到是右符号时就与栈顶数据匹配,能匹配上就出栈。

当匹配不上时则说明格式错误,数据遍历完毕后如果栈为空时说明数据合法。

其实仔细观察 JSON 的语法也是类似的:

{
    "name": "cj",
    "object": {
        "age": 10,
        "sex": "girl"
    },
    "list": [
        {
            "1": "a"
        },
        {
            "2": "b"
        }
    ]
}

BeginObject:{ 与 EndObject:} 一定是成对出现的,中间如论怎么嵌套也是成对的。 而对于 "age":10 这样的数据,: 冒号后也得有数据进行匹配,不然就是非法格式。

所以基于刚才的括号匹配原理,我们也能用类似的方法来解析 token 集合。

我们也需要创建一个栈,当遇到 BeginObject 时就入栈一个 Map,当遇到一个 String 键时也将该值入栈。

当遇到 value 时,就将出栈一个 key,同时将数据写入当前栈顶的 map 中。

当然在遍历 token 的过程中也需要一个全局状态,所以这里也是一个有限状态机

举个例子:当我们遍历到 Token 类型为 String,值为 "name" 时,预期下一个 token 应当是 :冒号;

所以我们得将当前的 status 记录为 StatusColon,一旦后续解析到 token 为 SepColon 时,就需要判断当前的 status 是否为 StatusColon ,如果不是则说明语法错误,就可以抛出异常。

同时值得注意的是这里的 status 其实是一个集合,因为下一个状态可能是多种情况。

{"e":[1,[2,3],{"d":{"f":"f"}}]} 比如当我们解析到一个 SepColon 冒号时,后续的状态可能是 value 或 BeginObject { 或 BeginArray [

因此这里就得把这三种情况都考虑到,其他的以此类推。

具体解析过程可以参考源码:

https://github.com/crossoverJie/xjson/blob/main/parse.go

虽然是借助一个栈结构就能将 JSON 解析完毕,不知道大家发现一个问题没有: 这样非常容易遗漏规则,比如刚才提到的一个冒号后面就有三种情况,而一个 BeginArray 后甚至有四种情况

StatusArrayValue, StatusBeginArray, StatusBeginObject, StatusEndArray

这样的代码读起来也不是很直观,同时容易遗漏语法,只能出现问题再进行修复。

既然提到了问题那自然也有相应的解决方案,其实就是语法分析中常见的递归下降算法。

我们只需要根据 JSON 的文法定义,递归的写出算法即可,这样代码阅读起来非常清晰,同时也不会遗漏规则。

完整的 JSON 语法查看这里:

https://github.com/antlr/grammars-v4/blob/master/json/JSON.g4

我也预计将下个版本改为递归下降算法来实现。

总结

当目前为止其实只是实现了一个非常基础的 JSON 解析,也没有做性能优化,和官方的 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

同时还有一些基础功能没有实现,比如将解析后的 JSONObject 可以反射生成自定义的 Struct,以及我最终想实现的支持 JSON 的四则运算:

xjson.Get("glossary.age+long*(a.b+a.c)")

目前我貌似没有发现有类似的库实现了这个功能,后面真的完成后应该会很有意思,感兴趣的朋友请持续关注。

源码:https://github.com/crossoverJie/xjson

以上就是go语言用八百行代码实现一个JSON解析器的详细内容,更多关于go语言实现JSON解析器的资料请关注编程网其它相关文章!

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

go语言用八百行代码实现一个JSON解析器

下载Word文档到电脑,方便收藏和打印~

下载Word文档

猜你喜欢

几百行代码实现一个 JSON 解析器

当目前为止其实只是实现了一个非常基础的 JSON​ 解析,也没有做性能优化,和官方的 JSON 包对比性能差的不是一星半点。

几百行代码实现一个脚本解释器

当前版本是使用 go 编写的,确实也如标题所说,核心代码还不到 1k 行代码,当然这也和目前功能简陋有关。

编程热搜

  • Python 学习之路 - Python
    一、安装Python34Windows在Python官网(https://www.python.org/downloads/)下载安装包并安装。Python的默认安装路径是:C:\Python34配置环境变量:【右键计算机】--》【属性】-
    Python 学习之路 - Python
  • chatgpt的中文全称是什么
    chatgpt的中文全称是生成型预训练变换模型。ChatGPT是什么ChatGPT是美国人工智能研究实验室OpenAI开发的一种全新聊天机器人模型,它能够通过学习和理解人类的语言来进行对话,还能根据聊天的上下文进行互动,并协助人类完成一系列
    chatgpt的中文全称是什么
  • C/C++中extern函数使用详解
  • C/C++可变参数的使用
    可变参数的使用方法远远不止以下几种,不过在C,C++中使用可变参数时要小心,在使用printf()等函数时传入的参数个数一定不能比前面的格式化字符串中的’%’符号个数少,否则会产生访问越界,运气不好的话还会导致程序崩溃
    C/C++可变参数的使用
  • css样式文件该放在哪里
  • php中数组下标必须是连续的吗
  • Python 3 教程
    Python 3 教程 Python 的 3.0 版本,常被称为 Python 3000,或简称 Py3k。相对于 Python 的早期版本,这是一个较大的升级。为了不带入过多的累赘,Python 3.0 在设计的时候没有考虑向下兼容。 Python
    Python 3 教程
  • Python pip包管理
    一、前言    在Python中, 安装第三方模块是通过 setuptools 这个工具完成的。 Python有两个封装了 setuptools的包管理工具: easy_install  和  pip , 目前官方推荐使用 pip。    
    Python pip包管理
  • ubuntu如何重新编译内核
  • 改善Java代码之慎用java动态编译

目录