记录下写的代码,不然感觉久了会忘
原文地址：https://github.com/jamiebuilds/the-super-tiny-compiler
仅用作学习。
今天我们要一起写一个编译器 —— 极简编译器
这个编译器代码量大概仅仅只有200行，但已经能够完整完成一整套编译流程了。
我们将使用「极简编译器」把一些类似 LISP 语法的函数调用编译成一些类似 C 语言的函数调用。
如果你对 LISP 或是 C 不太熟悉也没关系，我们简单介绍一下他们：
如果我们有两个函数 add 和 subtract，在 LISP 和 C 中，它们会写成这样：
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）：
Parsing 将原始代码转化为更抽象的代码表示。
Transformation 基于这种抽象代码表示进行操作，以执行编译器想要它做的任何事情。
Code Generation 基于这种抽象代码表示，将其转换为新代码。
解析通常分为两个阶段：词法分析和句法分析（Lexical Analysis and Syntactic Analysis）。
Lexical Analysis 获取原始代码并通过称为分词器（或词法分析器）的东西将其拆分为一些小的单元，一般称作 token 。tokens 是一组微小的小单元，它们描述了语法的一些独立的部分。它们可以是数字、标签、标点符号、运算符等等。
Syntactic Analysis 分析 tokens ，并将它们重新格式化为描述语法的每个部分及其相互关系的表示。 这被称为中间代码（intermediate representation） 或 抽象语法树（Abstract Syntax Tree），简称 AST，是一个深度嵌套的对象，它以一种易于使用的方式表示代码，同时包含了很多信息。
举个例子：
(add 2 (subtract 4 2))
该语句的 Tokens 应该为以下内容：
[
{ 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',
}]
}]
}]
}
编译器的下一个阶段是转换。同样，这只是从最后一步获取AST并对其进行更改。它可以用同一种语言操纵AST，也可以将其翻译成一种全新的语言。
接下来我们来学习如何转换 AST。
您可能会注意到我们的 AST 中包含看起来非常相似的元素。这些对象都具有 type 属性。这些中的每一个都称为 AST 节点。这些节点上定义了描述树的一个独立部分的属性。
我们有一个类型为 NumberLiteral 的 AST 节点：
{
type: 'NumberLiteral',
value: '2',
}
也有类型为 CallExpression 的 AST 节点：
{
type: 'CallExpression',
name: 'subtract',
params: [...nested nodes go here...],
}
在转换 AST 时，我们可以通过 添加(adding)/删除(removing)/替换(replacing) 属性来操作节点，我们可以添加新节点、删除节点，或者我们可以不理会现有的 AST 并基于它创建一个全新的 AST。
由于我们的目标是一种新语言，因此我们将专注于创建特定于目标语言的全新 AST。
为了浏览所有这些节点，我们需要能够遍历它们。该遍历过程首先到达 AST 深度中的每个节点，即对 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'
}]
}]
}]
}
针对以上 AST，我们的遍历顺序为：
如果我们直接操作这个AST，而不是创建一个单独的AST，我们可能会在这里引入各种抽象。但是仅仅访问树中的每个节点就足够了。
如果我们不另外创建一颗 AST ，而直接对当前 AST 进行操作，我们可能会需要在这里引入各种个样的 abstractions，但是我们要做的仅仅是 “visiting” 当前这个 AST 的每个节点就好，这也是我们极简编译器应该考虑的。
之所以使用 “visiting” 一词，是因为有这样一种模式，即如何表示对象结构元素上的操作。
这里的基本思想是我们将创建一个 “visitor” 对象，该对象具有接受各种以节点类型为名的钩子方法。
var visitor = {
NumberLiteral() {},
CallExpression() {},
};
当我们遍历 AST 时，每当我们 进入 匹配的类型节点时，我们都会调用 visitor 上的方法。
我们将遍历到的节点和其父级节点传入钩子方法，使 visitor 有更多的操作空间。
var visitor = {
NumberLiteral(node, parent) {},
CallExpression(node, parent) {},
};
但是，也存在在 退出 时调用钩子函数的可能性。 想象一下我们之前的列表形式的树结构：
- Program
- CallExpression
- NumberLiteral
- CallExpression
- NumberLiteral
- NumberLiteral
当我们进行深度遍历时，我们将到达有死胡同的分支。 当我们完成树的每个分支时，我们 退出 它。在遍历时，我们遇到一个新的节点，此时我们调用钩子中的enter方法，遍历完该节点时，我们调用exit方法。
-> 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)
为了支持以上能力，我们 visitor 的最终形式将如下所示：
var visitor = {
NumberLiteral: {
enter(node, parent) {},
exit(node, parent) {},
}
};
编译器的最后阶段是代码生成(Code Generation)。 有时编译器会做一些与转换重叠的事情，但在大多数情况下，代码生成只是意味着将我们的 AST 和字符串化代码取出来。
代码生成器有几种不同的工作方式，一些编译器会重用之前的标记，另一些编译器会创建代码的单独表示，以便它们可以线性地打印节点，但据我所知，大多数将使用我们刚刚创建的相同 AST，这就是我们要关注的。
实际上，我们的代码生成器将知道如何“输出” AST 的所有不同节点类型，并且它将递归调用自身以输出嵌套节点，直到将所有内容拼接成一长串代码。
以上就是编译器的所有核心部分。
并不是说每个编译器看起来都和我在这里描述的完全一样。
编译器有许多不同的用途，它们可能需要比我详细说明的更多的步骤。
但是现在您应该对大多数编译器的外观有了大致的了解。
现在我已经解释了所有这些，你们都可以编写自己的编译器了吧？
开个玩笑，我在这里就是帮助你们来完成这一步的 :P
那么让我们开始吧……
/**
* ============================================================================
* (/^▽^)/
* THE TOKENIZER!
* ============================================================================
*/
我们将从 解析 Parsing 的第一阶段开始，词法分析（Lexical Analysis），使用分词器（TOKENIZER）。
需要做的只是将我们的代码字符串分解成一个 token 数组。
即：
(add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
tokenizer实现以及注释：
// tokenizer 接收一个 code string 作为输入，同时需要初始化两个值。
function tokenizer(input) {
/* 用于遍历 code string 的指针，代表了当前遍历的 index */
let current = 0;
/* 用于存储解析出来的 token，为一个数组 */
let tokens = [];
// 使用 while 循环进行遍历
// 当超出 code string 长度时，结束遍历
// 我们在 while 中识别和处理所有的 token
while (current < input.length) {
// 存储当前遍历到的字符
let char = input[current];
// 第一件要做的事情是识别 前括号 ‘(’，这代表一个call expression的开始
if (char === '(') {
// 当 char 确实为 '(' 时，我们将其type设置为 'paren'，并把其值设置为 '('
// 并 push 到 tokens 当中
tokens.push({
type: 'paren',
value: '(',
});
// 将指针 current 自增
current++;
// 跳出循环，因为该token已被收集，下个 char 需要重新完整通过整个流程
continue;
}
// 同样的，我们识别 ')' 并将其 push 进 tokens
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
// 继续处理
// 我们需要 空格 将关键字进行分割，但遗憾的是我们并不需要把 空格 作为一个 token
// 当我们遇到 空格 时，直接跳过
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 下一种类型的标记是数字。
// 这与我们之前做的事情不同，因为数字可以是任意数量的字符。
// 我们希望将整个字符序列进行捕获，并作为一个 token。
//
// (add 123 456)
// ^^^ ^^^
// 只有两个 number token
//
// 当我们遇到第一个数字时，即开始处理
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
// 创建一个 value 用于存储和拼接数字
let value = '';
// 紧接着继续判断下一个字符是否也为数字
// 如果是，则继续向 value 中进行拼接
// 直到遇到其他字符
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
// 当我们捕获完整个 number token 后，将其 push 进 tokens
tokens.push({ type: 'number', value });
// 接着进行遍历
continue;
}
// 针对字符串，我们需要同样的处理，但字符串是以 '"' 为开头的
// 它同样以 '"' 结尾，我们可以基于此进行捕获操作
//
// (concat "foo" "bar")
// ^^^ ^^^ string tokens
//
// 判断是否遇到了 字符串
if (char === '"') {
// Keep a `value` variable for building up our string token.
let value = '';
// 跳过双引号，因为双引号并不包含在字符串当中
char = input[++current];
// 遍历拼接所有字符，直至遇到另一个双引号 '"'
while (char !== '"') {
value += char;
char = input[++current];
}
// 跳过尾部的 双引号
char = input[++current];
// push 字符串 token
tokens.push({ type: 'string', value });
continue;
}
// 最后是捕获所有的关键字，他们为简单的字符拼接
//
// (add 2 4)
// ^^^
// Name token
//
let LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
let value = '';
// 匹配到字符时，开始拼接，直至遭遇非[a-z]的内容
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
// And pushing that value as a token with the type `name` and continuing.
tokens.push({ type: 'name', value });
continue;
}
// 如果遇到无法理解的内容，这里抛出错误
throw new TypeError('I dont know what this character is: ' + char);
}
// 返回 tokens
return tokens;
}
/**
* ============================================================================
* ヽ/❀o ل͜ o\ﾉ
* THE PARSER!!!
* ============================================================================
*/
对于我们的语法分析器，我们将获取我们的 tokens 数组并将其转换为 AST。
[{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
好的，我们定义了一个 parser 函数，它接受我们的 tokens 数组:
function parser(tokens) {
// 我们依旧定义 current ，将它当作指针使用
let current = 0;
// 但是我们现在需要的是使用递归进行处理
// 所以我们把 while 循环改为 walk 函数，以便递归调用
function walk() {
// 在 walk 中，获取到当前的 token
let token = tokens[current];
// 我们将把每种类型的 token 拆分为不同的代码路径，从 number token 开始。
//
// 判断 token 的 type 是否为 number
if (token.type === 'number') {
// 如果是，自增 current 指针
current++;
// 并且返回 NumberLiteral AST 节点
return {
type: 'NumberLiteral',
value: token.value,
};
}
// 针对 string token， 我们作同样处理
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
// 接下来我们查找 CallExpression
// 当我们遇到 '(' 时，我们认为遇到了 CallExpression 的头部
if (
token.type === 'paren' &&
token.value === '('
) {
// 自增 current 指针，此时指针指向 CallExpression 的方法名
token = tokens[++current];
// 我们构造一个 AST 节点对象，将 type 设为 CallExpression
// 将值设为 token.value
// 同时给该 AST 添加 params 属性，用于存储调用参数
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// 再次自增 current 向后遍历
token = tokens[++current];
// 现在我们要遍历后续的每个 token，
// 这些 token 将成为我们 CallExpression 的 params ，直到遇到一个右括号。
//
// 这就是使用递归的好处了。
// 我们将依靠递归来解决问题，
// 而不是试图解析可能无限嵌套的节点集。
//
// 为了解释这一点，让我们以我们的 Lisp 代码为例。
// 您可以看到 add 的参数是一个数字和一个嵌套的 CallExpression
// CallExpression 中又包含它自己的调用参数。
//
// (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: ')' }, <<< 闭括号
// ]
//
// 我们将使用嵌套的 walk 函数的调用来使 current 指针不断增长
// 直至遍历完所有的 CallExpression。
// 所以我们创建一个 while 循环进行遍历
// 直至遇到一个闭括号 ')'
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 我们在这里嵌套调用 walk ，获取其返回的 AST 节点
node.params.push(walk());
token = tokens[current];
}
// 最后，我们自增 current，跳过闭括号 ')'
current++;
// 返回 AST 节点
return node;
}
// 同样的，遇到无法识别的 token， 我们抛出错误
throw new TypeError(token.type);
}
// 现在，我们创建一个名为 Program 的 AST 根节点
let ast = {
type: 'Program',
body: [],
};
// 调用我们的 walk 函数，将节点 push 到 ast.body 数组中。
// 我们在循环中这样做的原因是因为：
// 我们的程序也可能并行编写 CallExpression 而不是嵌套。
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}
// 最后，我们返回 AST
return ast;
}
/**
* ============================================================================
* ⌒(❀>◞౪◟<❀)⌒
* THE TRAVERSER!!!
* ============================================================================
*/
现在我们有了 AST，我们希望能够通过 visitor 访问不同的节点。 我们需要能够在遇到具有匹配类型的节点时调用 visitor 的钩子方法。
traverse(ast, {
Program: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
CallExpression: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
NumberLiteral: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
});
我们定义一个遍历函数，它接受一个 AST 和一个 visitor 。 在里面我们将定义两个函数……
function traverser(ast, visitor) {
// traverseArray 支持遍历 iterator 类型变量
// 对其每一子项调用 traverseNode
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
// traverseNode 接收 node 和 parent 两个参数，以便将其传递进入 visitor 的钩子函数中
function traverseNode(node, parent) {
// 获取当前遍历节点的 visitor 中的钩子
let methods = visitor[node.type];
// 如果钩子存在，并且存在 enter 方法，则调用。
if (methods && methods.enter) {
methods.enter(node, parent);
}
// 接下来分别针对 AST 节点的 type 进行处理
switch (node.type) {
// Program 中包含名为 body 的 AST 数组，我们使用 traverseArray 进行遍历
case 'Program':
traverseArray(node.body, node);
break;
// 针对 CallExpression 节点，我们同样需要使用 traverseArray 遍历其 params 属性
case 'CallExpression':
traverseArray(node.params, node);
break;
// 针对 NumberLiteral 和 StringLiteral ，我们无任何子节点需要继续遍历，直接break
case 'NumberLiteral':
case 'StringLiteral':
break;
// 同样的，遇到无法识别的 AST 节点，抛出错误
default:
throw new TypeError(node.type);
}
// 当遍历完成当前节点后，调用钩子中的 exit 方法
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// 最后，将 ast 作为参数传入， 因为是顶层节点，所以 parent 为 null
traverseNode(ast, null);
}
/**
* ============================================================================
* ⁽(◍˃̵͈̑ᴗ˂̵͈̑)⁽
* THE TRANSFORMER!!!
* ============================================================================
*/
接下来是转换器。 我们的转换器将获取我们已经构建的 AST，并将其与 visitor 一起传递给我们的 traverser 函数，并将创建一个新的 AST。
----------------------------------------------------------------------------
Original AST | Transformed 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'
| }]
(sorry the other one is longer.) | }
| }
| }]
| }
----------------------------------------------------------------------------
我们创建 transformer 函数，它接受 lisp AST 作为参数：
function transformer(ast) {
// 我们将创建一个'newAst'，它与前面的AST一样将有一个 Program 节点。
let newAst = {
type: 'Program',
body: [],
};
// 接下来，我们做一些 hack 操作，在父节点上添加一个 _context属性
// 将节点 push 进 _context 属性中
// 一般来讲，你可能有一个更好的实现，但这里为了达成我们的目的，我们作一些简化操作
// 请注意，_context 是从 旧ast 到 新ast 的引用。
ast._context = newAst.body;
// 我们调用 traverser，同时定义我们的 visitor
traverser(ast, {
// 第一个钩子是 NumberLiteral
NumberLiteral: {
// 我们在 enter 钩子中做一些操作
enter(node, parent) {
// 我们构建出一个基本一致的新 AST 节点 push 进 parent._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) {
// 我们创建一个 expression 节点， 并创造一个 Identifier 子树
// 将 CallExpression 的 name 传入
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};
// 接下来我们在原有 CallExpression 节点上添加 _context 属性
// _context 会指向 expression.arguments
// 以便我们后续将参数传入
node._context = expression.arguments;
// 接下来， 我们需要判断parent是否为 CallExpression， 如果不是的话：
if (parent.type !== 'CallExpression') {
// 我们需要包装我们的 CallExpression 为一个 ExpressionStatement
// 我们这样做是因为 JavaScript 中的顶层 CallExpression 实际上是一个 ExpressionStatement。
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
// 最后，我们将 构建好的 expression 节点 推送值 parent._context中
parent._context.push(expression);
},
}
});
// 最后我们返回刚刚创建的 newAst
return newAst;
}
/**
* ============================================================================
* ヾ（〃＾∇＾）ﾉ♪
* THE CODE GENERATOR!!!!
* ============================================================================
*/
现在让我们进入最后一个阶段：代码生成器(CODE GENERATOR)。
我们的代码生成器将递归调用自身，以将树中的每个节点打印成一个巨大的字符串。
function codeGenerator(node) {
// 我们将按 node 的 type 进行细分。
switch (node.type) {
// 如果是 Program 节点，我们将其 body 中的内容通过map调用codeGenerator
// 并在 body 中的每个节点生成的 code 之间添加换行符
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 对于 ExpressionStatement， 我们对其 expression 调用 codeGenerator 进行代码生成
// 并添加一个分号（严谨）
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';' // << (...because we like to code the *correct* way)
);
// 对于 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 + '"';
// 遇到无法识别的 type 抛出错误
default:
throw new TypeError(node.type);
}
}
/**
* ============================================================================
* (۶* ‘ヮ’)۶”
* !!!!!!!!THE COMPILER!!!!!!!!
* ============================================================================
*/
/**
* 我们终于完成了所有编译器的核心部分，下面是他们预期的调用过程：
*
* 1. input => tokenizer => tokens
* 2. tokens => parser => ast
* 3. ast => transformer => newAst
* 4. newAst => generator => output
*/
function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
// and simply return the output!
return output;
}
/**
* ============================================================================
* (๑˃̵ᴗ˂̵)و
* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!YOU MADE IT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* ============================================================================
*/
// Now I'm just exporting everything...
module.exports = {
tokenizer,
parser,
traverser,
transformer,
codeGenerator,
compiler,
};