Build your own JSON Parser

最近正好趁着假期翻了下《编程语言设计模式》和《ANTRL4 权威指南》，写这篇文章记录下用不同的方式实现 JSON Parser，第一部分用 ANTLR4 生成解析器，第二部分根据根据 JSON 语法图规则用 VanillaJS 手写 JSON Parser 的词法分析部分。

ANTLR4 生成 JSON Parser

ANTLR4 是一个解析器生成器，支持 EBNF 描述语法，ANLTR 的运行库提供了两种遍历解析树的机制，在这个例子中我们使用访问器的方式来控制访问子节点。

查看 JSON 规范可以看到和 EBNF 等价的语法图：

从语法图左边开始，对于对象来说，第一个字符必须是”{”，然后有以下选择：

→ whitespace → “}”

→ whitespace → string → whitespace → “:” → value

→ “}”
→ “,” → ... → “}”

这里的 whitespace 在 JSON 规范页面的底部，拉到最下面可以看到其语法图。以此类推，对照规范将 JSON 的语法图转化为 EBNF 的结果如下：


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

STRING: '"' ESC* '"';
// 规则声明为fragment可以告诉 ANTLR，该规则本身不是一个词法符号，它只会被其他的词法规则使用。
fragment ESC: '\\' (["\\/bfnrt] | UNICODE);
fragment UNICODE: 'u' HEX HEX HEX HEX;
fragment HEX: [0-9a-fA-F];

NUMBER: '-'? INT ('.' [0-9]+)? EXP?;
fragment INT: '0' | [1-9] [0-9]*;
fragment EXP: [Ee] [+\-]? INT;

WS: [ \t\n\r]+ -> skip;

用 ANTLR 生成访问器文件：


antlr4 -Dlanguage=JavaScript  -no-listener -visitor JSON.g4

访问器文件关键代码如下，同样非常好理解，匹配对应的分支，对于基本类型进行转换返回结果，对于数组和对象会递归求解：


visitProg(ctx) {
	return this.visitChildren(ctx);
}

visitValue(ctx) {
	if (ctx.obj()) {
		return this.visitObj(ctx.obj());
	} else if (ctx.arr()) {
		return this.visitArr(ctx.arr());
	} else if (ctx.STRING()) {
		return ctx.STRING().getText();
	} else if (ctx.NUMBER()) {
		return Number(ctx.NUMBER().getText())
	} else if (ctx.getText() === 'true') {
		return true;
	} else if (ctx.getText() === 'false') {
		return false;
	} else if (ctx.getText() === 'null') {
		return null;
	} else {
		throw new Error('...')
	}
}

visitObj(ctx) {
	const obj = {};
	const length = ctx.STRING().length;
	for (let i = 0; i < length; i++) {
		const key = ctx.STRING()[i].getText().replaceAll('"', '');
		const value = this.visitValue(ctx.value()[i]);
		obj[key] = value;
	}
	return obj;
}

visitArr(ctx) {
	const arr = [];
	for (let i = 0; i < ctx.value().length; i++) {
		arr.push(this.visitValue(ctx.value(i)));
	}
	return arr;
}

VanillaJS 实现 JSON Parser

实现一个 Parser 并不一定需要经过完整的词法分析、语法分析等阶段，例如 JSON Parser with JavaScript 这篇文章的示例并没有一个词法分析阶段，而是基于条件判断 + 正则匹配，但最终要达到的目的都是能够识别某种语法。

词法分析

首先根据 JSON 语法图就能够找出所有的词法单元：


['{', ':', ',', '}', '[', ']', 'true', 'false', 'null', 'STRING', 'NUMBER'];

那么我们需要编写 Token 类，Lexer 抽象类和具体的 JSONLexer 实现：


// Token 具有词法类型和字符串两个属性
class Token {
  constructor(type, text) {
    this.type = type
    this.text = text
  }
}


class Lexer {
  constructor(input) {
    this.input = input      // 输入字符串
    this.i = 0;             // 当前输入字符的下表
    this.c = this.input[0]; // 当前字符
  }

  // consume 方法消耗一个字符，并检测输入字符串是否结束
  consume() {
    this.i++;
    if (this.i < this.input.length) {
      this.c = this.input[this.i];
    } else {
      this.c = null;
    }
  }

  // match 方法匹配一个字符并调用 consume，如果匹配失败抛出错误
  match(x) {
    if (this.c === x) {
      this.consume();
    } else {
      throw new Error(`Expected ${x} but got ${this.c}`)
    }
  }
 
  // nextToken 方法生成下一个词法单元
  public abstract nextToken();
  public abstract getTokenName(tokenType)
}


class JSONLexer extends Lexer {
  constructor(input) {
    super(input);
  }

  tokenNames = ['{', ':', ',', '}', '[', ']', 'true', 'false', 'null', 'STRING', 'NUMBER'];

  getTokenName(tokenType) {
    return this.tokenNames[tokenType - 1];
  }

  nextToken() {
    while (!this.isEOF) {
      switch (this.c) {
        case ' ': case '\t': case '\r': case '\n': this.WS(); continue;
        case '{': this.consume(); return new Token(1, '{');
        case ':': this.consume(); return new Token(2, ':');
        case ',': this.consume(); return new Token(3, ',');
        case '}': this.consume(); return new Token(4, '}');
        case '[': this.consume(); return new Token(5, '[');
        case ']': this.consume(); return new Token(6, ']');
        default:
          if (this.isKeyword('true')) return this.keywordToken('true');
          else if (this.isKeyword('false')) return this.keywordToken('false');
          else if (this.isKeyword('null')) return this.keywordToken('null');
          else if (isString(this.c)) return this.STRING();
          else if (isNumber(this.c)) return this.NUMBER();
          else throw new Error(`Lexer: Unexpected character ${this.c}`)
      }
    }
    return new Token(-1, 'EOF');
  }

  isKeyword(text) {
    return this.input.slice(this.i, this.i + text.length) === text
  }

  keywordToken(text) {
    const TOKEN_MAP = { 'true': 7, 'false': 8, 'null': 9 };
    for (let i = 0; i < text.length; i++) {
      this.consume();
    }
    return new Token(TOKEN_MAP[text], text);
  }

  STRING() {
    this.consume(); //消耗左引号
    let result = '';
    while (this.c !== '"') {
      result += this.c;
      this.consume();
    }
    this.consume(); // 消耗右引号
    return new Token(10, result);
  }

  NUMBER() {
    let result = '';
    while (isNumber(this.c)) {
      result += this.c;
      this.consume();
    }
    return new Token(11, result);
  }

  WS() {
    while (isWhitespace(this.c)) {
      this.consume();
    }
  }
}

上面的代码应该不难理解，扫描并识别字符串中的模式，生成词法单元流，完整的代码请在 Github 中查看。测试一下结果如下：


const input = '{"name": "John", "age": 30, "children": [{"name": "Mary", "age": 5}, {"name": "Moe", "age": 3}]}';
const lexer = new JSONLexer(input);
while (lexer.c !== null) {
  console.log(lexer.nextToken());
}

/**
Token {type: 1, text: '{'}
Token {type: 10, text: 'name'}
Token {type: 2, text: ':'}
Token {type: 10, text: 'John'}
Token {type: 3, text: ','}
Token {type: 10, text: 'age'}
Token {type: 2, text: ':'}
Token {type: 11, text: '30'}
Token {type: 3, text: ','}
Token {type: 10, text: 'children'}
Token {type: 2, text: ':'}
Token {type: 5, text: '['}
Token {type: 1, text: '{'}
Token {type: 10, text: 'name'}
Token {type: 2, text: ':'}
Token {type: 10, text: 'Mary'}
Token {type: 3, text: ','}
Token {type: 10, text: 'age'}
Token {type: 2, text: ':'}
Token {type: 11, text: '5'}
Token {type: 4, text: '}'}
Token {type: 3, text: ','}
Token {type: 1, text: '{'}
Token {type: 10, text: 'name'}
Token {type: 2, text: ':'}
Token {type: 10, text: 'Moe'}
Token {type: 3, text: ','}
Token {type: 10, text: 'age'}
Token {type: 2, text: ':'}
Token {type: 11, text: '3'}
Token {type: 4, text: '}'}
Token {type: 6, text: ']'}
Token {type: 4, text: '}'}
*/

词法分析部分结束，下一章，我们会写 JSON Parser 的语法分析部分。

Build your own JSON Parser - 1

ANTLR4 生成 JSON Parser

VanillaJS 实现 JSON Parser

词法分析