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

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

2、描述為A=（G，V，F(xiàn)）G是一個上下文無關(guān)文法V是G中各個符號的屬性的有窮集合F是有關(guān)屬性的斷言或謂詞的有窮集合，每個斷言和文法的某產(chǎn)生式相關(guān)聯(lián)。語法制導(dǎo)翻譯:在語法分析的過程中，完成附加在產(chǎn)生式上的語義規(guī)則描述的動作。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 屬性文法中，每個產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語義規(guī)則，形式為 b:= f(c1, c2, , ck)。 （1）若b是產(chǎn)生式左部A的一個屬性，c1,

3、c2, , ck是產(chǎn)生式右部符號或A的屬性，則b是A的綜合屬性。在分析樹中，一個結(jié)點的綜合屬性值是從其子結(jié)點的屬性值計算出來的。（2）若b是產(chǎn)生式右部符號X的一個屬性，c1, c2, , ck是A或右部符號的屬性，則b是X的繼承屬性。在分析樹中，一個結(jié)點的繼承屬性值是由該結(jié)點兄弟結(jié)點和父結(jié)點的屬性值計算出來的綜合屬性和繼承屬性5例2：簡單算術(shù)表達式的語義描述 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：變量的類型說明 規(guī)則 語義規(guī)則 D TL L.in:=T.type /將L.in屬性值設(shè)置為T.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：把標識符的類型信息登錄在符號表中相關(guān)項內(nèi)DTLintLid2,id1屬性信息傳遞情況7結(jié)論:（1）非終結(jié)符可以有綜合屬性和繼承屬性，但文法開始符沒有繼承屬性（2）終結(jié)符只有綜合屬性,由詞法分析程序提供88.2 語法制導(dǎo)翻譯 1、基于屬性文法的語法制導(dǎo)翻譯：對單詞符號串進行語法分析，構(gòu)造語法分析樹，再根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹，并在語法樹的各結(jié)點處按語義規(guī)則進行計算。屬性依賴圖DTL4realtypeLLid1,id3,id2in5in7in9101entry82entry3entry6例4：real id1, id2, id3; D TL；Tre

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

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

8、J 表達式為假跳轉(zhuǎn)到序號處16 格式： ifthenelse; 逆波蘭表達式： FJ 序號1指語句2的逆波蘭式的第1個符號處 RJ 序號2是指緊跟語句2的逆波蘭式的最后1個符號處 17例3：條件語句的逆波蘭表示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)語句的逆波蘭表示循環(huán)語句：(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等價代碼練習1：P202 1（7）20（三）四

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

11、 T3）四元式(:=, T3, / ,x)例3:223、轉(zhuǎn)向語句和條件語句的四元式（RJ,A,/,/)（TJ,A,B,/)（FJ,C,B,/)無條件跳轉(zhuǎn)到序號為A的四元式B為真跳轉(zhuǎn)到序號為A的四元式B為假跳轉(zhuǎn)到序號為C的四元式（1）跳轉(zhuǎn)語句:23（2）條件語句: ifthenelse;四元式： （FJ,A,T,/) 序號A是指語句2的開始處。 （RJ,C,/,/) 序號C是指緊跟語句2的四元式的編號 : :24例4：條件語句的四元式: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)語句的四元式:循環(huán)語句：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)四元式表示等價代碼26（四）三元式三元式： ( ,）四元式： （,）三元式與四元式的區(qū)別：四元式運算結(jié)果存儲在變量中；三元式運算結(jié)

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

14、到序號為A的三元式B為真跳轉(zhuǎn)到序號為A的三元式B為假跳轉(zhuǎn)到序號為A的三元式（1）跳轉(zhuǎn)語句:（2）條件語句:ifthenelse;三元式： （FJ,A,B) 序號A指語句2的第一個三元式的編號 （RJ,A,/) 序號A指緊跟語句2的三元式的編號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：條件語句 if ab then x:=a+b else x:=a-b 四元式與三元式比較30例4：循環(huán)語句的三元式循環(huán)語句：(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等價代碼練習2：P202 1（7）三元式，四元式318.4 簡單賦值語句的翻譯四元式: (op, arg1, arg2, result)幾個函數(shù)與符號lookup():審查是否在符號表中,如存在, 則返回該表項的指針, 否則返回nil。emit(): 將四元式輸出到中間代碼文件中。newtemp: 生成一個新的臨時變量/單元。E.place: 存放E值的變量名在符號表中的位置。32簡單賦值語句的四元式翻譯(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若是乘法運算呢？33類型轉(zhuǎn)換的語義處理：EE1*E2 E.pla