如何写一个json语法解析器

前言

最近正在补习编译原理的相关理论基础。于是琢磨着写个简单的语言解析器。

0x00. 根基

1. python编程（ply库）
2. 正则表达式

0x01. 了解json的语法规范

1. json里的字典key必须是字符串型，value可以是任意类型；
2. json根基点必须是字典或者数组；
3. json支持的值包括：
- 数字（整数或浮点数）
- 字符串（在双引号中）
- 逻辑值（true 或 false）
- 数组（在方括号中）
- 对象（在花括号中）
- null
4. 分割符为逗号",".

0x02. 书写文法

1. 上下文无关文法；
2. 避免二义性，或者使用规则解决二义性冲突；
3. 判断二义性存在的方法：某一段输入可以用两棵以上语法树解释的，我们认为存在二义性；
4. 优先级，需要n+1个非终结符号；

下面先祭出自己写的json的文法–BNF范式。

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 上。

相关术语翻译：

第一步. 词法解析（Lex）

1. 声明tokens，所有用到的token；

   
   # List of token names. This is always required
   tokens = (
   'LSBRACKET',
   'RSBRACKET',
   'LBRACE',
   'RBRACE',
   'COLON',
   'NORMSTRING',
   'CONSTANT',
   'VARIABLE',
   'COMMA',
   'KEYWORDS',
   )
   

2. 在赋值表达式或者函数中，使用正则扣取token，并返回这个值。值得注意的是换行或者注释是不再tokens里面的，而且没有返回值。

   
   t_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)
   

3. 错误句柄，在解析过程中报错时，会调用这个函数。放一些调试信息进去会帮助你快速定位问题。

   ```
   def t_error(t):
   raise Exception('Error {} at line {}'.format(t.value[0], t.lineno))
   ```
   

4. 解析，扣tokens的方法有了，解析就是给定一段输入，输出tokens。

   ```
   # 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没有返回值

输入为：

{"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"} }

报错信息如下：

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语法解析器所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。