手写 JSON 解析器

实现原理

  • 理解JSON的语法，可以使用 https://www.json.cn/ 。按照 json 规范，除了对象，输入 Array、Boolean、Number、Undefined 都是可以的。

  • 绘制「对象」有限状态机：

    Untitled.png

    • 说明：先不用考虑状态机整体，先考虑最常用的对象输入
    • 对象状态机流程：
      • 首先判断 { 字符
      • 紧接着判断空白字符，判断其后是否为 }
        • 如果是，则结束
        • 如果不是，则解析 字符串 作为 key， 解析 空白字符，解析 : ，解析 value 的值。
        • 因为可以有多个 key value 对，所以继续解析 , 然后重复上一步
代码实现 
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
 /**
   * 解析对象
   * @returns {object}
   */
  function parseObject() {
      if (str[idx] === '{') {
          ++idx;
          skipWhiteSpace(); // 跳过空白字符

          const res = {};
          let init = true;
          while (str[idx] !== '}') { // 循环匹配，找到多个 key-value
              if (!init) { // 如果不是第一个key-value，应该匹配 , 
                  skipWhiteSpace();
                  eatComma();
                  skipWhiteSpace();
              }
              init = false;

              const key = parseString(); // 解析 key
              skipWhiteSpace();
              eatColon(); // 匹配 : 
              skipWhiteSpace();
              const value = parseValue(); // 解析 value
              res[key] = value;
          }
          ++idx;
          return res;
      }
  }

/**
   * 解析值
   * @returns {any}
   */
  function parseValue() {
      skipWhiteSpace(); // 跳过空白字符
		// 这里就是把 value 当作 string / number / object / array 等进行尝试匹配
      // 如果匹配成功，指针idx会移动，并且能拿到 val 
      const val = parseString() ?? parseNumber() ?? parseObject() ?? parseArray() ??
          parseKeyword("true", true) ?? parseKeyword("false", false) ?? parseKeyword("null", null) ?? parseKeyword("undefined", undefined);
      skipWhiteSpace(); // 跳过空白字符

      return val;
  }

  • 绘制「数组」有限状态机：

    Untitled.png

    • 说明：数组状态机简单一些
    • 流程：类似对象状态机。
代码实现 
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
/**
   * 解析数组
   * @returns {any[]}
   */
  function parseArray() {
      if (str[idx] === "[") {
          ++idx;
          skipWhiteSpace();

          const res = []
          let init = true;
          while (str[idx] !== ']') {
              if (!init) {
                  skipWhiteSpace();
                  eatComma();
                  skipWhiteSpace();
              }
              init = false;

              const value = parseValue();
              res.push(value);
          }
          ++idx;
          return res;
      }
  }

  • 依次绘制「其它数据类型」有限状态机，直接看代码即可，这里不重复了。其中比较麻烦的是 Number 。

  • 最终，由于前面提到的JSON规范，对象、Array数组等都可以直接作为Input进行解析，所以函数返回就是 parseValue 调用，而不是 parseObject 。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    /**
     * @description 解析json
     * @author dongyuanxin
     * @param {string} str 
     */
    function parseJson(str) {
        let idx = 0;
        return parseValue(str);
    		// ... 各种parse定义
    }

  • 使用效果

    Untitled.png

源码地址

bookmark

根据文章，自己也实现了一份JSON解析器代码。

参考链接

bookmark

bookmark