共计 13438 个字符，预计需要花费 34 分钟才能阅读完成。
本文是对 the-super-tiny-compiler 仓库的翻译，原文章（代码）：https://github.com/jamiebuild…
明天咱们一起入手写一个编译器，但不是咱们平时所说的编译器，而是一个超级超级小的编译器，小到如果你把本文件的所有正文都删了，真正的代码也就 200 多行。
咱们将把 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))是不是很简略？
很好，这就是咱们要编译的，尽管这并不是一个残缺的 LISP 或C语法，然而这小局部的语法足以向咱们展现一个古代编译器的次要局部。
大多数的编译器都会分成三个次要的阶段：解析（Parsing）、转换（Transformation）以及生成代码（Code Generation）。
1.Parsing会将源代码转换成更形象的代码示意；
2.Transformation会对这个形象的代码示意进行任何它想要的操作；
3.Code Generation会把操作完的代码形象示意生成新代码；
解析（Parsing）
解析通常分为两个阶段：词法剖析和语法分析。
1.词法剖析 会应用一个叫做分词器（tokenizer）的货色来把源代码切割成一个个叫做标记（token）的货色；
tokens是一个数组，外面每项都是用来形容语法中一个独立块的最小对象，它们能够是数字、标签、标点、运算符等等。
2.语法分析 会把标记重新组合，用来形容语法的每个局部，并建设起它们之间的分割，这个别被称作为“形象语法树”。
一个形象语法树（简称为AST），是一个深层嵌套的对象，以一种又简略又能通知咱们大量信息的形式来示意代码。
对于上面的语法：
(add 2 (subtract 4 2))
token列表是上面这样的：
[{ 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: ')' },
]AST是这样的：
{
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',
}]
}]
}]
}转换（Transformation）
编译器的下一个阶段是转换，再强调一次，这个阶段只是把上个阶段生成的 AST 拿来进行一些批改，它能够放弃原来的语言，也能够把它翻译成全新的语言。
让咱们看看如何转换AST。
你可能会留神到咱们 AST 里的元素看起来都十分类似，这些对象都有一个 type 属性，每个节点都被称为 AST 节点，这些节点上都定义了一些属性，用来形容树的一个局部。
咱们能够为 NumberLiteral 创立一个节点：
{
type: 'NumberLiteral',
value: '2',
}或者为 CallExpression 创立一个节点：
{
type: 'CallExpression',
name: 'subtract',
params: [... 嵌套节点...],
}当转换 AST 的时候，咱们能够通过这些形式来操作节点：增加 、 移除 、 替换 属性，咱们能够增加新节点，或者咱们能够不论现有的AST，间接在它的根底上创立一个新的AST。
因为咱们的指标是一个新语言，所以咱们将基于目标语言创立一个全新的AST。
遍历（Traversal）
为了在所有节点中穿梭，咱们须要可能遍历它们，这个遍历的过程会以深度优先的形式达到每个节点。
{
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，咱们将顺次拜访：
1.Program – 从
AST的顶层开始2.CallExpression (add) – 挪动到 Program 的 body 列表的第一个元素
3.NumberLiteral (2) – 挪动到 CallExpression 的 params 列表的第一个元素
4.CallExpression (subtract) – 挪动到 CallExpression 的 params 列表的第二个元素
5.NumberLiteral (4) – 挪动到 CallExpression (subtract)的 params 列表的第一个元素
6.NumberLiteral (2) – 挪动到 CallExpression (subtract)的 params 列表的第二个元素
如果咱们间接操作这个AST，而不是从新创立一个，咱们可能会在这里引入各种抽象概念。但其实间接拜访（visiting）树的每个节点就够咱们应用了。
我之所以应用“拜访”（visiting）这个词，是因为这里存在这样一种模式，即如何示意对对象构造上的元素的操作。
访问者（Visitors）
基本思路是创立一个 visitor 拜访器对象，提供一些承受不同节点类型的办法。
var visitor = {NumberLiteral() {},
CallExpression() {},
};当咱们遍历AST，每当遇到一个匹配的节点时，咱们会调用这个拜访器上对应节点类型的办法。
为了能让这些办法更有用，咱们会传入两个参数，以后遍历到的节点，以及它的父节点。
var visitor = {NumberLiteral(node, parent) {},
CallExpression(node, parent) {},};然而，当退出时也存在须要拜访的可能性，设想一下咱们之前列表模式的树结构：
- Program
- CallExpression
- NumberLiteral
- CallExpression
- NumberLiteral
- NumberLiteral当咱们向下遍历时，很容易在一个分支上走到头，当咱们遍历完某个分支了咱们就会退出它，所以往下走的时候咱们会“进入”每个节点，往上走时会“退出”节点。
-> Program (enter)
-> CallExpression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Call Expression (enter)
-> Number Literal (enter)
<- Number Literal (exit)
-> Number Literal (enter)
<- Number Literal (exit)
<- CallExpression (exit)
<- CallExpression (exit)
<- Program (exit)为了反对这种状况，最终的拜访器是这样的：
var visitor = {
NumberLiteral: {enter(node, parent) {},
exit(node, parent) {},}
};生成代码（Code Generation）
编译器的最初一个阶段是生成代码，有时编译器会做一些和转换重合的事件，但大多数状况下，生成代码只是意味着把 AST 转换回代码字符串。
代码生成器有几种不同的工作形式，一些编译器会重用之前的token，其余的会创立一个独立的代码示意，这样就能够线性的打印节点，但据我所知，大多数的都会间接应用咱们刚刚创立的AST，咱们也会这么干。
实际上咱们的代码生成器晓得如何去打印 AST 上所有不同类型的节点，它会递归调用本人去打印所有嵌套节点，直到所有内容都被打印到一个长长的代码字符串中。
小结一下
下面就是咱们要做的编译器，它蕴含了一个真正编译器的所有局部。
但这并不意味着所有编译器都和我下面形容的一样，每个编译器可能都有不同的用处，所以它们除了我下面提到的内容外，可能它们还会有更多的步骤。
然而你当初应该会对大多数编译器有一个总体的根本的意识。
既然我曾经把编译器的内容都介绍完了，当初你是否能本人写一个编译器了呢？
开个玩笑了，上面让我来帮你一起实现它。
开始吧。。。
代码实现
分词器
咱们将从解析的第一个阶段开始，应用分词器进行词法剖析。
咱们要做的只是把代码字符串分解成一个 token 数组：
(add 2 (subtract 4 2)) => [{type: 'paren', value: '('}, ...]函数接管一个代码字符串为入参，咱们要做两件事：
function tokenizer(input) {
// `current` 变量就像一个游标，跟踪咱们在代码中以后的地位
let current = 0;
// `tokens` 数组用来寄存生成的 token
let tokens = [];
// 咱们从创立一个 while 循环开始，在循环中会依照咱们想要的递增量来更新 current
// 这样做是因为可能一个循环里会屡次更新 current，因为一个 token 的长度是任意的
while (current < input.length) {
// 以后地位的字符
let char = input[current];
// 首先要查看的是左括号 `（`，前面会用于 `CallExpression`，然而当初咱们只关怀字符
// 查看是否是左括号：if (char === '(') {
// 如果匹配到了，增加一个类型为 `paren` 的 token，设置它的值为 `(`
tokens.push({
type: 'paren',
value: '(',});
// 递增 `current`
current++;
// 跳过以后循环，进入下一个循环
continue;
}
// 接下来查看是否是右括号 `)`，和方才一样：匹配到右括号，增加一个新的 token，递增 current，最初跳过以后循环进入下一个循环
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
// 持续，接下来咱们要查看的是空白符，空白符是用来分隔字符的，但它实际上并不重要，所以不会把它当做一个 token 进行增加
// 所以这里咱们仅仅查看是否匹配到了空白符，匹配到了就跳过
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 下一个 token 类型是 number，这和之前的几种不一样，因为数字可能有任意长度，咱们须要把数字整体作为一个 token 进行增加
//
// (add 123 456)
// ^^^ ^^^
// 尽管有六个字符，然而只算两个独自的 token
//
// 当遇到序列中的第一个数字时，咱们就开始了...
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
// 创立一个 value 变量，用来保留整个数字
let value = '';
// 接下来遍历这之后的每一个字符，直到遇到非数字字符
while (NUMBERS.test(char)) {
// 拼接以后数字
value += char;
// 更新 current，挪动到下一个字符
char = input[++current];
}
// 之后咱们增加一个 number 类型的 token
tokens.push({type: 'number', value});
// 持续
continue;
}
// 咱们也要减少对字符串的反对，即任何被双引号包裹起来的字符（"）//
// (concat "foo" "bar")
// ^^^ ^^^ 字符串类型的 token
//
// 咱们先检查一下结尾的引号（"）：if (char === '"') {
// 创立一个 value 变量用来保留 token 的值
let value = '';
// 跳过结尾的双引号
char = input[++current];
// 遍历之后的每一个字符，直到遇到结尾的双引号
while (char !== '"') {
// 更新 value
value += char;
// 移到下一个字符
char = input[++current];
}
// 跳过结尾的双引号
char = input[++current];
// 增加一个 string 类型的 token
tokens.push({type: 'string', value});
continue;
}
// 还剩最初一种 `name` 类型的 token，这是一个字母模式的字符，不是数字，作为咱们的 lisp 语法里的函数名
//
// (add 2 4)
// ^^^
// Name token
//
let LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
let value = '';
// 同样的，还是循环遍历之后的所有字符
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
// 增加一个 `name` 类型的 token，而后持续到下一个循环
tokens.push({type: 'name', value});
continue;
}
// 最初，如果到这里还有咱们没有匹配到的字符，那就相当于语法有误，咱们搞不定了，那么就间接抛错而后停止循环
throw new TypeError('I dont know what this character is:' + char);
}
// 最初的最初，咱们的分词器只有返回 token 列表就能够了
return tokens;
}解析器
对于解析器来说，要做的是把 token 列表转换成AST：
[{type: 'paren', value: '('}, ...] => {type: 'Program', body: [...] }定义一个 parser 函数，接管 token 列表作为参数：
function parser(tokens) {
// 同样的，咱们保护一个 `current` 变量作为游标
let current = 0;
// 然而这里咱们将应用递归，而不是 while 循环，定义一个递归函数
function walk() {
// 先获取并保留以后地位的 token
let token = tokens[current];
// 咱们将把每种类型的 token 分成不同的代码门路，从 `number` 类型的 token 开始
//
// 判断是否是一个 `number` 类型的 token
if (token.type === 'number') {
// 如果是的话，先递增一下 current
current++;
// 返回一个新的 AST 节点，类型是 `NumberLiteral`，它的 value 就是 token 的 value
return {
type: 'NumberLiteral',
value: token.value,
};
}
// `string` 类型和 `number` 类型一样，创立一个 `StringLiteral` 类型的节点并返回
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
// 接下来，咱们要找的是 `CallExpressions`，这从咱们遇到左括号开始
if (
token.type === 'paren' &&
token.value === '(') {
// 递增 current，跳过左括号，因为它在 AST 里不须要
token = tokens[++current];
// 创立一个根底的 `CallExpression` 节点，而后把值设置为以后 token 的 value，因为左括号的左边紧接着就是函数名
let node = {
type: 'CallExpression',
name: token.value,
params: [],};
// 递增 current 跳过函数名 token
token = tokens[++current];
// 接下来遍历前面的节点作为调用表达式 `CallExpression` 的参数 `params`，直到遇到右括号
//
// 这就是递归的用途，咱们将依赖递归来解析一组可能有限嵌套的节点
//
// 为了解释这一点，让咱们再看看 Lisp 代码，你能够看到 `add` 办法有一个数字参数和一个嵌套的 `CallExpression`，同样它又存在两个数字参数：//
// (add 2 (subtract 4 2))
//
// 你也会留神到 token 列表中存在多个右括号：//
// [// { 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: ')' }, <<< 右括号
// ]
//
// 咱们将依赖嵌套的 `walk` 函数来递增 `current`，直到所有的 `CallExpression` 之后
// 因而咱们创立一个 `while` 循环，递归调用 `walk`，直到遇到右括号
// 译者注：这里其实就是考查递归思维，如果一个工作能够拆解成更小的子工作，且子工作和大工作的逻辑是一样的就能够应用递归，对于这里来说，add 函数的参数的类型是任意的，能够是数字，能够是字符串，也能够是另外一个函数，另一个函数又会遇到和 add 函数一样的问题，所以间接交给递归函数执行，对于 add 来说，你只有返回 AST 节点就能够了。while ((token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 调用递归函数，它将返回一个 AST 节点，增加到以后的 `params` 列表里
node.params.push(walk());
token = tokens[current];
}
// 递增 current，用来跳过右括号
current++;
// 返回节点
return node;
}
// 同样的，如果遇到咱们无奈辨认的 token 就抛错
throw new TypeError(token.type);
}
// 创立一个 `AST` 的根节点 `Program`
let ast = {
type: 'Program',
body: [],};
// 接下来开启一个循环，来增加节点到 `ast.body` 数组里
// 这里应用循环是因为可能有多个并列的 `CallExpression`
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {ast.body.push(walk());
}
// 最初返回 ast 即可
return ast;
}遍历
到这里咱们曾经有 AST 了，咱们想能通过拜访器来拜访不同类型的节点。咱们须要可能在遇到匹配类型的节点时调用拜访器上的办法。
traverse(ast, {
Program: {enter(node, parent) {// ...},
exit(node, parent) {// ...},
},
CallExpression: {enter(node, parent) {// ...},
exit(node, parent) {// ...},
},
NumberLiteral: {enter(node, parent) {// ...},
exit(node, parent) {// ...},
},
});所以咱们定义一个 traverser 函数，接管一个 AST 和一个拜访器，外部还会再定义两个函数 …
function traverser(ast, visitor) {
// `traverseArray` 函数用来遍历数组，外面会调用上面定义的 `traverseNode` 函数
function traverseArray(array, parent) {
array.forEach(child => {traverseNode(child, parent);
});
}
// `traverseNode` 接管一个 `node` 和它的父节点
function traverseNode(node, parent) {
// 首先确认匹配到的 `type` 是否在拜访器里有对应办法
let methods = visitor[node.type];
// 如果存在 `enter` 办法，那么就调用它，传入以后节点和父节点
if (methods && methods.enter) {methods.enter(node, parent);
}
// 接下来依据类型类型来别离解决
switch (node.type) {
// 从顶层节点 `Program` 开始，因为 Program 节点的属性 `body` 是数组类型，所以调用 `traverseArray` 办法来遍历
// (记住 `traverseArray` 办法外部会顺次调用 `traverseNode`，所以会递归遍历树)
case 'Program':
traverseArray(node.body, node);
break;
// `CallExpression` 类型也是一样的，只不过遍历的是它的 `params` 属性
case 'CallExpression':
traverseArray(node.params, node);
break;
// `NumberLiteral` 和 `StringLiteral` 类型的节点没有子节点，所以间接跳过
case 'NumberLiteral':
case 'StringLiteral':
break;
// 还是同样的，如果呈现了咱们无奈辨认的节点就抛错
default:
throw new TypeError(node.type);
}
// 如果存在 `exit` 办法，在这里调用，传入 `node` 和它的 `parent`
if (methods && methods.exit) {methods.exit(node, parent);
}
}
// 最初咱们调用 `traverseNode` 来开启遍历，传入 ast，因为顶层节点没有 `parent`，所以传 null
traverseNode(ast, null);
}译者注：这个办法其实就是树的深度优先遍历，而后在前序遍历的地位调用拜访器的 enter 办法，在后序遍历地位调用拜访器的 exit 办法。
转换
接下来，转换器（transformer），它会把咱们构建的 AST，再加上一个拜访器visitor，一起传给traverser 函数，而后返回一个新的AST。
----------------------------------------------------------------------------
原 AST | 转换后的 AST
----------------------------------------------------------------------------
{ | {
type: 'Program', | type: 'Program',
body: [{ | body: [{
type: 'CallExpression', | type: 'ExpressionStatement',
name: 'add', | expression: {
params: [{ | type: 'CallExpression',
type: 'NumberLiteral', | callee: {value: '2' | type: 'Identifier',}, { | name: 'add'
type: 'CallExpression', | },
name: 'subtract', | arguments: [{
params: [{ | type: 'NumberLiteral',
type: 'NumberLiteral', | value: '2'
value: '4' | }, { }, { | type: 'CallExpression',
type: 'NumberLiteral', | callee: {value: '2' | type: 'Identifier',}] | name: 'subtract'
}] | },
}] | arguments: [{ } | type: 'NumberLiteral',
| value: '4'
---------------------------------- | }, {
| type: 'NumberLiteral',
| value: '2'
| }]
(不好意思，左边的比拟长) | }
| }
| }]
| }
----------------------------------------------------------------------------所以咱们的 transformer 函数会承受一个 lisp 的AST作为参数：
（译者注：要了解上面这个函数，还是先要搞清楚从旧的到新的都做了哪些转换，回到下面的比照，能够看到 CallExpression 节点的 type 没变，然而把 name 属性批改成了 callee，另外参数列表由params 变成了 arguments，最初如果CallExpression 节点的父节点不是 CallExpression 节点的话那么会创立一个 ExpressionStatement 节点来包裹，所以转换过程是这样的，咱们首先创立一个新的 AST 根节点，然而咱们遍历的是旧的 AST，所以怎么能在新的AST 上增加节点呢，能够通过在旧的 AST 节点上创立一个属性来援用新的 AST 上的列表属性，这样就能够在遍历旧的树时往新的树的列表里增加节点。）
function transformer(ast) {
// 新 AST，和之前的 AST 一样，也要有一个 Program 节点
let newAst = {
type: 'Program',
body: [],};
// 接下来我要做一个小改变，在父节点上增加一个 `context` 属性，而后会把每个节点都增加到它们父节点的 `context` 里，通常状况下你会有一个更好的形象，然而为了咱们的目标，这样做更简略
//
// 须要留神的是旧的 AST 里的 context 属性只是新 AST 属性的一个援用
ast._context = newAst.body;
// 接下来调用 traverser 办法，传入 AST 和一个拜访器对象
traverser(ast, {
// 第一个访问者接管 `NumberLiteral` 类型的节点
NumberLiteral: {
// 进入时
enter(node, parent) {
// 创立一个新的 `NumberLiteral` 节点，增加到父节点的 context 里
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
// 接下来是 `StringLiteral`
StringLiteral: {enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
// 而后是 `CallExpression`
CallExpression: {enter(node, parent) {
// 创立一个新节点 `CallExpression`，外面嵌套一个 `Identifier` 节点
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],};
// 接下来咱们给原 `CallExpression` 节点定义一个新的 context 属性，援用咱们方才新创建的节点的 arguments 属性，这样在遍历旧节点的参数时就能够给新的节点增加参数了
node._context = expression.arguments;
// 接下来检查一下父节点是否是 `CallExpression` 节点
// 如果不是的话...
if (parent.type !== 'CallExpression') {
// 创立一点 `ExpressionStatement` 节点来包裹 `CallExpression` 节点，这样做是因为顶层的 `CallExpression` 在 JavaScript 里实际上是语句
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
// 最初，把(可能是被包裹的) `CallExpression` 节点增加到父节点的 `context` 里
parent._context.push(expression);
},
}
});
// 函数的最初返回新创建的 AST
return newAst;
}生成代码
当初让咱们来看最初一个阶段：生成代码。
咱们的代码生成器会递归的调用本人，把树中的每个节点都打印到一个微小的字符里。
function codeGenerator(node) {
// 咱们将按节点类型进行别离解决
switch (node.type) {
// 如果是 `Program` 节点，那就遍历它的 `body` 列表，对每个节点调用 codeGenerator 办法，而后把它们用换行符拼接起来
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 对于 `ExpressionStatement` 节点，对它的 expression 节点调用对每个节点调用 codeGenerator 办法办法，而后再增加一个分号...
case 'ExpressionStatement':
return (codeGenerator(node.expression) +
';' // << (... 在一个语句的开端增加分号是符合标准的)
);
// 对于 `CallExpression` 节点，咱们要打印的是 `callee`，而后拼接一个左括号，而后遍历参数 `arguments` 的每个节点，调用 codeGenerator 办法把它们转成字符串，而后用逗号拼接起来，最初再增加一个右括号
case 'CallExpression':
return (codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(',') +
')'
);
// 对于 `Identifier` 节点，只有返回 name 属性的值即可
case 'Identifier':
return node.name;
// 对于 `NumberLiteral` 节点，返回它的 value 属性值
case 'NumberLiteral':
return node.value;
// 对于 `StringLiteral` 节点，须要应用双引号来包裹它的 value 值
case 'StringLiteral':
return '"'+ node.value +'"';
// 如果遇到无奈辨认的节点，那么抛错
default:
throw new TypeError(node.type);
}
}最终的编译器~
最初让咱们来创立一个 compiler 函数，在这个函数里把下面的所有流程串起来：
1. input => tokenizer => tokens
2. tokens => parser => ast
3. ast => transformer => newAst
4. newAst => generator => outputfunction compiler(input) {let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
// 把代码生成后果返回就 ok 了
return output;
}
功败垂成
当初，让咱们把下面所有的函数导出：
module.exports = {
tokenizer,
parser,
traverser,
transformer,
codeGenerator,
compiler,
};总结
正文太多可能影响浏览代码，能够点此浏览纯享版 https://github.com/wanglin2/the-super-tiny-compiler/blob/master/the-super-tiny-compiler.js。
本文由博客一文多发平台 OpenWrite 公布！