第三章 抽象語(yǔ)法樹(shù)

1、第三章 抽象語(yǔ)法樹(shù)在現(xiàn)代編譯器的構(gòu)造過(guò)程中，前端主要實(shí)現(xiàn)從源程序到中間形式（Intermediate Representation）的轉(zhuǎn)換，而編譯器的后端用來(lái)完成從中間形式到具體目標(biāo)機(jī)代碼的轉(zhuǎn)換，這是一種廣泛采用的編譯器構(gòu)造模型。雖然源程序到目標(biāo)程序的直接轉(zhuǎn)換是可行的，但是使用獨(dú)立于具體目標(biāo)平臺(tái)的中間形式有以下優(yōu)點(diǎn)：（1）使用中間形式可以比較容易地構(gòu)造面向不同目標(biāo)平臺(tái)和不同語(yǔ)言的編譯器。在不改動(dòng)已有編譯器前端的情況下，為新的目標(biāo)平臺(tái)構(gòu)造一個(gè)生成該平臺(tái)目標(biāo)程序的后端，就可以構(gòu)造出新平臺(tái)的編譯器。同樣對(duì)于一個(gè)新的語(yǔ)言，在不改動(dòng)已有編譯器后端的情況下，為新語(yǔ)言構(gòu)造一個(gè)識(shí)別該語(yǔ)言的前端，就可以構(gòu)造出新

2、語(yǔ)言的編譯器。（2）針對(duì)中間形式，可以進(jìn)行獨(dú)立于目標(biāo)平臺(tái)的代碼優(yōu)化。這樣可以生成較高質(zhì)量的目標(biāo)代碼，在此基礎(chǔ)上可以對(duì)目標(biāo)代碼進(jìn)行平臺(tái)相關(guān)的優(yōu)化，進(jìn)而生成更高質(zhì)量的目標(biāo)代碼。使用中間形式的主要缺點(diǎn)是，產(chǎn)生中間代碼的編譯過(guò)程與不產(chǎn)生中間代碼的編譯過(guò)程相比在效率上會(huì)顯得有些低。這是因?yàn)橹虚g代碼還要進(jìn)行再一次的翻譯才能生成目標(biāo)代碼。但是，增加一層中間形式可以使編譯器更好地模塊化，并且可以在中間形式上做很多優(yōu)化，這些足以抵消兩次翻譯所帶來(lái)的低效率。所以，很多現(xiàn)代的編譯器都使用了中間形式，比較常見(jiàn)的中間形式有逆波蘭表示，N元表示和樹(shù)形表示三種。由于，在本系統(tǒng)中，我們使用抽象語(yǔ)法樹(shù)作為中間形式，所以不再對(duì)前

3、兩種中間形式做以介紹，感興趣的讀者可以參考編譯原理（Alfred V.Aho編著）。3.1 樹(shù)形表示樹(shù)形表示是一種非常流行的中間形式，它與三元式表示有著密切的關(guān)系，三元式表示可以看成是樹(shù)形表示的直接形式。例如，表達(dá)式W*X+(Y+Z)的樹(shù)形表示如圖3.1所示：+*ZZY+XW圖3.1 表達(dá)式W*X+(Y+Z)的樹(shù)形表示 在現(xiàn)代編譯器的構(gòu)造過(guò)程中，經(jīng)常使用抽象語(yǔ)法樹(shù)（Abstract Syntax Tree）作為一種中間形式，這樣做可以把翻譯過(guò)程從語(yǔ)法分析過(guò)程中分離出來(lái)，使得層次非常清晰。引入抽象語(yǔ)法樹(shù)是基于多方面原因的，其中的一個(gè)原因在于適于語(yǔ)法分析的文法可能并不反映語(yǔ)言成分的自然層次結(jié)構(gòu)。比

4、如Fortran的文法可能把子程序看成是簡(jiǎn)單的語(yǔ)句序列，而這并不能反映出DO循環(huán)的嵌套。如果我們采用能夠反映DO循環(huán)嵌套的樹(shù)形表示，那么子程序的語(yǔ)義分析將會(huì)更容易一些。因此，很多編譯器經(jīng)常要構(gòu)造語(yǔ)法樹(shù)。在這里我們之所以稱其為“抽象”語(yǔ)法樹(shù)，是因?yàn)槌橄笳Z(yǔ)法樹(shù)的結(jié)構(gòu)不依賴于被編譯語(yǔ)言的原文法，也就是語(yǔ)法分析階段所采用的文法。在語(yǔ)法分析過(guò)程中，為了能夠適應(yīng)摸中分析方法的需要，有時(shí)需要對(duì)文法進(jìn)行等價(jià)的轉(zhuǎn)換（比如，消除左遞歸，避免回溯等），這些轉(zhuǎn)換在采用特定的分析方法進(jìn)行語(yǔ)法分析時(shí)是有必要的，但是這樣做同時(shí)也會(huì)帶來(lái)一些問(wèn)題。比如，會(huì)引入多余的非終結(jié)符和多余的產(chǎn)生式等，所有這些多余的成分都會(huì)對(duì)下面的編譯階

5、段產(chǎn)生一定的限制，甚至?xí)垢麟A段變得非常混亂。按照這些文法進(jìn)行推導(dǎo)時(shí)，每一個(gè)正確的輸入在理論上都對(duì)應(yīng)一個(gè)依賴于這些文法的具體分析樹(shù)。但是正如上面提到的，這種分析數(shù)不大適合直接使用，所以我們引入了抽象語(yǔ)法樹(shù)。抽象語(yǔ)法樹(shù)在語(yǔ)法分析和后面的各編譯階段之間建立了一個(gè)清晰的接口，它能夠反映源程序本身的語(yǔ)法結(jié)構(gòu)?；谝陨显颍橄笳Z(yǔ)法樹(shù)在現(xiàn)代編譯器的構(gòu)造中使用得越來(lái)越廣泛，本系統(tǒng)也構(gòu)造了抽象語(yǔ)法樹(shù)。下面我們先簡(jiǎn)單的介紹一下語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)，并對(duì)它們做以簡(jiǎn)單的比較。語(yǔ)法分析樹(shù)也稱為具體語(yǔ)法樹(shù)，因?yàn)檫@種樹(shù)中的一切都是明示的，完全而又具體，顯示了如何根據(jù)相應(yīng)上下文無(wú)關(guān)文法推導(dǎo)出特定的單詞序列。在我們知道了

6、一個(gè)單詞序列為合法之后，后續(xù)的編譯階段就不再需要語(yǔ)法分析樹(shù)上的許多信息了。因此，語(yǔ)法分析結(jié)束以后，一般會(huì)將這種語(yǔ)法分析樹(shù)轉(zhuǎn)換為一棵抽象語(yǔ)法樹(shù)（又稱AST，簡(jiǎn)稱語(yǔ)法樹(shù)），刪除樹(shù)內(nèi)部的大部分“人為”結(jié)點(diǎn)，并對(duì)剩下的結(jié)點(diǎn)標(biāo)注有用的信息。附在特定節(jié)點(diǎn)上的標(biāo)注被稱為它的屬性。例如語(yǔ)句if(a>b) a = a-b;的語(yǔ)法分析樹(shù)和抽象語(yǔ)法樹(shù)分別可表示成圖3.2和圖3.3。=ifaZa+babZZ圖3.2 語(yǔ)句if(a>b) a = a-b的語(yǔ)法分析樹(shù)If語(yǔ)句條件部分Then部分Else部分圖3.3語(yǔ)句if(a>b) a = a-b的抽象語(yǔ)法樹(shù)在許多編譯器里，帶標(biāo)注的語(yǔ)法樹(shù)就是從前端傳遞到

7、后端的中間形式，而在另一些編譯器里，語(yǔ)義分析器最后可能還要遍歷這棵樹(shù)，生成某種另外的中間形式。本系統(tǒng)將這種語(yǔ)法樹(shù)作為中間表示，不再對(duì)它做一步的轉(zhuǎn)換3.2 系統(tǒng)抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)表示¨ While語(yǔ)句節(jié)點(diǎn)產(chǎn)生式：while-stmt while( expression ) statementwhile語(yǔ)句的抽象語(yǔ)法樹(shù)說(shuō)明：對(duì)于while語(yǔ)句，根節(jié)點(diǎn)是while，第一個(gè)孩子節(jié)點(diǎn)表示條件(expression)，第二個(gè)孩子節(jié)點(diǎn)是條件為真的時(shí)候的執(zhí)行語(yǔ)句(statement)。這些說(shuō)明部分在下面的抽象語(yǔ)法樹(shù)圖中是很直觀的表示，因此以下語(yǔ)句結(jié)點(diǎn)語(yǔ)法樹(shù)將不再贅述。 While語(yǔ)句expressio

8、nstatementChild0Child1 圖3.4while語(yǔ)句的抽象語(yǔ)法樹(shù)¨ If語(yǔ)句節(jié)點(diǎn)表示產(chǎn)生式：if-stmt if( expression ) statement else statement If語(yǔ)句expressionstatementelse Child0Child1Child2 圖3.5 If語(yǔ)句的抽象語(yǔ)法樹(shù)¨ 函數(shù)聲明節(jié)點(diǎn)產(chǎn)生式：fun-declaration ( void | int ) ID( params ) compound-stmt 函數(shù)定義節(jié)點(diǎn)語(yǔ)句1語(yǔ)句2sibling參數(shù)1參數(shù)2siblingChild0Child1函數(shù)名返回類型 圖3

9、.6 函數(shù)聲明的語(yǔ)法樹(shù)¨ 表達(dá)式語(yǔ)句節(jié)點(diǎn)產(chǎn)生式：expression ID = expression | simple-expressionsimple-expression additive-expression relop additive-expression relop < | <= | > | >= | = | != additive-expression term ( + | - ) term term factor ( * | / ) factor factor ( expression )| ID | call | NUM= + - <

10、>ID ID圖3.7 表達(dá)式語(yǔ)句的語(yǔ)法樹(shù)¨ 程序節(jié)點(diǎn)產(chǎn)生式：program var-declaration | fun-declaration 全局變量函數(shù)函數(shù)siblingsibling參數(shù)列表childchildchild 圖3.8程序的語(yǔ)法樹(shù)例：如下程序段代碼：int pi;int add(int x, int y) return x+y;void main() 語(yǔ)法分析結(jié)束后生成的抽象語(yǔ)法樹(shù)如下圖3.9所示： piaddmainsiblingsiblingChild【0】Child【1】xsiblingreturn+xChild【1】Child【0】yy 圖3.9 生成

11、的語(yǔ)法樹(shù)3.3 抽象語(yǔ)法樹(shù)的設(shè)計(jì)在本章前面幾節(jié)中，我們介紹了抽象語(yǔ)法樹(shù)的基本概念，與語(yǔ)法分析樹(shù)的比較以及在系統(tǒng)中抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)表示。在本節(jié)中，我們將詳細(xì)講解本系統(tǒng)中抽象語(yǔ)法樹(shù)節(jié)點(diǎn)設(shè)計(jì)，并且對(duì)抽象語(yǔ)法樹(shù)的實(shí)現(xiàn)代碼做以解釋。抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)類型如下所示：/抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)類型public enum NodeType FunDecl, VarDecl, Para,ADD, SUB, MUL, DIV, REQ, RLT, RGT, RNEQ, RNGT, RNLT,AssignStm, IfStm, IfElseStm, ElseStm, WhileStm, ReturnStm,FunCall,

12、ConstID, VarID,OTHER, ERROR; 在此基礎(chǔ)上，我們?cè)俳o出了抽象語(yǔ)法樹(shù)的節(jié)點(diǎn)定義，見(jiàn)第二章表2.1。下面，我們給出抽象語(yǔ)法樹(shù)的實(shí)現(xiàn)代碼并給出必要的解釋。所給出的代碼與文件parser/Parser.cs中的源代碼略有不同，但是基本思路一致，為了便于讀者理解，parser/Parser.cs特改寫(xiě)成以下代碼形式：class ParserToken curtoken;void parse() curtoken = getNextToken();/取得第一個(gè)tokenTreeNode root = null;root = program(); /遞規(guī)下降分析！構(gòu)建語(yǔ)法樹(shù)，并返回

13、根節(jié)點(diǎn)函數(shù)parse()：這個(gè)函數(shù)所做的工作就是從詞法分析所生成的單詞序列中取得第一個(gè)單詞Token，然后，調(diào)用program()函數(shù)，構(gòu)建抽象語(yǔ)法樹(shù)，并返回抽象語(yǔ)法樹(shù)的根節(jié)點(diǎn)；void match(TokenType expected)if(curtoken.TType = expected) curtoken=getNextToken();else ParseError();函數(shù)match(TokenType expected)：用來(lái)通過(guò)將當(dāng)前單詞類型與語(yǔ)法上應(yīng)該出現(xiàn)的正確單詞類型進(jìn)行比較，檢查是否有語(yǔ)法錯(cuò)誤。如果沒(méi)有語(yǔ)法錯(cuò)誤，則從單詞序列中取得下一個(gè)單詞，以便后面繼續(xù)進(jìn)行語(yǔ)法分析，構(gòu)建抽

14、象語(yǔ)法樹(shù)使用，如果出現(xiàn)語(yǔ)法錯(cuò)誤，則調(diào)用函數(shù)ParseError()進(jìn)行出錯(cuò)處理；TreeNode program() Token p, 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;Return root;TreeNode var_decl() 函數(shù)program()：此函數(shù)的作

15、用是進(jìn)行遞歸下降分析，生成抽象語(yǔ)法樹(shù)，返回抽象語(yǔ)法樹(shù)的根節(jié)點(diǎn)root。這個(gè)函數(shù)中的變量p用來(lái)記錄前一次所生成的節(jié)點(diǎn)，變量q用來(lái)記錄當(dāng)前所生成的節(jié)點(diǎn)。 TreeNode retnode, nextnode, curnode; retnode = curnode; retnode.NType = curnode.NType = NodeType.VarDecl; while(curtoken.TType!=TokenType.SEMI) Switch(curtoken.TType) case TokenType.INT: match(TokenType.INT); break;case Token

16、Type.ID:nextnode.NodeStr = curtoken.str; curnode.Sibling = nextnode;curnode = nextnode;match(TokenType.ID);break;case TokenType.COMMA:match(TokenType.COMMA);break;default:ParseError(); break; Match(TokenType.SEMI);Return retnode;函數(shù)var_decl()：這個(gè)函數(shù)實(shí)現(xiàn)了一個(gè)變量聲明語(yǔ)句的抽象語(yǔ)法樹(shù)節(jié)點(diǎn)的構(gòu)建，并且返回其根節(jié)點(diǎn)retnode。這里的變量聲明僅限于簡(jiǎn)單變量，

17、且數(shù)據(jù)類型為整型。TreeNode fun_decl() TreeNode retnode; retnode.NType = NodeType. FunDecl; While(curtoken.TType!=TokenType. LPAREN) Switch(curtoken.TType) case TokenType.INT: case TokenType.VOID: retnode.retType = curtoken.str; match(curtoken.TType);break;case TokenType.ID: retnode.NodeStr = curtoken.str; match(TokenType.ID);break;default:ParseError(); break; match(TokenType.LPAREN); if(token.TType != TokenType.RPAREN) /匹配參數(shù)列表,第1個(gè)子節(jié)點(diǎn) TreeNode paramsNode = param_list();retnode.child0 = paramsNode; match(TokenType.RPAREN); TreeNode stmtNode = compound_stmt()