AST（抽象语法树）原理及应用
前言
在编程世界中，源代码的解析和转换是一个非常重要的过程。无论是代码的语法检查、格式化，还是高级功能的实现（如代码压缩、语法转换），都离不开对代码结构的深入理解。而 抽象语法树（AST）正是这一过程的核心工具。本文将带你深入探索AST的概念，并通过一个实际的例子——手写一个小型编译器，帮助你理解AST的工作原理及其在实际开发中的应用。
通过阅读本文，你将掌握以下内容：
AST是什么？ 它如何表示代码的语法结构？
如何从零开始实现一个编译器？ 从解析源代码到生成目标代码的全过程。
AST的实际应用场景：包括代码转换、语法检查等。
二、AST（抽象语法树）是什么？
抽象语法树（AbstractSyntaxTree，AST） 是源代码的一种树状表示形式。它将代码的语法结构抽象为树形结构，每个节点代表代码中的一个语法单元（如变量、函数、操作符等）。AST的核心作用是将代码从文本形式转换为结构化的数据，从而方便程序对其进行处理。
以前我们在做小学语文题时，经常会做到的一种题型就是在一句话中找出不恰当的部分，比如："你是猪，"
解题方法通常是：
- 第一步：找出语句中的主语、谓语、宾语
- 第二步：找出语句中的形容词、动词、标点符号等进行分析
如果将其程序化，我们按照上面的方法可以先将其进行拆分成这样：
[
{ type: "主语", value: "你" },
{ type: "谓语", value: "是" },
{ type: "宾语", value: "猪" },
{ type: "标点符号", value: "，" },
]
在这一步骤中可以很快的发现第一个错误：在句末使用的是一个逗号❌，实际应该使用句号。
接着再对主语、谓语、宾语中的词语进行依次分析，将数据结构整理成这样：
{
type: "语句",
body: {
type: "肯定陈述句",
declarations: [
{
type: "声明",
person: {
type: "Identifier",
name: "你",
},
name: {
type: "animal",
value: "猪",
},
},
],
},
};
在这个结构中我们发现：在一个肯定陈述句中，将一个人比作一个猪🐷，显然不合适...❌，因此找出第二个错误。
在上面这个简单的例子中，其实和AST的生成和应用就颇为相似，AST是源代码的抽象语法结构的树状表现形式，简单点就是一个深度嵌套对象，这个对象能够描述我们书写代码的所有信息。
为了帮大家加深理解，接下来我将手牵手带大家撸一个小型的编译器。
三、手写编译器
该小节分为两个部分：设计篇和原理篇。
设计篇侧重整体设计，原理篇则是手撕代码，侧重编码实现，在阅读过程中建议将重心放在设计篇，学习思想最重要。
3.1、设计篇
3.1.1、整体流程
一个完整的编译器整体执行过程可以分为三个步骤：
Parsing(解析过程)：这个过程要经
词法分析、语法分析、构建AST（抽象语法树）一系列操作；Transformation（转化过程）：这个过程就是将上一步解析后的内容，按照编译器指定的规则进行处理，
形成一个新的表现形式；CodeGeneration（代码生成）：将上一步处理好的内容
转化为新的代码；
如图所示：
接下来，我们先看一个小Demo，将lisp)的函数调用编译成类似C的函数，如果你不熟悉也没关系，看完下面的代码相信大家能够快速的理解：
LISP 代码： (add 2 (subtract 4 2))
C 代码: add(2, subtract(4, 2))
释义： 2 + （ 4 - 2 ）
3.1.2、Parsing(解析)
解析过程分为2个步骤：词法分析、语法分析。
词法分析是使用tokenizer(分词器)或者lexer(词法分析器)，将源码拆分成tokens，tokens是一个放置对象的数组，其中的每一个对象都可以看做是一个单元（数字，标签，标点，操作符...）的描述信息。
结合最开始做的语文题目（"你是猪，"），我们照葫芦画瓢，对(add2(subtract42))进行词法分析后得到：
[
{ 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: ")" },
];
像这样对中文语句进行了主谓宾的拆解得到了tokens，但这并不能帮助我们判断该条语句是否合法，还需要进行语法解析。
语法解析则是将tokens重新整理成语法相互关联的表达形式，这种表达形式一般被称为中间层或者AST（抽象语法树）。
还是拿语文题目（"你是猪，"）来照葫芦画瓢，(add2(subtract42))进行语法解析后得到的AST：
3.1.3、Transformation(转化)
这个过程主要是改写AST（抽象语法树），或者根据当前AST（抽象语法树）生成一个新的AST（抽象语法树），这个过程可以是相同语言，或者可以直接将AST（抽象语法树）翻译为其他语言。
注意看上述生成的AST（抽象语法树），有一些特殊的对象，都具有自己的类型描述，他们就是这个“树”上的节点，如下所示
// 数字片段节点
{
type: 'NumberLiteral',
value: '2',
}
// 调用语句节点
{
type: 'CallExpression',
name: 'subtract',
params: [{
type: 'NumberLiteral', // 数字片段节点
value: '4',
}, {
type: 'NumberLiteral', // 数字片段节点
value: '2',
}]
}
在案例中我们是想将lisp)语言转化为C语言，因此需要构建一个新的AST（抽象语法树），这个创建的过程就需要遍历这个“树”的节点并读取其内容，由此引出Traversal(遍历)和Visitors(访问器)。
Traversal(遍历)：顾名思义这个过程就是，遍历这个AST（抽象语法树）的所有节点，这个过程使用深度优先原则，大概执行顺序如下：
进入Program - 最顶层开始
进入CallExpression (add)
进入NumberLiteral (2)
离开NumberLiteral (2)
进入CallExpression (subtract)
进入NumberLiteral (4)
离开NumberLiteral (4)
进入NumberLiteral (2)
离开NumberLiteral (2)
离开CallExpression (subtract)
离开CallExpression (add)
离开Program
Visitors(访问器)：访问器最基本的思想是创建一个“访问器”对象，这个对象可以处理不同类型的节点函数,如下所示
const visitor = {
NumberLiteral(node,parent){}, // 处理数字类型节点
CallExpression(node,parent){} // 处理调用语句类型节点
}
在遍历节点的时候，当enter(进入)到该节点，我们会调用访问器，然后会调用针对于这个节点的相关函数，同时这个节点和其父节点作为参数传入。
同时在exit（离开）的时候我们也希望能够调用访问器，当enter一个节点的时候，最外层节点就相当于一个分支，他是一个节点，这个分支的内部依然存在若干节点，就像上边遍历的那样。
我们会按照深度优先的原则，依次遍历到这个分支的最内层，当达到最内层的时候，针对当前分支的访问就完成了，接着会依次exit（退出）节点，这个过程是由内向外的。
为了能够处理到enter和exit，访问器最终会做成这个样子
const visitor = {
NumberLiteral:{
enter(node, parent) {},
exit(node, parent) {},
}
}
3.1.4、CodeGeneration(生成代码)
最后就是代码生成阶段了，其实就是将生成的新AST树再转回代码的过程。大部分的代码生成器主要过程是，不断的访问Transformation生成的AST(抽象语法树)或者再结合tokens，按照指定的规则，将“树”上的节点打印拼接最终还原为新的code，自此编译器的执行过程就结束了。
3.2、原理篇：
接下来按照上述步骤，开始手写编译器。
3.2.1、生成Tokens
第一步:将代码解析为tokens。这个过程需要tokenzier(分词器)函数，整体思路就是通过遍历字符串的方式，对每个字符按照一定的规则进行switchcase，最终生成tokens数组。
function tokenizer (input) {
let current = 0; //记录当前访问的位置
let tokens = [] // 最终生成的tokens
// 循环遍历input
while (current < input.length) {
let char = input[current];
// 如果字符是开括号，我们把一个新的token放到tokens数组里，类型是`paren`
if (char === '(') {
tokens.push({
type: 'paren',
value: '(',
});
current++;
continue;
}
// 闭括号做同样的操作
if (char === ')') {
tokens.push({
type: 'paren',
value: ')',
});
current++;
continue;
}
//空格检查，我们关心空格在分隔字符上是否存在，但是在token中他是无意义的
let WHITESPACE = /\s/;
if (WHITESPACE.test(char)) {
current++;
continue;
}
//接下来检测数字，这里解释下 如果发现是数字我们如 add 22 33 这样
//我们是不希望被解析为2、2、3、3这样的，我们要遇到数字后继续向后匹配直到匹配失败
//这样我们就能截取到连续的数字了
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;
}
// 最后一个检测的是name 如add这样，也是一串连续的字符，但是他是没有“”的
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;
}
// 容错处理，如果我们什么都没有匹配到，说明这个token不在我们的解析范围内
throw new TypeError('I dont know what this character is: ' + char);
}
return tokens
}
3.2.2、生成AST
第二步：将生成好的tokens转化为AST。现在需要定义parser函数，接收上一步处理好的tokens：
function parser (tokens) {
let current = 0; //访问tokens的下标
//walk函数辅助我们遍历整个tokens
function walk () {
let token = tokens[current]
// 现在就是遍历出每一个token，根据其类型生成对应的节点
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]
//这里以一个例子解释(add 2 3) 这样的代码 "(" 就是 paren token ，而接下来的node其实就是那个 name 类型的token "add"
let node = {
type: "CallExpression",
value: token.value,
params: []
}
//获取name后我们需要继续获取接下来调用语句中的参数，直到我们遇到了")",这里会存在嵌套的现象如下
// (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: ')' },
]
*/
token = tokens[++current];
//这里我们通过递归调用不断的读取参数
while (
(token.type !== 'paren') || (token.type === 'paren' && token.value !== ')')
) {
node.params.push(walk())
token = tokens[current] //因为参数的if判断里会让 current++ 实际上就是持续向后遍历了tokens,然后将参数推入params
}
// 当while中断后就说明参数读取完了，现在下一个应该是")"，所以我们++越过
current++
return node // 最终将CallExpression节点返回了
}
//当然这里做了容错处理，如果没有匹配到预计的类型，就说明出现了，parse无法识别的token
throw new TypeError(token.type);
}
// 现在我们创建AST，树的最根层就是Program
let ast = {
type: 'Program',
body: [],
};
//然后我们通过调用walk遍历tokens将tokens内的对象，转化为AST的节点，完成AST的构建
while (current < tokens.length) {
ast.body.push(walk());
}
return ast;
}
3.2.3、遍历和访问生成好的AST
现在已经有AST了，然后我们希望能够通过访问器访问不同的节点，当遇到不同的节点的时候，调用访问器的不同函数，大致设计成这样：
// traverse(ast,visitor) 迭代器(抽象语法树，访问器)
traverse(ast, {
Program: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
CallExpression: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
},
NumberLiteral: {
enter(node, parent) {
// ...
},
exit(node, parent) {
// ...
},
}
})
接下来实现traverse函数：
function traverse (ast, visitor) {
//遍历数组，在遍历数组的同时会调用traverseNode来遍历节点
function traverseArray (array, parent) {
array.forEach(child => {
traverseNode(child, parent)
});
}
function traverseNode (node, parent) {
// 判断访问器中是否有合适处理该节点的函数
let methods = visitor[node.type];
// 如果有就执行enter函数，因为此时已经进入这个节点了
if (methods && methods.enter) {
methods.enter(node, parent);
}
//接下来就根据node节点类型来处理了
switch (node.type) {
case 'Program':
traverseArray(node.body, node); //如果你是ast的根部，就相当于树根，body中的每一项都是一个分支
break;
case 'CallExpression':
traverseArray(node.params, node); //这个和Program一样处理，但是这里是为了遍历params,上面是为了遍历分支
break;
// 字符串和数字没有子节点需要访问直接跳过
case 'NumberLiteral':
case 'StringLiteral':
break;
// 最后容错处理
default:
throw new TypeError(node.type);
}
// 当执行到这里时，说明该节点（分支）已经遍历到尽头了，执行exit
if (methods && methods.exit) {
methods.exit(node, parent);
}
}
//我们从ast开始进行节点遍历，因为ast没有父节点所以传入null
traverseNode(ast, null);
}
3.2.4、Transformer转化
现在已经生成好AST了。在这一步需要使用到转换器，帮助我们将刚才生成的AST转化为新的AST。在转化之前，必须要明确转化后的AST长什么样，记得之前的案例：
LISP 代码 (add 2 (subtract 4 2))
C 代码 add(2, subtract(4, 2))
将原来的AST转化为目标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'
* | }]
* | }
* | }
* | }]
* | }
具体代码实现：
function transformer (ast) {
// 将要被返回的新的AST
let newAst = {
type: 'Program',
body: [],
};
// 这里相当于将在旧的AST上创建一个_content,这个属性就是新AST的body，因为是引用，所以后面可以直接操作就的AST
ast._context = newAst.body;
// 用之前创建的访问器来访问这个AST的所有节点
traverser(ast, {
// 针对于数字片段的处理
NumberLiteral: {
enter (node, parent) {
// 创建一个新的节点，其实就是创建新AST的节点，这个新节点存在于父节点的body中
parent._context.push({
type: 'NumberLiteral',
value: node.value,
});
},
},
// 针对于文字片段的处理
StringLiteral: {
enter (node, parent) {
parent._context.push({
type: 'StringLiteral',
value: node.value,
});
},
},
// 对调用语句的处理
CallExpression: {
enter (node, parent) {
// 在新的AST中如果是调用语句，type是`CallExpression`，同时他还有一个`Identifier`，来标识操作
let expression = {
type: 'CallExpression',
callee: {
type: 'Identifier',
name: node.value,
},
arguments: [],
};
// 在原来的节点上再创建一个新的属性，用于存放参数 这样当子节点修改_context时，会同步到expression.arguments中，这里用的是同一个内存地址
node._context = expression.arguments;
// 这里需要判断父节点是否是调用语句，如果不是，那么就使用`ExpressionStatement`将`CallExpression`包裹，因为js中顶层的`CallExpression`是有效语句
if (parent.type !== 'CallExpression') {
expression = {
type: 'ExpressionStatement',
expression: expression,
};
}
parent._context.push(expression);
},
}
});
return newAst;
}
3.2.5、新代码生成
最后一步：新代码生成。到这一步就是用新的AST，遍历其每一个节点，根据指定规则生成最终新的代码。
function codeGenerator(node) {
// 我们以节点的种类拆解(语法树)
switch (node.type) {
// 如果是Progame,那么就是AST的最根部了，他的body中的每一项就是一个分支，我们需要将每一个分支都放入代码生成器中
case 'Program':
return node.body.map(codeGenerator)
.join('\n');
// 如果是声明语句注意看新的AST结构，那么在声明语句中expression，就是声明的标示，我们以他为参数再次调用codeGenerator
case 'ExpressionStatement':
return (
codeGenerator(node.expression) + ';'
);
// 如果是调用语句，我们需要打印出调用者的名字加括号，中间放置参数如生成这样"add(2,2)",
case 'CallExpression':
return (
codeGenerator(node.callee) + '(' + node.arguments.map(codeGenerator).join(', ') + ')'
);
// 如果是识别就直接返回值 如： (add 2 2),在新AST中 add就是那个identifier节点
case 'Identifier':
return node.name;
// 如果是数字就直接返回值
case 'NumberLiteral':
return node.value;
// 如果是文本就给值加个双引号
case 'StringLiteral':
return '"' + node.value + '"';
// 容错处理
default:
throw new TypeError(node.type);
}
}
最终按照上面的步骤实现compiler完成这个微型编译器,注意这个过程的顺序。
function compiler(input) {
let tokens = tokenizer(input); //生成tokens
let ast = parser(tokens); //生成ast
let newAst = transformer(ast); //拿到新的ast
let output = codeGenerator(newAst); //生成新代码
return output;
}
现在一个小型的编译器就完整实现了，我们来测试一下：测试通过😄。
四、AST的广泛应用
在讲AST的广泛应用之前，我们先来了解一下Babel是什么？以免一部分同学不熟悉，影响后面的学习。
Babel其实就是一个最常用的Javascript编译器，它能够转译ECMAScript2015+的代码，使它在旧的浏览器或者环境中也能够运行，工作过程分为三个部分（其实就跟我们上面手写的一样，相信大家现在肯定倍感亲切）：
Parse(解析)将源代码转换成抽象语法树，树上有很多的estree节点
Transform(转换)对抽象语法树进行转换
Generate(代码生成)将上一步经过转换过的抽象语法树生成新的代码
当然我们现在不用从零开始手写了，可以借助于babel插件：
@babel/parser可以把源码转换成
AST@babel/traverse用于对
AST的遍历，维护了整棵树的状态，并且负责替换、移除和添加节点@babel/generate可以把
AST生成源码，同时生成sourcemap@babel/types用于
AST节点的Lodash式工具库,它包含了构造、验证以及变换AST节点的方法，对编写处理AST逻辑非常有用@babel/coreBabel的编译器，核心API都在这里面，比如常见的
transform、parse，并实现了插件功能
先安装：
4.1、小试牛刀：使用Babel修改函数名
上面铺垫了这么多，现在开始进入实战演习。
要求：借助Babel给函数重命名。
根据前面学过的知识点，我们先来整理下思路：
先将源代码转化成
AST遍历
AST上的节点，找到hello函数名节点并修改将转换过的
AST再生成JS代码
将源代码拷贝到在线ast转换器中，查看hello函数名节点：
接下来再看看目标函数的AST，和原函数的AST做个比较：
现在我们已经有了思路：只需要将该节点的name字段修改即可。
该例子比较简单，直接上代码：
const parser = require("@babel/parser");
const traverse = require("@babel/traverse");
const generator = require("@babel/generator");
// 源代码
const code = `
const hello = () => {};
`;
// 1. 源代码解析成 ast
const ast = parser.parse(code);
// 2. 转换
const visitor = {
// traverse 会遍历树节点，只要节点的 type 在 visitor 对象中出现，变化调用该方法
Identifier(path) {
const { node } = path; //从path中解析出当前 AST 节点
if (node.name === "hello") {
node.name = "world"; //找到hello的节点，替换成world
}
},
};
traverse.default(ast, visitor);
// 3. 生成
const result = generator.default(ast, {}, code);
console.log(result.code); //const world = () => {};
参考文档： https://juejin.cn/post/7155151377013047304
原文地址：https://webfem.com/post/ast，转载请注明出处
