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

1、第七章 中間代碼生成 7.1 幾種常見的中間表示 7.2 中間代碼中生成的幾個(gè)問(wèn)題 7.3 表達(dá)式的中間代碼生成 7.4 原子語(yǔ)句的中間代碼生成 7.5 結(jié)構(gòu)語(yǔ)句的中間代碼生成 7.6 聲明的中間代碼生成7.2 中間代碼生成中的幾個(gè)問(wèn)題語(yǔ)義信息的獲取和保存目標(biāo)代碼階段保留符號(hào)表，則可用標(biāo)識(shí)符在符號(hào)表中的地址不保留符號(hào)表，則用FORM結(jié)構(gòu)保存標(biāo)識(shí)符的語(yǔ)義信息語(yǔ)義棧Sem及其操作語(yǔ)義棧的內(nèi)容：運(yùn)算分量的類型和FORM數(shù)據(jù)結(jié)構(gòu)定義：typedef struct SemElem typ: ElemType; Form: FormStructtypedef SemElem SemStackMax 變量及

2、操作：SemStack Sem; /聲明Sem為語(yǔ)義棧int top; /聲明top為語(yǔ)義棧棧頂push(x) : 將x的類型和Form壓入語(yǔ)義棧 pop(n) ：從Sem棧棧頂依次彈出n個(gè)元素7.2 中間代碼生成中的幾個(gè)問(wèn)題常用的語(yǔ)義子程序申請(qǐng)臨時(shí)單元new_dir(t): 在臨時(shí)變量區(qū)申請(qǐng)一個(gè)單元t，且t是直接尋址new_indir(t): t是間接尋址存放中間代碼子程序Generate(,left,right,result)將一條四元式中間代碼存放到中間代碼區(qū)中產(chǎn)生一條中間代碼子程序GenCode()產(chǎn)生一條中間代碼子程序GenCode()調(diào)用該函數(shù)時(shí)，左右操作數(shù)已進(jìn)語(yǔ)義棧Sem;分別取

3、出左右操作數(shù)；檢查類型是否相同，不同則進(jìn)行轉(zhuǎn)換，產(chǎn)生類型轉(zhuǎn)換四元式；產(chǎn)生中間代碼（ *, Semtop-1, Semtop,t）pop(2); /彈出左右分量push(t) /壓入結(jié)果t的類型和FormL.typ, L.formR.typ, R.formSemtopt.typ, t.formSemtop7.3 表達(dá)式的中間代碼生成表達(dá)式的中間代碼就是依據(jù)原表達(dá)式的語(yǔ)義產(chǎn)生出正確計(jì)算表達(dá)式值的四元式中間代碼（即將計(jì)算順序體現(xiàn)出來(lái)）表達(dá)式的運(yùn)算分量可以是簡(jiǎn)單變量、復(fù)雜變量和函數(shù)調(diào)用表達(dá)式的運(yùn)算符可以是算術(shù)運(yùn)算符，關(guān)系運(yùn)算符，邏輯運(yùn)算符等首先給出簡(jiǎn)單算術(shù)表達(dá)式的中間代碼生成復(fù)合變量的中間代碼生成表達(dá)

4、式的四元式表達(dá)式E a *（3.5 + i *b）假設(shè)a,b為實(shí)型變量，i為整型變量 E生成的四元式如下：(FLOAT, i, -, t1)(MULTF, t1, b, t2)(ADDF, 3.5, t2, t3)(MULTF, a, t3, t4)表達(dá)式四元式生成LL(1)語(yǔ)法制導(dǎo)E T EsEs Es + T EsEs - T EsT P TsTs Ts *P TsTs /PTsP CP idP (E)E T EsEs Es + T #GenCode(+)#EsEs - T #GenCode(-)# EsT P TsTs Ts *P #GenCode(*)# TsTs /P #GenCod

5、e(/)# TsP C #Push(C)#P id #Push(id)#P (E)E a*(3.5+i*b)T Es a*(3.5+i*b)P Ts Es a*(3.5+i*b)id Ts Es a*(3.5+i*b) Ts Es *(3.5+i*b)Ts Es *(3.5+i*b)*PTs Es *(3.5+i*b)P Ts Es (3.5+i*b)(E) Ts Es (3.5+i*b)E) Ts Es 3.5+i*b)T Es) GenCode(*) Ts Es 3.5+i*b)P Ts Es) Ts Es 3.5+i*b)C Ts Es ) Ts Es 3.5+i*b) Ts Es )

6、Ts Es +i*b) Ts Es ) Ts Es +i*b)Ts Es) Ts Es +i*b)Es ) Ts Es +i*b)+ T Es ) Ts Es +i*b)T Es ) Ts Es i*b)PTs Es) Ts Es i*b)id Ts Es ) Ts Es i*b) Ts Es ) Ts Es *b)Ts Es ) Ts Es *b)*P Ts Es ) Ts Es *b)P Ts Es ) Ts Es b)id Ts Es) Ts Es b) Ts Es ) Ts Es ) Ts Es ) Ts Es )Ts Es ) Ts Es ) Es ) Ts Es )Es ) Ts

7、Es ) ) Ts Es ) Ts EsTs Es Es復(fù)合變量：下標(biāo)變量 Aij, 域名變量 , 指針變量 *p復(fù)合變量的中間代碼是計(jì)算復(fù)合變量地址的四元式變量的語(yǔ)法:V idV1 V2 EV1 V2.idV1 *V2地址: addr(V) = addr(id) addr(V1) = addr(V2)+(E-low+1)*Elesize addr(V1) = addr(V2)+offset(id) addr(V1) = content(addr(V2)復(fù)合變量的四元式生成一維下標(biāo)變量 ai和多維下標(biāo)變量 aijk下標(biāo)變量的四元式生成Var A:array L1.U1L2.U2L

8、nUn of T;(n=1)數(shù)組第1行的寬度是 D1=U1-L1+1;數(shù)組第i行的寬度是 Di=Ui-Li+1；設(shè)類型T所占單元數(shù)為，則數(shù)組A占單元數(shù)為size(A) = D1*D2*Dn* 下標(biāo)變量AE1E2Ek地址為：Addr(A) + (E1-L1)*S1 + (Ek-Lk)*Sk)*size(T)其中 當(dāng) i =1時(shí)，s1 = 1，否則 si = Di+1*Di+2*Dn sn = 1AE1E2Ek (k=n)(ASSIG, size(T), -, tsize)E1 t1(SUBI, t1, L1, t2)(MULTI, t2, s1, t3)(MULTI, t3, tsize, t4

9、)(AADD , addr(A), t4, ad)(SUBI, tn, Lk, tn+1)(MULTI, tn+1, sk, tn+2)(MULTI, tn+2, tsize, tn+3)(AADD , ad, tn+3, tn+4)Ek tn表達(dá)式代碼生成的例子typedef struct char name30; int age; float height; person;int x10; person class10; person *ptr;class5.age + *ptr.age(L, 0)(L, 10)(L, 340)class5.age t1*ptr.age t2 (+, t1

10、, t2, t3) class5 t4 (AADD , t4, 30, t1)(-, 5, 0, t5)(*, t5, 33, t6)(AADD, class, t6, t4) *ptr t7 (AADD , t7, 30, t2)(Assig, ptr, _, t7)t1,t2,t4和t7的mode是indir;第七章 中間代碼生成 7.1 幾種常見的中間表示 7.2 中間代碼中生成的幾個(gè)問(wèn)題 7.3 表達(dá)式的中間代碼生成 7.4 原子語(yǔ)句的中間代碼生成 7.5 結(jié)構(gòu)語(yǔ)句的中間代碼生成 7.6 聲明的中間代碼生成7.4 原子語(yǔ)句的中間代碼生成賦值語(yǔ)句: V = Exp;I/O 語(yǔ)句Read(

11、V);Write(Exp);Goto 語(yǔ)句 : Goto Label標(biāo)號(hào)語(yǔ)句: Label: Statement;函數(shù)調(diào)用返回語(yǔ)句: Return Exp;函數(shù)調(diào)用: F(Exp1, , Expn)賦值語(yǔ)句Left = RightLeft.code(ASSIG, t.Form, n, left.Form)Right.code其中n表示 Right.typ所占空間大小.(FLOAT, Right, _, t.Form)I/O 語(yǔ)句Write(Exp);Read(V)V.code(READ, _, _, V.Form)Exp.code(WRITE, _, _, Exp.Form)Goto語(yǔ)句和La

12、bel語(yǔ)句L: SGoto L(JUMP, _, _, LL)(LABEL, _, _, LL)S.codeReturn語(yǔ)句Return EE.code(RETURN, _, _, E.Form)Return(RETURN, _, _, _ )函數(shù)調(diào)用語(yǔ)句f(E1, , En)從符號(hào)表中獲取f 的屬性Level, params, type生成中間代碼E1.code函數(shù)調(diào)用形實(shí)參結(jié)合En.code(VALACT, 實(shí)參.Form, offset, size)(VARACT, 實(shí)參.Form, offset, size)(call, f, true, t)(call, f, false, t)函數(shù)

13、調(diào)用例子函數(shù)f(x+1,Y)，其中x是一般整型變量, Y是變參整型變量，假定f是實(shí)在函數(shù)，f的兩個(gè)形參一個(gè)是值參一個(gè)是變參(ADDI, x, 1, t1）(VALACT, t1, offset1, 1)(VARACT, Y, offset2, 1)(CALL, f, true, t2)第七章 中間代碼生成 7.1 幾種常見的中間表示 7.2 中間代碼中生成的幾個(gè)問(wèn)題 7.3 表達(dá)式的中間代碼生成 7.4 原子語(yǔ)句的中間代碼生成 7.5 結(jié)構(gòu)語(yǔ)句的中間代碼生成 7.6 聲明的中間代碼生成7.5 結(jié)構(gòu)語(yǔ)句的中間代碼生成條件語(yǔ)句If 語(yǔ)句Switch 語(yǔ)句循環(huán)語(yǔ)句While 語(yǔ)句Repeat 語(yǔ)句F

14、or 語(yǔ)句IF語(yǔ)句If語(yǔ)句有下面兩種形式： If then else If then ENYS1S2ENYSIF語(yǔ)句If 語(yǔ)句的中間代碼結(jié)構(gòu)： If then else E.code(THEN, E.Form, _, _)S1.code(ELSE, _, _, _)S2.code(ENDIF, _, _, _) If then E.code(THEN, E.Form, _, _)S1.code(ENDIF, _, _, _)IF語(yǔ)句中間代碼生成的LL(1)制導(dǎo) If then else If then 提取左公共前綴后，文法變?yōu)?If then else else else , #上述文法仍不

15、是LL(1)文法為使文法滿足LL(1)條件，為IF語(yǔ)句增加一個(gè)結(jié)束符endif ,則文法變?yōu)?IF語(yǔ)句中間代碼生成的LL(1)制導(dǎo) If then else endif If then endif提取左公共前綴后，文法變?yōu)?If then else endif else endif endif文法滿足LL(1)文法條件，語(yǔ)法制導(dǎo)： If then#ThenIf# else#ElseIf# endif #EndIf# endif #EndIf#IF語(yǔ)句的例子if (ab) then mark = true; c=a; else mark = false; c=b; endifIF語(yǔ)句If (E)

16、 S ENYSE.code(JUMP0, E.Form, _, exitL)S.code(LABEL, _, _, exitL)IF語(yǔ)句If (E) S1 else S2ENYS1S2E.code(JUMP0, E.arg, _, ElseL)S1.code(LABEL, _, _, ElseL)(JUMP, _, _, ExitL)S2.code(LABEL, _, _, ExitL)其中 ElseL 和 ExitL 是通過(guò)調(diào)用 NewLabel()生成的.While語(yǔ)句E.code(DO, E.Form, _, _)S.code(ENDWHILE, _, _,_)ENYS(WHILE, _

17、, _, _)while (E) SWhile語(yǔ)句例子while (a0) sum = sum*a; a-While語(yǔ)句E.code(JUMP0, E.Form, _, ExitL)S.code(JUMP, _, _, StartL)(LABEL, _, _, ExitL)其中StartL 和 ExitL 用NewLabel()生成.ENYS(LABEL, _, _, StartL)while (E) SSwitch語(yǔ)句switch E of case c1: S1; break; case cn: Sn; break; default: S; break; Ec1S1Endc2S2cnSno

18、therSSwitch語(yǔ)句Main ideaGenerate following labels with the function NewLabel()L1, , Ln, L : correspond to the entry to S1, , Sn, S;OutL: corresponds to the end of the switch statement; The process of executing switch statementCalculate E at first;Comparing the result of E with c1, , cn, if the result

19、of E is equal to ci, then goto Li;For each branch, generate labeled codes;Generate code for “OutL”;Switch語(yǔ)句四元式結(jié)構(gòu)E.codeswitch E of case c1: S1; break; case cn: Sn; break; default: S; break; L1: S1.code; (goto OutL)Ln: Sn.code; (goto OutL)L: S.code; (goto OutL)(JUMP1, E.arg=c1, L1)(JUMP1, E.arg=cn, Ln

20、)(JUMP, _, _, L)(LABEL, _, _, OutL)Switch語(yǔ)句的例子switch (a+b) of case 1: x=1; break; case 3: x=3; case 5: x=5; break; default: y=4; For語(yǔ)句for (E1; E2; E3) SE2YE1SE3NE3.code(JUMP0, E2.arg, _, ExitL)(LABEL, _, _, ExitL)(LABEL, _, _, StartL)E1.codeE2.code(JUMP, _, _, SL)(LABEL, _, _, EL)S.code(JUMP, _, _,

21、StartL)(LABEL, _, _, SL)(JUMP, _, _, EL)For語(yǔ)句for (E1; E2; E3) SE2YE1SE3NE3.code(JUMP0, E2.arg, _, ExitL)(LABEL, _, _, ExitL)(LABEL, _, _, StartL)E1.codeE2.codeS.code(JUMP, _, _, StartL)S.codeE3.codeFor語(yǔ)句for ( i=1 ; i10; i+ ) a= a*i;for ( ; i =0; ) i = f() ;Repeat語(yǔ)句Repeat S until EENYSE.code(JUMP0, E

22、.arg, _, StartL)S.code(LABEL, _, _, StartL)What about “do-while” statement?第七章 中間代碼生成 7.1 幾種常見的中間表示 7.2 中間代碼中生成的幾個(gè)問(wèn)題 7.3 表達(dá)式的中間代碼生成 7.4 原子語(yǔ)句的中間代碼生成 7.5 結(jié)構(gòu)語(yǔ)句的中間代碼生成 7.6 聲明的中間代碼生成聲明的四元式常量聲明 - 不生成代碼類型聲明 - 不生成代碼變量聲明 - 動(dòng)態(tài)數(shù)組時(shí)生成代碼 int a 函數(shù)聲明 - 順序生成下列代碼函數(shù)入口 (ENTRY, )參數(shù)聲明函數(shù)體函數(shù)出口(ENDFUN,)函數(shù)聲明一般形式：主要思想：在函數(shù)聲明中一讀到函數(shù)名 f , 為 f 分配一個(gè)新的標(biāo)號(hào) Lf ; 生成四元式 (ENTRY, Lf, size, leve