前言
本文将介绍抽象语法树AST(abstract syntax tree)的相关内容.
之前的我们通过讲解语法规则和语法树的action讲到了可以通过在语法规则文件中添加action来进行定制操作,比如返回String类型的语义值.
生成语法树就是在语法规则中逐个编写action,最终生成的文件结构就是语法树.
节点
AST是由名为节点Node的数据结构构成的.下图表示为使用各自对应的节点来表示语句,表达式以及变量等.
所以,生成语法树的核心就是生成节点,下面我们会介绍如何在各个语法规则中生成对应的节点.
AST中用继承自 Node 类的子类来表示单个的节点,继承Node的类很多,层次也很复杂,我们现在只对一级继承的重要的类进行讲解
Node的location属性
我们只需要了解Node类中,会有一个特定的返回location的方法,location是节点对应的语法在代码中的位置,如果代码中存在错误的话,编译器会将出错的语句或表达式所在的文件和行数表示出来,而这些信息就是以location的形式返回的.
Node表示抽象语法树
Node类中会通过dump方法来以文本的形式表示抽象语法树.dump方法生成的语法树对象.
语法树对象大概有如下属性:
- 节点的类名
- 节点对应语法记载的文件名和行号
- 参数列表
- 等
各种类型生成抽象语法树
之后要学习的就是实际地在语法规则文件中添加生成抽象语法树的 action,通过实际例子来理解语法树生成的具体过程,需要分析生成的类型有
- 表达式的抽象语法树生成
- 语句的抽象语法树生成
- 声明的抽象语法树生成
这里涉及到具体的表达式,语句或者声明的设计和具体实现,其中结合了语法分析和语法分析中各个规则的组合使用,以及action的合理编写和对调用时机的控制,非常细节和琐碎,感兴趣的烤鸭具体查看,我们现在只列出类型,不讨论实现.
表达式的抽象语法树生成
本节我们将讲解表达式(expr)的抽象语法树的生成,该章节被细分为
- 字面量的抽象语法树
- 一元运算的抽象语法树
- 二元运算的抽象语法树
- 条件表达式的抽象语法树
- 赋值表达式的抽象语法树
赋值表达式中提到了运算规则的结合性(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语句以及程序块为代表来理解.
- if语句的抽象语法树
- while语句的抽象语法树
- 程序块的抽象语法树
声明的抽象语法树
本段内容是关于函数声明及变量声明对应的抽象语法树的生成.
- 变量声明列表的抽象语法树
- 函数定义的抽象语法树
- 表示声明列表的抽象语法树
- 表示程序整体的抽象语法树
- 外部符号的import
