第三章抽象语法树

1第三章抽象语法树在现代编译器的构造过程中，前端主要实现从源程序到中间形式（IntermediateRepresentation）的转换，而编译器的后端用来完成从中间形式到具体目标机代码的转换，这是一种广泛采用的编译器构造模型。虽然源程序到目标程序的直接转换是可行的，但是使用独立于具体目标平台的中间形式有以下优点：（1）使用中间形式可以比较容易地构造面向不同目标平台和不同语言的编译器。在不改动已有编译器前端的情况下，为新的目标平台构造一个生成该平台目标程序的后端，就可以构造出新平台的编译器。同样对于一个新的语言，在不改动已有编译器后端的情况下，为新语言构造一个识别该语言的前端，就可以构造出新语言的编译器。（2）针对中间形式，可以进行独立于目标平台的代码优化。这样可以生成较高质量的目标代码，在此基础上可以对目标代码进行平台相关的优化，进而生成更高质量的目标代码。使用中间形式的主要缺点是，产生中间代码的编译过程与不产生中间代码的编译过程相比在效率上会显得有些低。这是因为中间代码还要进行再一次的翻译才能生成目标代码。但是，增加一层中间形式可以使编译器更好地模块化，并且可以在中间形式上做很多优化，这些足以抵消两次翻译所带来的低效率。所以，很多现代的编译器都使用了中间形式，比较常见的中间形式有逆波兰表示，N元表示和树形表示三种。由于，在本系统中，我们使用抽象语法树作为中间形式，所以不再对前两种中间形式做以介绍，感兴趣的读者可以参考《编译原理》（AlfredV.Aho编著）。3.1树形表示树形表示是一种非常流行的中间形式，它与三元式表示有着密切的关系，三元式表示可以看成是树形表示的直接形式。例如，表达式W*X+(Y+Z)的树形表示如图3.1所示：图3.1表达式W*X+(Y+Z)的树形表示++*ZZY+XW2在现代编译器的构造过程中，经常使用抽象语法树（AbstractSyntaxTree）作为一种中间形式，这样做可以把翻译过程从语法分析过程中分离出来，使得层次非常清晰。引入抽象语法树是基于多方面原因的，其中的一个原因在于适于语法分析的文法可能并不反映语言成分的自然层次结构。比如Fortran的文法可能把子程序看成是简单的语句序列，而这并不能反映出DO循环的嵌套。如果我们采用能够反映DO循环嵌套的树形表示，那么子程序的语义分析将会更容易一些。因此，很多编译器经常要构造语法树。在这里我们之所以称其为“抽象”语法树，是因为抽象语法树的结构不依赖于被编译语言的原文法，也就是语法分析阶段所采用的文法。在语法分析过程中，为了能够适应摸中分析方法的需要，有时需要对文法进行等价的转换（比如，消除左递归，避免回溯等），这些转换在采用特定的分析方法进行语法分析时是有必要的，但是这样做同时也会带来一些问题。比如，会引入多余的非终结符和多余的产生式等，所有这些多余的成分都会对下面的编译阶段产生一定的限制，甚至会使各阶段变得非常混乱。按照这些文法进行推导时，每一个正确的输入在理论上都对应一个依赖于这些文法的具体分析树。但是正如上面提到的，这种分析数不大适合直接使用，所以我们引入了抽象语法树。抽象语法树在语法分析和后面的各编译阶段之间建立了一个清晰的接口，它能够反映源程序本身的语法结构。基于以上原因，抽象语法树在现代编译器的构造中使用得越来越广泛，本系统也构造了抽象语法树。下面我们先简单的介绍一下语法分析树和抽象语法树，并对它们做以简单的比较。语法分析树也称为具体语法树，因为这种树中的一切都是明示的，完全而又具体，显示了如何根据相应上下文无关文法推导出特定的单词序列。在我们知道了一个单词序列为合法之后，后续的编译阶段就不再需要语法分析树上的许多信息了。因此，语法分析结束以后，一般会将这种语法分析树转换为一棵抽象语法树（又称AST，简称语法树），删除树内部的大部分“人为”结点，并对剩下的结点标注有用的信息。附在特定节点上的标注被称为它的属性。例如语句if(ab)a=a-b;的语法分析树和抽象语法树分别可表示成图3.2和图3.3。图3.2语句if(ab)a=a-b的语法分析树=if＞aZa+babaZZ﹣Z3图3.3语句if(ab)a=a-b的抽象语法树在许多编译器里，带标注的语法树就是从前端传递到后端的中间形式，而在另一些编译器里，语义分析器最后可能还要遍历这棵树，生成某种另外的中间形式。本系统将这种语法树作为中间表示，不再对它做一步的转换3.2系统抽象语法树的节点表示While语句节点产生式：while-stmt→while(expression)statementwhile语句的抽象语法树说明：对于while语句，根节点是while，第一个孩子节点表示条件(expression)，第二个孩子节点是条件为真的时候的执行语句(statement)。这些说明部分在下面的抽象语法树图中是很直观的表示，因此以下语句结点语法树将不再赘述。图3.4while语句的抽象语法树If语句节点表示产生式：if-stmt→if(expression)statement[elsestatement]图3.5If语句的抽象语法树If语句expressionstatementelseChild[0]Child[1]Child[2]While语句expressionstatementChild[0]Child[1]If语句条件部分Then部分Else部分4函数声明节点产生式：fun-declaration→(void|int)ID(params)compound-stmt图3.6函数声明的语法树表达式语句节点产生式：expression→ID=expression|simple-expressionsimple-expression→additive-expression[relopadditive-expression]relop→|=||=|==|!=additive-expression→term[(+|-)term]term→factor[(*|/)factor]factor→(expression)|ID|call|NUM图3.7表达式语句的语法树程序节点产生式：program→{var-declaration|fun-declaration}图3.8程序的语法树例：如下程序段代码：intpi;intadd(intx,inty)全局变量函数函数siblingsibling参数列表childchildchild函数定义节点语句1语句2sibling参数1参数2siblingChild[0]Child[1]函数名返回类型=+-IDID5{returnx+y;}voidmain(){…}语法分析结束后生成的抽象语法树如下图3.9所示：图3.9生成的语法树3.3抽象语法树的设计在本章前面几节中，我们介绍了抽象语法树的基本概念，与语法分析树的比较以及在系统中抽象语法树的节点表示。在本节中，我们将详细讲解本系统中抽象语法树节点设计，并且对抽象语法树的实现代码做以解释。抽象语法树的节点类型如下所示：//抽象语法树的节点类型publicenumNodeType{FunDecl,VarDecl,Para,ADD,SUB,MUL,DIV,REQ,RLT,RGT,RNEQ,RNGT,RNLT,AssignStm,IfStm,IfElseStm,ElseStm,WhileStm,ReturnStm,FunCall,ConstID,VarID,OTHER,ERROR……};在此基础上，我们再给出了抽象语法树的节点定义，见第二章表2.1。下面，我们给出抽象语法树的实现代码并给出必要的解释。所给出的代码与文件parser/Parser.cs中的源代码略有不同，但是基本思路一致，为了便于读者理解，parser/Parser.cs特改写成以下代码形式：piaddmainsiblingsiblingChild【0】Child【1】xsiblingreturn+xChild【1】Child【0】yy6classParser{Tokencurtoken;voidparse(){curtoken=getNextToken();//取得第一个tokenTreeNoderoot=null;root=program();//递规下降分析！构建语法树，并返回根节点}函数parse()：这个函数所做的工作就是从词法分析所生成的单词序列中取得第一个单词Token，然后，调用program()函数，构建抽象语法树，并返回抽象语法树的根节点；voidmatch(TokenTypeexpected){if(curtoken.TType==expected)curtoken=getNextToken();elseParseError();}函数match(TokenTypeexpected)：用来通过将当前单词类型与语法上应该出现的正确单词类型进行比较，检查是否有语法错误。如果没有语法错误，则从单词序列中取得下一个单词，以便后面继续进行语法分析，构建抽象语法树使用，如果出现语法错误，则调用函数ParseError()进行出错处理；TreeNodeprogram(){Tokenp,q;p=root;while(curtoken.TType!=TokenType.ENDFILE){if(curtoken.TType==TokenType.FunDecl)q=fun_decl();if(curtoken.TType==TokenType.VarDecl)q=var_decl();p.Sibling=q;p=p.Sibling;}Returnroot;}TreeNodevar_decl(){函数program()：此函数的作用是进行递归下降分析，生成抽象语法树，返回抽象语法树的根节点root。这个函数中的变量p用来记录前一次所生成的节点，变量q用来记录当前所生成的节点。TreeNoderetnode,nextnode,curnode;retnode=curnode;retnode.NType=curnode.NType=NodeType.VarDecl;while(curtoken.TType!=TokenType.SEMI){Switch(curtoken.TType){caseTokenType.INT:match(TokenType.INT);break;caseTokenType.ID:nextnode.NodeStr=curtoken.str;curnode.Sibling=nextnode;curnode=nextnode;match(TokenType.ID);break;7caseTokenType.COMMA:match(TokenType.COMMA);break;default:ParseError();break;}}Match(TokenType.SEMI);Returnretnode;}函数var_decl()：这个函数实现了一个变量声明语句的抽象语法树节点的构建，并且返回其根节点retnode。这里的变量声明仅限于简单变量，且数据类型为整型。TreeNodefun_decl(){TreeNoderetnode;retnode.NType=NodeType.FunDecl;While(curtoken.TType!=TokenType.LPAREN){Switch(curtoken.TType){caseTokenType.INT:caseTokenType.VOID:retnode.retType=curtoken.str;match(curtoken.TType);break;caseTokenType.ID:retnode.NodeStr=curtoken.str;match(TokenType.ID);break;default:ParseError();break;}}match(TokenType.LPAREN);if(token.TType!=TokenType.RP