概念
抽象语法树 (Abstract Syntax Tree)，简称 AST，它是源代码语法结构的一种抽象表示。它以树状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构
Abstract Syntax Tree抽象语法树（通常被简写成AST）实际上只是一个解析树(parse tree)的一个精简版本。一棵解析树是包含代码所有语法信息的树型结构，它是代码的直接翻译。所以解析树，也被成为具象语法树（Concret Syntax Tree, 简称CST）;而抽象语法树，忽略了一些解析树包含的一些语法信息，剥离掉一些不重要的细节
应用
-
编辑器的错误提示、代码格式化、代码高亮、代码自动补全；
-
elint、pretiier对代码错误或风格的检查； -
webpack通过babel转译javascript语法；
AST 如何生成
js 执行的第一步是读取 js 文件中的字符流，然后通过词法分析生成 token，之后再通过语法分析( Parser )生成 AST，最后生成机器码执行
词法分析
词法分析，也称之为扫描（scanner），简单来说就是scanner会从左到右扫描文本，把文本拆成一些单词。然后，这些单词传入分词器，经过一系列的识别器（关键字识别器、标识符识别器、常量识别器、操作符识别器等），确定这些单词的词性，这一过程的产物是token序列
token在机内一般用<type, value>形似的二元组来表示，type表示一个单词种类，value为属性值
例如 var 这三个字符，它只能作为一个整体，语义上不能再被分解，因此它是一个 Token，它的type本身就可表示这个关键字，不再需要属性值， 用二元组表示就是<VAR, ->
词法分析器里，每个关键字是一个 Token ，每个标识符是一个 Token，每个操作符是一个 Token，每个标点符号也都是一个 Token。除此之外，还会过滤掉源程序中的注释和空白字符（换行符、空格、制表符等)
最终，整个代码将被分割进一个tokens列表
语法分析
token序列会经过我们的解析器，由解析器识别出代码中的各类短语，会根据语言的文法规则(rules of grammar)输出解析树，同时，验证语法，语法如果有错的话，抛出语法错误
解析树（具象语法树）
文法可表示为:
G=(T,N,P,S)
-
T表示终结符的集合（如little、girl等，即词法分析中提到的token）
-
N表示非终结符的集合（如<>里包括的部分，表示了语法成分， 因为它们可以推导出其他句子成分，所以称为非终结符）
-
P表示产生式集合（上面分析英语句子的每一条规则都是一个产生式，如<动词短语> -> <动词> <名词短语>， 就是一个产生式）
-
S表示开始符号（S属于N的子元素，是一个特殊的非终结符）
5 + (12 * 1)根据对应的文法生成的解析树
解析树的一些性质
-
解析树的根节点为文法开始符号
-
解析树内部节点表示一个产生式的应用
-
叶节点既可以是非终结符也可以是终结符。从左到右的叶节点得到的符号串成为这颗树的产出(yield)
抽象语法树（AST）
上文可见，根据文法规则生成的解析树会非常冗余。例如EXP->1这种结点，看上去有点冗余，我们把这种结点叫做单继承节点，实际上我们并不会关心EXP是什么，只会关心继承它的那个值，这里即1；再例如我们发现括号似乎也是冗余的，可以隐藏在树的结构中
把冗余的层修剪掉，我们可以得到一颗AST树
解析树和抽象语法树的不同之处:
-
AST不含有语法细节，比如冒号、括号、分号
-
AST会压缩单继承节点
-
操作符会变成内部节点，不再会以叶子节点出现在树的末端
AST虽然小而美，生成并不容易。生成解析树相反会容易很多，它直接包含了语言的文法推导细节。很多解析器生成AST前会先生成解析树，这意味着多的步骤；也有一些编译器一步到位，跳过解析树，直接生成AST。
它之所以被称为抽象，也是与CST中的Concret一词相对的，它不会表达出真实语法中的每一个细节，仅仅只是浓缩了语法中的必要结构成分
AST会出现在大量的代码工具中，正是因为它比CST提供更清晰、简洁的接口，为开发人员操作源代码提供了便捷的渠道
实战：用AST修改源码
下面我们就来完成一个在调用 console.log(xx) 时候给前面加一个函数名
// 源代码
function getData() {
console.log("data")
}
-------------------------------------------------------
// 转化为下面代码
function getData() {
console.log("getData", "data");
}
1、创建 js 文件, 编写大致布局如下 使用babel
// @babel/parser : 将 js 代码 ---> AST 抽象语法树
// @babel/traverse 对 AST 节点进行递归遍历；
// @babel/types 对具体的 AST 节点进行进行修改；
// @babel/generator : AST 抽象语法树 ---> 新的 js 代码；
const generator = require("@babel/generator");
const parser = require("@babel/parser");
const traverse = require("@babel/traverse");
const types = require("@babel/types");
function compile(code) {
// 1.parse 将代码解析为抽象语法树（AST）
const ast = parser.parse(code);
// 2,traverse 转换代码
traverse.default(ast, {});
// 3. generator 将 AST 转回成代码
return generator.default(ast, {}, code);
}
const code = `
function getData() {
console.log("data")
}
`;
const newCode = compile(code)
使用 node 跑出结果，因为compile方法中并未做任何处理，此时输出的是原代码
2、完善compile方法
function compile(code) {
// 1.parse
const ast = parser.parse(code);
// 2.traverse
const visitor = {
CallExpression(path) {
// 拿到 callee 数据
const { callee } = path.node;
// 判断是否是调用了 console.log 方法
// 1. 判断是否是成员表达式节点，上面截图有详细介绍
// 2. 判断是否是 console 对象
// 3. 判断对象的属性是否是 log
const isConsoleLog =
types.isMemberExpression(callee) &&
callee.object.name === "console" &&
callee.property.name === "log";
if (isConsoleLog) {
// 如果是 console.log 的调用 找到上一个父节点是函数
const funcPath = path.findParent(p => {
return p.isFunctionDeclaration();
});
// 取函数的名称
const funcName = funcPath.node.id.name;
// 将名称通过 types 来放到函数的参数前面去
path.node.arguments.unshift(types.stringLiteral(funcName));
}
}
};
// traverse 转换代码
traverse.default(ast, visitor);
// 3. generator 将 AST 转回成代码
return generator.default(ast, {}, code);
}
上面的 path.node 如下
{
"type": "CallExpression",
"start": 24,
"end": 43,
"loc": {
"start": { "line": 3, "column": 2 },
"end": { "line": 3, "column": 21 }
},
"callee": {
"type": "MemberExpression",
"start": 24,
"end": 35,
"loc": {
"start": { "line": 3, "column": 2 },
"end": { "line": 3, "column": 13 }
},
"object": {
"type": "Identifier",
"start": 24,
"end": 31,
"loc": {
"start": { "line": 3, "column": 2 },
"end": { "line": 3, "column": 9 },
"identifierName": "console"
},
"name": "console"
},
"property": {
"type": "Identifier",
"start": 32,
"end": 35,
"loc": {
"start": { "line": 3, "column": 10 },
"end": { "line": 3, "column": 13 },
"identifierName": "log"
},
"name": "log"
},
"computed": false
},
"arguments": [
{
"type": "StringLiteral",
"start": 36,
"end": 42,
"loc": {
"start": { "line": 3, "column": 14 },
"end": { "line": 3, "column": 20 }
},
"extra": { "rawValue": "data", "raw": "'data'" },
"value": "data"
}
]
}
//方便阅读可以将不必要的位置信息（start, end, loc）等属性删除
此时再执行，输出结果为我们修改后的代码
总结
-
js 语法解析成 AST；
-
修改 AST；
-
AST 转成 js 语法；
实现
以下是一个简化的步骤和思路：
-
词法分析： 遍历源代码，将其分解成一系列的标记（tokens）。标记可以是关键字、运算符、变量名等。
-
语法分析： 利用上下文无关文法（Context-Free Grammar，CFG）定义编程语言的语法规则，然后编写一个递归下降分析器（Recursive Descent Parser）。
a. 定义文法规则： 将编程语言的语法规则翻译成一系列的产生式，其中每个产生式表示一个语法结构。
b. 编写递归下降分析器： 对于每个非终结符（语法规则的左侧），编写一个相应的递归函数。这些函数可以递归地调用彼此，每个函数负责解析一个特定的语法结构，并返回相应的AST子树。
-
构建抽象语法树： 在语法分析的过程中，递归下降分析器的每个函数都会返回一个AST子树。通过在这些函数中构造和连接这些子树，最终形成整个源代码的AST。
a. 节点表示： 定义AST的节点类型，每个节点类型对应语法规则中的一个语法结构，如赋值语句、条件语句等。
b. 构建过程： 在递归下降分析器的各个函数中，根据语法规则，创建相应的AST节点，并将其连接起来形成树状结构。
-
语义分析： 在构建AST的过程中，可以执行一些简单的语义分析，例如检查变量的声明与引用是否匹配、类型检查等