抽象语法树

当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的实现:

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中没有内置的机制支持这样的结构,只能说现在这个方案还算可以接受,我个人不是很满意。

Last updated