前言
想要对编程技术提高一个维度,编译原理是绕不过的坎;它是 TypeScript、Babel、ESLint、Stylus、Vue、React、Marked 等开源前端框架的理论基石之一;了解编译原理能够对所接触的框架有更充分的认识。但是学习编译原理是一个比较复杂而又繁琐的过程,于是在 GitHub 上搜到了一个超级无敌小的编译器!它小到如果把所有注释删去的话,大概只剩 200 行左右的代码,麻小脏全,作者的注释也是超详细,当入门教程是非常不错的。
![真系大嗮 真系大嗮]()
渔:https://git.io/compiler
我们将会用它将 Lisp 风格的函数调用转换为 C 风格。如果你对这两种风格不是很熟悉,下面是一个简单的介绍。
假设有两个函数,add
和 subtract
,那么它们的写法将会是下面这样:
|
Lisp(风格) |
C(风格) |
2 + 2 |
(add 2 2) |
add(2, 2) |
4 - 2 |
(subtract 4 2) |
subtract(4, 2) |
2 + (4 - 2) |
(add 2 (subtract 4 2)) |
add(2, subtract(4, 2)) |
即输入 (add 2 2)
,要求输出 add(2, 2)
。虽然这并不包含 lisp 或者 C 的全部语法,但它足以向我们展示现代编译器很多要点。
设计
大多数编译器可以分成三个阶段:
- 解析(Parsing):将原始代码转换为一种更加抽象的表示(即 AST)。
- 转换(Transformation):将对这个抽象的表示做一些处理,让它能做到编译器期望它做到的事情。
- 代码生成(Code Generation):接收处理之后的代码表示,然后把它转换成新的代码。
解析(Parsing)
解析一般分成两个阶段:
词法分析(Lexical Analysis):接收原始代码,然后转换成一系列 Token(词法单元) ,这个过程由词法分析器( Tokenizer 或者 Lexer)中完成的。Token 是一个数组,由代码语句的碎片组成。它们可以是数字、标签、标点符号、运算符,或者其它任何东西。
语法分析(Syntactic Analysis):把 Token 转换成一种抽象的表示,这种抽象的表示描述了代码语句中的每一个片段以及它们之间的关系。这被称为中间表示(intermediate representation)或抽象语法树(Abstract Syntax Tree, 缩写为 AST)。AST 是个深层嵌套的对象,易于处理并且携带着语法结构信息,例如:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38
| (add 2 (subtract 4 2))
[ { type: 'paren', value: '(' }, { type: 'name', value: 'add' }, { type: 'number', value: '2' }, { type: 'paren', value: '(' }, { type: 'name', value: 'subtract' }, { type: 'number', value: '4' }, { type: 'number', value: '2' }, { type: 'paren', value: ')' }, { type: 'paren', value: ')' } ]
{ type: 'Program', body: [{ type: 'CallExpression', name: 'add', params: [{ type: 'NumberLiteral', value: '2' }, { type: 'CallExpression', name: 'subtract', params: [{ type: 'NumberLiteral', value: '4' }, { type: 'NumberLiteral', value: '2' }] }] }] }
|
编译器的下一步就是转换。它只是把 AST 拿过来然后对它做一些修改。它可以在同种语言下操作 AST,也可以把 AST 翻译成全新的语言。
下面来看看该如何转换 AST。
你或许注意到了 AST 中有很多相似的元素,这些元素都有 type 属性,它们被称为 AST 结点。这些结点有若干属性,可以用于描述 AST 的部分信息。
1 2 3 4 5 6 7 8 9 10 11
| { type: 'NumberLiteral', value: '2' }
{ type: 'CallExpression', name: 'subtract', params: [...nested nodes go here...] }
|
当转换 AST 的时候我们可以添加、移动、替代这些结点,也可以根据现有的 AST 生成一个全新的 AST;既然我们编译器的目标是把输入的代码转换为一种新的语言,所以我们将会着重于产生一个针对新语言的全新的 AST。
遍历(Traversal)
为了能处理所有的结点,所以需要遍历它们,使用的是深度优先遍历。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
| { type: 'Program', body: [{ type: 'CallExpression', name: 'add', params: [{ type: 'NumberLiteral', value: '2' }, { type: 'CallExpression', name: 'subtract', params: [{ type: 'NumberLiteral', value: '4' }, { type: 'NumberLiteral', value: '2' }] }] }] }
|
对于上面的 AST 的遍历流程是这样的:
Program
- 从 AST 的顶部结点开始
CallExpression (add)
- Program
的第一个子元素
NumberLiteral (2)
- CallExpression (add)
的第一个子元素
CallExpression (subtract)
- CallExpression (add)
的第二个子元素
NumberLiteral (4)
- CallExpression (subtract)
的第一个子元素
NumberLiteral (2)
- CallExpression (subtract)
的第二个子元素
如果直接在 AST 内部操作,而不是产生一个新的 AST,那么就要在这里介绍所有种类的抽象,但是目前访问(visiting)所有结点的方法已经足够了。使用“访问(visiting)”这个词的是因为这是一种模式,代表在对象结构内对元素进行操作。
访问者(Visitors)
我们最基础的想法是创建一个“访问者(visitor)”对象,这个对象中包含一些方法,可以接收不同的结点。
1 2 3 4
| var visitor = { NumberLiteral() {}, CallExpression() {} };
|
当遍历 AST 的时候,如果遇到了匹配 type 的结点,可以调用 visitor 中的方法。一般情况下为了让这些方法可用性更好,会把父结点也作为参数传入。
代码生成(Code Generation)
编译器的最后一个阶段是代码生成,这个阶段做的事情有时候会和转换(transformation)重叠,但是代码生成最主要的部分还是根据 AST 来输出代码。
代码生成有几种不同的工作方式,有些编译器将会重用之前生成的 token,有些会创建独立的代码表示,以便于线性地输出代码。但是接下来还是着重于使用之前生成好的 AST。
代码生成器需要知道如何“打印”AST 中所有类型的结点,然后它会递归地调用自身,直到所有代码都被打印到一个很长的字符串中。
好了!这就是编译器中所有的部分了。
当然不是说所有的编译器都像我说的这样。不同的编译器有不同的目的,所以也可能需要不同的步骤。
但你现在应该对编译器到底是个什么东西有个大概的认识了,接下来才是重点。
实现
词法分析器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120
| function tokenizer(input) {
let current = 0;
let tokens = [];
while (current < input.length) {
let char = input[current];
if (char === '(') {
tokens.push({ type: 'paren', value: '(' });
current++;
continue; }
if (char === ')') { tokens.push({ type: 'paren', value: ')' }); current++; continue; }
const WHITESPACE = /\s/; if (WHITESPACE.test(char)) { current++; continue; }
const NUMBERS = /[0-9]/; if (NUMBERS.test(char)) {
let value = '';
while (NUMBERS.test(char)) { value += char; char = input[++current]; }
tokens.push({ type: 'number', value: value });
continue; }
const LETTERS = /[a-z]/i; if (LETTERS.test(char)) { let value = '';
while (LETTERS.test(char)) { value += char; char = input[++current]; }
tokens.push({ type: 'name', value: value });
continue; }
throw new TypeError('I dont know what this character is: ' + char); }
return tokens; }
|
语法分析器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112
| function parser(tokens) {
let current = 0;
function walk() {
let token = tokens[current];
if (token.type === 'number') {
current++;
return { type: 'NumberLiteral', value: token.value }; }
if (token.type === 'paren' && token.value === '(') { token = tokens[++current];
var node = { type: 'CallExpression', name: token.value, params: [] };
token = tokens[++current];
while ( (token.type !== 'paren') || (token.type === 'paren' && token.value !== ')') ) { node.params.push(walk()); token = tokens[current]; }
current++;
return node; }
throw new TypeError(token.type); }
const ast = { type: 'Program', body: [] };
while (current < tokens.length) { ast.body.push(walk()); }
return ast; }
|
遍历器
现在有了 AST,还需要一个 visitor 去遍历所有的结点。当遇到某个类型的结点时,需要调用 visitor 中对应类型的处理函数。把访问节点的操作提出来作为 visitor 层,遍历过程中按词法单元类型调用对应的 enter/exit
方法即可,算是个小技巧。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26
| traverse(ast, { Program(node, parent) { enter(node, parent) { }, exit(node, parent) { } }, CallExpression(node, parent) { enter(node, parent) { }, exit(node, parent) { } }, NumberLiteral(node, parent) { enter(node, parent) { }, exit(node, parent) { } } });
|
所以定义一个遍历器,它有两个参数,AST 和 vistor。在它的里面又定义了两个函数…
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53
| function traverser(ast, visitor) { function traverseArray(array, parent) { array.forEach(function(child) { traverseNode(child, parent); }); }
function traverseNode(node, parent) {
let methods = visitor[node.type];
if (methods && methods.enter) { methods.enter(node, parent); }
switch (node.type) {
case 'Program': traverseArray(node.body, node); break;
case 'CallExpression': traverseArray(node.params, node); break;
case 'NumberLiteral': break;
default: throw new TypeError(node.type); } if (methods && methods.exit) { methods.exit(node, parent); } }
traverseNode(ast, null); }
|
转换器
目的:接收之前构建好的 AST,然后把它和 visitor 传递进入遍历器中,最后得到一个新的 AST。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101
|
function transformer(ast) {
const newAst = { type: 'Program', body: [] };
ast._context = newAst.body;
traverser(ast, {
NumberLiteral: { enter (node, parent) { parent._context.push({ type: 'NumberLiteral', value: node.value }); }, }
CallExpression: { enter (node, parent) { let expression = { type: 'CallExpression', callee: { type: 'Identifier', name: node.name }, arguments: [] };
node._context = expression.arguments;
if (parent.type !== 'CallExpression') {
expression = { type: 'ExpressionStatement', expression: expression }; }
parent._context.push(expression); } } });
return newAst; }
|
代码生成器
现在只剩最后一步啦:代码生成器。代码生成器会递归地调用它自己,把 AST 中的每个结点打印到一个很大的字符串中。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| function codeGenerator(node) { switch (node.type) {
case 'Program': return node.body.map(codeGenerator).join('\n');
case 'ExpressionStatement': return ( codeGenerator(node.expression) + ';' );
case 'CallExpression': return ( codeGenerator(node.callee) + '(' + node.arguments.map(codeGenerator) .join(', ') + ')' );
case 'Identifier': return node.name;
case 'NumberLiteral': return node.value;
default: throw new TypeError(node.type); } }
|
编译器
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27
|
function compiler(input) { var tokens = tokenizer(input); var ast = parser(tokens); var newAst = transformer(ast); var output = codeGenerator(newAst);
return output; }
module.exports = { tokenizer: tokenizer, parser: parser, transformer: transformer, codeGenerator: codeGenerator, compiler: compiler };
|
去掉注释完整代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 244 245 246 247 248 249 250 251 252 253 254 255 256 257 258 259 260 261
| function tokenizer(input) { let current = 0; let tokens = [];
while (current < input.length) { let char = input[current]; if (char === '(') { tokens.push({ type: 'paren', value: '(', });
current++; continue; }
if (char === ')') { tokens.push({ type: 'paren', value: ')', }); current++; continue; }
let WHITESPACE = /\s/; if (WHITESPACE.test(char)) { current++; continue; }
let NUMBERS = /[0-9]/; if (NUMBERS.test(char)) { let value = ''; while (NUMBERS.test(char)) { value += char; char = input[++current]; }
tokens.push({ type: 'number', value }); continue; }
if (char === '"') { let value = ''; char = input[++current];
while (char !== '"') { value += char; char = input[++current]; }
char = input[++current]; tokens.push({ type: 'string', value }); continue; } let LETTERS = /[a-z]/i; if (LETTERS.test(char)) { let value = '';
while (LETTERS.test(char)) { value += char; char = input[++current]; }
tokens.push({ type: 'name', value }); continue; }
throw new TypeError('I dont know what this character is: ' + char); }
return tokens; }
function parser(tokens) { let current = 0;
function walk() { let token = tokens[current]; if (token.type === 'number') { current++; return { type: 'NumberLiteral', value: token.value, }; }
if (token.type === 'string') { current++; return { type: 'StringLiteral', value: token.value, }; }
if (token.type === 'paren' &&token.value === '(') { token = tokens[++current]; let node = { type: 'CallExpression', name: token.value, params: [], };
token = tokens[++current];
while ( (token.type !== 'paren') || (token.type === 'paren' && token.value !== ')') ) { node.params.push(walk()); token = tokens[current]; }
current++; return node; }
throw new TypeError(token.type); }
let ast = { type: 'Program', body: [], };
while (current < tokens.length) { ast.body.push(walk()); }
return ast; }
function traverser(ast, visitor) {
function traverseArray(array, parent) { array.forEach(child => { traverseNode(child, parent); }); }
function traverseNode(node, parent) { let methods = visitor[node.type];
if (methods && methods.enter) { methods.enter(node, parent); }
switch (node.type) { case 'Program': traverseArray(node.body, node); break; case 'CallExpression': traverseArray(node.params, node); break; case 'NumberLiteral': case 'StringLiteral': break; default: throw new TypeError(node.type); }
if (methods && methods.exit) { methods.exit(node, parent); } } traverseNode(ast, null); }
function transformer(ast) { let newAst = { type: 'Program', body: [], }; ast._context = newAst.body;
traverser(ast, { NumberLiteral: { enter(node, parent) { parent._context.push({ type: 'NumberLiteral', value: node.value, }); }, }, StringLiteral: { enter(node, parent) { parent._context.push({ type: 'StringLiteral', value: node.value, }); }, }, CallExpression: { enter(node, parent) { let expression = { type: 'CallExpression', callee: { type: 'Identifier', name: node.name, }, arguments: [], }; node._context = expression.arguments; if (parent.type !== 'CallExpression') { expression = { type: 'ExpressionStatement', expression: expression, }; } parent._context.push(expression); }, } }); return newAst; }
function codeGenerator(node) { switch (node.type) { case 'Program': return node.body.map(codeGenerator).join('\n'); case 'ExpressionStatement': return ( codeGenerator(node.expression) + ';' ); case 'CallExpression': return ( codeGenerator(node.callee) + '(' + node.arguments.map(codeGenerator) .join(', ') + ')' ); case 'Identifier': return node.name; case 'NumberLiteral': return node.value; case 'StringLiteral': return '"' + node.value + '"'; default: throw new TypeError(node.type); } }
function compiler(input) { let tokens = tokenizer(input); let ast = parser(tokens); let newAst = transformer(ast); let output = codeGenerator(newAst); return output; }
module.exports = { tokenizer, parser, traverser, transformer, codeGenerator, compiler, };
|
参考: