Node

AST 抽象语法树

Lucas

• 7 min read

什么是 AST

Abstract Syntax Tree（AST，抽象语法树） 是一种用于表示程序源代码的抽象语法结构的树形数据结构。每个节点（Node）都表示源代码中的一个语法构造（Syntax Construct），例如表达式、语句、操作符、函数、变量等。AST 通过去除代码中的不必要的语法细节（如括号、逗号、空格和注释），提供了一种更高层次的代码表示形式，使编译器或解释器可以更容易地进行分析、优化和代码生成。

在前端开发过程中，其实有很多工具都需要依赖于AST抽象语法树，比如：ESLint、Babel、Prettier等等。当我们使用 Vue.js 编写 template 时， template 转化成 render function 的过程，其实就是 AST 的转换过程，AST 是帮助程序理解代码的重要工具。

AST 的结构

前面已经提过 AST 是树形数据结构，接下来将简单介绍以下树形的组成：

  • 节点（Node）：每个节点表示一个特定的语法元素或操作。节点类型可能包括：

    • 表达式节点（Expression Nodes）：表示各种表达式，如二元运算（加减乘除）、函数调用、赋值等。
    • 语句节点（Statement Nodes）：表示各种语句，如 if 语句、for 循环、while 循环、return 语句等。
    • 标识符节点（Identifier Nodes）：表示变量名、函数名、类型名等。
    • 字面量节点（Literal Nodes）：表示常量值，如数字、字符串、布尔值等。

  • 边（Edge）：边连接节点，表示它们之间的语法关系。例如，一个二元操作符节点（如加法 +）的两个子节点表示其左操作数和右操作数。

表达式 2 + 3 * 4 的 AST 表示如下：

                                (+)
                                /   \
                              (2)   (*)
                                    /  \
                                  (3)  (4)

在 AST 中会忽略括号等不必要的语法细节， 如果表达式为 (2 + 3) * 4 ，则 AST 会变成：

                                 (*)
                                /   \
                              (+)   (4)
                             /  \
                           (2)  (3)

AST 的生成

  • 词法分析 （Lexical Analysis）
    • 词法分析是 AST 生成的第一步，将源代码文本转换为一系列的标记（Token）。每个标记代表源代码中的一个最小的语法单元，例如关键字、操作符、标识符、字面量等。词法分析器（Lexer 或 Scanner）逐字符扫描源代码，根据语言的词法规则识别出标记，并将其分类。
    • 词法分析过程会忽略空格、换行符、注释等无关语法的元素，同时检查标记是否符合语言的词法规则。如果词法分析器发现无法识别的标记，则抛出错误。

示例：let x = 2 + 3，词法分析器会将源代码转换为以下标记序列：

[LET, IDENTIFIER(x), ASSIGN, NUMBER(2), PLUS, NUMBER(3), SEMICOLON]
  • 语法分析（Syntax Analysis）
    • 语法分析的目的是将标记序列转换为 AST。这一步由语法分析器（Parser）完成，语法分析器会根据编程语言的语法规则（通常由上下文无关文法描述）将标记序列解析为抽象语法树。
    • 语法分析器会验证标记序列的结构是否符合语言的语法规则（如表达式、语句、块的结构等）。同时分析器会验证语法，如果语法错误则会抛出。
  • 语义分析（Semantic Analysis）
    • 在生成初步的 AST 之后，编译器通常会执行语义分析来进一步检查程序的正确性。这一步不直接生成 AST，但可能会根据语义信息修改或注释 AST。
    • 语义分析的任务包括： 类型检查，作用域检查，符号解析。
  • AST 优化（AST Optimization）
    • 在生成并验证 AST 后，编译器可以对 AST 进行优化（这一步是可选的）
    • 常见的优化有：常量折叠，常量传播，死代码删除，循环展开，循环不变式 hoisting 等。
  • 代码生成（Code Generation）
    • 虽然不是 AST 生成的一部分，但它依赖于 AST。

JS Parser 是 js 语法解析器，它可以将 js 源码转成 AST，常见的 Parser 有 esprima、traceur、acorn、shift 等。

以 Acorn 为例，可以使用 AST Explorer 生成 AST。

const hello = 'world';

astexplorer.jpg

AST 的应用场景

  1. 编译器和解释器
    • 编译器通过 AST 验证源代码是否符合语言的语法规则。例如，确保条件语句的结构和函数调用的参数匹配等。
    • 在 AST 中检查变量作用域、类型兼容性等语义信息。编译器使用 AST 确认每个语句的含义是正确的，比如变量的声明和使用是一致的。
    • 解释器基于 AST 逐行解释和执行代码，例如 JavaScript 引擎通过解析 JavaScript 代码生成 AST 并解释执行。
  2. 静态代码分析
    • 例如 ESLint、PyLint 等工具通过 AST 进行静态分析，查找潜在的错误、优化、性能问题、代码风格不一致等质量问题。
    • Semgrep， SonarQube 等工具使用 AST 识别代码中可能存在的安全漏洞，例如 SQL 注入、XSS 攻击、缓冲区溢出等。通过分析代码结构，可以检测出潜在的安全风险。
    • 工具可以基于 AST 执行类型推断和类型检查，发现类型不一致的问题，提高代码的安全性和可维护性。
  3. 优化变更代码，改变代码结构.
    • 如 Babel、TypeScript 编译器、Recast，AST 是代码转换和重写工具核心数据结构，能够将一种代码格式转换为另一种。
    • Babel 等转译器利用 AST 将现代 JavaScript（如 ES6+）转换为向后兼容的旧版本（如 ES5），使其能够在不支持新特性的浏览器上运行。
    • 将 TypeScript 转换为 JavaScript，或将 CoffeeScript 转换为 JavaScript。
  4. 代码格式化和美化
    • 如 Prettier 等代码美化工具，通过分析 AST，格式化工具可以自动调整代码的缩进、行间距、括号位置等，使代码风格保持一致，提高代码的可读性和可维护性。

实践

接下来我们将借用 AST 实现插件：将箭头函数转换成普通函数

  1. 首先安装依赖。（使用 Babel 的原因是个人比较熟悉，你也可以使用其他的工具。）
pnpm i @babel/core @babel/types
  1. 创建一个文件，例如 transform.js，并写入以下代码：
const babel = require("@babel/core");
const types = require("@babel/types");

const arrowFunction2NormalFunctionPlugin = {
  visitor: {
    VariableDeclaration(path) {
      const declaration = path.node.declarations[0];
      if (types.isArrowFunctionExpression(declaration.init)) {
        const arrowFunc = declaration.init;
        const functionDeclaration = types.functionDeclaration(
          declaration.id,
          arrowFunc.params,
          // 函数体 需要判断是否在 {...} 中
          types.isBlockStatement(arrowFunc.body)
            ? arrowFunc.body
            : types.blockStatement([types.returnStatement(arrowFunc.body)]),
          false, // 不是生成器函数
          false  // 不是异步函数
        );

        path.replaceWith(functionDeclaration);
      }
    },
  },
};

const code = `
const add = (a, b) => a + b;
const greet = (name) => {
  console.log(\`Hello, \${name}!\`);
};
`;
const output = babel.transformSync(code, {
  plugins: [arrowFunction2NormalFunctionPlugin],
});
console.log(output.code);

为了方便理解，将 node 中的用不上的信息删除 并只以 add() 为例：
EBAF6A86-0E61-46b3-8BE2-845E53B7F12C.png

  1. 执行node transform.js，输出结果如下：
function add(a, b) {
  return a + b;
}
function greet(name) {
  console.log(`Hello, ${name}!`);
}