编译原理从零到一 写一个 JSON parser
最近在做 Chrome 插件的高级功能，突然想要试试可视化选择 key 的路径，再一想，咦，这不就是个编译原理的典型例题吗？
于是我就开始着手学编译原理了，主要参考 dalao 的以下两篇文章：
编译原理一共分为四个部分：词法分析，语法（文法）分析，语义分析，代码生成。
词法分析，就是逐个解析之后加上词性，语法分析则是将词法分析后的结果解析为抽象语法树，语义分析是在语法分析时针对具体的实例加上额外的动作解释。具体的可以见上面的链接。
在 JSON 的首页有非常完整的词法和语法分析的 token 列表甚至是流程图，所以可以省去了一些劳动。
在词法分析上，我们要首先抽象出哪些是我们 tokens，进行归类，然后一个个字符的进行 read() 。最简单的方法只要逐个阅读看看满足哪一个 token 的条件处理并存入就行了，上文的链接中也有词法分析器的介绍，写得非常清楚。
1class Lexer {
2 constructor() {
3 this.chunk = '';
4 }
5
6 lex(input) {
7 this.chunk = input;
8 this.tokens = [];
9 while(!this.readEOF()) {
10 let consumed = this.readWhiteSpace()
11 || this.readString()
12 || this.readNumber()
13 || this.readBoolean()
14 || this.readNull()
15 || this.readLiteral()
16 this.chunk = this.chunk.slice(consumed);
17 }
18 return this.tokens;
19 }
20 pushToken(type, value) {
21 this.tokens.push([type, value]);
22 }
23
24 readEOF() {
25 if (!this.chunk) {
26 this.pushToken('EOF', '');
27 return true;
28 };
29 }
30
31 readWhiteSpace() {
32 return this.chunk.match(/^\s*/)[0].length;
33 }
34
35 readString() {
36 let match = this.chunk.match(/^"(?:[^"\\\x00-\x1F\x7F\x80-\x9F]|\\["\\/bfnrt]|\\u[0-9a-fA-F]{4})*"/);
37 if (match) {
38 this.pushToken('String', match[0]);
39 return match[0].length;
40 }
41 }
42
43 readNumber() {
44 let match = this.chunk.match(/^-?[1-9]*\d+(?:\.\d+)?(?:[eE][+-]?\d+)?/);
45 if (match) {
46 this.pushToken('Number', match[0]);
47 return match[0].length;
48 }
49 }
50
51 readBoolean() {
52 let match = this.chunk.match(/^(?:true|false)/);
53 if (match) {
54 this.pushToken('Boolean', match[0].toLowerCase());
55 return match[0].length;
56 }
57 }
58
59 readNull() {
60 let match = this.chunk.match(/^null/);
61 if (match) {
62 this.pushToken('Null', match[0]);
63 return match[0].length;
64 }
65 }
66
67 readLiteral() {
68 const value = this.chunk.charAt(0);
69 this.pushToken(value, value);
70 return value.length;
71 }
72}
73
词法分析器的流程非常简单，只要一个不拉的列出 tokens 并且存入即可，之后我们就可以得到一个词法分析的结果数组。
parser 的部分原博并没有写，实际上也就是遍历并构造一颗抽象语法树，我们这里用自顶向下的构建法，深度优先遍历得出构造的结果。
从表面上来说和词法分析器是一样的，区别只是构造数组和构造树的区别——我们利用解析后的词法分析结果数组作为输入，逐个分析类型并且处理结果。
最后，我们需要做一些自定义的操作，比如我们想要格式化或者生成 JSON，就非常容易了：只需要根据结果的 token 类型匹配再进行一些操作即可：
1class Parser {
2 constructor() {
3 this.tokens = [];
4 }
5
6 parse(input) {
7 this.i = 0;
8 this.tokens = new Lexer().lex(input);
9 const value = this.getValue();
10 if (!value) throw new TypeError('failed to parse JSON, expect value');
11 return value;
12 }
13
14 format(input, indent = ' ') {
15 const ast = this.parse(input);
16 return this._format(ast, indent);
17 }
18
19 _format(node, indent) {
20 switch(node.type) {
21 case 'String':
22 return JSON.stringify(JSON.parse(node.value));
23 case 'Number':
24 case 'True':
25 case 'False':
26 case 'Null':
27 return node.value;
28 }
29 let [begin, end] = node.type === 'Object' ? ['{', '}'] : ['[', ']'];
30 let output = begin;
31 const innerMembers = node.value;
32 if (!innerMembers.length) return output + end;
33 output += '\n';
34 innerMembers.forEach((item, index, arr) => {
35 output += indent;
36 if (node.type === 'Object') output += item.key.value + ': ';
37 const value = node.type === 'Object' ?
38 this._format(item.value, indent).replace(/\n/g, '\n' + indent) :
39 this._format(item, indent).replace(/\n/g, '\n' + indent);
40 output += value;
41 if (index !== arr.length - 1) output += ',\n';
42 });
43 return output += '\n' + end;
44 }
45
46 getValue() {
47 return this.readString() || this.readNumber() || this.readObject() || this.readArray() || this['true']() || this['false']() || this['null']();
48 }
49
50 readString() {
51 const [tag, value] = this.tokens[this.i];
52 if (tag === 'String') {
53 this.i++;
54 return { type: 'String', value };
55 }
56 }
57
58 readNumber() {
59 const [tag, value] = this.tokens[this.i];
60 if (tag === 'Number') {
61 this.i++;
62 return { type: 'Number', value };
63 }
64 }
65
66 readObject() {
67 const [tag] = this.tokens[this.i];
68 if (tag === '{') {
69 this.i++;
70 const members = this.readMembers() || [];
71 const [tag] = this.tokens[this.i];
72 if (tag !== '}') throw new TypeError('failed to parse object, expect "}"');
73 this.i++;
74 return { type: 'Object', value: members };
75 }
76 }
77
78 readMembers() {
79 let pair = this.readPair();
80 if (!pair) return [];
81 let members = [ pair ];
82 while (true) {
83 const [tag] = this.tokens[this.i];
84 if (tag !== ',') break;
85 this.i++;
86 pair = this.readPair();
87 members.push(pair);
88 }
89 return members;
90 }
91
92 readPair() {
93 const string = this.readString();
94 if (!string) throw new TypeError('failed to parse pair, expect string');
95 const [tag] = this.tokens[this.i];
96 if (tag !== ':') throw new TypeError('failed to parse pair, expect colon');
97 this.i++;
98 const value = this.getValue();
99 if (!value) throw new TypeError('failed to parse pair, expect value');
100 return { key: string, value };
101 }
102
103 readArray() {
104 const [tag] = this.tokens[this.i];
105 if (tag === '[') {
106 this.i++;
107 const elements = this.readElements() || [];
108 const [tag] = this.tokens[this.i];
109 if (tag !== ']') throw new TypeError('failed to parse object, expect "]"');
110 this.i++;
111 return { type: 'Array', value: elements };
112 }
113 }
114
115 readElements() {
116 let value = this.getValue();
117 if (!value) return [];
118 let elements = [ value ];
119 while (true) {
120 const [tag] = this.tokens[this.i];
121 if (tag !== ',') break;
122 this.i++;
123 value = this.getValue();
124 elements.push(value);
125 }
126 return elements;
127 }
128
129 'true'() {
130 const [tag, value] = this.tokens[this.i];
131 if (tag === 'Boolean' && value === 'true') {
132 this.i++;
133 return { type: 'True', value };
134 }
135 }
136
137 'false'() {
138 const [tag, value] = this.tokens[this.i];
139 if (tag === 'Boolean' && value === 'false') {
140 this.i++;
141 return { type: 'False', value };
142 }
143 }
144
145 'null'() {
146 const [tag, value] = this.tokens[this.i];
147 if (tag === 'Null') {
148 this.i++;
149 return { type: 'Null', value };
150 }
151 }
152}
153
这样就完成了一个 JSON parser。
评论 (0)