編譯原理課件第五章中間代碼生成

1、翻譯方式有兩種:,第五章 中間代碼生成,中間代碼的特點: 結(jié)構(gòu)簡單,功能明確,易于優(yōu)化,易于翻譯.,2,第一節(jié) 中間代碼簡介,1) 逆波蘭表示法 運算量在前,運算符在后的后綴式表示法. 例如: 表達式后綴式 a+bab+ (a+b)*cab+c* a*(b+c)abc+* (a+b)*(c+d)ab+cd+*,3,2) 三元式表示法 三元式就是三元組: ( 操作符,操作數(shù)1,操作數(shù)2) 例如: 語句 D:=A+B*C 可翻譯為下述三元式表: (1) (*,B,C) (2) (+,A,(1) (3) (:=,D,(2) 三元式?jīng)]有明確指出結(jié)果放在何處.,4,3) 四元式表示法 四元式就是四元組:

2、 ( 操作符,操作數(shù)1,操作數(shù)2,結(jié)果) 例如: 語句 D:=A+B*C 可翻譯為下述四元式表: (1) (* ,B ,C ,T1) (2) (+ ,A ,T1,T2) (3) (:= ,T2, , D ) 四元式間通過臨時變量傳值. 操作符實現(xiàn)的運算也非常簡單, 本章主要介紹各種語句到四元式的翻譯.,5,第二節(jié) 語法制導(dǎo)翻譯的基本思想,1 何謂語法制導(dǎo)翻譯 在語法分析的每次歸約或推導(dǎo)時,根據(jù)產(chǎn)生式的語義進行 翻譯的一種方法. 翻譯時,除了產(chǎn)生中間代碼外,還有許多輔助工作,包括: 改變語法變量的值;查填符號表;診查與報告源程序錯誤等. 2 與翻譯相關(guān)的若干約定 1) 臨時變量 在翻譯中,可能會

3、引入許多臨時變量存放中間結(jié)果. 通過調(diào)用 newtemp() 返回一個臨時變量 Ti .,6,2) 分析棧 分析棧中的內(nèi)容為語法單位,每個語法單位包含兩個部分: (語法單位名稱,語法單位屬性),屬性可能有多個值. 例如: E 為表達式的語法單位, E.place 代表了該表達式值 存放的地方. 3) 符號表 符號表用于存放變量及屬性值,由如干項構(gòu)成,每個項為: (變量名, 變量信息). 4) 四元式表 四元式表用于存放翻譯中產(chǎn)生的四元 式,通過過程 Gen( 操作符,操作數(shù)1,操作數(shù)2,結(jié)果) 把四元式存入四元式表的 NXQ 所指 空間中, NXQ 自動加 1.,四元式表,NXQ,7,5 一些

4、基本操作,newtemp( ) 產(chǎn)生一臨時變量; gen(操作符,操作數(shù)1,操作數(shù)2,結(jié)果) 填入四元式表; fill( i,屬性)填入符號表; entry( i )查符號表,返回 i 在符號表中的位置; backpatch( m,n) 把 n 填入 四元式表第 m 個四元式中;,8,第三節(jié) 簡單變量說明語句的翻譯,程序設(shè)計中,首先應(yīng)該對程序中使用的變量進行說明.其目的 是規(guī)定變量所占用空間的大小. 編譯時, 對變量說明語句的翻譯工 作,本質(zhì)上就是把變量名及屬性登記在符號表中,以便后續(xù)工作中 使用. pascal 語言的簡單變量說明語句為: x,y,z:real; 語法可表示為: D NAME

5、LIST:T NAMELIST NAMELIST,i | i T integer|real|boolean|char,該文法代表了所有 非結(jié)構(gòu)型變量的說明語 句.,9,當(dāng)然,也可以用如下文法表示: Di:T | i,D T integer|real|boolean|char 我們已經(jīng)知道用該文法如何分析一個說明語句,下面要解決 的是,怎樣在分析的過程中, 把該語句表達的意思完整的翻譯清楚. 說明語句的含義是: 說明的變量具有給定類型; 編譯時則翻譯為:把每個變量及類型登記在符號表中. 語法制導(dǎo)翻譯就是為每一條產(chǎn)生式配一個子程序,當(dāng)用某個 產(chǎn)生式歸約時,就調(diào)用相應(yīng)的子程序進行適當(dāng)?shù)姆g工作. 這

6、些子程序稱為語法單位的語義子程序(或語義動作).,10,下面討論如下文法的各產(chǎn)生式的語義子程序及翻譯過程 Di:T | i,D T integer|real|boolean|char 1) T integer T.att:=integer; 2) T real T.att:=real; 3) T boolean T.att:=boolean; 4) T char T.att:=char; 5) Di:T D.att:= T.att ; fill(i,T.att) ; 6) Di:D D.att:= D .att ; fill(i, D .att) ;,11,12,第四節(jié) 簡單算術(shù)表達式 和賦值

7、語句的翻譯,簡單算術(shù)賦值語句的文法可表示為: Si:=E EE+E | E-E | E*E | E/E | (E) | i 該文法為二義文法,但如果規(guī)定每個終結(jié)符的優(yōu)先關(guān)系,并按 優(yōu)先關(guān)系進行歸約,則可以避免二義性. 賦值語句的含義是:計算出 E 的值,并寫入變量 i 中. 編譯中,并不關(guān)心值是多少,而關(guān)心的是怎樣計算值的過程; 也即,哪些變量參加運算,怎樣運算? 上面文法的各產(chǎn)生式語義子程序如下:,13,Ei E.place:=entry(i) /E.place 表示了表達式E 的值放在什么變量中 E(E1) E.place:= E1.place E E1 + E2 E.place:=new

8、temp( ) Gen( + , E1 .place, E2.place, E.place) E E1 - E2 E.place:=newtemp( ) Gen( - , E1 .place, E2.place, E.place) E E1 * E2 E.place:=newtemp( ) Gen( * , E1 .place, E2.place, E.place) E E1 / E2 E.place:=newtemp( ) Gen( / , E1 .place, E2.place, E.place) S i := E Gen( := , E.place , ,entry( i ) 四元式中的

9、操作數(shù)及結(jié)果,實質(zhì)上是一指向變量的指針.,14,示例: x:=y+z,x:=y+z,x:=y,x:=E,x:=E+z,x:=E1+E2,E.place=entry(y),E1.place=entry(y); E2.place=entry(z),+z,+z,x:=E,E .place=T1 ;Gen(+,y,z, T1),S,Gen(:=, T1 , , x ),15,第五節(jié) 布爾表達式的翻譯,布爾表達式文法可表示為: Bnot B | B and B | B or B | (B) | i | E ROP E ROP | = | 該文法也為二義文法,但如果規(guī)定每個終結(jié)符的優(yōu)先關(guān)系,并按 優(yōu)先關(guān)系

10、進行歸約,則可以避免二義性. 各產(chǎn)生式語義子程序如下: ROP | = | ROP.val= 或 =或 ,16,Bi B.place:=entry(i) /B.place 表示了表達式B 的值放在什么變量中 B(B1) B.place:= B1.place B not B1 B.place:=newtemp( ) Gen( not , B1 .place, , B.place) B B1 and B2 B.place:=newtemp( ) Gen( and , B1 .place, B2.place, B.place) B B1 or B2 B.place:=newtemp( ) Gen(

11、or, B1 .place, B2.place, B.place) B E1 ROP E2 B.place:=newtemp( ) Gen( ROP.val, E1 .place, E2.place, B.place) ,17,第六節(jié) 分支語句的翻譯,分支語句包括: if case(省略) goto,1 if 語句的翻譯 在程序設(shè)計種,if 語句可以表示為: if B then S1 else S2; if 語句翻譯后,將得到一組四元式,其流程可以表示為:,18,分析是從前向后進行的,按四元式 流程的要求, (1)首先歸約布爾表達式,產(chǎn)生B的四元式; (2)在歸約S1之前,應(yīng)產(chǎn)生條件轉(zhuǎn)移語句,

12、也即 當(dāng)歸約 if B then 時,產(chǎn)生條件轉(zhuǎn)移語句; 由于 S1 S2 還未處理,因此,條件轉(zhuǎn)移語句 的轉(zhuǎn)移地址未知,只有等到S1處理完畢并 產(chǎn)生了無條件轉(zhuǎn)移語句,才能知道條件轉(zhuǎn) 移語句轉(zhuǎn)移的確切地址. (3)歸約S1;并在歸約 S1 else 時,產(chǎn)生無條件 轉(zhuǎn)移語句;此時,由于S2未處理, 無條件轉(zhuǎn) 移語句的轉(zhuǎn)移地址不確定;回填條件轉(zhuǎn)移語句的地址. (4)歸約S2;回填無條件轉(zhuǎn)移語句的地址.,*,*,19,從以上分析,可以將文法設(shè)計為: STS2 TCS1else Cif B then 語義子程序為: Cif B then C.chain:=NXQ; Gen(Jz,B.place, ,

13、xxxx) T CS1elseT.chain:=NXQ; Gen(J , , ,xxxx); backpatch(C.chain,NXQ) STS2backpatch (T.chain,NXQ),并設(shè):T C 有屬性值 T.chain及C.chain,用于 記錄條件及無條件轉(zhuǎn)移 四元式的序號.,20,示例: if A1 then x:=2 else y:=4,x:=2 else y:=4,C,CS1else,T,TS2,x:=2 else y:=4,y:=4,if B then,四元式序列 (1) (,A,1,T1) (2) (Jz,T1, ,xxxx) (5) (3) (:=,2, ,x)

14、(4) (J , , ,xxxx) (6) (5) (:=,4, ,y) (6),y:=4,S,C.chain=(2);Gen(Jz,T1, ,xxxx),T.chain=(4);Gen(J , , ,xxxx); backpatch(2),(5),backpatch(4),(6),NXQ,21,2 標號及轉(zhuǎn)移語句的翻譯 處理標號包括三個含義: 標號說明 標號定義 標號引用 (1) 標號說明的翻譯 標號說明語句的語法如下: Lablabel c | Lab,c 標號說明語句用于說明程序中使用 的所有標號,翻譯時只需將所有標號登 記在標號表中. 標號表的內(nèi)容如右圖所示: Lablabel c f

15、ill(c,未,0) Lab Lab,c fill(c,未,0) ,22,(2) 標號定義及引用 標號定義是指:確定標號所代表的某個四元式地址. 一般形式為: c:S c 這一標號代表了S的第一條四元式地址. 標號引用一般通過 goto c 實現(xiàn). 一般程序設(shè)計中,允許標號的引用及定義交叉進行,如下所示:,goto c; goto c; c: S; goto c;,因此,當(dāng)翻譯到第一個 goto 語句時, 標號 c 還未定義, goto 語句的轉(zhuǎn)移地址 不確定,只有翻譯到標號定義時,才能回 過頭來回填地址.,23,可以利用標號表地址欄,當(dāng)標號已定義時,地址欄就是標號 所代表的地址;當(dāng)標號未定義

16、時,地址欄用于連接所有轉(zhuǎn)移到該 標號的轉(zhuǎn)移四元式,當(dāng)翻譯到標號定義時,以便回填所有轉(zhuǎn)移到 該標號的轉(zhuǎn)移四元式. 文法及語義動作如下: S goto c 若 c 已定義 則 Gen(J, , , entry(c).addr) 否則 Gen(J, , , entry(c).addr); entry(c).addr:=NXQ-1 Ldefc: 令 entry(c).定義否:=已定義; 用 NXQ 回填 entry(c).addr 鏈中所有 轉(zhuǎn)移四元式 ,24,第七節(jié) 循環(huán)語句的翻譯,循環(huán)語句有三種方式: while B do S repeat S until B for i:=E1 to E2 do

17、 S 1 while B do S 的翻譯 該語句翻譯為如右圖所示的 四元式系列. 從流程圖中可以看出,有兩處 的四元式地址需特殊處理:,*,*,25,while 語句的文法及語義子程序如下: SWd S Gen(J , , , Wd .q ) backpatch(Wd .chain,NXQ) Wd W B do Wd .q := W.q /傳遞給Wd. Wd .chain:=NXQ; Gen(Jz,B.place, , xxxx) Wwhile W.q:=NXQ /記住 B 的第一條四元式地址,26,2 repeat S until B 的翻譯 SR S until B Gen(Jz, B.

18、place, ,R.q) Rrepeat R.q:=NXQ *S 可以是復(fù)合語句,S 的四元式,B為真?,B的四元式,F,T,27,3 for i:=E1 to E2 do S 的翻譯 SF2 do S Gen( inc, , , F2.place) Gen( J , , , F2.chain) backpatch(F2.chain, NXQ ) F2F1 to E2 F2.chain:=NXQ; F2.place:=F1.place Gen (Jg,F1.place ,E2.place, xxxx) F1for i:= E1 Gen (:= ,E1.place, ,entry(i) F1.p

19、lace :=entry(i) ,E1的四元式,i E2?,E2的四元式,T,i:=E1,S的四元式,i:=i+1,28,第八節(jié) 數(shù)組的翻譯,這節(jié)討論三個問題: 數(shù)組說明的翻譯 數(shù)組元素的翻譯 含數(shù)組元素的賦值語句的翻譯 1 數(shù)組說明語句的翻譯 進行數(shù)組說明語句的 翻譯時,要把數(shù)組名填入符號表, 并建立一內(nèi)情向量表,記錄維數(shù),下標上下界,類型等. 簡單起見,只考慮如下的數(shù)組說明: A:arrayL1:U1, L2:U2,. Ln:Un of TYPE,29,文法如下: Di:array LIST of T LISTi(1):i(2)| LIST (1) , i(1):i(2) Tinteger

20、|real|char|boolean 語義子程序如下: LISTi(1):i(2)建立一個僅含 i(1):i(2) 的隊列LIST.Q LIST LIST (1) , i(1):i(2) 把 i(1):i(2) 插入隊列LIST.Q中 Di:array LIST of T i 填入符號表并標志為數(shù)組;開辟內(nèi)情向量表, 把LIST.Q 中的上下界對逐一取出,計算 di, 并將 i(1),i(2) , di, 放入內(nèi)情向量表;計算維數(shù) n 及 c, 將 T.attr,n,c 填入內(nèi)情向量表. 數(shù)組說明語句不產(chǎn)生四元式.,30,c = ( L1 )*d2d3d4.dn + ( L2 )* d3d4.

21、dn + ( Ln-1)* dn + ( Ln ) *elemlength = (.(L1d2+L2)d3+L3)d4+L4).) dn + Ln *elemlength,31,2 數(shù)組元素的翻譯 設(shè)數(shù)組元素為: A E1,E2,.En, 要取得該元素值,首先要計算 出該元素的地址: addr=conspart+varpart conspart =a -c varpart = (.(E1d2+E2)d3+E3)d4+E4).) dn + En conspart 的 a c 已經(jīng)通過數(shù)組說明語句的翻譯登記在內(nèi) 情向量表中; 而 varpart 中含有未知數(shù),只能在程序運行時通過如 下算法實現(xiàn):,

22、32,varpart:=E1;k:=1; while kn do varpart:=varpart*dk +1 + Ek +1; K:=k+1 下面是包含數(shù)組元素的變量的文法: Vi | i E1,E2,.En 為了便于翻譯上面的算法,文法改為如下形式: Vi | Elist Elisti E | Elist1,E V 有兩個值 : V.place , V.off 對于簡單變量 , V.place = entry(i),V.off=0; 對于數(shù)組變量 , V.place = a -c , V.off=varpart;,33,Elist 有三個值 : Elist.array/ i 在符號表中的位置 Elist.dim/ i 的維數(shù) Elist.