抽象语法

形式陈述 ​

抽象语法以一组构造子归纳定义程序项，而不把空格、括号优先级、关键字拼写等具体记号保留为语义对象。例如简单表达式可由

生成。形式上，这给出满足下列闭包条件的最小集合 $\mathrm{Expr}$：

1. 每个数值字面量 $n$ 产生项 $\mathrm{num}(n)$；
2. 若 $e_1,e_2\in \mathrm{Expr}$，则 $\mathrm{add}(e_1,e_2)\in \mathrm{Expr}$；
3. 若 $x$ 是变量且 $e_1,e_2\in \mathrm{Expr}$，则 $\mathrm{let}(x,e_1,e_2)\in \mathrm{Expr}$。

具体语法字符串经词法分析与解析映射到抽象语法项。该映射可以把 1 + (2) 与 1+2 送到同一项，也可在语法糖消解后把多种表面形式送到同一个核心构造。

带绑定子的抽象语法还必须规定自由变量、替换和 $\alpha$-等价。此时“变量名完全相同”通常不是语义上对象相同的最终标准。

直觉 ​

抽象语法回答“程序由哪些结构组成”，具体语法回答“用户怎样写出来”。括号、缩进和分号帮助解析；解析完成后，语义规则通常只关心加法、函数、绑定与控制结构等构造子。

抽象语法是一类数学项，不等同于某种内存布局。树、DAG、de Bruijn 索引、显式共享图和高阶抽象语法都可表示同一抽象结构，各自改变实现成本或绑定处理方式，却不应改变语言定义。

例子与边界 ​

字符串

1 + 2 * 3

在给定优先级后解析为

若语言改为加法优先，同一字符串会映射到不同抽象项；因此解析约定属于具体语法到抽象语法的映射，而不是抽象语法项内部的事实。

宏展开、类型标注消除和 desugaring 常产生多层抽象语法。源语言 AST 与核心语言项不能在未给转换函数时混用。带共享的表达式在内存中可能是 DAG，强行复制为树会改变空间成本，但不必改变展开后的抽象项。

推论与应用 ​

抽象语法树公理库抽象语法树Abstract syntax tree · AST把抽象语法构造表示为有根有序树的常见编译器数据结构。是最常见的具体表示，而不是抽象语法本身。变量绑定公理库变量绑定Variable binding · Binding occurrence语法中的绑定出现将变量使用关联到其作用域内声明。定义自由变量、捕获规避替换与 $\alpha$-等价；操作语义公理库操作语义Operational semantics用执行判断、转移规则或抽象机定义程序如何运行。和类型系统则在抽象语法项上归纳给出判断与规则。

编译器前端把源文本转换为抽象语法，后续控制流构造、类型检查、优化与代码生成都应明确自己消费的是哪一层语言。证明语义保持时，也必须区分表面语法、核心语法与目标中间表示。