AST抽象语法树

作者：马育民 • • 阅读：10244

介绍

在计算机科学中，抽象语法树（Abstract Syntax Tree，AST），或简称语法树（Syntax tree），是源代码语法结构的一种抽象表示，即：表示源代码语法结构的抽象数据结构

它以 树 状的形式表现编程语言的语法结构，树上的每个节点都表示源代码中的一种结构，提炼代码的核心语法逻辑，忽略无关的语法细节（如空格、注释、分隔符等）。

AST是编译器、解释器、代码分析工具等的核心组件，是程序从“文本形式”转换为“可处理结构”的关键一步。

应用场景

AST是代码处理工具的“核心骨架”，几乎所有涉及代码分析、转换、执行的工具都依赖AST：

  1. 编译与解释

    • 编译器通过AST进行语义分析（如检查变量是否定义、类型是否匹配）；
    • 对AST进行代码优化（如将2 + 3直接替换为5，称为“常量折叠”）；
    • 将AST转换为目标代码（如机器码、字节码，如Java编译器将AST转换为class文件）。

  2. IDE功能

    • 语法高亮：通过AST识别节点类型（如关键字、字符串），对应不同颜色；
    • 代码重构：如“重命名变量”时，遍历AST替换所有引用该变量的节点；
    • 自动补全：分析AST中已声明的变量/函数，在输入时提示可用选项。

  3. 代码分析工具

    • 静态检查工具（如ESLint、Pylint）通过AST检测代码风格问题（如未使用的变量）或潜在错误（如空指针风险）；
    • 代码覆盖率工具（如JaCoCo）通过AST标记哪些代码被执行过。

  4. 跨语言转换

    • 如TypeScript转JavaScript、CoffeeScript转JavaScript，本质是将源语言的AST转换为目标语言的AST，再生成代码。

为什么需要AST？

源代码是人类可读的文本（如int a = 5 + 3;），但计算机无法直接理解其逻辑。AST的作用是：

  1. 剥离冗余：去除语法中无关的细节（如分号、括号、换行），只保留核心结构（如“变量声明”“加法表达式”）。
  2. 结构化表示：将线性的代码文本转换为树状的层级结构，清晰反映语法成分的嵌套关系（如“表达式中的子表达式”“函数中的语句”）。
  3. 便于处理：树状结构可通过遍历（如深度优先、广度优先）高效实现分析、修改、转换等操作（如语法检查、代码优化）。

AST的构成

AST由节点（Node） 和边（Edge） 组成：

  • 节点：代表源代码中的一个语法成分（如变量、表达式、语句）。
  • 边：表示节点之间的包含或依赖关系（如“函数声明包含参数列表和函数体”）。

1. 节点的类型与属性

不同编程语言的AST节点类型略有差异，但核心类型通用，以下是常见分类：

节点类型 含义示例 核心属性
程序/模块节点 整个程序或代码文件的根节点 包含所有顶级语句（如函数、变量）
声明节点 变量声明（int a = 5）、函数声明（def f(x): ...） 类型、名称、初始化值/参数/函数体
语句节点 赋值（a = b + 3）、条件（if x > 0）、循环（for i in list） 语句类型、关联的表达式或子语句
表达式节点 二元运算（a + b）、函数调用（f(a, b)）、变量引用（a） 运算符/函数名、操作数/参数列表
字面量节点 数字（123）、字符串（"hello"）、布尔值（true） 存储具体值（如123、"hello"）

2. 节点的层级关系

AST的层级严格反映代码的语法嵌套关系。例如，对于代码：

int a = (b + 3) * 2;

其AST结构如下：

                         VariableDeclNode（类型：int，名称：a）
                                ↓
                  BinaryExprNode（运算符：*）  // 根表达式：(b+3)*2
                       /             \
          BinaryExprNode（+）       LiteralNode（2）  // 右操作数：2
               /         \
VariableRefNode（b）   LiteralNode（3）  // 左操作数：b+3
  • 最上层是“变量声明节点”，表示int a = ...；
  • 其初始化值是“乘法表达式节点”，表示(b+3)*2；
  • 乘法表达式的左子节点是“加法表达式节点”（b+3），右子节点是“字面量节点”（2）；
  • 加法表达式的左子节点是“变量引用节点”（b），右子节点是“字面量节点”（3）。

AST的生成过程

AST通常由编译器的语法分析器（Parser） 生成，是源代码处理的中间步骤，完整流程如下：

1. 词法分析（Lexical Analysis）

第一步是将源代码拆分为最小的语法单元（称为Token），例如：
对于int a = (b + 3) * 2;，词法分析会生成：
int（关键字）、a（标识符）、=（赋值运算符）、(（左括号）、b（标识符）、+（加法运算符）、3（数字字面量）、)（右括号）、*（乘法运算符）、2（数字字面量）、;（分号）。

2. 语法分析（Syntactic Analysis）

语法分析器根据编程语言的语法规则（如上下文无关文法），将Token序列转换为AST。例如：

  • 识别int a = ...符合“变量声明”规则，生成VariableDeclNode；
  • 识别(b + 3) * 2符合“二元表达式”规则，生成以*为根的BinaryExprNode，并递归处理子表达式b + 3。

AST与语法树（Parse Tree）的区别

很多人会混淆AST和语法树（Parse Tree，也叫“解析树”），二者的核心区别在于：

  • 语法树（Parse Tree）：是语法规则的“忠实复现”，包含所有语法细节（如括号、关键字、分隔符），结构冗余。例如，(b + 3)的语法树会包含(和)节点，用于体现括号的存在。
  • AST：是语法树的“抽象简化”，仅保留逻辑结构，忽略冗余细节。例如，(b + 3)的AST中没有括号节点，直接通过层级关系表达“b + 3是一个整体”。

简单说：语法树是“怎么写的”，AST是“表达了什么逻辑”。

Java实现抽象语法树

AST抽象语法树-Java例子

工具

可以通过工具可视化AST，快速理解其结构：

在线工具

AST Explorer（https://astexplorer.net/）支持JavaScript、Python、Java等多种语言，输入代码即可实时查看AST结构。

Python标准库

ast模块可生成AST并打印，例如：

import ast
code = "a = (b + 3) * 2"
tree = ast.parse(code)
print(ast.dump(tree, indent=2))  # 打印AST结构

Antlr 语法分析工具

总结

AST是源代码的“抽象语法骨架”，它剥离了文本层面的冗余信息，以树状结构清晰展现代码的语法逻辑。从编译器到IDE，从代码分析到跨语言转换，AST是连接人类可读代码与机器可处理结构的核心桥梁，是理解程序语言处理流程的关键概念。

原文出处：/show_1IX39EXaBJra.html

吉ICP备15003043号