> For the complete documentation index, see [llms.txt](https://mashplant.gitbook.io/decaf-doc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://mashplant.gitbook.io/decaf-doc/pa1a/chou-xiang-yu-fa-shu.md).

# 抽象语法树

当lexer和parser成功解析一个字符串时，输出结果是一棵抽象语法树(ast，abstract syntax tree)。

ast是指一种只跟我们关心的内容有关的语法树表示形式。抽象语法是相对于具体语法而言的，所谓具体语法是指针对字符串形式的语法规则，而且这样的语法规则没有二义性，适合于指导语法分析过程。抽象语法树是一种非常接近源代码的中间表示，它的特点是：

1. 不含我们不关心的终结符，例如逗号等
2. 不具体体现语法分析的细节步骤，例如对于`List -> List E | E`这样的规则，按照语法分析的细节步骤来记录的话应该是一棵二叉树，但是在ast中我们只需要表示成一个`Vec`，这样可能更高效且便于后续处理
3. 可能在结构上含有二义性，例如加法表达式在抽象语法中可能是`Expr -> Expr + Expr`，但是这种二义性并不影响对于ast的分析，因为现在已经获得了ast，脱离了具体语法，源程序中的优先级和结合性等都已经没有意义了
4. 依然能体现源程序的语法结构

使用抽象语法树表示程序的最大好处是把语法分析结果保存下来，后面可以反复利用。

在oo的语言中描述ast往往使用继承的结构，一般而言产生式的左端项为基类，每种右端项对应于一个子类。但在rust中，更常用的表示方法是使用enum这个内建的tagged-union机制。

然而rust完全不支持继承，在ast的表示上也的确造成了一些麻烦。ast的一种常见的模式是，许多种节点(例如各种`Expr`)包含一些公有的成员(如类型和位置)，每个节点也有自己独有的成员。如果想在rust中表示这种模式，就像框架中使用的一样，是将每个节点特有的成员放在enum中，作为一个struct的成员。例如框架中`Expr`的实现：

```rust
pub struct Expr<'a> {
  pub loc: Loc,
  pub ty: Cell<Ty<'a>>,
  pub kind: ExprKind<'a>,
}

pub enum ExprKind<'a> {
  VarSel(VarSel<'a>),
  IndexSel(IndexSel<'a>),
  ...
}
```

这样看起来还是不太直接，而且想从各个节点中访问公有的成员比较困难。我认为描述ast的节点一个更方便的结构是类似于scala中的`case class`或者kotlin中的`sealed class`，既支持继承，也支持模式匹配。rust中没有内置的机制支持这样的结构，只能说现在这个方案还算可以接受，我个人不是很满意。