前言

本文将介绍抽象语法树AST(abstract syntax tree)的相关内容.
之前的我们通过讲解语法规则和语法树的action讲到了可以通过在语法规则文件中添加action来进行定制操作,比如返回String类型的语义值.
生成语法树就是在语法规则中逐个编写action,最终生成的文件结构就是语法树.

节点

AST是由名为节点Node的数据结构构成的.下图表示为使用各自对应的节点来表示语句,表达式以及变量等.

抽象语法树和节点

所以,生成语法树的核心就是生成节点,下面我们会介绍如何在各个语法规则中生成对应的节点.
AST中用继承自 Node 类的子类来表示单个的节点,继承Node的类很多,层次也很复杂,我们现在只对一级继承的重要的类进行讲解

重要的节点类

Node的location属性

我们只需要了解Node类中,会有一个特定的返回location的方法,location是节点对应的语法在代码中的位置,如果代码中存在错误的话,编译器会将出错的语句或表达式所在的文件和行数表示出来,而这些信息就是以location的形式返回的.

Node表示抽象语法树

Node类中会通过dump方法来以文本的形式表示抽象语法树.dump方法生成的语法树对象.
语法树对象大概有如下属性:

• 节点的类名
• 节点对应语法记载的文件名和行号
• 参数列表
• 等

各种类型生成抽象语法树

之后要学习的就是实际地在语法规则文件中添加生成抽象语法树的 action,通过实际例子来理解语法树生成的具体过程,需要分析生成的类型有

1. 表达式的抽象语法树生成
2. 语句的抽象语法树生成
3. 声明的抽象语法树生成

这里涉及到具体的表达式,语句或者声明的设计和具体实现,其中结合了语法分析和语法分析中各个规则的组合使用,以及action的合理编写和对调用时机的控制,非常细节和琐碎,感兴趣的烤鸭具体查看,我们现在只列出类型,不讨论实现.

表达式的抽象语法树生成

本节我们将讲解表达式(expr)的抽象语法树的生成,该章节被细分为

1. 字面量的抽象语法树
2. 一元运算的抽象语法树
3. 二元运算的抽象语法树
4. 条件表达式的抽象语法树
5. 赋值表达式的抽象语法树

赋值表达式中提到了运算规则的结合性(associativity),如果x OP y OP z的含义为(x OP y) OP z,则称运算符OP为左结合(left
associative),如果含义为 x OP (y OP z),则称运算符 OP 为右结合(right associative).一般二元运算符都是左结合,只有赋值运算符=是右结合的.

随便提一下,还存在既非左结合也非右结合的二元运算符。例如 ==,因此 x==y ==z这样的表达式的语法是错误的.像这样不允许x OP y OP z的运算符称为非结合(non- associative)运算符.

语句的抽象语法树

想了解语句的抽象语法树生成,可以以if语句(stmt)和while语句以及程序块为代表来理解.

1. if语句的抽象语法树
2. while语句的抽象语法树
3. 程序块的抽象语法树

声明的抽象语法树

本段内容是关于函数声明及变量声明对应的抽象语法树的生成.

1. 变量声明列表的抽象语法树
2. 函数定义的抽象语法树
3. 表示声明列表的抽象语法树
4. 表示程序整体的抽象语法树
5. 外部符号的import