文章目录
- 一、实现 JSON lexer（词法解析器）
- 二、lex 词法分析
- 2.1 lex string 解析
- 2.2 lex number 解析
- 2.3 lex bool 和 null 解析
- 三、syntax parser 句法分析
- 3.1 parse array 解析数组
- 3.2 parse object 解析对象
- 四、封装接口
一、实现 JSON lexer（词法解析器）
首先，把输入的 string 拆分为 tokens，过程中会忽略注释、空格。迭代解析字符串流，解析为基本的、非递归定义的语言结构，如正数、字符串、布尔文字。
最终期望实现的效果如下：
assert_equal(lex('{"foo": [1, 2, {"bar": 2}]}'),
['{', 'foo', ':', '[', 1, ',', 2, ',', '{', 'bar', ':', 2, '}', ']', '}'])
整体逻辑大概如下：
def lex(string):
tokens = []
while len(string):
json_string, string = lex_string(string)
if json_string is not None:
tokens.append(json_string)
continue
# TODO: lex booleans, nulls, numbers
if string[0] in JSON_WHITESPACE:
string = string[1:]
elif string[0] in JSON_SYNTAX:
tokens.append(string[0])
string = string[1:]
else:
raise Exception('Unexpected character: {}'.format(string[0]))
return tokens
这里的目标是尝试匹配字符串、数字、布尔值和空值并将它们添加到标记列表中。如果这些都不匹配，请检查该字符是否为空格，如果是则将其丢弃。否则，如果它是 JSON 语法的一部分（如左括号），则将其存储为 token。如果字符/字符串与这些模式都不匹配，最后抛出异常。
二、lex 词法分析
整体框架如下：
def lex_string(string):
return None, string
def lex_number(string):
return None, string
def lex_bool(string):
return None, string
def lex_null(string):
return None, string
def lex(string):
tokens = []
while len(string):
json_string, string = lex_string(string)
if json_string is not None:
tokens.append(json_string)
continue
json_number, string = lex_number(string)
if json_number is not None:
tokens.append(json_number)
continue
json_bool, string = lex_bool(string)
if json_bool is not None:
tokens.append(json_bool)
continue
json_null, string = lex_null(string)
if json_null is not None:
tokens.append(None)
continue
if string[0] in JSON_WHITESPACE:
string = string[1:]
elif string[0] in JSON_SYNTAX:
tokens.append(string[0])
string = string[1:]
else:
raise Exception('Unexpected character: {}'.format(string[0]))
return tokens
2.1 lex string 解析
对于该lex_string函数，要点是检查第一个字符是否是引号。如果是，则迭代输入字符串，直到找到结束引号。
- 如果没有找到初始 quote，返回 None 和原始列表。
- 如果找到初始引号和结束引号，返回引号内的字符串以及未检查的输入字符串的其余部分。
def lex_string(string):
json_string = ''
if string[0] == JSON_QUOTE:
string = string[1:]
else:
return None, string
for c in string:
if c == JSON_QUOTE:
return json_string, string[len(json_string)+1:]
else:
json_string += c
raise Exception('Expected end-of-string quote')
2.2 lex number 解析
迭代输入，直到找到不能属于数字的字符。
- 如果已经找到了字符，则返回 float 或 int
- 否则，返回 None。
def lex_number(string):
json_number = ''
number_characters = [str(d) for d in range(0, 10)] + ['-', 'e', '.']
for c in string:
if c in number_characters:
json_number += c
else:
break
rest = string[len(json_number):]
if not len(json_number):
return None, string
if '.' in json_number:
return float(json_number), rest
return int(json_number), rest
2.3 lex bool 和 null 解析
def lex_bool(string):
string_len = len(string)
if string_len >= TRUE_LEN and string[:TRUE_LEN] == 'true':
return True, string[TRUE_LEN:]
elif string_len >= FALSE_LEN and string[:FALSE_LEN] == 'false':
return False, string[FALSE_LEN:]
return None, string
def lex_null(string):
string_len = len(string)
if string_len >= NULL_LEN and string[:NULL_LEN] == 'null':
return True, string[NULL_LEN:]
return None, string
到现在为止， lex 就完成了，完整源码见 https://github.com/eatonphil/pj/blob/master/pj/lexer.py
三、syntax parser 句法分析
句法分析的基本工作是：迭代 一维 的 tokens 数组，匹配为一组组的 token 对。匹配失败时，期望能报错：用户实际的输入，和期望的输入。
对于 JSON parser，就是解析 lex() 函数的结果，匹配为若干 objects、lists、plain values 等。
期望的效果如下：
tokens = lex('{"foo": [1, 2, {"bar": 2}]}')
assert_equal(tokens,
['{', 'foo', ':', '[', 1, ',', 2, '{', 'bar', ':', 2, '}', ']', '}'])
assert_equal(parse(tokens),
{'foo': [1, 2, {'bar': 2}]})
基本框架如下：
def parse_array(tokens):
return [], tokens
def parse_object(tokens):
return {}, tokens
def parse(tokens):
t = tokens[0]
if t == JSON_LEFTBRACKET: # [
return parse_array(tokens[1:])
elif t == JSON_LEFTBRACE: # {
return parse_object(tokens[1:])
else:
return t, tokens[1:] # 解析出 t，并返回除去 t 之外剩余的部分
该词法分析器和解析器之间的一个关键结构差异是词法分析器返回一个一维标记数组。解析器通常以递归方式定义并返回递归的树状对象。由于 JSON 是一种数据序列化格式而不是一种语言，因此解析器应该生成 Python 中的对象，而不是语法树，您可以在语法树上执行更多分析（或者在编译器的情况下生成代码）。
而且，词法分析独立于解析器进行的好处是，这两段代码都更简单并且只涉及特定元素。
3.1 parse array 解析数组
解析数组，就是解析数组成员，并期望它们之间有逗号标记或指示数组结尾的右括号。
def parse_array(tokens):
json_array = []
t = tokens[0]
if t == JSON_RIGHTBRACKET: # ] 表示第一个字符就直接遇到 ] 了，即数组结尾了
return json_array, tokens[1:]
while True:
json, tokens = parse(tokens) # 解析出一项数组的内容
json_array.append(json) # 追加到 json_array 变量中
t = tokens[0] # 下一个待解析的字符
if t == JSON_RIGHTBRACKET: # ]
return json_array, tokens[1:] # 结束匹配
elif t != JSON_COMMA: # , 数组各项元素之间应通过逗号分隔
raise Exception('Expected comma after object in array')
else: # t 为 逗号，则继续循环处理后续字符 tokens[1:]
tokens = tokens[1:]
raise Exception('Expected end-of-array bracket')
3.2 parse object 解析对象
解析对象就是解析一个键值对，内部用冒号分隔，外部用逗号分隔，直到到达对象的末尾。
def parse_object(tokens):
json_object = {}
t = tokens[0]
if t == JSON_RIGHTBRACE: # }
return json_object, tokens[1:]
while True:
# 期望 json key 是 字符串, 例如 "A": 1.123
json_key = tokens[0] # 即 json_key = A
if type(json_key) is str:
tokens = tokens[1:]
else:
raise Exception('Expected string key, got: {}'.format(json_key))
# 期望用冒号分隔
if tokens[0] != JSON_COLON:
raise Exception('Expected colon after key in object, got: {}'.format(t))
json_value, tokens = parse(tokens[1:])
json_object[json_key] = json_value
t = tokens[0]
if t == JSON_RIGHTBRACE:
return json_object, tokens[1:]
elif t != JSON_COMMA:
raise Exception('Expected comma after pair in object, got: {}'.format(t))
tokens = tokens[1:]
raise Exception('Expected end-of-object brace')
至此，parser 就完成了，源码详见 https://github.com/eatonphil/pj/blob/master/pj/parser.py
四、封装接口
为了提供理想的接口，可以用 from_string 包装 lex 和 parse 函数。
def from_string(string):
tokens = lex(string)
return parse(tokens)[0]
完整源码见 https://github.com/eatonphil/pj
一些解析器选择在一个阶段中实现词法分析和句法分析。对于某些语言，这可以完全简化解析阶段。或者，在 Common Lisp 等更强大的语言中，它可以允许使用读取器宏一步动态扩展词法分析器和解析器，详见 https://gist.github.com/chaitanyagupta/9324402。
