第三章抽象语法树..doc

第三章 抽象语法树 在现代编译器的构造过程中，前端主要实现从源程序到中间形式（Intermediate Representation）的转换，而编译器的后端用来完成从中间形式到具体目标机代码的转换，这是一种广泛采用的编译器构造模型。虽然源程序到目标程序的直接转换是可行的，但是使用独立于具体目标平台的中间形式有以下优点： （1）使用中间形式可以比较容易地构造面向不同目标平台和不同语言的编译器。在不改动已有编译器前端的情况下，为新的目标平台构造一个生成该平台目标程序的后端，就可以构造出新平台的编译器。同样对于一个新的语言，在不改动已有编译器后端的情况下，为新语言构造一个识别该语言的前端，就可以构造出新语言的编译器。 （2）针对中间形式，可以进行独立于目标平台的代码优化。这样可以生成较高质量的目标代码，在此基础上可以对目标代码进行平台相关的优化，进而生成更高质量的目标代码。 使用中间形式的主要缺点是，产生中间代码的编译过程与不产生中间代码的编译过程相比在效率上会显得有些低。这是因为中间代码还要进行再一次的翻译才能生成目标代码。但是，增加一层中间形式可以使编译器更好地模块化，并且可以在中间形式上做很多优化，这些足以抵消两次翻译所带来的低效率。所以，很多现代的编译器都使用了中间形式，比较常见的中间形式有逆波兰表示，N元表示和树形表示三种。由于，在本系统中，我们使用抽象语法树作为中间形式，所以不再对前两种中间形式做以介绍，感兴趣的读者可以参考《编译原理》（Alfred V.Aho编著）。 3.1 树形表示 树形表示是一种非常流行的中间形式，它与三元式表示有着密切的关系，三元式表示可以看成是树形表示的直接形式。例如，表达式W*X+(Y+Z)的树形表示如图3.1所示： 图3.1 表达式W*X+(Y+Z)的树形表示 在现代编译器的构造过程中，经常使用抽象语法树（Abstract Syntax Tree）作为一种中间形式，这样做可以把翻译过程从语法分析过程中分离出来，使得层次非常清晰。引入抽象语法树是基于多方面原因的，其中的一个原因在于适于语法分析的文法可能并不反映语言成分的自然层次结构。比如Fortran的文法可能把子程序看成是简单的语句序列，而这并不能反映出DO循环的嵌套。如果我们采用能够反映DO循环嵌套的树形表示，那么子程序的语义分析将会更容易一些。因此，很多编译器经常要构造语法树。 在这里我们之所以称其为“抽象”语法树，是因为抽象语法树的结构不依赖于被编译语言的原文法，也就是语法分析阶段所采用的文法。在语法分析过程中，为了能够适应摸中分析方法的需要，有时需要对文法进行等价的转换（比如，消除左递归，避免回溯等），这些转换在采用特定的分析方法进行语法分析时是有必要的，但是这样做同时也会带来一些问题。比如，会引入多余的非终结符和多余的产生式等，所有这些多余的成分都会对下面的编译阶段产生一定的限制，甚至会使各阶段变得非常混乱。按照这些文法进行推导时，每一个正确的输入在理论上都对应一个依赖于这些文法的具体分析树。但是正如上面提到的，这种分析数不大适合直接使用，所以我们引入了抽象语法树。抽象语法树在语法分析和后面的各编译阶段之间建立了一个清晰的接口，它能够反映源程序本身的语法结构。 基于以上原因，抽象语法树在现代编译器的构造中使用得越来越广泛，本系统也构造了抽象语法树。下面我们先简单的介绍一下语法分析树和抽象语法树，并对它们做以简单的比较。 语法分析树也称为具体语法树，因为这种树中的一切都是明示的，完全而又具体，显示了如何根据相应上下文无关文法推导出特定的单词序列。在我们知道了一个单词序列为合法之后，后续的编译阶段就不再需要语法分析树上的许多信息了。因此，语法分析结束以后，一般会将这种语法分析树转换为一棵抽象语法树（又称AST，简称语法树），删除树内部的大部分“人为”结点，并对剩下的结点标注有用的信息。附在特定节点上的标注被称为它的属性。 例如语句if(ab) a = a-b;的语法分析树和抽象语法树分别可表示成图3.2和图3.3。 图3.2 语句if(ab) a = a-b的语法分析树 图3.3语句if(ab) a = a-b的抽象语法树 在许多编译器里，带标注的语法树就是从前端传递到后端的中间形式，而在另一些编译器里，语义分析器最后可能还要遍历这棵树，生成某种另外的中间形式。本系统将这种语法树作为中间表示，不再对它做一步的转换 系统抽象语法树的节点表示 While语句节点 产生式： while-stmt→ while( expression ) statement while语句的抽象语法树 说明：对于while语句，根节点是while，第一个孩子节点表示条件