形式陈述

抽象语法树是由语法构造子归纳生成的有限树；每个节点标签决定其子节点数量与类别。与具体语法树相比，AST 通常省略括号、分隔符和可由结构恢复的非终结符，只保留语义分析需要的构造。

直觉

源代码字符串先被解析为“程序由哪些子程序构成”的树。树形结构使作用域、类型和求值规则可以递归定义。

例子与边界

表达式 1 + 2 * 3 的 AST 根是加法，右子树是乘法，优先级已编码在结构中。不同表面语法可以映到同一 AST。若完全丢弃源位置或注释，会影响诊断与格式化，但不改变核心语义。

推论与应用

编译器在 AST 上进行名称解析、类型检查和变换；结构归纳证明也沿 AST 构造展开。后续 IR 可能改用控制流图或 SSA，但它们不是 AST 本身。

参考资料

• Robert Harper, Practical Foundations for Programming Languages, 2nd ed., Cambridge University Press, 2016, Chapters 1–4。
• Benjamin C. Pierce, Types and Programming Languages, MIT Press, 2002, Chapters 3–5。