一、使用Python和Rust手写Json parser
source link: https://zhuanlan.zhihu.com/p/408780427
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
一、使用Python和Rust手写Json parser
前言
断断续续接触过parser，最近突然想手写一个，更好地理解parser。
所以阐述如何写一个“麻雀型”的Parser。
前段时间写了几篇我理解Rust的文章，如，
所以，现在用Python和Rust各自实现一遍，对比两者语言的使用感受。
本文先阐述如何使用Python实现。
这个Parser是一个阉割版的JSON parser，它能解析下面的文本，
{
"name": "good",
"books": [ "C++", "Rust", 234],
"great": True,
"year": 2200
}但因为自己从零开始写的，我做了一些简化，比如数字只支持整数。不过“五脏俱全”！
手写parser
当接触parser为零的时候，如果让我写一个JSON的parser，那么我会这么写，
def parse(s): if s == "":
return "" if s[0] == '{':
# 下面要parse一个object
s = remove_whitespaces(s)
return parse_object(s)
...
一个字符一个字符地读入，如果碰到空格（\t, \n, space,)的话，就把空格忽略，但是如果在引号里面就不忽略空格。
万事开头难，于是我们可以先写一个函数parse JSON里面的key 和value组合，比如，"k1": "v1", "k2": "v2"。
def parse_items(s):
items = []
if s == "":
return items
s = skip_whitespace(s)
if s[0] != '"':
raise Exception("not begin with quotes")
item, s = parse_item(s)
if s != "":
if s[0] == ',':
items = parse_items(s[1:])
else:
raise Exception("str not end correctly.")
return [item] + itemsparse_items()负责解析key,value对，parse_item()负责解析一堆key和value，如果解析以后，还剩逗号，说明我们还有key value需要继续解析。
这么写比较”顺手“，但是繁琐，因为我发现经常要跳过空格，比如花括号后面可以有很多空格。
lexer登场了！在编译器里面，lexer负责将输入的字符转化为tokens。而tokens会被传给parser，parser负责根据语法生成AST(abstract syntax tree，抽象语法树），如下图
https://www.cs.utexas.edu/~pingali/CS380C/2016/lectures/Recursive-descent.pdf为了避免要经常跳过空格，我们可以先将字符串转化成token steam，这样parser只用处理token就可以了。
将字符串转化成token比较直观，只需要注意，当有双引号的时候，空格不能去掉，而要保留。所以字符串转token的代码先略过。
Parser
下面就是我们的重头戏——parser。
parser有很多种，LL(k), LR(k)，PEG等等。我是为了练手，就挑了我觉得最容易写的方法：recursive descent。
recursive descent parser又叫top-down parser，是一种自顶向下的方法，就像一个树一下，从根节点不停地向叶节点生长。
为什么自顶向下，手写起来比较容易呢？因为我们从一个节点出发，选择其中下一个节点，没有太多细节需要处理。每次进入一个节点，我们接下来要去哪里也清晰。
根据JSON的语法规则 https://www.json.org/json-en.html
我们可以看到value，可以是对象，数组，string， true, false， null，
所以我们可以编写我们的parse_value()函数如下，
根据第一个字符是{，还是[,还是 ”,来决定我们接下来要进入哪一个节点。
class Parser:
def __init__(self):
pass
def parse(self, s):
lexer = Lexer()
lexemes = lexer.lexers(s)
if len(lexemes) < 2:
Exception('Ill format json.')
item, _ = self.parse_value(lexemes)
return item.value
def parse_value(self, lexemes: list[Token]):
if len(lexemes) == 0:
return Item('string', '', 'string')
if lexemes[0].lexeme == '{':
return self.parse_object(lexemes)
if lexemes[0].lexeme == '[':
return self.parse_array(lexemes)
if lexemes[0].lexeme == '"':
item, lexemes = self.get_string(lexemes)
return item, lexemes- 当进入string节点的时候，我们就可以调用对应的get_string()函数来获取字符串。
- 当进入数组节点的时候，我们就可以调用parse_array()函数来获取数组。
- 当进入对象节点的时候，我们就可以调用parse_object()函数来获取对应的对象。
而如果我们要支持更多的类型，只需要添加对应的代码即可。
如果想看完整的代码，可以查看https://github.com/Celthi/writing-parser
单元测试
这时候，我们要编写对应的单元测试。写代码有趣的前提之一是测试要自动化。
这样每次修改代码，我们只需要跑相应的单元测试，如果测试通过，就说明我们没有改坏了。
from parser_with_lexer import Parser
import unittest
class TestParserLexer(unittest.TestCase):
def test_parse(self):
parser = Parser()
self.assertDictEqual(
{"key": "value"}, parser.parse('{ "key" : "value"}'))
self.assertDictEqual({"key": 234}, parser.parse('{ "key" : 234 }'))
self.assertDictEqual({}, parser.parse('{}'))
self.assertDictEqual({"key": 234, "k2": "value"},
parser.parse('{ "key" : 234, "k2": "value" }'))
self.assertDictEqual({"key": 234, "k2": "value", "k3": "v3"}, parser.parse(
'{ "key" : 234, "k2": "value" , "k3": "v3"}'))
self.assertDictEqual({"key": 234, "k2": "value", "k3": "v3", "k4": {"ik1": "iv"}}, parser.parse(
'{ "key" : 234, "k2": "value" , "k3": "v3", "k4": {"ik1": "iv"} }'))
self.assertDictEqual({"key": 234, "k2": "value", "k3": "v3", "k4": {"ik1": "iv", "ik2": 678}}, parser.parse(
'{ "key" : 234, "k2": "value" , "k3": "v3", "k4": {"ik1": "iv", "ik2": 678}} }'))（持续更新）
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK