编译原理从零到一 写一个 JSON parser
最近在做 Chrome 插件的高级功能，突然想要试试可视化选择 key 的路径，再一想，咦，这不就是个编译原理的典型例题吗？
于是我就开始着手学编译原理了，主要参考 dalao 的以下两篇文章：
编译原理一共分为四个部分：词法分析，语法（文法）分析，语义分析，代码生成。
词法分析，就是逐个解析之后加上词性，语法分析则是将词法分析后的结果解析为抽象语法树，语义分析是在语法分析时针对具体的实例加上额外的动作解释。具体的可以见上面的链接。
在 JSON 的首页有非常完整的词法和语法分析的 token 列表甚至是流程图，所以可以省去了一些劳动。
在词法分析上，我们要首先抽象出哪些是我们 tokens，进行归类，然后一个个字符的进行 read() 。最简单的方法只要逐个阅读看看满足哪一个 token 的条件处理并存入就行了，上文的链接中也有词法分析器的介绍，写得非常清楚。
class Lexer {
constructor() {
this.chunk = '';
}
lex(input) {
this.chunk = input;
this.tokens = [];
while(!this.readEOF()) {
let consumed = this.readWhiteSpace()
|| this.readString()
|| this.readNumber()
|| this.readBoolean()
|| this.readNull()
|| this.readLiteral()
this.chunk = this.chunk.slice(consumed);
}
return this.tokens;
}
pushToken(type, value) {
this.tokens.push([type, value]);
}
readEOF() {
if (!this.chunk) {
this.pushToken('EOF', '');
return true;
};
}
readWhiteSpace() {
return this.chunk.match(/^\s*/)[0].length;
}
readString() {
let match = this.chunk.match(/^"(?:[^"\\\x00-\x1F\x7F\x80-\x9F]|\\["\\/bfnrt]|\\u[0-9a-fA-F]{4})*"/);
if (match) {
this.pushToken('String', match[0]);
return match[0].length;
}
}
readNumber() {
let match = this.chunk.match(/^-?[1-9]*\d+(?:\.\d+)?(?:[eE][+-]?\d+)?/);
if (match) {
this.pushToken('Number', match[0]);
return match[0].length;
}
}
readBoolean() {
let match = this.chunk.match(/^(?:true|false)/);
if (match) {
this.pushToken('Boolean', match[0].toLowerCase());
return match[0].length;
}
}
readNull() {
let match = this.chunk.match(/^null/);
if (match) {
this.pushToken('Null', match[0]);
return match[0].length;
}
}
readLiteral() {
const value = this.chunk.charAt(0);
this.pushToken(value, value);
return value.length;
}
}词法分析器的流程非常简单，只要一个不拉的列出 tokens 并且存入即可，之后我们就可以得到一个词法分析的结果数组。
parser 的部分原博并没有写，实际上也就是遍历并构造一颗抽象语法树，我们这里用自顶向下的构建法，深度优先遍历得出构造的结果。
从表面上来说和词法分析器是一样的，区别只是构造数组和构造树的区别——我们利用解析后的词法分析结果数组作为输入，逐个分析类型并且处理结果。
最后，我们需要做一些自定义的操作，比如我们想要格式化或者生成 JSON，就非常容易了：只需要根据结果的 token 类型匹配再进行一些操作即可：
class Parser {
constructor() {
this.tokens = [];
}
parse(input) {
this.i = 0;
this.tokens = new Lexer().lex(input);
const value = this.getValue();
if (!value) throw new TypeError('failed to parse JSON, expect value');
return value;
}
format(input, indent = ' ') {
const ast = this.parse(input);
return this._format(ast, indent);
}
_format(node, indent) {
switch(node.type) {
case 'String':
return JSON.stringify(JSON.parse(node.value));
case 'Number':
case 'True':
case 'False':
case 'Null':
return node.value;
}
let [begin, end] = node.type === 'Object' ? ['{', '}'] : ['[', ']'];
let output = begin;
const innerMembers = node.value;
if (!innerMembers.length) return output + end;
output += '\n';
innerMembers.forEach((item, index, arr) => {
output += indent;
if (node.type === 'Object') output += item.key.value + ': ';
const value = node.type === 'Object' ?
this._format(item.value, indent).replace(/\n/g, '\n' + indent) :
this._format(item, indent).replace(/\n/g, '\n' + indent);
output += value;
if (index !== arr.length - 1) output += ',\n';
});
return output += '\n' + end;
}
getValue() {
return this.readString() || this.readNumber() || this.readObject() || this.readArray() || this['true']() || this['false']() || this['null']();
}
readString() {
const [tag, value] = this.tokens[this.i];
if (tag === 'String') {
this.i++;
return { type: 'String', value };
}
}
readNumber() {
const [tag, value] = this.tokens[this.i];
if (tag === 'Number') {
this.i++;
return { type: 'Number', value };
}
}
readObject() {
const [tag] = this.tokens[this.i];
if (tag === '{') {
this.i++;
const members = this.readMembers() || [];
const [tag] = this.tokens[this.i];
if (tag !== '}') throw new TypeError('failed to parse object, expect "}"');
this.i++;
return { type: 'Object', value: members };
}
}
readMembers() {
let pair = this.readPair();
if (!pair) return [];
let members = [ pair ];
while (true) {
const [tag] = this.tokens[this.i];
if (tag !== ',') break;
this.i++;
pair = this.readPair();
members.push(pair);
}
return members;
}
readPair() {
const string = this.readString();
if (!string) throw new TypeError('failed to parse pair, expect string');
const [tag] = this.tokens[this.i];
if (tag !== ':') throw new TypeError('failed to parse pair, expect colon');
this.i++;
const value = this.getValue();
if (!value) throw new TypeError('failed to parse pair, expect value');
return { key: string, value };
}
readArray() {
const [tag] = this.tokens[this.i];
if (tag === '[') {
this.i++;
const elements = this.readElements() || [];
const [tag] = this.tokens[this.i];
if (tag !== ']') throw new TypeError('failed to parse object, expect "]"');
this.i++;
return { type: 'Array', value: elements };
}
}
readElements() {
let value = this.getValue();
if (!value) return [];
let elements = [ value ];
while (true) {
const [tag] = this.tokens[this.i];
if (tag !== ',') break;
this.i++;
value = this.getValue();
elements.push(value);
}
return elements;
}
'true'() {
const [tag, value] = this.tokens[this.i];
if (tag === 'Boolean' && value === 'true') {
this.i++;
return { type: 'True', value };
}
}
'false'() {
const [tag, value] = this.tokens[this.i];
if (tag === 'Boolean' && value === 'false') {
this.i++;
return { type: 'False', value };
}
}
'null'() {
const [tag, value] = this.tokens[this.i];
if (tag === 'Null') {
this.i++;
return { type: 'Null', value };
}
}
}这样就完成了一个 JSON parser。
植入部分
如果您觉得文章不错，可以通过赞助支持我。
如果您不希望打赏，也可以通过关闭广告屏蔽插件的形式帮助网站运作。