- 抽象语法树（AST）表示程序的逻辑结构，消除了无关的语法细节。
- AST 由字母表、元数函数和树语法构成，定义了哪些节点和结构是有效的。
- 杜威分类法和运算符，例如“.”或“/”，可以精确地引用这些结构中的子树和路径。
- 编译器、解释器和代码分析工具都依赖抽象语法树 (AST) 来可靠地优化、转换和理解程序。
抽象语法树是编程中一个乍听之下非常理论化的概念，但一旦掌握了它，你就会发现它无处不在：编译器、解释器、代码分析、重构工具，甚至结构化数据查询语言中都有它的身影。本质上，它是机器“理解”程序结构（超越纯文本）的一种方式。
尽管抽象语法树（AST）有时会被误认为是经典的语法分析树，但它们有自己独特的规则。抽象语法树不仅仅是一张漂亮的图画：它是一种紧凑且设计精良的数据结构，它剔除了具体语法中所有多余的部分（例如括号、逗号、冗余关键字等），而专注于本质：执行哪些操作、操作对象是什么以及操作顺序是什么。
抽象语法树（AST）究竟是什么？
在编程语言理论中，抽象语法树（AST）是一种树状结构，它以简化的形式表示程序的语法，与具体的语法分析树相比，它包含与语法分析树相同的基本信息，但组织方式更加紧凑和易于管理。
句法分析树包含语法的所有产生式和所有终结符，包括括号、逗号、分号和其他纯粹的句法元素。而抽象语法树（AST）则去除这些不贡献语义的细节，只保留表达式和句子的逻辑结构。
在实现方面，抽象语法树 (AST) 通常由节点对象组成，节点对象具有类型，用于指示它是哪种语法结构（常量、标识符、函数应用、二元运算符等），以及描述其内容的附加属性：值、名称、子节点、参数列表等。
AST 的优点在于它有助于编译器或解释器的后续阶段，例如类型检查、优化或代码生成，因为它提供了程序结构的清晰视图，而没有语法噪声。
具体语法树和抽象语法树的区别
为了充分理解抽象语法树（AST）的作用，首先将具体的语法分析树与抽象语法分析树进行比较会很有帮助。想象一个简单的语法，它可以识别像“a + 4 * 5”这样的算术表达式。具体的语法分析树准确地反映了每条语法规则的应用：非终结符、终结符、括号、运算符等等。
这棵特殊的树通常很深，包含许多中间节点，这些节点仅用于维护语法的形式结构。例如，可能存在“表达式”、“项”、“因子”节点，以及诸如“+”、“*”之类的终结符、标识符和数字。每个产生式都成为树的一个分支，从而增加了结构的复杂性。
另一方面，同一表达式的抽象语法树仅限于表示实际的运算和操作数。因此，我们不再需要多层“表达式”和“项”，而可以用一个表示加法的根节点，它有两个子节点：左侧是标识符a，右侧是乘法节点，其子节点分别是值 4 和 5。纯粹的语法节点消失了，部分结构被重新排序或简化。
这意味着抽象语法树（AST）和具体的语法树包含相同的语义信息，但前者以更直接、更简洁的形式呈现。这种精简对于在分析或执行工具中高效处理代码至关重要。
具有元数函数的树和字母表
为了从数学角度形式化这些树，通常会使用带有元数函数的字母表。字母表并非简单地包含一组符号，而是定义了一个字母表，其中每个符号都与一个数字相关联，该数字表示该符号在树中可以有多少个子节点。
带有元数函数的字母表，通俗地讲，是由有限个符号和一个函数组成的二元组，该函数为每个符号分配一个自然数（包括零）。这个数表示符号的元数：如果为 0，则该符号作为叶节点；如果为 1，则作为一元节点；如果为 2，则为二进制节点；依此类推。通常也允许运算符的参数列表使用可变元数的符号。
元数为 0 的符号对应于树的叶子节点（例如，常量或标识符）。元数为 1 的符号用于包含单个子表达式的结构。元数为 2 的符号表示经典的二元运算，例如加法、乘法、赋值等。而元数可变的符号允许对接受不确定数量子树的结构进行建模，例如带有多个参数的函数调用。
从这个具有 k 个元数的字母表中，可以定义所有可能的树的集合：从空树（如果考虑的话）开始，添加所有元数为 0 和可变的符号，并进行归纳扩展：如果一个符号是 k 元的，它可以作为 k 个已构造子树的父节点。这样就得到了与该字母表关联的树语言（或术语）。
树状语言和节点的概念
在此上下文中，由字母表及其元数函数构成的所有树的集合被称为树语言或项语言。它相当于克莱恩闭包对字符串的作用，只不过是针对树结构而言。
就像分析字符串时我们用“标记” （token）一词来指代序列中字母符号的出现次数一样，处理树时我们通常使用“节点” （node）一词。本质上，节点是指树中特定位置上具有特定元数的字母符号的具体出现次数。
从这个角度来看，树状语言之于节点，正如字符串集合之于词元出现次数。每棵树都被解释为由字母表逐步构建而成的结构，而节点则是构成其符号的各个组成部分。
这种看待问题的方式在设计解析器和 AST 生成器时非常有用，因为它允许以类似于字符串语法的方式推理这些树的构造规则，但直接作用于层次结构。
特定抽象语法树（AST）中节点的元数：以 Egg 为例
从理论到实践，许多教学材料都使用Egg语言来演示抽象语法树 (AST) 的构建和操作。在 Egg 语言中，使用了几种主要的节点类型，每种节点都有明确定义的元数，这使得操作起来非常容易。
在典型的 Egg AST 中， VALUE节点被视为叶子节点：它们代表字面量，例如字符串或数字。它们没有子节点；它们只存储一个值。类似地，用于标识符（变量名、函数名等）的 WORD 节点也被视为叶子节点，并具有一个存储名称的属性。
Egg 中的关键节点是APPLY类型，它表示函数或运算符的应用。这种节点类型有两个概念上的子节点：一个OPERATOR子节点，指向正在应用的表达式；以及一个ARGS子节点，它实际上是一个特殊的 ARRAY 节点，负责维护一个子树集合，每个参数对应一个子树。
因此，数组是向 AST 中引入可变参数量的自然方法：APPLY 始终有两个组成部分（运算符和参数列表），但该内部列表可以包含零个、一个或多个子树，具体取决于所表示的特定调用。
Egg 中 AST 结节的详细解剖结构
在实现层面，Egg 的抽象语法树 (AST) 节点通常表示为带有属性的对象，这与 JavaScript 等语言完美契合。所有节点都共享一个公共属性：`type`，它标识节点类型（VALUE、WORD、APPLY、ARRAY 等），从而决定对象其余部分的结构。
VALUE 节点用于表示字面常量。它们包含一个属性，通常称为value，其中存储了它们所代表的数字或字符串。它们没有其他子节点，因为它们的内容已完全由该字面值描述。
词节点专用于存储标识符：变量名、函数名、参数名等等。它们通常有一个`name`属性，用于存储字符串形式的标识符。与值节点类似，它们在树中充当叶节点，因为它们的唯一作用就是提供名称。
应用节点代表应用或调用。它们包含一个运算符属性，指向被应用的表达式（另一个节点）；以及一个参数属性，链接到一个数组节点。后者是抽象语法树 (AST) 中的一个特定节点，其目的是保存应用的参数列表。
ARRAY 节点可以理解为其他节点的结构化容器，代表一系列子树。从参数数量的角度来看，它引入了灵活性，因为它允许在同一个 APPLY 语句中使用无参数、单参数或多参数调用，而无需更改主节点类型的定义。
AST示例：只有一个值的简单应用程序
为了形象化以上所有内容，让我们考虑一下简单指令的表示，例如使用单个参数 5 应用函数 X。解析器生成的 AST 对应于一个由 VALUE、WORD 和 APPLY 节点构造的项，遵循 Egg 的规则。
从概念层面来说，我们会在根节点放置一个APPLY节点。它的 operator 属性指向一个名为 X 的 WORD 节点，而它的 args 属性指向一个包含单个元素的 ARRAY 节点：一个数值为 5 的 VALUE 节点。这样，该结构就清晰地反映了操作对象和操作内容。
如果我们想明确所有属性，可以编写更详细的表示法，显示类型、运算符、参数、名称和值。这种更详尽的表示法对于调试解析器或理解文本表达式如何在解释器中被转换为树对象非常有用。
在实际应用中，这棵树通常会被序列化为JSON格式，以便于存储、传输或检查。事实上，诸如npm 生态系统中的evm2term包之类的工具和模块，提供了这些抽象语法树 (AST) 的紧凑表示形式，方便进行分析或转换。
抽象语法树示例：嵌套加法和乘法
另一个典型例子是稍微复杂一些的表达式，例如“+(a, *(4, 5))”。这里我们有一个加法运算，它的第一个参数是标识符 a，第二个参数是 4 乘以 5 的结果。该表达式生成的抽象语法树 (AST) 反映了这种嵌套结构。
在树的根节点，我们再次会看到一个 APPLY 节点，它代表加法运算。它的运算符是一个名为“+”的 WORD 节点，而它的参数则位于一个包含两个元素的 ARRAY 节点中：第一个元素是一个名为“a”的 WORD 节点；第二个元素是另一个 APPLY 节点，它代表乘法运算。
第二个 APPLY 运算符的参数是一个名为“*”的 WORD，参数是一个包含两个 VALUE 节点的 ARRAY：一个节点的值为 4，另一个节点的值为 5。从整体上看，该结构清楚地表明，求值顺序是将 4 乘以 5，然后将结果加到 a 上。
如果我们扩展这种表示法，使其包含所有属性，我们就能看到所有节点的类型、名称或具体值，以及它们之间的关系。这种明确的描述与 Egg 解释器中的实际实现相对应，其中每个节点都是一个具有上述属性的对象。
树语法和解析器语法
这些抽象语法树的生成方式并非任意的：它基于所谓的树文法。在典型的表述中，这种文法被定义为一个四元组，由一个具有n个元数的字母表、一个有限的句法（非终结符）变量集、一个有限的产生式规则集和一个起始符号组成。
在每条产生式规则中，一个变量被替换为一棵树，该树的根节点是具有指定元数的字母表符号，其子节点则依次为变量或已定义的树。这种结构类似于经典的正则文法或上下文无关文法，但它适用于直接生成树而不是符号串。
与此更正式的定义相关的是 Egg 解析器用于生成其树的特定语法。该语法通常在文档中以非正式的方式呈现，它精确地描述了语言中接受哪些关键字、运算符、括号等的组合，以及它们如何转换为 VALUE、WORD、APPLY 和 ARRAY 类型的节点。
这种树语法可以看作是文献中所谓的正则树语法的一个特例。其核心思想是拥有明确定义的规则，用于将输入标记序列转换为结构化的抽象语法树（AST），然后对其进行解释或编译。
杜威分类法：树状图中的坐标
一旦我们有了抽象语法树 (AST)，我们经常需要引用特定的子树：例如，函数的第二个参数、表达式的运算符等等。一种非常优雅的方法是所谓的杜威十进制表示法，它借鉴了用于对文档中的章节和子章节进行编号的方案。
在这种表示法中，从树 t 开始，子树用一串以句点分隔的数字表示。每个数字表示一个子节点的位置（通常从 1 开始），序列沿着树向下排列。因此，像 t/2.1.3 这样的表达式指的是 t 的第二个子节点的第一个子节点的第三个子节点。
这种表示法的归纳定义很简单：空字符串指的是整棵树本身；如果一个字符串由一个数字和更多用句点分隔的数字组成，则首先取与指定索引对应的子树，然后递归地将相同的逻辑应用于字符串的其余部分。
例如，假设我们有一个树 t，它表示一个表达式“+(a, *(4,5))”，根节点是 APPLY（加法），子节点是 WORD（加号），另一个子节点是 APPLY（乘法），我们可以确定具体的节点位置。因此，如果我们对子节点进行适当的编号， t/1可以是运算符为“+”的 WORD 节点，t/2.1 可以是标识符为“a”的 WORD 节点，t/2.2.2.1 可以是值为 4 的 VALUE 节点。
在 AST 中给出“坐标”的方式对于在报告错误、导航树或对特定节点应用局部变换时指出特定位置非常有用，而且不会产生歧义。
编程和工具中的等效符号
杜威符号背后的思想并非树论所独有；事实上，它反复出现在我们日常编程和结构化数据处理中使用的许多实用符号中，即使我们并不总是意识到这一点。
在编程语言中，当我们使用点运算符编写表达式（例如 object.property.subproperty）时，我们实际上是在做类似的事情：遍历嵌套对象树，每一步都通过名称而不是位置编号来选择子对象。从根节点开始，我们向下遍历到更深层的节点。
同样的模式也出现在类 Unix 文件系统中，其中使用正斜杠运算符 (/)来分隔目录：/src/js/tutu.js 描述了从文件系统根目录到特定资源的路径，遍历树结构的连续层级。
在结构化文档领域，像XPath这样的语言使用非常相似的符号来选择 XML 树中的节点。例如，“A//B/*”这样的查询会选择元素 A 的后代元素 B 的第一个子元素（无论其名称如何），该子元素的位置取决于当前上下文，并使用单斜杠和双斜杠来表示深度级别。
另一个知名的工具jq语言使用并行系统来浏览 JSON 结构，允许通过复合路径、过滤器和表达式来选择子对象。所有这些表示法都只是在树状结构中表达路径的不同方式，与杜威十进制分类法非常相似，但都针对各自的领域进行了调整。
语言学和编程中的句法分析树
除了编译器领域之外，语法树在语言学中也用于表示句子结构。在语言学中，它们被称为推导树或句法分析树，展示了句子是如何分解成短语、单词和语法范畴的。
在这些树中，就像在编程中一样，我们发现了三种基本类型的节点：根节点，它代表完整的句子或全局结构；内部节点或分支节点，它们充当父节点并将句子的子集分组；以及叶节点，它们通常对应于输入字符串中出现的特定单词。
根节点是唯一的：整个树状结构都依附于它。分支节点位于根节点或其他父节点的正下方，用于按层次结构组织句子或程序的各个部分。而叶节点则位于树的最底层，没有子节点，从而封闭了分支结构。
这些树状图被认为是强大的教学工具，因为它们有助于将复杂的句子分解成易于理解的元素。这同样适用于编程：一个结构良好的抽象语法树（AST）可以让你一目了然地看到哪些操作是串联在一起的，哪些表达式是嵌套的，以及求值是如何进行的。
根据分析目标的不同，我们可以找到不同类型的分析树。有些分析树强调词语或成分之间的依赖关系（例如，句子中谁依赖于谁），而另一些则侧重于将词语或成分分组，从而形成两大类分析树。
按依存关系和按成分划分的语法树
依存句法树是其中一种最广为人知的类型。在这种变体中，句子中的所有词或所有相关元素都被视为叶节点，它们之间的连接表示直接的依存关系（例如，主要动词及其主语）。因此，与其他方案相比，这种方案通常能生成节点更少的树。
这种简洁性使得它们对初学者和某些语言处理任务尤为方便，因为其结构专注于关系依存，而无需引入过多的中间节点。应用于编程时，其理念是只关注必要的关系，省略语法修饰。
另一方面，我们还有基于成分或组成部分的句法树，它们区分根节点、内部分支节点和叶节点，并将所有相关的分组清晰地呈现出来。这些树通常包含更多节点，并能更详细地反映句子或程序的层级结构。
常见的成分树模板通常展示具有众多叶节点、多层分支和一个明确根节点的长句。它们尤其适用于剖析具有多层嵌套结构的复杂句子或程序。
在依存关系树和组成关系树中，示例和可视化资源均以模板形式提供，您只需填写所需信息即可。这节省了时间，避免了每次需要展示结构时都必须从头开始设计图表。
与AST相关的实际应用和工具
抽象语法树（AST）并非仅仅是一个理论概念：任何与代码打交道的人都会在各种日常工具中积极使用它们。编译器、解释器、代码压缩器、代码格式化工具和静态分析器几乎都依赖 AST 来执行其功能。
典型的编译器会获取源代码，对其进行词法分析、语法分析，并生成抽象语法树（AST）。然后，它会执行语义检查（类型、变量作用域、结构使用不当等），并通过遍历和转换 AST 来进行代码优化，最终生成机器代码，即字节码。
代码检查器或格式化器等工具也适用于抽象语法树 (AST)：它们分析结构以检测问题模式、不良实践或不一致之处，并提出更改以保持树的语义结构，但调整代码的呈现方式。
例如，在 JavaScript 生态系统中，有多个库以 JSON 格式公开 AST，这使得其他工具更容易依赖它来执行重构、生成自动文档或创建复杂程序结构的可视化。
即使在一些更专业的领域，例如用于测量测试覆盖率的工具或将源代码转换为其他语言，AST 也是许多现代解决方案的基础，因为它允许在原始文本和机器代码之间非常舒适的抽象级别上工作。
总而言之，抽象语法树是连接语言形式语法、编译器或解释器内部表示以及我们用于安全高效地编写、分析和转换代码的高级工具的关键所在。理解它们的构造方式、如何浏览它们（例如使用杜威十进制分类法）以及涉及哪些类型的节点（VALUE、WORD、APPLY、固定或可变元数结构等），有助于我们更清晰地了解机器在处理程序时实际执行的操作。
