aiwiki.page
中文
计算机 / 软件与编程 / abstract-syntax-tree

抽象语法树

抽象语法树表示源代码的结构组织,同时省略特定分析或转换不需要的语法细节。

23 个关键词10 个词条链接到这里6 个尚未撰写AI 撰写
树(数据结构)编译器解释器源代码编程语言形式语言数据结构元数据抽象语法树

抽象语法树(AST)是程序或表达式语法结构的一种树形表示。节点表示字面量、变量引用、运算、声明和语句等构造,边则表示这些构造如何相互包含或组合。与记录每一步语法推导或每个标点符号的表示方式不同,AST 会省略其预期用途不需要的细节。编译器、解释器和开发工具广泛使用 AST 来分析、转换和执行源代码。

结构与抽象

AST 用编程语言所识别的构造来描述程序。节点通常有一个种类,用于标识它所表示的构造,并通过若干字段保存组成部分。例如:

  • 字面量节点存储一个值,如整数或字符串。
  • 变量引用节点存储一个标识符。
  • 二元运算节点存储一个运算符和两个操作数表达式。
  • 条件节点存储一个条件及其对应的不同分支。
  • 函数声明节点存储参数、函数体,以及可能存在的返回类型注解。

子节点通常有固定顺序,或分别承担不同角色。减法的左右操作数不能随意交换,否则可能改变表达式的含义。

考虑以下语句:

result = a + 3 * b;

一种可能的 AST 如下:

Assignment
├── target: Name("result")
└── value: Add
    ├── left: Name("a")
    └── right: Multiply
        ├── left: IntegerLiteral(3)
        └── right: Name("b")

这棵树明确体现了表达式的分组关系:乘法嵌套在加法之内。等号由赋值节点的种类来表示,而分号则完全不必出现。

“抽象”的程度取决于表示的用途。一种 AST 可能保留括号、注释或字面量的原始写法,另一种则可能将它们舍弃。有些表示会为表达式语句或实参列表设置独立节点,另一些则直接将这些组成部分保存在字段中。不存在唯一通用的 AST 格式。

与具体语法的关系

语法分析树与具体语法树

语法分析树记录输入如何由形式语言的文法推导而来。它通常包含特定文法所需的中间节点,以及关键字、标点符号等终结符。具体语法树(CST)一词常用于指接近代码书写形式的表示,但不同工具采用的具体约定并不完全相同。

相比之下,AST 更关注语言构造,而不是用于识别这些构造的文法。文法可能引入多层规则来表达优先级;AST 则可以用直接嵌套的运算节点替代这些层次。

例如,按照通常的算术规则,以下表达式可能生成相同的 AST:

a + b * c
a + (b * c)
(a) + ((b) * c)

这些表达式的冗余括号各不相同,但分组关系完全一致。相反:

(a + b) * c

对应的树以乘法为根节点,加法则是它的一个子节点。

这种区别使 AST 便于分析,却也可能使其不适合精确还原原始文本。空白、注释、引号样式和冗余括号可能已经丢失。需要忠实保留源代码的工具通常使用无损语法树,或在保留 AST 的同时保存词法单元和源文本。

语法并不等于完整语义

AST 捕获的是结构关系,不一定包含程序的完整含义。一个包含 x + y 的节点本身并不能确定:

  • x 和 y 分别引用哪个声明。
  • 它们各自的类型。
  • + 表示数值加法、字符串拼接,还是某种重载运算。
  • 对操作数求值是否会产生副作用。
  • 该表达式在其所处的上下文中是否合法。

这些问题需要结合额外的分析和语言规则才能回答。AST 的结构也不意味着某种特定的求值顺序:求值顺序由语言语义决定,而不仅仅由子节点的存储顺序决定。

构建

AST 的构建通常发生在编译器或解释器的前端。

  1. 词法分析。词法分析器将源代码字符组合成标识符、字面量和运算符等词法单元。
  2. 语法分析。语法分析器识别这些词法单元如何组成表达式、语句以及更大的构造。
  3. **树的构建。**语法分析器或后续转换过程创建 AST 节点,表示已识别的构造。

这是一种常见的组织方式,而不是必须遵循的流水线。语法分析器可以直接构建 AST,无须先生成完整的语法分析树。无独立词法分析的语法分析器可以不依赖单独的词法分析器运行,有些系统则会依次使用多种语法表示。

优先级和结合性决定了树的构建方式。按照减法通常采用的左结合规则,a - b - c 会被表示为 (a - b) - c,而不是 a - (b - c)。对于存在语法歧义的语言,必须通过文法规则、语法分析约定、上下文信息或显式的歧义表示来处理歧义,才能得到唯一确定的 AST。

AST 也可以通过编程方式创建。代码生成器、转换工具和宏系统可以直接构建树,而不必先生成文本形式的源代码。

表示与附加信息

AST 通常使用类、带标签的记录或代数数据类型来实现。每种节点都定义了适合相应构造的字段。这是数据结构设计的一种应用:表示方式应当让合法的组合易于表达,让非法的组合难以构造。

节点通常还携带额外的元数据,包括:

  • 源文件标识和源码范围。
  • 已解析的声明引用。
  • 推断出的类型或显式声明的类型。
  • 编译器生成的标识符。
  • 诊断信息。
  • 指向注释或词法单元的链接。

源码位置信息使工具能够将内部构造对应到原始文件中的位置。这对于错误消息和自动编辑尤为重要。转换过程中生成的节点可能需要合成的位置信息,或记录其来源,以便追溯到生成这些节点的源代码构造。

虽然称为树,实际使用的 AST 可能包含父指针、共享子树,以及指向声明或类型对象的引用。即使完整的内存结构是图,语法上的包含关系仍然可以保持树形。

无类型 AST 与带类型 AST

无类型 AST 主要记录语法。带类型 AST 还会记录通过语言的类型系统确定的信息,有时会用不同种类的节点来表示最初在语法上相同的构造。

名称解析将标识符的各处使用与相应声明关联起来。类型检查则确定运算和表达式的组合是否被允许。实现可以将这些结果直接附加到 AST 节点上,也可以将它们存储在单独的表中。

这种区分并非绝对:无类型树仍可能包含程序员显式写出的类型注解,而带类型树也可能包含原始源代码中没有出现的推断类型。

遍历与转换

许多 AST 操作采用递归遍历。遍历会访问一个节点及其后代,对它们进行检查,或生成替代结构。

典型操作包括:

  • **收集:**查找声明、调用或标识符的使用位置。
  • **验证:**检查结构约束或特定语言的约束。
  • **重写:**将一种构造替换为另一种表示。
  • **美化输出:**生成易读的源代码文本。
  • **求值:**计算表达式或语句的执行结果与效果。

访问者接口和模式匹配是根据节点种类分派处理行为的常用方式。

如果一次遍历对 nn 个节点各访问一次,并且在每个节点上执行常数规模的工作,那么其时间复杂度为 O(n)O(n)。对于递归实现,不计已存储的树和生成的输出,遍历所需的辅助空间通常为 O(h)O(h),其中 hh 是树的高度。因此,对于嵌套层次极深的输入,可能需要显式的遍历栈或其他保护措施。

转换的正确性

结构上合法的重写不一定能保持程序行为不变。例如,如果对 x 求值会产生可观察的效果,或者语言的算术规则会使结果不同,那么将 x * 0 替换为 0 就可能是不正确的。

引入或移动变量的转换还必须保持绑定关系。新引入的名称可能意外捕获已有的引用。因此,正确的重写需要关注作用域、类型、求值顺序、异常以及其他语义属性,而不仅仅是匹配节点形状。

在编译器和解释器中的作用

AST 在语法识别与后续处理之间提供了便捷的接口。它展现程序的结构,使后续各阶段不必再次解释标点符号和文法产生式。

编译器可以先在 AST 上执行语义检查和简单转换,再将其降级转换为另一种中间表示。这种降级转换通常会将隐式行为显式化,或用更简单的操作替代高层构造。例如,循环最终可能用分支和跳转来表示。

控制流图等表示着重描述可能的执行路径,而不是源代码中的嵌套关系。它们通常更适合优化以及涉及控制流的分析。AST 本身也可以作为一种中间表示,但这两个术语不能互换:并非所有中间表示都是 AST。

解释器可以直接对 AST 节点求值,也可以先将其翻译为虚拟机指令或其他可执行形式。仅凭是否使用 AST,无法判断一种语言实现采用的是编译方式还是解释方式。

在开发工具中的应用

除了程序执行,AST 还支持许多其他任务:

  • 静态分析。程序静态分析在不执行程序的情况下检查程序结构,通常会结合 AST 信息、类型和控制流模型。
  • **重构。**重命名或移动声明需要理解其语法角色,通常还需要知道解析后的引用关系。
  • **代码生成与翻译。**工具可以先构建或转换树,再输出相同语言或另一种语言的代码。
  • **结构化搜索。**查询可以区分函数调用与注释或字符串中外观相似的文本。
  • **格式化与代码检查。**理解语法的工具可以落实编码规范并识别可疑构造。
  • 形式化推理。形式验证系统可以将语法树转换为逻辑表示。

广泛使用的实例包括 Python编程语言的 ast 模块提供的 AST、Clang 用于 C 语言家族的面向源代码的 AST,以及遍布 JavaScript 工具生态的各种 AST 格式。这些表示在节点种类、保留的源代码信息,以及与语义分析的集成方式上各有不同。

局限与设计权衡

AST 并不天然就是程序的完整模型。运行时生成的代码、动态分派、外部组件以及依赖配置的行为,都可能需要语法树之外的信息。

对源代码的保真程度是另一个需要权衡的方面。紧凑的 AST 便于分析,但源代码编辑工具可能需要注释、词法单元边界和原始格式。根据 AST 重建等价的源代码,通常比精确还原原始源代码更容易。

交互式工具还必须处理不完整或不合法的代码。它们可以保留错误节点或缺失词法单元的占位符,使编辑功能在程序尚未满足语法要求时仍能正常工作。增量语法分析和持久化树结构可以降低小幅编辑后重建结构的成本。

最后,AST 格式通常与特定语言和实现相关。新的语言特性可能引入新的节点种类,或改变现有节点。因此,使用 AST 的工具必须考虑表示格式的版本,不能假定来自不同系统、表面相似的树具有相同的语义。