抽象语法树

在计算机科学中，抽象语法树（AST），或只是语法树，是用一种形式语言编写的文本（通常是源代码）的抽象语法结构的树状表示。树上的每个节点都表示文本中出现的一个结构。语法是抽象的，因为它并不代表真实语法中出现的每一个细节，而只是代表结构或内容相关的细节。例如，分组括号在树状结构中是隐含的，所以这些括号不需要作为单独的节点来表示。同样地，像if-condition-then语句这样的语法结构可以用一个有三个分支的节点来表示。这就把抽象的语法树与具体的语法树（传统上称为解析树）区分开来。在源代码翻译和编译过程中，解析树通常由解析器构建。一旦建成，通过后续处理，例如上下文分析，额外的信息被添加到AST中。抽象语法树也被用于程序分析和程序转换系统中。

抽象语法树是编译器中广泛使用的数据结构，用来表示程序代码的结构。语法树通常是一个编译器的语法分析阶段的结果。它经常作为程序的中间表示，通过编译器需要的几个阶段，对编译器的最终输出有很大影响。

一个AST有几个特性，可以帮助编译过程的后续步骤。一个AST可以被编辑和增强，它包含的每个元素都有属性和注释等信息。与源代码相比，AST不包括不必要的标点和定界符（大括号、分号、小括号等）。由于编译器的连续分析阶段，AST通常包含关于程序的额外信息。例如，它可以存储每个元素在源代码中的位置，允许编译器打印有用的错误信息。由于编程语言及其文档的固有性质，需要AST。语言在本质上往往是含糊不清的。为了避免这种模糊性，编程语言通常被指定为无语境语法（CFG）。然而，编程语言的某些方面往往是CFG所不能表达的，但却是语言的一部分，并被记录在其规范中。这些细节需要一个上下文来确定其有效性和行为。

例如，如果一种语言允许声明新的类型，CFG不能预测这种类型的名称，也不能预测它们的使用方式。即使一种语言有一套预定义的类型，强制执行正确的使用通常也需要一些上下文。另一个例子是鸭子类型，其中一个元素的类型可以根据上下文而改变。运算符重载是另一种情况，正确的用法和最终的功能都取决于上下文。

一个AST的设计通常与编译器的设计和它的预期功能密切相关。核心要求包括以下几点。变量类型必须被保留，以及每个声明在源代码中的位置。可执行语句的顺序必须被明确表示和很好地定义。二进制操作的左和右组件必须被存储和正确识别。对于赋值语句必须存储标识符和它们的赋值。这些要求可以用来设计AST的数据结构。有些操作总是需要两个元素，例如加法的两个项。然而，有些语言结构需要任意多的子元素，例如从命令外壳传递给程序的参数列表。因此，用于表示用这种语言编写的代码的AST也必须足够灵活，以允许快速增加未知数量的子元素。为了支持编译器的验证，应该可以将AST解读为源代码的形式。在重新编译时，产生的源代码应该与原始代码在外观上有足够的相似性，并且在执行上也是相同的。AST在语义分析中被大量使用，编译器检查程序和语言元素的正确用法。在语义分析期间，编译器还根据AST生成符号表。对树的完整遍历可以验证程序的正确性。在验证了正确性之后，AST作为代码生成的基础。AST经常被用来生成一个中间表示法（IR），有时被称为中间语言，用于代码生成。