各位JSer大家好，今天我想和大家聊聊我最感兴趣的话题之一：什么是抽象语法树，以及通过它我们能做些什么。我们会通过编写几个简单的demo来了解抽象语法树。
你可以在这里下载到可运行的实例代码，以便了解一下我们今天将覆盖的几个demo。
名词解释
首先让我们来了解一下以下名词：抽象语法树、词法分析、语法分析。
抽象语法树
抽象语法树（Abstract Syntax Tree，AST。后文将统一使用AST来称呼）指的是源代码的抽象语法结构的树状表现形式，树上的每个节点都表示源代码中的一种结构。
例如对于if-else结构的代码可能会以一个带有3个子节点（判断条件，判断为真时的逻辑，判断为假时的逻辑）所组成的节点，而while结构的代码则可能包含两个子节点（判断条件，循环体的逻辑）。
代码从源码转换为抽象语法树将经历两个重要的过程：词法分析与语法分析。
词法分析
词法分析，或简称为分词（tokenize）指的是将源码的字符序列转换为单词（token）序列的过程。完成这一工作的工具被称为词法分析器（lexer，或tokenizer）。
例如对于a = b + 1这段代码，在词法分析后将得到[a, =, b, +, 1]这五个单词（或在最后再包含一个EOF标识）。每个单词可能会包含如下信息：
- 单词的原文，例如'a'，'='，'1'
- 单词在源代码中的位置，例如
b的位置是从5至6 - 单词的类型，例如
a是一个标识符，它表示的是一个变量名，而=和+是操作符，1则是一个字面量。
语法分析
通过词法分析，我们获得了链状的单词序列，之后语法分析器（Parser）会根据语法规则将单词序列转化为树状的AST。我们通常会使用巴科斯范式（Backus-Naur Form，BNF）来描述我们的语法。
在语法分析的过程中，我们还可以通过一些优化规则，对语法树的结构做出一些改动，使得编译器（compiler）/解释器（interpreter）在执行代码时更加高效。
工具
今天我们将依赖于acorn.js提供的解析功能，它能将JS代码解析为AST。
也许有些小伙伴还不知道acorn.js是什么，但很可能你已经接触过并正在使用它，因为很多工具都依赖于它：例如webpack、uglify-es、eslint等等。
我们今天并不会深入探索它的工作原理（我们将在以后的文章中对语法分析的原理进行探索），因此只需要通过文档了解一下它所提供的API就可以了。
源代码
接下来，我们将围绕以下代码通过acorn.js生成的语法树编写我们的代码：
var sum = 0;
var count = 1;
var result;
while (count <= 10) {
sum = sum + count;
count = count + 1;
}
if (count < 10) {
result = false;
} else {
result = true;
}
展示单词序列
首先我们从一个简单的任务开始。
acorn.js提供了词法分析器（tokenizer），通过它，我们可以逐一获取单词直至eof：
const getTokenList = function getTokenList(code) {
const tokens = acorn.tokenizer(code);
const arr = [];
let token = tokens.getToken();
while(token.type.label !== 'eof') {
arr.push(token);
token = tokens.getToken();
}
return arr;
};
由此，我们可以进行单词序列的展示：
每个单词都会包含以下信息：start与end标识了单词在源代码中的位置，label表示单词类型，value则是单词的值。
例如var sum = 0;中的0，位置是10至11，类型为num，值为0。
我们可以注意到，在单词序列中，换行和空格都被去除了，但是;是保留的。
展示语法树
同样acorn.js提供了语法分析（parse）：
const tree = acorn.parse(code);
于是我们可以对acorn.js生成的AST进行可视化展示：
我们可以看到，每个节点也包含了节点类型、起始位置、子节点等信息。不同类型的节点将会拥有不同数量、名称的子节点。而类似Identifier和Literal节点将不会包含子节点，但将包含指明其标识符的name或其值的raw信息。
代码高亮
在单词序列或是AST的基础上，我们可以对语法进行代码高亮展示。
demo中展示了如何使用词法分析的结果来高亮展示代码。
我们需要做的是，借助单词序列，替换源代码，例如将：
var sum = 0;
替换为：
<span class="token-var">var</span> sum <span class="token-assign">=</span> 0;
单词序列提供了单词的起始位置，因此我们可以很方便的完成这一替换。这里的小技巧在于，如果你顺序进行替换，那么你需要累计记录每次替换后产生的便宜，或者你可以从尾部开始替换，或是像我一样，从单词序列出发进行组装，当发现相邻的单词并没有头尾相接时，我将从原文中取出它们之间的内容（空格和换行）并塞回它们中间。
如果我们使用语法分析得到的结果，将可以提供更多有趣的功能，例如允许代码块（Block，例如if和while的代码块）的折叠，或是变量、函数、类的声明的跳转等等。
代码压缩
接下来的任务是压缩代码。
基于单词序列
首先我们将基于单词序列进行压缩，由于我们单词序列中已经不包含空格和换行，我们只需要将单词序列中每个单词的value连接起来就行了。不过我们要注意一些特例，例如在var sum之间的空格我们仍然需要重新补上才行：
var a=0;var b=1;var c;while(b<=10){a=a+b;b=b+1;}if(b<10){c=false;}else{c=true;}
这里我们还进行了一项小工作：对于变量名，我们将建立一个对应表按照它们首次出现的顺序将它们对应为a, b, c..., a0, b0, ...。不过这里我们并不会考虑嵌套作用域的情况，例如：
var sum = 0;
...
var count = 1;
var func = () => {
var count = 0;
...
}
可能将被转化为：
var a = 0;
...
var b2 = 1;
var b3 = () => {
var b2 = 0;
...
}
然而事实上两个count并不在同一个作用域下，因此我们应当使用一张全新的对应表：
var b3 = () => {
var a = 0;
...
}
仅仅在单词序列的基础上我们无法提供不同的作用域，在提供了AST信息的基础上我们可以对此进行处理（不过demo中我也跳过了这一点）。
基于AST
以上的压缩代码还有不少可以进一步提高的空间。例如;并非总是必须的，例如对于一个块中的最后一句代码：
while(b<=10){a=a+b;b=b+1;}
可以表示为：
while(b<=10){a=a+b;b=b+1}
同级下的变量声明也可以合并：
var a=0,b=1,c;
这里我们就需要利用到AST所提供的信息。
在./walker/index.js中我们提供了defaultPs，这是遍历语法树的一个例子。defaultPs什么都没做，不过我们可以通过修改它来完成各种功能：
const defaultPs = {
Program(node, env) {
let item;
for (item of node.body) {
defaultPs.process(item, env);
}
},
BlockStatement(node, env) {
let item;
for (item of node.body) {
defaultPs.process(item, env);
}
},
...
process(node, env) {
const p = defaultPs[node.type];
if (!p) {
console.error('未处理的类型', node.type, node);
return;
}
return p(node, env);
},
};
defaultPs会遍历语法树，根据每个节点的类型做出不同的反应。node是当前处理的节点，env用来放置一些全局的数据，demo中的实例代码非常简单，因此我们只覆盖了一部分节点类型的处理，例如BlockStatement，VariableDeclaration，Identifier，WhileStatement等等。
这里我们遍历节点并拼接字符串：
const joinCode = function joinCode(list) {
return list.filter(x => x != null).join(';');
};
const ps = {
...
BlockStatement(node, env) {
const result = [];
let item;
result.push(preProcessVars(node, env));
for (item of node.body) {
result.push(ps.process(item, env));
}
return joinCode(result);
},
...
};
这里我们再列举几个典型的节点的处理：
Identifier(node, env) {
return env.nextName.getName(node.name);
},
Literal(node, env) {
// 压缩true和false
if (node.raw === 'true') return '!0';
if (node.raw === 'false') return '!1';
return node.raw;
},
WhileStatement(node, env) {
const test = ps.process(node.test, env);
const body = ps.process(node.body, env);
return `while(${test}){${body}}`;
},
IfStatement(node, env) {
const test = ps.process(node.test, env);
const consequent = ps.process(node.consequent, env);
let str = `if(${test}){${consequent}}`;
const alternate = ps.process(node.alternate, env)
if (node.alternate) str += `else{${alternate}}`;
return str;
},
BinaryExpression(node, env) {
return ps.process(node.left, env) + node.operator + ps.process(node.right, env);
},
例如IfStatement是将相应节点的代码用if、else等等连接起来。而它的这些子节点则会被递归的处理。
与此前相比，由于我们获得了树状的结构，因此我们可以优先遍历一颗树下的所有变量声明节点，并将它们一起提到头部，同时我们可以知晓一句代码是否是一个块中的最后一句，从而省略其后的;。
demo中生成了如下代码：
var a=0,b=1,c;while(b<=10){a=a+b;b=b+1};if(b<10){c=!1}else{c=!0}
这里我们又加入了一个小技巧：用!0代替true同时用!1代替false。结果看起来还不错，但还有可以提高的地方，例如while和if之间的;可以省略，如果你打算做这样的尝试，注意区分：
var a = {};if (...) ...
以及：
while (...) { ... }if (...) ...
之间的区别。你需要搞清楚前一个节点的}来自与一个块还是其它什么例如对象字面量，来决定是否两个节点之间不需要;相连。
在demo中我们将变量声明统一提到了代码块的头部。作为JSer我想你一定听说过变量提升，或许你也听说过Java中的指令重排，或是SQL的优化引擎，这些都是编译器等等在执行代码之前可能会对代码的抽象结构做出改动以实现优化的例子。
现在的代码压缩工具，还会进行更多的静态分析以进一步压缩代码，例如tree-shaking。
const a = () => {};
const b = () => {};
export {
a,
};
例如对于以上的这个模块，b即没有被导出，也没有在模块内被使用，因此处理后的代码会完全丢弃这一块。
又例如：
const a = () => {
const a = 3;
const b= 1;
return a + b;
};
会被一些工具直接优化为类似如下的代码：
const a = () => 4;
文档生成
这个例子是关于自动生成文档。
我们将使用的示例代码如下：
class Photo extends MediaContent {
/**
* @owner: User
*/
constructor(owner) {
this.owner = owner;
}
/**
* @return: Array | 照片数组
*/
list() {}
/**
* @hash: String | 从七牛返回的hash
* @return: Int | 新照片的id
*/
create(hash) {}
delete(id, useSoftDelete) {}
}
class Video extends MediaContent {
constructor(owner) {
this.owner = owner;
}
/**
* @return: Array | 视频数组
*/
list() {}
/**
* @url: String | 视频的url
* @return: Int | 新视频的id
*/
create(url) {}
/**
* @id: Int
* @useSoftDelete: Boolean
*/
delete(id, useSoftDelete) {}
}
当我们遍历生成的AST，我们将会看到两个ClassDeclaration节点，每一个ClassDeclaration节点将包含类名、父类名称（若存在）等信息，并拥有数个MethodDefinition节点，而MethodDefinition节点会包含params列表。
不过这些信息对于生成文档来说还显得有些单薄。我们希望展示更多信息，例如参数的类型和说明文字、返回值的说明等等。要从Javascript代码中获取这些信息并不容易，所以我们决定借助于注释。
我们需要处理的问题在于，acorn.js生成的语法树并不包含注释节点，我们只能通过onComment将注释节点都收集到一个独立的数组中，然后根据注释节点和方法节点的位置信息（start和end）来猜测注释所属的方法。
至于注释内容的处理，可以使用正则表达式或其它任何合适的方法。
除此之外，我们还能为类和方法提供查看源码的功能。
编译
当我们获得了AST，我们可以重组源码，可以转换为压缩代码，当然也可以转化为其它语言的代码，例如Python代码：
sum = 0
count = 1
result = None
while count <= 10:
sum = sum + count
count = count + 1
if count < 10:
result = False
else:
result = True
对于demo中的代码，处理起来也比较简单。这里需要注意的点在于缩进的处理，我们需要为生成的Python代码保留正确的缩进。
这里我们将改写joinCode方法来补上空格。
const prependSpace = function prependSpace(level) {
let str = '';
for (let i = 0; i < level; i++) {
str += ' ';
}
return str;
};
const joinCode = function joinCode(list, level = 0) {
const space = prependSpace(level);
return list.filter(x => x != null).map(x => space + x).join('\n');
};
我们还是来看一些典型的节点：
WhileStatement(node, env) {
const test = ps.process(node.test, env);
const body = ps.process(node.body, env);
return `while ${test}:\n${body}`;
},
IfStatement(node, env) {
const test = ps.process(node.test, env);
const consequent = ps.process(node.consequent, env);
let str = `if ${test}:\n${consequent}`;
const alternate = ps.process(node.alternate, env)
if (node.alternate) str += `\nelse:\n${alternate}`;
return str;
},
BinaryExpression(node, env) {
return `${ps.process(node.left, env)} ${node.operator} ${ps.process(node.right, env)}`;
},
这里的技巧在于维护正确的缩进层次。在什么情况下缩进层级会改变呢？在代码进入和退出一个新的BlockStatement时。因此我们只需要在这里维护层级就可以了。
事实上我们也可以在进入和退出BlockStatement时往维护变量名作用域，推入新的变量名对应表或是弹出栈顶的作用域，同时在获取和设置变量时需要自顶向下遍历多个对应表（不过需要注意的是不同于const和let，var并非是块级作用域的）。不过我们的demo中并没有设计这类问题的处理。
解释器
接下来我们就可以试着通过遍历AST对节点求值来执行代码。如果是一个AssignmentExpression我们需要设置变量，对于Identifier我们需要区分是要为其变量设置值还是取得这个变量的值，WhileStatement和IfStatement同样需要处理相应的结构：
...
Identifier(node, env, opts) {
if (!opts.name) return env.names[node.name];
return node.name;
},
Literal(node, env) {
return eval(node.raw);
},
WhileStatement(node, env) {
while (ps.process(node.test, env)) {
ps.process(node.body, env)
}
},
IfStatement(node, env) {
if (ps.process(node.test, env)) {
ps.process(node.consequent, env)
} else {
ps.process(node.alternate, env)
}
},
BinaryExpression(node, env) {
switch (node.operator) {
case '<=': {
return ps.process(node.left, env) <= ps.process(node.right, env)
}
case '<': {
return ps.process(node.left, env) < ps.process(node.right, env)
}
case '+': {
return ps.process(node.left, env) + ps.process(node.right, env);
}
}
},
...
事实上任何节点都应当有返回值，例如BlockStatement的返回值应当是其最后一个节点的返回值，而IfStatement的返回值则根据其test的结果而异。不过由于我的偷懒，demo中并没有对所有节点都进行返回，而且如前所述，我没有处理嵌套的作用域，而是直接使用了一张表（而且还没用Map，哈哈）。相信你能比我做的更好。
单步调试
最后，既然我们实现了一个简单的解释器，那自然我们想看看是否能实现单步调试器？
由于使用了JS，而且是在浏览器环境中，我们无法使用ptrace进行进程跟踪，无法中断和恢复指令，不过既然解释器是我们自己实现的，我们还是可以做一些有趣的尝试：
我们可以promisify所有节点的求值过程（./walker/step.js）。
Identifier和Literal是最简单的节点，我们可以直接使用Promise.resolve。例如BinaryExpression节点，我们需要用Promise.all等待左右子树求职完成。稍稍麻烦的是WhileStatement和BlockStatement。
WhileStatement需要在其test为假之前重复执行自身节点的求值：
WhileStatement(node, env) {
return ps.process(node.test, env).then((flag) => {
if (flag) {
return ps.process(node.body, env).then(() => {
return ps.process(node, env)
});
} else {
// done
}
});
},
而BlockStatement则需要依次处理所有节点：
BlockStatement(node, env, opts) {
const index = opts.index || 0;
let item = node.body[index];
return ps.process(item, env).then(() => {
if (index === node.body.length - 1) {
// done
} else {
return ps.process(node, env, {
index: index + 1,
});
}
});
},
在第一次编写的时候这让我有些晕，不过验证了这种这一尝试的可行性后还是觉得挺好玩儿的。
在用Promise包裹所有的求值过程之后，我们接下来只需要在需要断点的节点类型里劫持其resolve即可（./walker/step2.js）：
BinaryExpression(node, env) {
return new Promise((r) => {
env.currentNode = node;
env.next = () => {
r(Promise.all([
ps.process(node.left, env),
ps.process(node.right, env)
]).then((arr) => {
const [left, right] = arr;
switch (node.operator) {
case '<=': {
return left <= right;
}
case '<': {
return left < right;
}
case '+': {
return left + right;
}
}
}));
};
});
},
在劫持resolve的同时，我们记录下了当前的节点，以便高亮显示其代码：
看着还不错，是吧？
总结
最后，感谢你阅读这篇文章，也希望你会觉得此文/抽象语法树很有趣。在之后的文章里，我会努力带来有趣的内容，包括介绍如何使用ohm.js以及自己动手来实现语法解析。
