語(yǔ)法制導(dǎo)翻譯和中間代碼生成課件

1、第八章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成教學(xué)目的理解語(yǔ)義處理的功能與作用掌握語(yǔ)法制導(dǎo)翻譯的方法掌握中間代碼的翻譯教學(xué)重點(diǎn)理解屬性、屬性文法的概念理解語(yǔ)法制導(dǎo)翻譯的基本原理掌握幾種常見(jiàn)的中間代碼了解常見(jiàn)語(yǔ)法結(jié)構(gòu)的翻譯1引言語(yǔ)義處理：在詞法分析程序、語(yǔ)法分析程序完成源程序結(jié)構(gòu)分析后，由語(yǔ)法分析程序直接調(diào)用相應(yīng)的語(yǔ)義子程序進(jìn)行語(yǔ)義處理。 語(yǔ)義處理的功能：靜態(tài)語(yǔ)義檢查，驗(yàn)證語(yǔ)法結(jié)構(gòu)合法的程序是否真正有意義代碼生成，如果靜態(tài)語(yǔ)義正確，則將源代碼翻譯成目標(biāo)代碼或中間代碼。28.1 屬性文法目前語(yǔ)義處理尚不能完全形式化，常采用屬性文法和語(yǔ)法制導(dǎo)翻譯方法進(jìn)行描述。屬性文法:包含一個(gè)上下文無(wú)關(guān)文法和一系列的語(yǔ)義規(guī)則，

2、描述為A=（G，V，F(xiàn)）G是一個(gè)上下文無(wú)關(guān)文法V是G中各個(gè)符號(hào)的屬性的有窮集合F是有關(guān)屬性的斷言或謂詞的有窮集合，每個(gè)斷言和文法的某產(chǎn)生式相關(guān)聯(lián)。語(yǔ)法制導(dǎo)翻譯:在語(yǔ)法分析的過(guò)程中，完成附加在產(chǎn)生式上的語(yǔ)義規(guī)則描述的動(dòng)作。3例1: 文法：ET1 + T2 | T1 or T2 Tnum | true | false分析 3+4ET1+T243T1.t=intT2.t=intT1.t=int AND T2.t=intN.t表示非終結(jié)符N相聯(lián)的屬性t4 屬性文法中，每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，形式為 b:= f(c1, c2, , ck)。 （1）若b是產(chǎn)生式左部A的一個(gè)屬性，c1,

3、c2, , ck是產(chǎn)生式右部符號(hào)或A的屬性，則b是A的綜合屬性。在分析樹(shù)中，一個(gè)結(jié)點(diǎn)的綜合屬性值是從其子結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的。（2）若b是產(chǎn)生式右部符號(hào)X的一個(gè)屬性，c1, c2, , ck是A或右部符號(hào)的屬性，則b是X的繼承屬性。在分析樹(shù)中，一個(gè)結(jié)點(diǎn)的繼承屬性值是由該結(jié)點(diǎn)兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的綜合屬性和繼承屬性5例2：簡(jiǎn)單算術(shù)表達(dá)式的語(yǔ)義描述 LE print (E.val) EE1+T E.val := E1.val +T.val ET E.val := T.val TT1*F T.val := T1.val *F.val TF T.val := F.val F(E) F.v

4、al := E.val Fdigit F.val := digit.lexval 其中E、T、F都有屬性val，都是綜合屬性。 Lexval 由詞法分析的結(jié)果提供EE1+TE.val := E1.val +T.val6例3：變量的類(lèi)型說(shuō)明 規(guī)則 語(yǔ)義規(guī)則 D TL L.in:=T.type /將L.in屬性值設(shè)置為T(mén).type T int T.type=integer Treal T.type:=real L L1,id L1.in:=L.in addtype(id.entry, L. in) /產(chǎn)生虛屬性 L id addtype(id.entry, L. in) 其中， L.in是繼承屬性

5、，T有綜合屬性type。Addtype：把標(biāo)識(shí)符的類(lèi)型信息登錄在符號(hào)表中相關(guān)項(xiàng)內(nèi)DTLintLid2,id1屬性信息傳遞情況7結(jié)論:（1）非終結(jié)符可以有綜合屬性和繼承屬性，但文法開(kāi)始符沒(méi)有繼承屬性（2）終結(jié)符只有綜合屬性,由詞法分析程序提供88.2 語(yǔ)法制導(dǎo)翻譯 1、基于屬性文法的語(yǔ)法制導(dǎo)翻譯：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，再根據(jù)需要構(gòu)造屬性依賴圖，遍歷語(yǔ)法樹(shù)，并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。屬性依賴圖DTL4realtypeLLid1,id3,id2in5in7in9101entry82entry3entry6例4：real id1, id2, id3; D TL；Tre

6、alL L,id； L id 9例5：分析2+3*5 歸約時(shí)完成語(yǔ)義處理LEE+TTF2T*FF53LEE+TTF(2)T*FF53LEE(2)+T(15)綜合屬性可自下而上進(jìn)行計(jì)算。2、簡(jiǎn)單算術(shù)表達(dá)式求值：用一個(gè)產(chǎn)生式進(jìn)行歸約時(shí)就執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作，在分析一個(gè)句子時(shí)，句子的值同時(shí)產(chǎn)生。（自下而上分析）102+3*5的分析和計(jì)值過(guò)程（p142表7.8）118.3 中間代碼形式源程序目標(biāo)代碼編譯程序一、編譯程序1、2、3、源程序詞法語(yǔ)法語(yǔ)義中間代碼目標(biāo)代碼生成源程序詞法語(yǔ)法語(yǔ)義中間代碼目標(biāo)代碼生成優(yōu)化優(yōu)化后的中間代碼12二、幾種常用的中間代碼形式中間代碼逆波蘭表 示四元式三元式樹(shù)約定：LJ表示轉(zhuǎn)

7、向某標(biāo)號(hào)處； TJ表示按真跳轉(zhuǎn)；FJ表示按假跳轉(zhuǎn)；RJ表示無(wú)條件跳轉(zhuǎn)13*-表達(dá)式的樹(shù)表示中綴：a*b-(c+d)/(e-f)ab/+cd-ef（后綴）逆波蘭： ab*cd+ef-/-（一）樹(shù)14（二）逆波蘭表示1、賦值語(yǔ)句的逆波蘭表示賦值語(yǔ)句 :=逆波蘭表達(dá)式 :=例1： y:=(a+b)*c; yab+c*:=2、轉(zhuǎn)向語(yǔ)句的逆波蘭表示 轉(zhuǎn)向語(yǔ)句：goto 逆波蘭式： LJ 例2：100：write（晚上好）； . goto 100;逆波蘭表示：100LJ 153、條件語(yǔ)句的逆波蘭表示（a）無(wú)條件跳轉(zhuǎn)： 逆波蘭式： RJ 例3： 100RJ （b）有條件跳轉(zhuǎn)： TJ表達(dá)式為真跳轉(zhuǎn)到序號(hào)處 F

8、J 表達(dá)式為假跳轉(zhuǎn)到序號(hào)處16 格式： ifthenelse; 逆波蘭表達(dá)式： FJ 序號(hào)1指語(yǔ)句2的逆波蘭式的第1個(gè)符號(hào)處 RJ 序號(hào)2是指緊跟語(yǔ)句2的逆波蘭式的最后1個(gè)符號(hào)處 17例3：條件語(yǔ)句的逆波蘭表示if ab then x:=a+b else x:=a-b1234567891011121314151617abi+j then begin k:=k-1; goto 10 end else k:=i*i-j*j i:=0; j:=0;end;(1)block(2)k100:=(5)kij+19FJ(12)kk1-:=5RJ(19)kii*jj*-:=(28)i0:=j0:=(34)bl

9、ockend(1) block(2) k100:=(5) 10:(7) kij+ 21FJ(14) kk1-:= 10LJ(21) kii*jj*-:=(30) i0:=(33) j0:=(36) blockend ( )( )( )( )21FJ10LJ194、循環(huán)語(yǔ)句的逆波蘭表示循環(huán)語(yǔ)句：(1)i1:=(4)i100=21FJ(9)ssi+:=(14)ii1+:=4RJ(21)逆波蘭表示for i:=1 to 100 do s:=s+ii:=1;10:if i=100 then begin s:=s+i; i:=i+1; goto 10 end等價(jià)代碼練習(xí)1：P202 1（7）20（三）四

10、元式四元式：四元式定義為一個(gè)四元組： （,） 其中指運(yùn)算結(jié)果。雙目運(yùn)算：a+b（ + ，a , b , T ）（,）臨時(shí)變量，存放a+b的結(jié)果單目運(yùn)算：a（ ，a , / , T ）單目運(yùn)算無(wú)需分量2，寫(xiě)成/21例1:a*b+c/d表達(dá)式（*, a, b, T1）（/, c, d, T2）（+, T1, T2, T3）四元式1、表達(dá)式的四元式:例2：（含單目運(yùn)算）-（a/b+c）表達(dá)式 （/,a, b, T1）（+, T1, c, T2）（ ,T2, /, T3）四元式2、賦值語(yǔ)句的四元式x:= -（a/b+c）賦值語(yǔ)句（/, a, b, T1）（+,T 1, c, T2）（ , T2, /,

11、 T3）四元式(:=, T3, / ,x)例3:223、轉(zhuǎn)向語(yǔ)句和條件語(yǔ)句的四元式（RJ,A,/,/)（TJ,A,B,/)（FJ,C,B,/)無(wú)條件跳轉(zhuǎn)到序號(hào)為A的四元式B為真跳轉(zhuǎn)到序號(hào)為A的四元式B為假跳轉(zhuǎn)到序號(hào)為C的四元式（1）跳轉(zhuǎn)語(yǔ)句:23（2）條件語(yǔ)句: ifthenelse;四元式： （FJ,A,T,/) 序號(hào)A是指語(yǔ)句2的開(kāi)始處。 （RJ,C,/,/) 序號(hào)C是指緊跟語(yǔ)句2的四元式的編號(hào) : :24例4：條件語(yǔ)句的四元式:if ab then x:=a+b else x:=a-b（1） （,a,b,T1)（2） （FJ,6,T1,/)（3） （+,a,b,T2)（4） （:=,T2

12、,/,x)（5） （RJ,8,/,/)（6） （-,a,b,T3)（7） （:=,T3,/,x)（8） ( . )25例5：循環(huán)語(yǔ)句的四元式:循環(huán)語(yǔ)句：for i:=1 to 100 do s:=s+ii:=1;10:if i=100 then begin s:=s+i; i:=i+1; goto 10 end(1)（:=,1,/i)(2)(=,I,100,B)(3)(FJ,7,B,/)(4)(+,s,i,s)(5)(+,i,1,i)(6)(RJ,2,/,/)(7)四元式表示等價(jià)代碼26（四）三元式三元式： ( ,）四元式： （,）三元式與四元式的區(qū)別：四元式運(yùn)算結(jié)果存儲(chǔ)在變量中；三元式運(yùn)算結(jié)

13、果用三元式的位置或序號(hào)來(lái)代替；a*b+c/d表達(dá)式（*,a,b,T1）（/,c,d,T2）（+,T1,T2,T3）四元式a*b+c/d表達(dá)式(1) (*,a,b）(2) (/,c,d）(3) (+,(1),(2)）三元式27例1a*b+c/d表達(dá)式(1) (*a,b）(2) (/,c,d）(3) (+,(1),(2)）三元式1、表達(dá)式的三元式：2、賦值語(yǔ)句的三元式x:= -（a/b+c）賦值語(yǔ)句 (1)（/,a,b, ）(2)（+,(1),c）(3)（ ,(2),/）三元式(4)(:=,(3),x)例2283、轉(zhuǎn)向語(yǔ)句和條件語(yǔ)句的三元式（RJ,A,/)（TJ,A,B)（FJ,A,B)無(wú)條件跳轉(zhuǎn)

14、到序號(hào)為A的三元式B為真跳轉(zhuǎn)到序號(hào)為A的三元式B為假跳轉(zhuǎn)到序號(hào)為A的三元式（1）跳轉(zhuǎn)語(yǔ)句:（2）條件語(yǔ)句:ifthenelse;三元式： （FJ,A,B) 序號(hào)A指語(yǔ)句2的第一個(gè)三元式的編號(hào) （RJ,A,/) 序號(hào)A指緊跟語(yǔ)句2的三元式的編號(hào)29（1） （, a, b)（2） （FJ, 6, (1)（3） （+, a, b)（4） （:=, (3), x)（5） （RJ, 8, /)（6） （-, a, b)（7） （:=, (6), x)（8） ( . )三元式（1） （, a, b, T1)（2） （FJ, 6, T1 ,/)（3） （+, a, b, T2)（4） （:=, T2, /,

15、 x)（5） （RJ, 8, /, /)（6） （-, a, b, T3)（7） （:=, T3, /, x)（8） ( . )四元式例3：條件語(yǔ)句 if ab then x:=a+b else x:=a-b 四元式與三元式比較30例4：循環(huán)語(yǔ)句的三元式循環(huán)語(yǔ)句：(1)(:=,1,i)(2)(=,i,100)(3)(FJ,9,(2)(4)(+,s,i)(5)(:=,(4),s)(6)(+,i,1)(7)(:=,(6),i)(8)(RJ,2,/)(9)三元式表示for i:=1 to 100 do s:=s+ii:=1;10:if i=100 then begin s:=s+i; i:=i+1;

16、 goto 10 end等價(jià)代碼練習(xí)2：P202 1（7）三元式，四元式318.4 簡(jiǎn)單賦值語(yǔ)句的翻譯四元式: (op, arg1, arg2, result)幾個(gè)函數(shù)與符號(hào)lookup():審查是否在符號(hào)表中,如存在, 則返回該表項(xiàng)的指針, 否則返回nil。emit(): 將四元式輸出到中間代碼文件中。newtemp: 生成一個(gè)新的臨時(shí)變量/單元。E.place: 存放E值的變量名在符號(hào)表中的位置。32簡(jiǎn)單賦值語(yǔ)句的四元式翻譯(1) S id := E P:=lookup () ; if Pnil then emit( P:=E.place) else error (2) EE1+E2 E.place:= newtemp; emit(E.place := E1.place+E2.place) (3) E - E1 E.place:=newtemp; emit(E.place := uminus E1.place)(4) E( E1) E.place:= E1.place(5) Eid E.place:=newtemp; P:=lookup(); if Pnil then E.place:=P else error若是乘法運(yùn)算呢？33類(lèi)型轉(zhuǎn)換的語(yǔ)義處理：EE1*E2 E.pla