前言
最近正在补习编译原理的相关理论基础。于是琢磨着写个简单的语言解析器。
0x00. 根基
1
2
31. python编程（ply库） 2. 正则表达式
0x01. 了解json的语法规范
1
2
3
4
5
6
7
8
9
10
111. json里的字典key必须是字符串型，value可以是任意类型； 2. json根基点必须是字典或者数组； 3. json支持的值包括： - 数字（整数或浮点数） - 字符串（在双引号中） - 逻辑值（true 或 false） - 数组（在方括号中） - 对象（在花括号中） - null 4. 分割符为逗号",".
0x02. 书写文法
- 上下文无关文法；
- 避免二义性，或者使用规则解决二义性冲突；
- 判断二义性存在的方法：某一段输入可以用两棵以上语法树解释的，我们认为存在二义性；
- 优先级，需要n+1个非终结符号；
下面先祭出自己写的json的文法–BNF范式。
1
2
3
4
5
6
7
8
root_block : LSBRACKET block_item_list RSBRACKET
| LBRACE block_item_list RBRACE
| CONSTANT
| NORMSTRING COLON root_block
| NORMSTRING
| KEYWORDS
block_item_list : block_item_list COMMA root_block
| root_block###
0x03. 编程
PLY 是纯粹由 Python 实现的 Lex 和 yacc（流行的编译器构建工具）。PLY 的设计目标是尽可能的沿袭传统 lex 和 yacc 工具的工作方式，包括支持 LALR(1)分析法、提供丰富的输入验证、错误报告和诊断。因此，如果你曾经在其他编程语言下使用过 yacc，你应该能够很容易的迁移到 PLY 上。
相关术语翻译：
| 英 | 译 |
|---|---|
| token | 标记 |
| context free grammar | 上下文无关文法 |
| syntax directed translation | 语法制导的翻译 |
| ambiguity | 二义性 |
| terminals | 终结符 |
| non-terminals | 非终结符 |
| documentation string | 文档字符串（python中的docstring） |
| shift-reduce | 移进-归约 |
| Empty Productions | 空产生式 |
| Panic mode recovery | panic恢复模式 |
第一步. 词法解析（Lex）
声明tokens，所有用到的token；
复制代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# List of token names. This is always required tokens = ( 'LSBRACKET', 'RSBRACKET', 'LBRACE', 'RBRACE', 'COLON', 'NORMSTRING', 'CONSTANT', 'VARIABLE', 'COMMA', 'KEYWORDS', )在赋值表达式或者函数中，使用正则扣取token，并返回这个值。值得注意的是换行或者注释是不再tokens里面的，而且没有返回值。
复制代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27t_ignore = ' tr' t_LSBRACKET = r'[' t_RSBRACKET = r']' t_LBRACE = r'{' t_RBRACE = r'}' t_COLON = r':' t_COMMA = r',' KEYWORDS = [ r'null', ] keyword = '|'.join(keyword.replace(' ', 's+') for keyword in KEYWORDS) @lex.TOKEN(keyword) def t_KEYWORDS(t): # todo: to support false,true t.value = None return t def t_newline(t): r'n+' t.lexer.lineno +=len(t.value)错误句柄，在解析过程中报错时，会调用这个函数。放一些调试信息进去会帮助你快速定位问题。
复制代码1
2
3
4
5``` def t_error(t): raise Exception('Error {} at line {}'.format(t.value[0], t.lineno)) ```解析，扣tokens的方法有了，解析就是给定一段输入，输出tokens。
复制代码1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16``` # Test it out data = ''' 3 + 4 * 10 + -20 *2 ''' # Give the lexer some input lexer.input(data) # Tokenize while True: tok = lexer.token() if not tok: break # No more input print tok ```
第二步. 语法解析(Yacc)
说下大致思路: 使用bnf范式，构建ast树。输出是你想把输入翻译成的样子，比如计算器，你想要的是结果。json我想要一段python版的json数据结构。
第三步. 导入头文件
看很多博文，给代码片段的博主都没有加头文件，天晓得你用的是什么库。
这里祭出完整的代码 –>传送门。
0x04. 调试
1. 词法解析时，被处理的token没有返回值
输入为：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
{"menu" :
{
"header": "SVG Viewer",
"items": [
{"id": "Open"},
{"id": "OpenNew", "label": "Open New"},
null,
{"id": "ZoomIn", "label": "Zoom In"},
{"id": "ZoomOut", "label": "Zoom Out"},
{"id": "OriginalView", "label": "Original View"},
null, # 这里是第11行，报错的位置，可以看到问题出在','前面
{"id": "Quality"},
{"id": "Pause"},
{"id": "Mute"},
null,
{"id": "Find", "label": "Find..."},
{"id": "FindAgain", "label": "Find Again"},
{"id": "Copy"},
{"id": "CopyAgain", "label": "Copy Again"},
{"id": "CopySVG", "label": "Copy SVG"},
{"id": "ViewSVG", "label": "View SVG"},
{"id": "ViewSource", "label": "View Source"},
{"id": "SaveAs", "label": "Save As"},
null,
{"id": "Help"},
{"id": "About", "label": "About Adobe CVG Viewer..."}
]
}, "a":{"aa":"nn"} }报错信息如下：
1
2
3
4
Syntax error in input! Parser State:
[0, 1, 6, 10, 1, 8, 11, 6, 10, 3, 9, 11]
LBRACE NORMSTRING COLON LBRACE block_item_list COMMA NORMSTRING COLON LSBRACKET block_item_list COMMA . LexToken(COMMA,',',11,310)
[2017-02-09 15:30:56,725] file_parser.py:113-ERROR: before: ',' ,line 11 column 13解析：
第二行的列表是词法解析的状态跳转栈，即从第0个状态跳到第11个状态。然而，在第11个状态中，因为异常无法跳到下一状态。
第三行是token的处理序列。重点是看序列的最后一个token和LexToken, 最后一个token代表现在能正确处理的最后一个位置，而LexToken表示现在处理的是哪个字符，他们中间的位置就是有问题的部分。可以看到第11行逗号前面是null, null在我的逻辑中应该归为KEYWORDS这类token，为什么没有出现呢？答案只有一个，就是在lex扣取null时没有返回值。
最后
以上就是不安夏天最近收集整理的关于如何写一个json语法解析器的全部内容，更多相关如何写一个json语法解析器内容请搜索靠谱客的其他文章。
发表评论 取消回复