編譯程序原理與實現(xiàn)：第7章 中間代碼生成(1)

1、中間代碼生成在編譯器中的作用詞法分析語法分析語義分析中間代碼優(yōu)化中間代碼生成目標(biāo)代碼生成分析合成中間代碼生成中間代碼生成是將源程序翻譯成等價中間表示的過程中間代碼生成 不是編譯程序的必經(jīng)階段生成中間代碼的目的有二：增強(qiáng)語言的可移植性進(jìn)行中間代碼級別的優(yōu)化 中間代碼生成方法：基于Token序列基于抽象語法樹語法制導(dǎo)的翻譯方法：屬性文法和動作文法生成中間代碼后，修改編譯器后端，可將編譯器移植到不同的機(jī)器上源程序Token序列詞法分析器語法分析器語法分析樹語義分析器中間代碼生成器中間代碼M1Mn中間代碼級別的優(yōu)化程序(代碼)優(yōu)化分為源程序級別優(yōu)化、中間代碼級別優(yōu)化、目標(biāo)代碼級別優(yōu)化源程序級別優(yōu)化取決

2、于用戶對算法的取舍編譯程序可進(jìn)行中間代碼和目標(biāo)代碼上的優(yōu)化中間代碼級別優(yōu)化：循環(huán)內(nèi)下標(biāo)變量地址的計算常表達(dá)式節(jié)省公共子表達(dá)式節(jié)省循環(huán)不變式外提中間代碼級別的優(yōu)化int Amn,t;for(int i= 0; im; i+;) for(int j=0;jn; j+) t = Aij; Aij = Aji; Aji = t; (subi,j,0,t5)(multi,t5,1,t6)(multi,t6,1,t7)(aadd,t4,t7,t8)(subi,i,0,t1)(multi,t1,n,t2)(multi,t2,1,t3)(aadd,A,t3,t4)第七章 中間代碼生成 7.1 幾種常見的中間代

3、碼表示 7.2 中間代碼生成中的幾個問題 7.3 表達(dá)式的中間代碼生成 7.4 原子語句的中間代碼生成 7.5 結(jié)構(gòu)語句的中間代碼生成 7.6 聲明的中間代碼生成7.1 常見的中間表示 后綴式，逆波蘭式 抽象語法樹 AST(abstract syntax tree) 無環(huán)有向圖 DAG(directed acyclic graph) 三元式 四元式三地址中間代碼7.1 常見的中間表示后綴式(逆波蘭式)通常用于表達(dá)式的中間表示中綴 (運(yùn)算符在操作數(shù)的中間)a*b前綴式(運(yùn)算符在操作數(shù)的前面)*ab后綴式(運(yùn)算符在操作數(shù)的后面)ab*如何由中綴式轉(zhuǎn)為后綴式？由抽象語法樹生成后綴式中綴式: a*d

4、+ b*c + e+*+ad*ebc抽象語法樹后根遍歷生成后綴式: a d * b c * + e +先根遍歷生成前綴式: + + * a d * b c e由Token序列生成后綴式（1）-不帶括號表達(dá)式的后綴式生成(1) 初始化: S1和S2為空; /S1是運(yùn)算符棧，S2是運(yùn)算分量棧 (2) 讀token: tk=ReadOne();(3) Switch tk of (i) #: if (S1為空) exit; else while (S1不為空) /*產(chǎn)生剩余操作符的后綴表示*/ op = pop(S1,1); (str1,str2)=pop(S2,2); push(S2, str2 +

5、 str1+ “op”); /str1是左操作數(shù)，str2是右操作數(shù)， (ii)運(yùn)算分量: push(S2,tk); goto (2); (iii)運(yùn)算符: if (S1為空 | tk優(yōu)先級大于Top(S1) push (S1,tk); goto(2); else while(tk小于等于Top(S1) & S1不為空) op = pop(S1,1); (str1, str2)=pop(S2,2); push(S2, str2+str1 + “op”); push(S1,tk); goto (2); 生成后綴式的例子中綴式表達(dá)式 : a * d + b * c + e # 運(yùn)算符棧 S1運(yùn)算分

6、量棧 S2由Token序列生成后綴式（2）帶括號表達(dá)式的后綴式生成注意: 任何運(yùn)算符的優(yōu)先級都大于 (; (1)初始化: S1和S2為空; (2) 讀token: tk=ReadOne(); (3) Switch tk of (i) #: if (S1為空) exit; else while (S1不為空) /*產(chǎn)生剩余運(yùn)算符的后綴表示*/ op = pop(S1,1); (str1, str2)=pop(S2,2); push(S2, str2 + str1 + “op” ); (ii)運(yùn)算分量: push(tk, S2); goto (2); ( : push(, S1); goto (2

7、); (iii)運(yùn)算符: if (S1為空 | tk優(yōu)先級大于Top(S1) push (tk, S1);goto(2); else while(tk小于等于Top(S1) & Top(S1) ( & S1不為空) op = pop(S1,1); (str1, str2)=pop(S2,2); push(S2, str2+str1 + “op”); goto(2); (iv) ): while (Top(S1) ( ) op = pop(S1,1); (str1, str2)=pop(S2,2); push(S2, str2+str1 + “op”); pop(S1,1); goto (2);

8、帶括號表達(dá)式的后綴式例子中綴式表達(dá)式: (a + (d + b) * c ) + e #Operator stack 運(yùn)算符棧 S1Operand stack運(yùn)算分量棧 S2后綴式: a d b + c * +e +7.1 常見的中間表示抽象語法樹-AST無環(huán)有向圖-DAG(共享的AST)a*c + a*c + eASTDAG +*+ac*eac+*+ac*eac7.1 常見的中間表示三地址中間代碼 三地址:兩個操作分量和一個結(jié)果的抽象地址;為方便起見, 通常用變量名代替抽象地址;三元式No. (op, operand1, operand2) 編號 (操作符, 操作分量1, 操作分量2)其中操

9、作分量可以是變量名(抽象地址)或者編號四元式(op, operand1, operand2, result)(操作符, 操作分量1, 操作分量2, 結(jié)果)其中操作分量可以是變量名(抽象地址)或者臨時變量(抽象地址)三地址代碼的例子a*d + b*c + e(1) (*, a, d)三元式(2) (*, b, c)(3) (+, (1), (2)(4) (+, (3), e) (*, a, d, t1)四元式 (*, b, c, t2) (+, t1, t2, t3) (+, t3, e, t4)常用四元式表達(dá)式運(yùn)算四元式 (op, id1,id2,ti),op可以是：ADDI, ADDF, S

10、UBI, SUBF, MULTI, MULTF, DIVI, DIVF, MOD,AND, OR, NOT, EQ, NE, GT, GE, LT, LE類型轉(zhuǎn)換(FLOAT, id1, _, id2)- 把整數(shù)id1轉(zhuǎn)換成實數(shù),并賦值給id2賦值(ASSIG, id1, n, id2) - 把id1的值賦值給id2(長度為n)I/O 操作(READI, _, _, id) - 輸入整數(shù)到id(READF, _, _, id) - 輸入實數(shù)到id(WRITE, _, _, id)- 把id的值輸出常用四元式地址加(AADD, id1, id2, id3)- id1對應(yīng)的地址加上id2后得到的地

11、址賦值給id3標(biāo)號(LABEL, _, _, label)- 定義label為標(biāo)號,并且定位于當(dāng)前位置跳轉(zhuǎn)(JUMP, _, _, label) - 無條件轉(zhuǎn)向標(biāo)號label(JUMP0, id, _, label) - 如果id為假則轉(zhuǎn)向標(biāo)號label(JUMP1, id, _, label) - 如果id為真則轉(zhuǎn)向標(biāo)號label常用四元式函數(shù)(ENTRY, label, size, level) - 函數(shù)入口(ENDFUNC, -,-,-) - 函數(shù)出口(CALL, f, true/false, Result)- 調(diào)用函數(shù)f,返回值給Result(RETURN, -,-, -)(RETUR

12、N, -,-, t)傳遞參數(shù)(VARACT, id, offset, size )- 傳地址(VALACT, id, offset, size )- 傳值結(jié)構(gòu)語句(THEN, t ,_,_) - THEN分支標(biāo)記(ELSE, _, _,_) - ELSE分支標(biāo)記(ENDIF, _ , _ , _ )- IF語句結(jié)束四元式(WHILE, _, _, _) -WHILE語句開始標(biāo)記(DO,t,_,_) -循環(huán)體開始標(biāo)記(ENDWHILE, _, _, _ )- WHILE語句結(jié)束標(biāo)記操作分量的抽象地址操作分量的種類 數(shù)值類整數(shù)或者實數(shù)標(biāo)號類標(biāo)號和過程/函數(shù)入口地址類變量和臨時變量層數(shù)，偏移，存取方式操作分量的FORM結(jié)構(gòu) - 內(nèi)部數(shù)據(jù)結(jié)構(gòu)