[工學(xué)]編譯原理課程設(shè)計(jì)報(bào)告

1、.編譯原理課程設(shè)計(jì)上海交通大學(xué)編譯原理課程設(shè)計(jì)報(bào)告Tiger編譯器的設(shè)計(jì)與實(shí)現(xiàn)張至先 5080309910目錄1.介紹32.詞法分析53.語(yǔ)法分析74.語(yǔ)義分析115.中間代碼生成186.匯編指令選擇247.寄存器分配298.生成匯編代碼359.感想3610.附錄A Tiger.flex3711.附錄B Grm.cup4112.附錄C queens.tig4613.附錄D parse.txt4714.附錄E lib.s5515.附錄F out.s5716.附錄G 參考文獻(xiàn)631. 介紹本課程設(shè)計(jì)旨在實(shí)現(xiàn)一個(gè)Tiger語(yǔ)言的編譯器。1.1 Tiger語(yǔ)言規(guī)范詳見(jiàn)Tiger Language Re

2、ference Manual。1.2 課程設(shè)計(jì)所用語(yǔ)言JAVA1.3 課程設(shè)計(jì)參考“虎書(shū)”Modern compiler implementation in JAVA，1st edtion1.4 實(shí)驗(yàn)環(huán)境（工具）Java 開(kāi)發(fā)環(huán)境: Eclipse詞法分析器: JFlex語(yǔ)法分析器: CUPMIPS模擬器：PCSPIM1.5 設(shè)計(jì)模塊編譯器的設(shè)計(jì)涉及到很多方面，可分為多個(gè)模塊，從前端（詞法分析）到后端（目標(biāo)代碼生成）依次完成。具體如下（按完成先后順序）：1. 詞法分析2. 語(yǔ)法分析3. 語(yǔ)義檢查4. 中間代碼生成5. 代碼規(guī)范化6. 匯編指令選擇7. 寄存器分配8. 目標(biāo)代碼生成9. 程序運(yùn)行

3、模塊流程圖如圖1.1所示。每個(gè)模塊的實(shí)現(xiàn)方法將在接下分章節(jié)詳述。圖1.1 Tiger編譯器模塊流程圖1.6 項(xiàng)目時(shí)間安排本學(xué)期第十周開(kāi)始啟動(dòng)該項(xiàng)目，第十四周完成詞法分析和語(yǔ)法分析（本項(xiàng)目的前兩個(gè)模塊），第十七周完成至寄存器分配之前，第十八周完成工程及課程設(shè)計(jì)文檔，第十九周提交檢查。1.7 項(xiàng)目完成情況基本上符合原計(jì)劃，現(xiàn)已完成最終的目標(biāo)代碼生成，可以將較復(fù)雜的tiger程序編譯MIPS匯編文件，并在模擬器上正確運(yùn)行。2. 詞法分析將源程序字符串讀入，利用了有窮自動(dòng)機(jī)原理將其按照詞法規(guī)則分割為符號(hào)單元，實(shí)現(xiàn)詞法分析程序由工具JFlex生成。122.1 安裝詞法分析工具JFlexJFlex是jav

4、a語(yǔ)言環(huán)境下非常好用的一款詞法分析工具，本次課程設(shè)計(jì)所用的JFlex為其官網(wǎng)上最新的JFlex1.4.3，本章中所有有關(guān)JFlex的操作均參考自JFlex User's Manual。由于本工程早期是在Linux下進(jìn)行的，所以我下載的是tar格式的壓縮包，再執(zhí)行以下指令進(jìn)行安裝：tar -C /zzx1989/ -xvzf jflex-1.4.3.tar.gzln -s /zzx1989/JFlex/bin/jflex /usr/bin/jflex運(yùn)行是運(yùn)行如下指令：jflex Tiger.flex即可生成詞法分析程序yylex.java。2.2 Tiger.flex代碼清單詳見(jiàn)附錄A

5、。2.3 問(wèn)題解決2.3.1 多重注釋在yylex中新加入一個(gè)狀態(tài)COMMENT。當(dāng)讀入/* 時(shí)進(jìn)入此狀態(tài)并設(shè)置一個(gè)計(jì)數(shù)器count。繼續(xù)讀入若讀入/*則計(jì)數(shù)器count+；若讀入/*則count-；并判斷當(dāng)前count值，若等于0則退出COMMENT狀態(tài)。2.3.2 轉(zhuǎn)義字符轉(zhuǎn)義字符位于字符串中，首先設(shè)定有STRING狀態(tài)。當(dāng)讀入”時(shí)進(jìn)入。而后對(duì)轉(zhuǎn)義字符進(jìn)行處理。典型如n t " 則直接進(jìn)行轉(zhuǎn)義處理。對(duì)于121等轉(zhuǎn)義字符，則先讀入判斷其數(shù)字大小是否屬于0,255中。若符合則進(jìn)行轉(zhuǎn)義，否則報(bào)錯(cuò)。具體代碼如下：<STRING>"yybegin(YYINITIAL)

6、;return tok(sym.STRING,string.toString();nt"+ string.append(yytext();tstring.append('t');nstring.append('n');"string.append('"');|string.append('');:digit:digit:digit:int d=new Integer(yytext().substring(1,4); if(d>=0&&d<=127) string.appen

7、d(char)d); else err("The escape sequence <"+yytext()+">is out of the range");(A-Z|_)char temp=yytext().charAt(2); int num=(int)temp-64; string.append(char)num);(WhiteSpace|LineTerminator)+.|n2.3.3 用到的開(kāi)關(guān)量在Tiger.flex開(kāi)頭的選項(xiàng)聲明部分打開(kāi)%line和%column兩個(gè)開(kāi)關(guān)，JFlex就會(huì)在掃描時(shí)維護(hù)兩個(gè)變量yyline和yycolum

8、n表示當(dāng)前掃描到的行與列，這在報(bào)錯(cuò)時(shí)可以用到。3. 語(yǔ)法分析這個(gè)模塊的目的是以詞法分析的結(jié)果作為輸入，進(jìn)行語(yǔ)法分析，輸出抽象語(yǔ)法樹(shù)。語(yǔ)法分析的中心思想依然是有窮自動(dòng)機(jī)。根據(jù)LR語(yǔ)法，將對(duì)應(yīng)的語(yǔ)法用實(shí)現(xiàn)其相應(yīng)自動(dòng)機(jī)。首先寫(xiě)出對(duì)應(yīng)語(yǔ)法，而后利用java_cup來(lái)生成對(duì)應(yīng)的自動(dòng)機(jī)。依次讀出lexer中的詞法單元，而后在自動(dòng)機(jī)的控制下按照語(yǔ)法逐漸規(guī)約，并在規(guī)約過(guò)程中通過(guò)result的傳遞得到對(duì)應(yīng)的語(yǔ)法樹(shù)，而后將抽象語(yǔ)法樹(shù)輸出。33.1 Symbol包Symbol包中封裝了符號(hào)(Symbol.Symbol)和符號(hào)表(Symbol.Table)。常用的函數(shù)有：Symbol.symbol (String)

9、靜態(tài)函數(shù)，如果字符串表示的符號(hào)存在，則返回原來(lái)的符號(hào)，否則新建一個(gè)與字符串對(duì)應(yīng)的符號(hào)。Table.put (Symbol, Object) 將“符號(hào)對(duì)象”序?qū)Ψ湃氘?dāng)前符號(hào)表中。Table.get (Symbol) 返回當(dāng)前符號(hào)表中符號(hào)所對(duì)應(yīng)的對(duì)象。Table.BeginScope() 在當(dāng)前符號(hào)表中新建一個(gè)子符號(hào)表。Table.EndScope() 退回到上一級(jí)符號(hào)表。注意，在Table.BeginScope()之后父符號(hào)表的內(nèi)容依然可見(jiàn)，但在Table.EndScope()之后子符號(hào)表的內(nèi)容將被刪去。符號(hào)(Symbol.Symbol)和符號(hào)表(Symbol.Table)將在接下來(lái)的模塊中用到

10、。3.2 Absyn包Absyn包中包含了抽象語(yǔ)法樹(shù)的結(jié)點(diǎn)。其中類的組織關(guān)系如圖3.1-3.5所示。圖3.1 Absyn包中的類圖（1）圖3.2 Absyn包中的類圖（2）圖3.3 Absyn包中的類圖（3）圖3.4 Absyn包中的類圖（4）圖3.5 Absyn包中的類圖（5）3.3 Java cup的使用javacup目錄提示符下輸入: java java_cup.Main -expect 2 <Grm.cup其中參數(shù) -expect 2 表示至多2個(gè)沖突(規(guī)約移進(jìn)或規(guī)約規(guī)約是允許的)，在這種情況下，javacup將使用移進(jìn)代替規(guī)約，遇到規(guī)約規(guī)約沖突時(shí)采用高優(yōu)先級(jí)。 運(yùn)行后將生成兩個(gè)

11、java文件:parser.java和sym.java。parser為分析器，sym為常數(shù)表。3.4 Grm.cup代碼清單詳見(jiàn)附錄B。3.5 問(wèn)題解決3.5.1 優(yōu)先級(jí)定義在開(kāi)始文法規(guī)則之前，javacup允許定義終結(jié)符號(hào)的優(yōu)先級(jí)和結(jié)合情況。precedence right FUNCTION,TYPE;precedence right OF;precedence right DO, ELSE, THEN;precedence nonassoc ASSIGN;precedence left OR;precedence left AND;precedence left LPAREN;preced

12、ence nonassoc LE, GT, EQ, NEQ, GE, LT;precedence left PLUS, MINUS;precedence left TIMES, DIVIDE;precedence left UMINUS;precedence left LBRACE;precedence left LBRACK;在這里，優(yōu)先級(jí)為由低到高排列，left/right/nonassoc表明其結(jié)合情況。特別的，將ELSE和THEN設(shè)置為又結(jié)合可以很好的解決if-else二義性的問(wèn)題。3.5.2 參數(shù)，表達(dá)式列表可以為空因此應(yīng)當(dāng)把為空的情況分別單獨(dú)列出來(lái)考慮。如函數(shù)調(diào)用：expr:=ID

13、:id LPAREN expr_list:e RPAREN : RESULT= new CallExp(idleft,idright,sym(id),e); :;expr:=ID:id LPAREN RPAREN : RESULT= new CallExp(idleft,idright,sym(id),null); :;3.5.3 下標(biāo)變量的規(guī)約沖突比如x.a3可以被規(guī)約成x.(a3)。解決的辦法是：lvalue:=ID:id1 DOT ID:id2 : RESULT= new FieldVar(id2left,id2right,new SimpleVar(id1left,id1right,s

14、ym(id1),sym(id2); :;lvalue:=lvalue:l DOT ID:id : RESULT= new FieldVar(idleft,idright,l,sym(id); :;lvalue:=lvalue:l LBRACK expr:e RBRACK : RESULT= new SubscriptVar(eleft,eright,l,e); :;lvalue:=ID:id LBRACK expr:e RBRACK : RESULT= new SubscriptVar(eleft,eright,new SimpleVar(idleft,idright,sym(id),e);

15、:;4. 語(yǔ)義分析語(yǔ)義分析主要是對(duì)上階段生成的抽象語(yǔ)法樹(shù)進(jìn)行語(yǔ)法規(guī)則檢查。檢查通過(guò)則交給接下來(lái)的中間代碼生成模塊產(chǎn)生中間代碼樹(shù)（IRTree）。從功能上看這兩個(gè)模塊是分開(kāi)的，但在實(shí)現(xiàn)的時(shí)候則并不是先后完成的，而往往是語(yǔ)義分析通過(guò)了一部分便立刻將其翻譯，再遞歸的分析翻譯接下來(lái)的部分。44.1 Semant包Semant包主要包括了和語(yǔ)義分析有關(guān)的類。具體如下：Entry：指明了一個(gè)非數(shù)據(jù)類型標(biāo)識(shí)符 (變量和函數(shù)) 的種類。VarEntry: 派生自Entry,用于普通變量LoopVarEntry: 派生自Entry,用于循環(huán)變量StdFuncEntry:派生自Entry,用于庫(kù)函數(shù)FuncEnt

16、ry:派生自Entry,用于普通函數(shù)Env：環(huán)境符號(hào)表，其中包含兩個(gè)Symble.Table tEnv和vEnv。tEnv 記錄了當(dāng)前的類型名稱,是符號(hào)類型表, 注意其中會(huì)有類型綁定機(jī)制: 如果其中的類型是用Types.NAME表示的，則實(shí)際類型存儲(chǔ)在NAME.binding里面。vEnv記錄了當(dāng)前的變量、函數(shù)等信息，是符號(hào)入口表。在其中的每個(gè)項(xiàng)目為Entry的某個(gè)派生類。LoopEnv:主要用于在分析時(shí)判斷是否處于循環(huán)當(dāng)中，具體詳見(jiàn)本章的問(wèn)題解決。Semant:負(fù)責(zé)對(duì)抽象語(yǔ)法分析樹(shù)進(jìn)行語(yǔ)義分析和翻譯，其中翻譯部分往往是通過(guò)調(diào)用其中的Translate成員變量來(lái)實(shí)現(xiàn)的，該類內(nèi)部的主要工作還是語(yǔ)

17、義分析。ExpTy：其實(shí)就是對(duì)Translate.Exp和Types.Type進(jìn)行分裝，在Semant類中對(duì)Absyn包中的表達(dá)式進(jìn)行翻譯，即返回帶類型的表達(dá)式ExpTy。4.2 Type包Type包主要用來(lái)描述數(shù)據(jù)類型標(biāo)識(shí)符，其類關(guān)系如圖4.1所示。圖4.1 Type包類圖Type類的coerceTo函數(shù)描述了關(guān)于類型的強(qiáng)制轉(zhuǎn)換部分的信息: 除了nil類型可以賦值給record類型外，其它只能轉(zhuǎn)換到本身，且不能將nil賦值給nil。4.3 語(yǔ)義分析步驟語(yǔ)義分析的一般步驟為： 當(dāng)檢查某個(gè)語(yǔ)法結(jié)點(diǎn)時(shí)，需要遞歸地檢查結(jié)點(diǎn)的（包括以后的中間代碼翻譯）每個(gè)子語(yǔ)法成分 ，確認(rèn)所有子語(yǔ)法成分的正確且翻譯完

18、畢后，調(diào)用Translate對(duì)整個(gè)表達(dá)式進(jìn)行翻譯。這些步驟主要是在Semant類中進(jìn)行的，主要用到的函數(shù)有：ExpTy Semant:transVar(Absyn.Var)將抽象語(yǔ)法樹(shù)中的變量翻譯成帶類型的表達(dá)式ExpTy Semant:transExp(Absyn.Exp)將抽象語(yǔ)法樹(shù)中的表達(dá)式翻譯成帶類型的表達(dá)式Expre Semant:transDec(Absyn.Dec)將抽象語(yǔ)法樹(shù)中的聲明翻譯成Translate.ExpreType Semant:transTy(Absyn.Ty)將抽象語(yǔ)法樹(shù)中的類型翻譯成數(shù)據(jù)類型標(biāo)識(shí)符4.4 語(yǔ)義檢查規(guī)則IntExp StringExpNilExp

19、 VarExp CalcExp左右均為int類型 EqExp左右中任一個(gè)不能為void類型 左右不能全為nil可以一個(gè)為nil一個(gè)為record類型 其它情況下必須左右類型完全一致 RelExp左右兩邊必須全為int或string AssignExp:t1:=t2 如果t1是簡(jiǎn)單變量并且在vEnv中查得它是LoopVarEntry,則報(bào)錯(cuò)不能給循環(huán)變量賦值如果t2是void類型則出錯(cuò) 如果t2不能強(qiáng)制轉(zhuǎn)換成t1則出錯(cuò) CallExp 如果在vEnv里查不到函數(shù)名或者它不是FuncEntry (包括StdFuncEntry) 則報(bào)錯(cuò):函數(shù)未定義 然后逐個(gè)檢查形參和實(shí)參是否匹配(用AssignEx

20、p的方法檢查),遇到不匹配則報(bào)錯(cuò). 在遍歷形參鏈表的時(shí)候,可能遇到鏈表空或有剩余的情況,此時(shí)分別報(bào)告實(shí)參過(guò)多或不足的錯(cuò)誤 RecordExp 先在tEnv中查找類型是否存在,若否或非記錄類型報(bào)告未知記錄類型錯(cuò)誤 然后逐個(gè)檢查記錄表達(dá)式和記錄類型域的名字是否相同 然后逐個(gè)檢查記錄表達(dá)式和記錄類型域的類型是否匹配 (用AssignExp方法檢查) 在遍歷記錄類型鏈表的時(shí)候,可能遇到鏈表空或有剩余的情況,此時(shí)分別報(bào)告域過(guò)多或不足的錯(cuò)誤ArrayExp 先在tEnv中查找類型是否存在,若否或非數(shù)組類型報(bào)告未知記錄類型錯(cuò)誤 再檢查數(shù)組范圍是否為整數(shù),若否報(bào)錯(cuò) 再用AssignExp的方法檢查tEnv中的

21、數(shù)組類型和實(shí)際類型是否匹配,若否報(bào)告類型匹配錯(cuò)誤IfExp 如果測(cè)試條件的表達(dá)式不返回整數(shù),報(bào)告測(cè)試條件錯(cuò)誤(Tiger中非0為真,0為假) 如果缺少else子句,且then子句有返回值,報(bào)錯(cuò)如果不缺少else 子句,檢查then 和else 的返回值是否匹配(采用AssignExp 的方法,只是都返回nil被認(rèn)為是合法的)WhileExp如果測(cè)試條件不是整數(shù),報(bào)告測(cè)試條件錯(cuò)誤如果循環(huán)體有返回值,則報(bào)錯(cuò)(while循環(huán)體不能有返回值)注意這里不需要使Begin/EndScope注意進(jìn)/出循環(huán)使要調(diào)用newLoop 和exitLoop (詳見(jiàn)break 表達(dá)式)ForExp如果初始值和終止值不是

22、整數(shù)類型,則報(bào)錯(cuò)用BeginScope進(jìn)入vEnv新的符號(hào)表 (循環(huán)內(nèi)部用)為幀分配循環(huán)變量的Access把循環(huán)變量添加到vEnv的LoopVarEntry項(xiàng)目中用EndScope退出vEnv的符號(hào)表注意進(jìn)/出循環(huán)使要調(diào)用newLoop 和exitLoop (詳見(jiàn)break 表達(dá)式)BreakExp設(shè)一個(gè)堆棧,進(jìn)入循環(huán)推入一個(gè)Label, 退出循環(huán)彈出一個(gè)Label,如果堆棧為空時(shí)出現(xiàn)break語(yǔ)句則報(bào)告錯(cuò)誤,關(guān)于棧的操作由以下函數(shù)完成:translate.loopExit (堆棧)void translate.newLoop (入棧)void translate.exitLoop (出棧)b

23、oolean translate.isInLoop (測(cè)試是否在堆棧中)newLoop和exitLoop在翻譯for和while語(yǔ)句時(shí)成對(duì)使用這樣做的優(yōu)點(diǎn)是在以后翻譯成IR 樹(shù)時(shí)可以利用這個(gè)堆棧LetExp無(wú)需錯(cuò)誤檢查,只需按如下步驟進(jìn)行:vEnv和tEnv分別用BeginScope進(jìn)入新的符號(hào)表翻譯定義部分 (letin 之間), 用bine2stm將IR 樹(shù)結(jié)點(diǎn)連接翻譯體部分 (inend 之間)vEnv和tEnv用EndScope返回到原符號(hào)表如果體部分為空或者沒(méi)有返回值,用bine2stm將定義和體部分連接如果體部分不空或有返回值,用bine2exp 將定義和體部分連接,把體部分的返回

24、值和類型作為最終的返回值和類型SeqExp無(wú)需錯(cuò)誤檢查,因?yàn)樗侨舾蓚€(gè)已經(jīng)檢查過(guò)的表達(dá)式的鏈分別將每個(gè)子表達(dá)式進(jìn)行翻譯,用 bine2stm函數(shù)將它們的IR樹(shù)結(jié)點(diǎn)連接起來(lái)在翻譯最后一個(gè)表達(dá)式時(shí):如果它的類型是VOID,則仍用combine2stm 將它們的IR 樹(shù)結(jié)點(diǎn)連接起來(lái),并返回VOID 作為返回類型否則,用bine2exp 將它們的IR 樹(shù)結(jié)點(diǎn)連接并返回最后一個(gè)表達(dá)式的值和類型作為返回值和返回類型SimpleVar先檢查vEnv, 若沒(méi)找到變量名或類型不是VarEntry則報(bào)告變量未定義SubscriptVar如果它除去下標(biāo)部分后的類型不是數(shù)組類型,則報(bào)錯(cuò)若下標(biāo)部分不是int類型報(bào)錯(cuò)Fi

25、eldVar若除去域部分后不是記錄類型,則報(bào)錯(cuò)然后逐個(gè)查找記錄的域,如果沒(méi)有一個(gè)匹配當(dāng)前域變量的域,則報(bào)錯(cuò)NameTy檢查tEnv,若沒(méi)有發(fā)現(xiàn)類型,則報(bào)告未知類型錯(cuò)誤ArrayTy檢查tEnv,若沒(méi)有發(fā)現(xiàn)類型,則報(bào)告未知類型錯(cuò)誤,否則返回轉(zhuǎn)換后的ARRAY 類型RecordTy檢查該記錄類型每個(gè)域的類型在tEnv中是否存在,若否,則報(bào)告未知類型錯(cuò)誤若全部正確,則最后返回轉(zhuǎn)換后的RECORD 類型下面是聲明的檢查,在這個(gè)階段可以不需要返回值VarDec如果有顯式的類型聲明,按AssignExp的方法檢查是否類型匹配若無(wú)顯式的類型聲明且初始值為nil,則報(bào)錯(cuò),因?yàn)橹挥杏涗涱愋涂梢杂胣il初始化若無(wú)

26、初始值,報(bào)錯(cuò),因?yàn)門(mén)iger語(yǔ)言所有的變量聲明必須有初始化如果沒(méi)有以上錯(cuò)誤,則為變量在幀上分配空間把變量作為VarEntry添加到vEnv中變量聲明不采用塊機(jī)制,而是在任何地方都直接覆蓋TypeDec1 Tiger 語(yǔ)言的類型聲明采用塊機(jī)制(見(jiàn)第二部分),所以要先在一個(gè)聲明塊中檢查否有重復(fù)的聲明(而在不同的塊中可以有重復(fù)的聲明的,新的將沖掉舊的),若有,報(bào)告重定義錯(cuò)誤(具體實(shí)現(xiàn)時(shí)可采用HashSet類)2 接下來(lái)翻譯出實(shí)際的Type 類型 (Typedec.ty.translate 方法) ,再?gòu)膖Env 中查找出NAME類型,將實(shí)際的Type類型綁定到NAME類型3 檢測(cè)循環(huán)定義問(wèn)題 (見(jiàn)4

27、.3)4 如果以上均正確,添加類型到tEnv中FunctionDec函數(shù)聲明同樣采用塊機(jī)制. 對(duì)于函數(shù)聲明塊中的每個(gè)聲明,做以下檢查15:1 同類型聲明類似,先檢查聲明塊中是否有重復(fù)的聲明2 還要檢查是否與標(biāo)準(zhǔn)函數(shù)沖突,可以通過(guò)掃描vEnv 中的StdFuncEntry 實(shí)現(xiàn),若有報(bào)錯(cuò)3 然后檢查參數(shù)列表,與記錄類型RecordTy的檢查完全相同,得到RECORD 類型的形參列表4 接著檢查函數(shù)返回值,如果沒(méi)有返回值則設(shè)置成void5 無(wú)誤后,為函數(shù)創(chuàng)建新層,將函數(shù)作為FuncEntry添加到vEnv中然后再重新掃描一遍聲明,如果某函數(shù)不是標(biāo)準(zhǔn)函數(shù),則做以下操作15:1 用BeginScope

28、進(jìn)入vEnv的一張子表(函數(shù)內(nèi)部用),并轉(zhuǎn)移到新層2 將函數(shù)參數(shù)存入子表3 翻譯函數(shù)體, 并用ProcEntryExit給函數(shù)體加上關(guān)于函數(shù)調(diào)用的指令4 檢查函數(shù)體的返回類型是否和聲明部分匹配,若否則報(bào)錯(cuò)5 用EndScope退出子表,轉(zhuǎn)移到當(dāng)前層4.5 問(wèn)題解決4.5.1 循環(huán)定義問(wèn)題Env中有一個(gè)類型為L(zhǎng)oopEnv的變量loopEnv，這是用來(lái)判斷當(dāng)前的Semant翻譯狀態(tài)是否處于循環(huán)體中。實(shí)現(xiàn)的原理與詞法分析中處理嵌套注釋的方法類似但更為復(fù)雜，考慮如下一種情況。Function aWhile()Function bWhile().xxxx如果簡(jiǎn)單的按處理嵌套注釋的方法，在xxxx初的l

29、oop值仍然大于零，意味著仍處于循環(huán)內(nèi)?？墒菍?shí)際上，如果xxxx是break則此處會(huì)有一個(gè)錯(cuò)誤。造成這個(gè)錯(cuò)誤的原因是函數(shù)間有不同的作用域，b的作用域屏蔽了a，在xxxx處是看不到a的循環(huán)的。處理辦法是LoopEnv中維護(hù)一個(gè)Stack<Stack<Label>>成員s。外層的stack表示作用域，內(nèi)層的stack表示是否有循環(huán)。當(dāng)進(jìn)入新的作用域時(shí)，push一個(gè)空的stack到外層的stack中去，作用域結(jié)束時(shí)則pop此stack。遇到循環(huán)開(kāi)始時(shí)在內(nèi)層stack中push一個(gè)Label,循環(huán)結(jié)束就pop這個(gè)Label。這樣的話，當(dāng)前處在循環(huán)體中的條件就變成了外層stack

30、的最頂層不為空。4.5.2 類型的循環(huán)定義在Tiger語(yǔ)言中類型的循環(huán)定義是不被允許的，如下列語(yǔ)法：type a1=a2 type a2=a3 type a3=a4 type a4=a1是錯(cuò)誤的。為了檢查出循環(huán)定義錯(cuò)誤，可以用NAME類型中的isLoop成員函數(shù)來(lái)判斷：public boolean isLoop() Type b = binding;boolean any;binding = null;if (b = null)any = true;else if (b instanceof NAME)any = (NAME) b).isLoop();elseany = false;bindi

31、ng = b;return any;5. 中間代碼生成結(jié)合一些和函數(shù)調(diào)用有關(guān)的活動(dòng)記錄，在通過(guò)了語(yǔ)義檢查之后，本模塊將抽象語(yǔ)法生成樹(shù)翻譯為中間表示樹(shù)（IRTree）。55.1 Frame包這個(gè)包主要包含以下3個(gè)類：Frame定義了抽象的程序幀結(jié)構(gòu)，用于存放函數(shù)參數(shù)，返回地址，寄存器，棧指針，幀指針?lè)祷刂档戎匾畔ⅰccess用于描述那些存放在幀中或是寄存器中的形式參數(shù)和局部變量,也是抽象數(shù)據(jù)類型。AccessList將Access串成鏈表。5.2 Mips包這個(gè)包包含4個(gè)類：MipsFrame具體描述了用于Mips機(jī)的幀信息,派生自Frame.Frame。主要任務(wù)為進(jìn)行初始化寄存器、新建幀、

32、分配Access及函數(shù)調(diào)用處理（procEntryExit1）。InFrame派生自Access，表示存放在幀中的變量。InReg派生自Access，表示存放在寄存器中的變量。因此兩者的exp和expFromStack方法的實(shí)現(xiàn)是不同的。Codegen代碼生成器，用于把IRTree節(jié)點(diǎn)轉(zhuǎn)換為InstrList，將在生成匯編指令時(shí)用到。圖5.1展示了以上兩個(gè)包中主要的類關(guān)系圖。圖5.1 Mips包和Frame包的類圖5.3 Level類Level是用來(lái)描述靜態(tài)連接用的數(shù)據(jù)結(jié)構(gòu)，它被封裝在Translate.Level中。Level總是和Frame綁定在一起的。Level描述了函數(shù)的靜態(tài)信息，而F

33、rame描述函數(shù)的動(dòng)態(tài)信息 Level類的主要類成員：Level parent上一級(jí)的層Frame.Frame frame對(duì)應(yīng)的幀結(jié)構(gòu)AccessList fomals 函數(shù)調(diào)用的參數(shù)（第一個(gè)為靜態(tài)鏈接）。靜態(tài)鏈接主要是在翻譯變量和函數(shù)調(diào)用時(shí)需要用到。5.4 Tree包Tree包定義了中間樹(shù)的節(jié)點(diǎn)，這是一種抽象的機(jī)器語(yǔ)言,它無(wú)需太多地考慮機(jī)器特性的細(xì)節(jié)就可以對(duì)目標(biāo)機(jī)的操作進(jìn)行表達(dá)。IRTree的節(jié)點(diǎn)可以分成Expr派生出來(lái)的和Stm派生出來(lái)的，這兩者的主要區(qū)別在于Expr有而Stm沒(méi)有返回值。他們的關(guān)系如圖5.2-5.3所示。圖5.2 Expr派生類圖圖5.3 Stm派生類圖5.5 Trans

34、late包這個(gè)包中的類可以分為幾個(gè)部分（例如上面提過(guò)的Level類也屬于這個(gè)包），最主要的是Expre及其派生類。這些類是IRTree的“代理建造者”。Translate不直接生成樹(shù)的具體結(jié)點(diǎn)，而是先生成這些代理類，由它們通過(guò)方法unEx,unCx 或unNx來(lái)生成具體的結(jié)點(diǎn)。這三個(gè)方法即Expre類的三種方法，表示分別轉(zhuǎn)換到Ex,Cx和Nx。Ex為有返回值的表達(dá)式，Nx為無(wú)返回值的表達(dá)式，Cx表示一個(gè)判斷條件,有真假兩個(gè)出口。因此這三種方法的返回值分別為T(mén)ree.Expr,Tree.Stm和Tree.Stm。這些類的關(guān)系如圖5.4所示。圖5.4 Expre派生類圖另一部分和Frag類有關(guān)。一

35、個(gè)Frag類可能是一個(gè)字符串或一個(gè)函數(shù)塊，因此派生出DataFrag和ProcFrag。DataFrag中包含標(biāo)號(hào)和字符數(shù)據(jù)；函數(shù)塊為ProcFrag, 其中有函數(shù)體 (Tree.Stm) 和其Frame。每個(gè)Frag都包含一個(gè)指向下一個(gè)Frag的指針，因此可以形成段鏈表。在翻譯過(guò)程中，段總是不斷增大的，段鏈表被私有地維護(hù)在Translate類中，它提供了AddFrag和GetResult兩個(gè)接口用于添加段和取回整個(gè)段鏈表。圖5.5 Frag派生類圖5.6 具體翻譯過(guò)程翻譯情況IR 樹(shù)結(jié)果整型常數(shù) valueCONST (value)字符串常數(shù) valueNAME (label)nil變量EX

36、(CONST(0)變量表達(dá)式 translate.ExpExp運(yùn)算表達(dá)式 left oper rightEX(BINOP (binop, left, right)字符串運(yùn)算 left oper rightRELCX(OPER, EX (COMP) , EX (0)其它關(guān)系運(yùn)算 left oper rightRELCX (OPER, LEFT, RIGHT)賦值運(yùn)算 lvalue=exNX(MOVE (lvalue, ex)TransCallExpEX(CALL(NAME(func_name), args)庫(kù)函數(shù)調(diào)用TransExtCallExpEX ( EXTERNAL_CALL )stm的連

37、接 e1, e2NX(SEQ(NX(E1), NX(E2)exp的連接 e1, e2EX(ESEQ(NX(E1), EX(E2)transRecordExpEX(ESEQ(SEQ(MOVE(TEMP(addr),alloc),init),TEMP(addr)transArrayExpEX(alloc)if, while, forIfExp, WhileExp, ForExpbreakNX (JUMP (LABEL)簡(jiǎn)單變量EX(MEM (BINOP (PLUS, TEMP(FP), CONST(OFFSET)下標(biāo)變量 varidxEX(MEM(BINOP(BINOP.PLUS, EX(VAR)

38、,BINOP(MUL,EX(IDX),CONST(WORDSIZE)域變量 varnumEX(MEM(BINOP(BINOP.PLUS, EX(VAR) , CONST(NUM*WORDSIZE)翻譯函數(shù)體procEntryExit這個(gè)表格給出了大致的翻譯方案，具體實(shí)現(xiàn)以代碼為準(zhǔn)。5.7 問(wèn)題解決5.7.1 ProcEntryExit函數(shù)族在本設(shè)計(jì)中用到了四個(gè)ProcEntryExit函數(shù)，它們分別是：Translate:ProcEntryExit為函數(shù)體加上返回值的信息, 并把IR樹(shù)結(jié)點(diǎn)加入段中Frame: ProcEntryExit1在函數(shù)體前加上保存fp,ra,Callee-save和參

39、數(shù)，并計(jì)算新fp，然后在函數(shù)體后恢復(fù)被保存的寄存器Frame: ProcEntryExit2函數(shù)體經(jīng)其處理后保持不變，僅僅增加一條空指令Frame: ProcEntryExit3主要為函數(shù)體分配幀空間，并為其設(shè)置函數(shù)體標(biāo)號(hào)。4個(gè)ProcEntryExit的執(zhí)行順序?yàn)?ProcEntryExit (translate.java) 中調(diào)用ProcEntryExit1emitProc中 (Main.java) 中調(diào)用ProcEntryExit3這樣最終生成的關(guān)于函數(shù)體的匯編代碼為:1) 設(shè)置函數(shù)體標(biāo)號(hào)2) 計(jì)算 $SP, 分配幀空間3) 保存原 $FP4) 計(jì)算新 $FP ($fp=$sp-幀空間+

40、4 bytes)5) 保存 $RA6) 保存 Callee-Saved 寄存器7) 保存參數(shù) $A0$A38) 函數(shù)體9) 將函數(shù)體返回值寫(xiě)入 $RV10) 恢復(fù) Callee-Saved 寄存器11) 恢復(fù) $RA12) 恢復(fù) $FP13) 恢復(fù) $SP, 將$SP 加上相應(yīng)的幀空間14) 跳轉(zhuǎn)到返回地址其中1,2,13,14由ProcEntryExit3完成,9由ProcEntryExit完成,其余由ProcEntryExit3完成。5.7.2 規(guī)范化從已經(jīng)得到的IR 樹(shù)出發(fā)，規(guī)范化過(guò)程將幫助完成下面的工作:AIR 樹(shù)被寫(xiě)成一個(gè)沒(méi)有SEQ和ESEQ 結(jié)點(diǎn)的規(guī)范樹(shù)表B根據(jù)該表劃分基本塊，每個(gè)

41、基本塊中不包含內(nèi)部跳轉(zhuǎn)和標(biāo)號(hào)C基本塊被順序放置，所有的CJUMP 都跟有false標(biāo)號(hào)由于這部分的代碼在實(shí)現(xiàn)框架中已經(jīng)提供所以我們不需要知道任何細(xì)節(jié)，只需將提供的Canon 文件夾復(fù)制,對(duì)于以上三步,只需在最后裝配時(shí)調(diào)用下面的接口就可以了。Canon.Canon.linearize (Tree.Stm s)Canon.BasicBlocks. BasicBlocks(Tree.StmList stms)Canon.TraceSchedule(BasicBlocks b)6. 匯編指令選擇66.1 常用MIPS匯編指令sw reg, addr 將寄存器reg保存到內(nèi)存地址addr中l(wèi)w reg,

42、 addr 將內(nèi)存地址addr中的內(nèi)容保存到寄存器reg中l(wèi)i reg, imm 將立即值imm保存到寄存器reg中l(wèi)a reg, addr 將地址addr (而不是其中的內(nèi)容) 保存到寄存器reg 中move reg1, reg2將寄存器reg2 移動(dòng)到寄存器reg1中jal label 無(wú)條件轉(zhuǎn)移到label, 返回地址 (下一指令) 存于$Ra寄存器jr reg 無(wú)條件轉(zhuǎn)移到reg中所保存的地址, 返回地址存于$Rasubu reg1,reg2,CONST 將reg2 的值減去CONST后放入reg1addu reg1,reg2,CONST 將reg2 的值加上CONST后放入reg1b

43、eq reg, src, label 當(dāng)reg=src時(shí)跳轉(zhuǎn)到labelbge reg, src, label 當(dāng)reg>=src時(shí)跳轉(zhuǎn)到labelbgt reg, src, label 當(dāng)reg>src時(shí)跳轉(zhuǎn)到labelble reg, src, label 當(dāng)reg<=src時(shí)跳轉(zhuǎn)到labelblt reg, src, label 當(dāng)reg<src時(shí)跳轉(zhuǎn)到labelbne reg, src, label 當(dāng)reg!=src時(shí)跳轉(zhuǎn)到labeladd reg1, reg2, src 將reg2+src送到reg1sub reg1, reg2, src 將reg2-src

44、送到reg1mul reg1, reg2, src 將reg2*src送到reg1div reg1, reg2, src 將reg2/src送到reg16.2 MIPS中的寄存器REGISTERNAMEUSAGE$0 $zero常量0(constant value 0)$1 $at保留給匯編器(Reserved for assembler)$2-$3$v0-$v1函數(shù)調(diào)用返回值(values for results and expression evaluation)$4-$7$a0-$a3函數(shù)調(diào)用參數(shù)(arguments)$8-$15$t0-$t7暫時(shí)的(或隨便用的)$16-$23$s0-$

45、s7保存的(或如果用，需要SAVE/RESTORE的)(saved)$24-$25$t8-$t9暫時(shí)的(或隨便用的)$28 $gp全局指針(Global Pointer)$29 $sp堆棧指針(Stack Pointer)$30 $fp幀指針(Frame Pointer)$31 $ra返回地址(return address)6.3 MIPS匯編語(yǔ)言語(yǔ)法注釋: 以 # 號(hào)開(kāi)始指令: 見(jiàn)本章第一節(jié)標(biāo)識(shí)符: 以字母,下劃線,點(diǎn)號(hào),數(shù)字序列(不以數(shù)字開(kāi)頭)標(biāo)號(hào) :標(biāo)識(shí)符后加冒號(hào)例如:.dataitem: .word 1.text.globl main # Must be globalmain: lw

46、$t0, item數(shù)值可以為十進(jìn)制或十六進(jìn)制，例如255或0xff字符串用引號(hào)括起來(lái)，可以使用如下轉(zhuǎn)義字符:n (換行) t (tab) ”(引號(hào))還有如下會(huì)用到的匯編指令:.globl symbol聲明symbol是全局的，main函數(shù)必須是全局的(globl main).text聲明指令區(qū):后面跟上連續(xù)的匯編指令.data聲明數(shù)據(jù)區(qū):后面跟上連續(xù)的數(shù)據(jù).word w1,w2在數(shù)據(jù)區(qū)中存儲(chǔ)連續(xù)的32位整數(shù).asciiz str 在數(shù)據(jù)區(qū)中存儲(chǔ)字符串，并用null結(jié)尾6.4 Assem包Instr類用來(lái)表示一條匯編語(yǔ)言指令。它有三個(gè)派生類OPER,LABEL和MOVE。OPER類中包含匯編語(yǔ)言

47、指令assem，一個(gè)操作數(shù)寄存器列表src 和一系列的結(jié)果寄存器dst，這些寄存器列表都可以是空的。方法OPER(assem, dst, src)將構(gòu)造跳轉(zhuǎn)至下一條指令的操作，并且jumps()方法的返回值為null；OPER(assem, dst, src, jump) 還擁有目標(biāo)標(biāo)記列表并通過(guò)查找這個(gè)列表進(jìn)行跳轉(zhuǎn)。LABEL表示程序?qū)⒁D(zhuǎn)的地點(diǎn)。其中包括一個(gè)assem，指明在匯編語(yǔ)言中如何找到標(biāo)號(hào)，有一個(gè)label參數(shù)，用于確定使用哪個(gè)標(biāo)號(hào)符號(hào)。MOVE與OPER 很接近，但MOVE必須進(jìn)行數(shù)據(jù)轉(zhuǎn)換。如果dst和src被分配給了同一個(gè)寄存器，MOVE指令將被刪除。Instr.Format

48、(m) 將匯編指令轉(zhuǎn)化成為字符串形式。m 是一個(gè)實(shí)現(xiàn)TempMap 接口的對(duì)象,在TempMap 接口中，存在一個(gè)方法可以為每個(gè)臨時(shí)變量分配一個(gè)寄存器或者為不同的變量分配相同的寄存器 (給出名字) 。Instr是與特定的機(jī)器無(wú)關(guān)的。圖6.1 Assem包類圖6.5 生成匯編指令這些工作在Mips.Codegen中完成，輸入中間表示樹(shù)節(jié)點(diǎn)，將生成Instr類對(duì)象將其加入到InstrList對(duì)象成員instrList中(調(diào)用emit)。接下來(lái)以Mips.Codegen:munchStm(MOVE s)為例，展示生成匯編指令的一半方法。以MOVE為樹(shù)根時(shí)總共有六種可能情況需要分別處理，如圖6.2所示

49、。圖 6.2 MOVE為根時(shí)的六種可能情形其中d標(biāo)記數(shù)據(jù)寄存器，a標(biāo)記地址寄存器。這六種情況的處理方式分別如下：情況1:sw d, CONST (a) /CONST 為常數(shù)偏移量, a 為內(nèi)存地址,下同情況2:sw d, CONST (a)情況3:sw d, CONST情況4:sw d, CONST情況5:li d, CONST /CONST 寫(xiě)入寄存器 d情況6:move d1, d2 /d2 寫(xiě)入寄存器 d1public void munchStm(MOVE s) Expr dst = s.dst;Expr src = s.src;if (dst instanceof MEM) MEM d

50、st1 = (MEM) dst;if (Expr.isBINOP(dst1.exp) && (BINOP) dst1.exp).binop = BINOP.PLUS&& Expr.isCONST(BINOP) dst1.exp).right) Temp t1 = munchExp(src);Temp t2 = munchExp(BINOP) dst1.exp).left);emit(new OPER("sw s0, "+ (CONST) (BINOP) dst1.exp).right).value + "(s1)",nul

51、l, new TempList(t1, new TempList(t2, null); else if (Expr.isBINOP(dst1.exp)&& (BINOP) dst1.exp).binop = BINOP.PLUS&& Expr.isCONST(BINOP) dst1.exp).left) Temp t1 = munchExp(src);Temp t2 = munchExp(BINOP) dst1.exp).right);emit(new OPER("sw s0, "+ (CONST) (BINOP) dst1.exp).lef

52、t).value + "(s1)",null, new TempList(t1, new TempList(t2, null); else if (Expr.isCONST(dst1.exp) Temp t1 = munchExp(src);emit(new OPER("sw s0, " + (CONST) dst1.exp).value, null,new TempList(t1, null); else Temp t1 = munchExp(src);Temp t2 = munchExp(dst1.exp);emit(new OPER("s

53、w s0, (s1)", null, new TempList(t1,new TempList(t2, null); else if (Expr.isTEMP(dst)if (Expr.isCONST(src) emit(new OPER("li d0, " + (CONST) src).value, new TempList(TEMP) dst).temp, null), null); else Temp t1 = munchExp(src);emit(new OPER("move d0, s0", new TempList(TEMP) dst).temp,null), new TempList(t1, null);其他匯編指令生成方式詳見(jiàn)工程代碼。7. 寄存器分配這個(gè)模塊可以說(shuō)是整個(gè)工程的難點(diǎn)，因?yàn)樯婕暗揭幌盗械乃惴?。大致的步驟為：根據(jù)匯編指令生成流圖 -> 活性分析 -> 生成干擾圖 > 根據(jù)干擾圖分配寄存器(著色算法)77.1 流圖的生成FlowGraph.AssembleFlowGroup封裝了一個(gè)面向匯編指令的流圖結(jié)構(gòu)，在這個(gè)類中每個(gè)結(jié)點(diǎn)代表一個(gè)匯編指令，邊為可能的控制轉(zhuǎn)移。該類還提供了一個(gè)構(gòu)造函數(shù)，可以輸入InstrList對(duì)象來(lái)生成