Build your own JSON Parser

这章我们写一个递归下降语法解析器中解析能力最弱，但理解起来最容易的 LL(1) 解析器。

语法图映射到解析器

下面是第一章中截取的 JSON 规范的 EBNF 描述中的语法规则：


obj: '{' STRING ':' value (',' STRING ':' value)* '}' | '{' '}';
arr: '[' value (',' value)* ']' | '[' ']';
value: STRING | NUMBER | obj | arr | 'true' | 'false' | 'null';

...

... | ...

(...)*

可以看出可以大致分为三类文法，映射可以得到如下关键代码：


class JSONParser extends Parser {
  obj() {
    this.match(1); this.match(10); this.match(2); this.value();
    while (this.lookahead.type === 3) {
      this.match(3); this.match(10); this.match(2); this.value();
    }
    this.match(4)
  }

  ary() {
    this.match(5); this.value();
    while (this.lookahead.type === 3) {
      this.match(3); this.value();
    }
    this.match(6)
  }

  value() {
    switch (this.lookahead.type) {
      case 1: this.obj(); break;
      case 5: this.ary(); break;
      case 7: this.match(7); break;
      case 8: this.match(8); break;
      case 9: this.match(9); break;
      case 10: this.match(10); break;
      case 11: this.match(11); break;
      default: throw new Error(`Parser: Expected value but got ${this.lexer.getTokenName(this.lookahead.type)} `);
    }
  }
}

为了得到具体的解析类 JSONParser，先要在抽象类加入一些辅助代码，代码框架如下：


class Parser {
  constructor(lexer) {
    this.lexer = lexer; // 词法解析器实例
    this.lookahead = lexer.nextToken(); // 当前的 lookahead 符号
  }

  match(x) {
    if (this.lookahead.type === x) {
      this.consume();
    } else {
      throw new Error(`Unexpected token ${this.lookahead.type}`);
    }
  }

  consume() {
    this.lookahead = this.lexer.nextToken();
  }
}

如果输入的字符串符合上面的语法，则代码会静默执行成功，否则则会抛出异常。

确定性解析策略

使用该 JSON 解析器时，如果输入字符串为 {} 时会报错，原因是 obj 方法期待下一个词法单元必须是 STRING 类型。为了能够处理这种情况，或许你会想要将 obj 方法按照 ...|... 这类文法进行映射，此时你会察觉到，因为 obj 规则开头的词法单元类型都是 {，无法直接映射。

因此只有在解析选项的 lookahead 集合不相同时，才能应用 LL 解析策略，有两个解决方法：

合并 obj 的解析选项为 '{' (STRING ':' value(',' STRING ':' value) * )? '}’

增加 lookahead 数量，例如此处为 LL(2) 即可识别不同解析选项

方式一带有子规则(...)? ，该子规则在 LL(1) 解析器中可以用，但是不如修改前易懂。下一步试着实现能够使用任意数量的 lookahead 符号的回溯解析器。

回溯解析器

回溯解析器的策略就是依次尝试每个解析选项，一直找到合适的为止。如果能够匹配，解析器回到原点用非推断的方式重新解析。之所以要解析两次，是为了方便执行副作用操作，可以根据解析器是否在推演，来充当控制相关代码是否执行的“开关”。

错误提示

回溯时当所有解析选项都失败时，我们希望给出最可靠的错误提示，一个较为可行的方案是抛出最多匹配的词法单元所在的解析选项的错误。

小结

这一章我们从实现 LL(1) 解析器入门，到实现 LL(∞) 的解析器，并且理解了 LL(∞) 是如何实现错误提示的。到目前为止，已经能够读入 JSON 字符串并检测其语法是否合法了，下一章我们将实现一个解释器处理输入的语句。

Ps. 代码仓库地址：https://github.com/kamuiiiii/backup-parser

Build your own JSON Parser - 2

语法图映射到解析器

确定性解析策略

回溯解析器

错误提示

小结