Build your own JSON Parser

这章我们要写一个解释器处理输入的语句，使用类似 ANLTR4 的访问者模式，允许用户自定义访问者来控制遍历解析树的行为，这样的好处是能够将输入和输出的模型解耦。如果你想要获得 AST 等中间模型，可以自定义并控制访问器的输出。

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

Context

这里的 context 指的是与语法规则对应的上下文，解析器检测语法时，递归进入一个语法规则中并生成对应的 context 对象，直到遇到词法单元结束递归，从而构造出一颗解析树。


class RuleContext {
  constructor(parent) {
    this.parentCtx = parent; // 指向父 context 的指针
    this.children = null; // 储存所有子 context 的指针数组
  }
}

export class ObjContext extends RuleContext {
  constructor(parent) {
    super(parent);
    this.ruleIndex = 1;
  }

  // 重写 accept 方法
  accept(visitor) {
    if (visitor) {
			// 接收一个访问者，调用具体对应 context 的 visitXxx 方法
      return visitor.visitObj(this);
    } else {
      return visitor.visitChildren(this);
    }
  }

  // 对于 ObjContext，允许有多个 STRING 词法单元
  STRING(i) {
    return return_helper(this.children.filter(child => child.symbol && child.symbol.type === 10), i);
  }

  value(i) {
    return return_helper(this.children.filter(child => child instanceof ValueContext), i);
  }
}

// 根据词法单元生成终结节点，结束递归
class TerminalNodeImpl {
  constructor(symbol) {
    this.symbol = symbol;
  }

  getText() {
    return this.symbol.text;
  }
}

改造 Parser

上一节说到解析器检测语法时需要生成解析树，因此我们需要改造 Parser 消耗词法单元部分的代码，并增加 enterRule 和 exitRule 两个方法，在进入和退出语法规则时调用，修改如下：


class Parser {
	// ...
  enterRule(localctx) {
		// 如果处于非推断模式，不进入当前规则上下文
    if (this.isSpeculating()) return;
    if (this._ctx !== null) {
      this._ctx.addChild(localctx);
      localctx.parentCtx = this._ctx;
    }
    this._ctx = localctx;
  }

  exitRule() {
		// 如果处于非推断模式，退出当前规则上下文
    if (this.isSpeculating()) return;
    this._ctx = this._ctx.parentCtx;
  }

	consume() {
    // 如果不处于非推断状态，父节点添加以当前词法单元节点构造的终结节点
    if (!this.isSpeculating()) {
      const ctx = new TerminalNodeImpl(this.LT(1));
      this._ctx.addChild(ctx);
      ctx.parentCtx = this._ctx;
    }
   // ...
  }
}

class JSONParser extends Parser {
	// ...
	obj() {
    const localctx = new ObjContext(this._ctx);
    this.enterRule(localctx);
	  // ...
    this.exitRule();
    return localctx
  }
}

小结

我们直接将第一章传递给 ANTLR4 的 Visitor 原封不动的传递给我们的 JSON Parser，测试结果如下：


import JSONLexer from "./lib/lexer.js";
import JSONParser from "./lib/parser.js";
import MyVisitor from "./my-visitor.js";

const input = '[{"a":{"e":  [44,11,44]}},{"b":true},{"c":null}, {}]';
const lexer = new JSONLexer(input);
const parser = new JSONParser(lexer);
const tree = parser.value();
const visitor = new MyVisitor();
const res = tree.accept(visitor);
console.log('res:', JSON.stringify(res));

// res: [{"a":{"e":[44,11,44]}},{"b":true},{"c":null},{}]

结果是正确的，至此我们成功从头实现了一个 JSON Parser 👏👏。

Build your own JSON Parser - 3

Context

改造 Parser

小结