如何写一个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 = ' \t\r'
       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时没有返回值。