原作者: James Long,前 Mozilla 工程师,NodeJS, ReactJS 社区活跃开发者。NodeJS 著名模板引擎作者,JavaScript 格式化工具作者。
原文github地址:https://github.com/thejameskyle/the-super-tiny-compiler/blob/master/the-super-tiny-compiler.js
译者: 10xjzheng
译文:
今天我们将一起写一个编译器,但不是真正意义上的编译器,只是一个极简编译器。简单到只要你把说明文字去掉,只剩下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语法,但用来表示编译器的主要过程已经足够了。
绝大多数的编译器的执行过程可以分为三个阶段:分析,转换,代码生成。
1.分析:目的是将最初的代码变成更为抽象的代码;
2.转化:将上一步骤的抽象代码变成编译器能够处理的操作;
3.代码生成:将上一步骤的操作生成另一种新的代码。
分析
分析一般分为两个阶段:词法分析和语法分析。
1.词法分析:将最初的代码用叫做分词器的东西切分成块(token);token,即一个包括一系列微小对象的数组,用来表示语法中的最小单元块,可以是数字,标签,符号,操作等等。
2.语法分析:将词法分析结果(token)重组,变成能够描述token与token直接关系的表示法。这就是所谓的中间表示法,即抽象语法树。
抽象语法树,简称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节点。这些节点都有自己的属性,这些属性描述了所在子树的特征。
我们用下面的节点来表示一个数字:
{
type: 'NumberLiteral',
value: '2',
}
用下面的节点来表示一个调用:
{
type: 'CallExpression',
name: 'subtract',
params: [...嵌套的节点...],
}
当对AST进行转化时,我们可以对节点做包括添加,删除,替换属性等操作,还可以添加新节点,移除节点,或者将已有的AST废弃掉,以旧的AST为基础重新生成一个完整的新AST。
既然我们选择用一种新语言来转化它,我们将专注于重新生成一个新的AST。
遍历(Traversal)
为了能操作所有节点,我们需要对节点进行遍历。遍历的流程是根据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我们的处理流程是:
1.Program-- 从AST的顶层开始;
2.CallExpression (add) -- 然后处理Program的内容,即body部分中的add调用;
3.NumberLiteral (2) -- 接着处理CallExpression的参数;
4.CallExpression (subtract) -- 再处理第二个subtract调用;
5.NumberLiteral (4) -- 处理subtract调用的第一个参数;
6.NumberLiteral (2) -- 处理subtract调用的第二个参数;
如果我们直接操作AST,而不是生成一个分离的AST,我可能会在这里介绍各种抽象。但现在我们只需要能访问各个节点就够了。
我用访问这个词的原因是它正好的描述了我们对对象结构的操作。
访问者(visitiors)
我们创建访问者的对象应该具备能够处理不同类型的节点的方法。
var visitor = {
NumberLiteral(node, parent) {},
CallExpression(node, parent) {},
};
然而,这里依然存在调用'exit'(退出)操作的可能性。想象我们的树结构之前的列表形式:
- Program
- CallExpression
- NumberLiteral
- CallExpression
- NumberLiteral
- NumberLiteral
当往下遍历,我们将到达分支的终点。当我们结束树的每个分支的终点时我们会执行'exit'操作。因此,往下遍历树的时候我们对每个节点执行“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)
为了实现上述操作,我们最终的访问者组成如下:
var visitor = {
NumberLiteral: {
enter(node, parent) {},
exit(node, parent) {},
}
};
代码生成(Code Generation)
编译器是最后阶段是代码生成。这一阶段有时候编译器会做一些和转化重叠的事情,但是大部分代码生成只是处理我们的AST和字符串代码。
代码生成有几种不同的方式,有些编译器会复用之前的tokens,有的会创建一些能独立表示的代码,便于他们能线性地打印出节点,但是由于我更多讲的是用我们创建的AST,因此我们将重点讲这种方式。
我们的代码生成将会知道如何去高效地打印AST所有类型的节点,它将递归地调用自身去打印嵌套的节点,直到所有节点都被打印成一组长长的字符串代码。
这就是编译器的所有不同组成阶段。
这里要阐明并不是所有的编译器都和我描述的一致。根据编译器的不同用途,可能会有更多的步骤。
但到此你应该对大多数编译器是什么样子的有个概念了吧。
现在,我该讲的已经都讲完了,你们这么聪明,应该都可以自己去写编译器了,对吗?
哈哈,只是开个玩笑,我在这里就是为了帮助你们,不等了,现在就开始吧...
/**
* ============================================================================
* (/^^)/
* 分词器
* ============================================================================
*/
/**
* 我们将从编译器的第一阶段词法分析开始,即分词器。
*
* 首先将字符串代码切分成一个token组成的数组
*
* (add 2 (subtract 4 2)) => [{ type: 'paren', value: '(' }, ...]
*/
// 输入一个字符串代码,然后我们要先做两件事:
function tokenizer(input) {
// `current` 变量的作用是指向处理字符串的位置,就像一个指针
let current = 0;
// 用来存放token的数组
let tokens = [];
// 我们将用一个while循环,在循环里面控制current值的增长来遍历处理字符串代码
//用循环的原因的是因为token的长度可以是任意长度的
//
while (current < input.length) {
// 将current作为input的索引
let char = input[current];
// 我们的第一件事就是检查开括号,因为后面调用方法的时候要用来判断,不过这里我们只关注字符
//
// 这里我们先检查是否是开括号字符:
if (char === '(') {
//如果满足条件,我们将把type:`paren`,value:'(' 写入数组tokens
// to an open parenthesis.
tokens.push({
type: 'paren',
value: '(',
});
// 指针 `current`自增
current++;
// 进行下一次循环
continue;
}
// 然后我们检查闭括号,我们将做和之前一样的事情:检查闭括号,加到tokens数组,然后将current自增,continue到下一次循环
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
// 继续前进, 现在我们要匹配空格, 这是有趣的,因为我们比较关心空格是怎么切分字符的,然而空格没必要作为token存储起来,因为它没什么用,所以我们会丢弃它。
// 判断字符是不是空格,不是直接跳过,进入下一次循环
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
// 下面我们检测类型是数字的token,这个和之前的处理不同,因为数字可以是任意多个数字字符的组合,我们的目的是捕获到这个数字序列作为一个token
//
// (add 123 456)
// ^^^ ^^^
// 只有两个独立的token
//
// 先匹配第一个遇到的数字
let NUMBERS = /[0-9]/;
if (NUMBERS.test(char)) {
// 先初始化一个value变量,用来存数字
let value = '';
// 我们将用一个循环来处理数字序列,直到遇到不是数字的字符,将value存到tokens数组,并且使current自增
while (NUMBERS.test(char)) {
value += char;
char = input[++current];
}
tokens.push({ type: 'number', value });
continue;
}
// 我们同样支持被双引号包括的字符串
//
// (concat "foo" "bar")
// ^^^ ^^^ string tokens
//
// 首先匹配开双引号
if (char === '"') {
// 用来存字符串的变量
let value = '';
// 跳过开双引号
char = input[++current];
// 我们将迭代处理每个字符直到遇到另外一个双引号
while (char !== '"') {
value += char;
char = input[++current];
}
// 跳过双引号
char = input[++current];
// 将字符串存储到tokens
tokens.push({ type: 'string', value });
continue;
}
//最后匹配的类型是一个'name'类型,这是一个字母序列,名字是我们的lisp语法的函数名
// (add 2 4)
// ^^^
// Name token
//
let LETTERS = /[a-z]/i;
if (LETTERS.test(char)) {
let value = '';
// 循环将所有字母合成一个value
while (LETTERS.test(char)) {
value += char;
char = input[++current];
}
// 将value存储到tokens
tokens.push({ type: 'name', value });
continue;
}
// 如果有不能识别的字符,我们将抛出异常
throw new TypeError('I dont know what this character is: ' + char);
}
// 最后返回tokens数组
return tokens;
}
/**
* ============================================================================
* ヽ/❀o ل͜ o\ノ
* 语法分析器
* ============================================================================
*/
/**
* 接下来我们将把tokens数组解析成AST(抽象语法树)
*
* [{ type: 'paren', value: '(' }, ...] => { type: 'Program', body: [...] }
*/
// 我们定义一个解析器函数用来处理tokens数组
function parser(tokens) {
// 我们还是用一个current变量作为指针
let current = 0;
// 这次我们用递归代替循环,所以我们定义了walk函数
function walk() {
// 函数内部的第一步,获取当前处理的token
let token = tokens[current];
// 我们将不同类型的token分开
//首先从数字开始
//
// 如果是数字
if (token.type === 'number') {
// `current`自增
current++;
// 返回新的AST节点,类型为NumberLiteral,值为token的值
return {
type: 'NumberLiteral',
value: token.value,
};
}
//如果遇到的是一个字符串,我们将和处理数字一样
// `StringLiteral` node.
if (token.type === 'string') {
current++;
return {
type: 'StringLiteral',
value: token.value,
};
}
//接下来我们匹配调用。处理调用的时候即是当我们遇到开括号的时候
if (
token.type === 'paren' &&
token.value === '('
) {
// 我们将自增current以跳过括号,因为我们不关心它
token = tokens[++current];
// 我们创建一个基本节点,类型为“CallExpression”,我们将把它的名字设置为当前token的值,因为开括号后面的token就是操作的函数名
let node = {
type: 'CallExpression',
name: token.value,
params: [],
};
// 再次自增current,跳过函数名的token
token = tokens[++current];
//现在我们将按顺序遍历每一个token,直到遇到了闭括号为止,闭括号之前的这些token将是最近一次调用操作的参数
// 到此开始进入递归,我们将依靠递归来解决问题,而不是尝试去解析可能掉入无限嵌套的节点集合。
//
// 为了解释它,看下面的lisp代码,我们可以看到add的参数是数字2和嵌套的调用(subtract ),这个调用又有自己的两个参数(4和2)
// (add 2 (subtract 4 2))
//
// 你可能还会注意到在tokens数组中,我们有多个闭括号
// parenthesis.
//
// [
// { 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: ')' }, <<< Closing parenthesis
// { type: 'paren', value: ')' }, <<< Closing parenthesis
// ]
//
// 我们将依赖嵌套的walk函数来增加current变量来遍历所有嵌套的调用
// 因此我们创建while循环,当它遇到开括号或者闭括号的时候会进入循环
//
// 括号
while (
(token.type !== 'paren') ||
(token.type === 'paren' && token.value !== ')')
) {
// 我们将调用walk方法,它会返回一个节点,我们把它放进node.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: [],
};
// 下面我们通过调用walk将节点都存储到ast.body
//这里用循环的原因是我们的程序有嵌套的调用操作
//
// (add 2 2)
// (subtract 4 2)
//
while (current < tokens.length) {
ast.body.push(walk());
}
//最后返回AST.
return ast;
}
/**
* ============================================================================
* ⌒(❀>౪<❀)⌒
* 转盘!!!
* ============================================================================
*/
/**
* 现在AST出来了,我们想用一个访问者来访问所有不同类型的节点,并且访问者有各种方法能够处理各种不同类型的节点
* traverse(ast, {
* Program(node, parent) {
* // ...
* },
*
* CallExpression(node, parent) {
* // ...
* },
*
* NumberLiteral(node, parent) {
* // ...
* },
* });
*/
// 因此我们定义了一个转化器函数,参数是ast和visito,里面我们会再定义两个函数
function traverser(ast, visitor) {
// `traverseArray` 函数的左右是遍历处理数组,里面调用了下面定义的traverseNode函数.
function traverseArray(array, parent) {
array.forEach(child => {
traverseNode(child, parent);
});
}
// `traverseNode` 参数是节点和它的父节点,因此它可以通过我们的访问者函数
function traverseNode(node, parent) {
//我们先检查特定类型的访问者方法是否存在
let methods = visitor[node.type];
// 如果methods的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);
}
// 如果methods存在exit方法,调用它
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
// Finally we kickstart the traverser by calling `traverseNode` with our ast
// with no `parent` because the top level of the AST doesn't have a parent.
traverseNode(ast, null);
}
/**
* ============================================================================
* ⁽(˃̵͈̑ᴗ˂̵͈̑)⁽
* 转化!!!
* ============================================================================
*/
/**
* 下一步,转化器将上一步生成的AST用下面的transformer方法生成一个新的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) {
// 用一个结构和之前的ast相似的变量来存信的ast
let newAst = {
type: 'Program',
body: [],
};
// Next I'm going to cheat a little and create a bit of a hack. We're going to
// use a property named `context` on our parent nodes that we're going to push
// nodes to their parent's `context`. Normally you would have a better
// abstraction than this, but for our purposes this keeps things simple.
//
// Just take note that the context is a reference *from* the old ast *to* the
// new ast.
ast._context = newAst.body;
// 调用traverser 函数,参数是ast和visitor.
traverser(ast, {
// visitor方法可以处理所有 `NumberLiteral`类型
NumberLiteral: {
// 用enter访问它们.
enter(node, parent) {
// 创建一个新的节点,类型也叫 `NumberLiteral` ,把它入栈parent context.
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
// 下一步处理`StringLiteral`类型
StringLiteral: {
enter(node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
// Next up, `CallExpression`.
CallExpression: {
enter(node, parent) {
//创建一个新的节点,类型为`CallExpression` 并且嵌套了一个`Identifier`类型
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.name,
},
arguments: [],
};
//下一步我们定义一个新的context变量用来指向表达式的参数
node._context = expression.arguments;
//如果检测到父节点是否 `CallExpression`类型
// 如果不是
if (parent.type !== 'CallExpression') {
// 我们将用一个表达式声明把调用表达式包起来,这样做的原因是在JS顶层调用表达式是需要声明的
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
// 将 `CallExpression`推入parent._context
parent._context.push(expression);
},
}
});
// transformer函数的最后我们返回刚刚创建的新AST
return newAst;
}
/**
* ============================================================================
* ヾ(〃^∇^)ノ
* 代码生成!!!!
* ============================================================================
*/
/**
* 最后的阶段到来:代码生成
*
*代码生成器将递归的调用自身,打印所有节点,将树变成一个长字符串
*/
function codeGenerator(node) {
// 我们根据节点类型进行处理
switch (node.type) {
// 如果是`Program` 节点. 我们将匹配body里面的所有节点
//并且通过代码生成器用换行符将他们分开
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 如果是`ExpressionStatement`类型,我们将对嵌套操作调用代码生成器并加分号
case 'ExpressionStatement':
return (
codeGenerator(node.expression) +
';' // << (...because we like to code the *correct* way)
);
//如果是 `CallExpression`,我们将用开括号和闭括号把参数包起来,并且参数之间用逗号隔开
case 'CallExpression':
return (
codeGenerator(node.callee) +
'(' +
node.arguments.map(codeGenerator)
.join(', ') +
')'
);
// 如果是`Identifier`类型我们之间返回节点名称
case 'Identifier':
return node.name;
// 如果是`NumberLiteral` 类型直接返回节点值
case 'NumberLiteral':
return node.value;
// 如果是`StringLiteral` 类型,则用双引号将节点值包起来
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 => output
*/
function compiler(input) {
let tokens = tokenizer(input);
let ast = parser(tokens);
let newAst = transformer(ast);
let output = codeGenerator(newAst);
// 输出返回值
return output;
}
/**
* ============================================================================
* (๑˃̵ᴗ˂̵)و
* !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!YOU MADE IT!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
* ============================================================================
*/
// 这里export所有方法
module.exports = {
tokenizer,
parser,
traverser,
transformer,
codeGenerator,
compiler,
};