第8章 語法制導翻譯及中間代碼(4學時)

1、第第8 8章章 語法制導翻譯和中間代碼語法制導翻譯和中間代碼n屬性文法屬性文法n語法制導翻譯語法制導翻譯n中間代碼的形式中間代碼的形式逆波蘭式、三元式、樹形表示、四元式逆波蘭式、三元式、樹形表示、四元式n一些語句的翻譯一些語句的翻譯 賦值語句賦值語句 布爾表達式布爾表達式 控制語句中的布爾表達式控制語句中的布爾表達式 For For循環(huán)語句循環(huán)語句8.1 8.1 屬性文法屬性文法預備知識預備知識n源程序與目標程序，源程序與目標程序，語法結(jié)構(gòu)完全不同語法結(jié)構(gòu)完全不同，但語義相同，但語義相同，所以所以表達的結(jié)果完全相同表達的結(jié)果完全相同。n語義分析的語義分析的2種處理方法：種處理方法：1）語法分析

2、之后，直接調(diào)用相應的）語法分析之后，直接調(diào)用相應的“語義子程序語義子程序”進行進行語義處理語義處理2）語法分析之后，先生成）語法分析之后，先生成“語法樹語法樹”或其他形式，再進或其他形式，再進行語義處理行語義處理n語義分析的處理結(jié)果：語義分析的處理結(jié)果：1）目標代碼）目標代碼2）中間代碼：復雜性介于源程序語言和機器語言之間）中間代碼：復雜性介于源程序語言和機器語言之間n靜態(tài)語義分析：審查語法結(jié)構(gòu)的靜態(tài)語義靜態(tài)語義分析：審查語法結(jié)構(gòu)的靜態(tài)語義 確定標識符的數(shù)據(jù)類型確定標識符的數(shù)據(jù)類型 類型檢查和轉(zhuǎn)換類型檢查和轉(zhuǎn)換：檢查運算對象的數(shù)據(jù)類型是否：檢查運算對象的數(shù)據(jù)類型是否合法，必要時進行類型轉(zhuǎn)換合法

3、，必要時進行類型轉(zhuǎn)換 一致性檢查一致性檢查：一個對象只能被聲明一次：一個對象只能被聲明一次 作用域檢查作用域檢查 控制流檢查控制流檢查：控制語句轉(zhuǎn)到合法的地方繼續(xù)執(zhí)行：控制語句轉(zhuǎn)到合法的地方繼續(xù)執(zhí)行n翻譯翻譯（若靜態(tài)語義分析正確后才翻譯）（若靜態(tài)語義分析正確后才翻譯） 語義處理的任務和功能語義處理的任務和功能 常用的語義分析方法常用的語義分析方法語法制導翻譯語法制導翻譯語法制導翻譯：語法制導翻譯：n首先，使用首先，使用屬性文法屬性文法為工具，描述程序設計語言的為工具，描述程序設計語言的語義規(guī)則。語義規(guī)則。 n在語法分析時，每應用一個產(chǎn)生式（推導或歸約），在語法分析時，每應用一個產(chǎn)生式（推導或歸

4、約），同時完成該產(chǎn)生式上所附的語義規(guī)則描述的動作，同時完成該產(chǎn)生式上所附的語義規(guī)則描述的動作，從而完成語義處理。從而完成語義處理。語義分析的方法語義分析的方法 n用于描述語義規(guī)則的文法。用于描述語義規(guī)則的文法。n對文法的對文法的每個符號引入一些屬性每個符號引入一些屬性，這些，這些屬性代表與文法符號相關(guān)的信息，例如：屬性代表與文法符號相關(guān)的信息，例如：類型、值、代碼序列、符號表內(nèi)容等。類型、值、代碼序列、符號表內(nèi)容等。n屬性屬性值值可以在語法分析過程中進行可以在語法分析過程中進行計算計算和傳遞和傳遞。n屬性的加工過程就是語義的處理過程。屬性的加工過程就是語義的處理過程。屬性文法屬性文法 ( (a

5、ttribute grammar)attribute grammar)n屬性文法的組成：屬性文法的組成：u一個一個 u一系列一系列（附在文法的每個產(chǎn)生式上）（附在文法的每個產(chǎn)生式上）n屬性文法的形式：三元組屬性文法的形式：三元組 A=(G,V,F)A=(G,V,F)G G: :是一個是一個上下文無關(guān)文法上下文無關(guān)文法V V: :有窮有窮屬性集屬性集, ,每個屬性與文法的一個終結(jié)符每個屬性與文法的一個終結(jié)符或非終結(jié)符關(guān)聯(lián)或非終結(jié)符關(guān)聯(lián)F F: :關(guān)于屬性的關(guān)于屬性的斷言或謂詞集斷言或謂詞集. .每個斷言與一個每個斷言與一個產(chǎn)生式關(guān)聯(lián)產(chǎn)生式關(guān)聯(lián). .而此斷言只引用該產(chǎn)生式的終結(jié)而此斷言只引用該產(chǎn)生

6、式的終結(jié)符或非終結(jié)符相關(guān)聯(lián)的屬性符或非終結(jié)符相關(guān)聯(lián)的屬性屬性文法屬性文法 ( (attribute grammar)attribute grammar)屬性文法屬性文法 舉例舉例例例1 1 說明語句中各種變量的類型信息的語義規(guī)則：說明語句中各種變量的類型信息的語義規(guī)則： 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 D DTLTL T Tcharchar T Tintint T Tfloatfloat L LL L1 1,id,id(1)(1) L Lidid L.in := T.type L.in := T.type T.type := char T.type := char T.type := int T

7、.type := int T.type := float T.type := float L L1 1.in := L.in.in := L.in addtype(id.entry, L.in) addtype(id.entry, L.in) addtype(id.entry, L.in) addtype(id.entry, L.in) 屬性文法屬性文法 舉例舉例例例2 2 表達式表達式類型檢查類型檢查和和求值求值的語義規(guī)則：的語義規(guī)則：假設：類型不同的兩個變量進行運算則語義錯誤。假設：類型不同的兩個變量進行運算則語義錯誤。 產(chǎn)生式產(chǎn)生式語義規(guī)則語義規(guī)則 L LE E E EE E1 1+T+

8、T E ET T T TT T1 1* *F F T TF F F F(E)(E)(1)(1) F Fidid print(E.val); print(E.val); if(Eif(E1 1.type=T.type).type=T.type) E.type:=EE.type:=E1 1.type;.type;E.val:=EE.val:=E1 1.val+T.val; .val+T.val; else error(); else error(); E.type:=T.type; E.val:=T.val E.type:=T.type; E.val:=T.val getType(F.type,

9、id.entry); getType(F.type, id.entry); F.val:=id.lexval; F.val:=id.lexval; 語法制導翻譯的語法制導翻譯的實質(zhì)實質(zhì)：根據(jù)每個產(chǎn)生式所對應的語義規(guī)則，隨語法分析的根據(jù)每個產(chǎn)生式所對應的語義規(guī)則，隨語法分析的每一步（推導或歸約），執(zhí)行相應的語義動作。每一步（推導或歸約），執(zhí)行相應的語義動作。語法制導翻譯的語法制導翻譯的過程過程：對單詞符號串進行語法分析，構(gòu)造語法分析樹；對單詞符號串進行語法分析，構(gòu)造語法分析樹；1)然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹，并然后根據(jù)需要構(gòu)造屬性依賴圖，遍歷語法樹，并在語法樹的各結(jié)點處按語義規(guī)則進行

10、計算。在語法樹的各結(jié)點處按語義規(guī)則進行計算。8.2 8.2 語法制導翻譯概論語法制導翻譯概論使用使用“依賴圖依賴圖”，從依賴圖的拓撲排序中得到計算語義，從依賴圖的拓撲排序中得到計算語義規(guī)則的順序，再依照順序?qū)斎氪M行語義分析規(guī)則的順序，再依照順序?qū)斎氪M行語義分析。依賴圖依賴圖一個有向圖，用于描述分析樹中的屬性和屬性之間一個有向圖，用于描述分析樹中的屬性和屬性之間的相互依賴關(guān)系。的相互依賴關(guān)系。構(gòu)造依賴圖舉例：參見構(gòu)造依賴圖舉例：參見P172 圖圖8.4屬性計算方法屬性計算方法 樹遍歷樹遍歷：事先建立語法樹，（深度優(yōu)先）遍歷：事先建立語法樹，（深度優(yōu)先）遍歷直至計算出所有屬性值。直至計算出

11、所有屬性值。 一遍掃描一遍掃描：在語法分析的同時計算屬性值。：在語法分析的同時計算屬性值。計算語義規(guī)則計算語義規(guī)則n屬性：屬性： 綜合屬性綜合屬性：可以在分析輸入串的同時，可以在分析輸入串的同時，自下而上自下而上地來計算。如：地來計算。如：valval 繼承屬性繼承屬性：一個結(jié)點的繼承屬性值是由此結(jié)點的一個結(jié)點的繼承屬性值是由此結(jié)點的父結(jié)點和（或）兄弟結(jié)點的某些屬性來決定的。父結(jié)點和（或）兄弟結(jié)點的某些屬性來決定的。如：如：L.inn屬性文法：屬性文法： S-S-屬性屬性文法文法：L-L-屬性文法的一個特例屬性文法的一個特例 L-L-屬性文法屬性文法：例例1 1就是一個就是一個L-L-屬性文法

12、屬性文法n屬性文法的計算：屬性文法的計算：可以是普通意義上的數(shù)學可以是普通意義上的數(shù)學運算，也可以是打印輸出等動作。運算，也可以是打印輸出等動作。屬性文法的類型和計算屬性文法的類型和計算S-屬性文法屬性文法：是是L-L-屬性文法的一個特例，只含有屬性文法的一個特例，只含有綜合屬性。例綜合屬性。例2 2是一個是一個S-S-屬性文法。屬性文法。S-屬性文法翻譯器屬性文法翻譯器：可以借助可以借助LRLR分析器實現(xiàn)。分析器實現(xiàn)。實現(xiàn)原理實現(xiàn)原理：LRLR分析器中增加一個棧（分析器中增加一個棧（語義值棧語義值棧）用來用來存放綜合屬性的值存放綜合屬性的值，進行歸約的同時，棧中，進行歸約的同時，棧中正在歸約

13、的產(chǎn)生式右部符號的綜合屬性值彈棧，正在歸約的產(chǎn)生式右部符號的綜合屬性值彈棧，并調(diào)用相應語義子程序進行相應計算（完成屬性并調(diào)用相應語義子程序進行相應計算（完成屬性文法中的語義規(guī)則），產(chǎn)生的新值入語義值棧。文法中的語義規(guī)則），產(chǎn)生的新值入語義值棧。舉例：舉例：參見參見P174 P174 圖圖8.78.7S-S-屬性文法和屬性文法和自下而上自下而上翻譯翻譯L-屬性文法屬性文法：對于對于文法中的每個產(chǎn)生文法中的每個產(chǎn)生式式A AX X1 1X X2 2X Xn n，其每個語義規(guī)則中的其每個語義規(guī)則中的每個屬性要么是綜合屬性，要么是每個屬性要么是綜合屬性，要么是X Xj j(1jn)(1jn)的一個繼承

14、屬性且該繼承的一個繼承屬性且該繼承屬性僅依賴于：產(chǎn)生式中屬性僅依賴于：產(chǎn)生式中X X1 1,X,X2 2, ,X Xj-1j-1的屬性和的屬性和A A的繼承屬性。的繼承屬性。L-屬性文法優(yōu)點：屬性文法優(yōu)點：允許一次遍歷就計允許一次遍歷就計算出所有屬性值。算出所有屬性值。L-L-屬性文法屬性文法L-屬性文法翻譯器屬性文法翻譯器：可以借助可以借助LLLL分析器實現(xiàn)。分析器實現(xiàn)。實現(xiàn)原理實現(xiàn)原理：在自頂向下分析的過程中，每應在自頂向下分析的過程中，每應用一個產(chǎn)生式進行推導，同時完成該產(chǎn)生式用一個產(chǎn)生式進行推導，同時完成該產(chǎn)生式上屬性文法的計算。上屬性文法的計算。LL(1)分析方法的語義描述：分析方法

15、的語義描述：語義動作不是語義動作不是附在產(chǎn)生式右部的末尾，而是嵌在兩個符號附在產(chǎn)生式右部的末尾，而是嵌在兩個符號之間。這樣的語義描述稱為之間。這樣的語義描述稱為翻譯模式翻譯模式。舉例：舉例：P174 例例8.3 例例8.4L-L-屬性文法在屬性文法在自上而下自上而下分析中的實現(xiàn)分析中的實現(xiàn)翻譯模式翻譯模式：語義動作不是附在產(chǎn)生式語義動作不是附在產(chǎn)生式右部的末尾，而是嵌在兩個符號之間。右部的末尾，而是嵌在兩個符號之間。翻譯模式是適合語法知道翻譯的另一翻譯模式是適合語法知道翻譯的另一種描述形式。種描述形式。翻譯模式給出了使用語義規(guī)則進行計翻譯模式給出了使用語義規(guī)則進行計算的次序，可把某些實現(xiàn)細節(jié)表

16、現(xiàn)出算的次序，可把某些實現(xiàn)細節(jié)表現(xiàn)出來。來。翻譯模式翻譯模式何時將屬性文法改寫成翻譯模式？何時將屬性文法改寫成翻譯模式？消除左遞歸時，原屬性文法將被改成翻譯消除左遞歸時，原屬性文法將被改成翻譯模式。模式。如何將屬性文法改寫成翻譯模式？如何將屬性文法改寫成翻譯模式？原文法：原文法：AA1YA.a=g(A1.a,Y.y)AXA.a=f(X.x)翻譯模式：翻譯模式：AXR.i=f(X.x)RA.a=R.s RYR1.i=g(R.i,Y.y)R1 R.s=R1.s RR.s=R.i改寫成翻譯模式改寫成翻譯模式L-屬性文法屬性文法中，如何實現(xiàn)中，如何實現(xiàn)自下而上自下而上計計算繼承屬性？算繼承屬性？方法方

17、法1 1：去掉翻譯模式中嵌入在產(chǎn)生式中：去掉翻譯模式中嵌入在產(chǎn)生式中間的動作。間的動作。方法方法2 2：改變原文法或：改變原文法或重新構(gòu)造文法，重新構(gòu)造文法，用用綜合屬性代替繼承屬性。綜合屬性代替繼承屬性。自學（自學（P176,177P176,177）L-L-屬性文法在屬性文法在自下而上自下而上分析中的實現(xiàn)分析中的實現(xiàn)8.3 8.3 中間代碼的形式中間代碼的形式中間代碼的常見形式：中間代碼的常見形式：逆波蘭記號逆波蘭記號三元式三元式樹形表示樹形表示四元式四元式逆波蘭記號（后綴式）逆波蘭記號（后綴式）特點：特點：將運算對象寫在前面，把運算符號寫在后面將運算對象寫在前面，把運算符號寫在后面標識符順

18、序與表達式中的一致標識符順序與表達式中的一致 運算符順序與計算順序一致運算符順序與計算順序一致 無括號無括號 表達式表達式逆波蘭式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+b*dabc*bd*+= 為什么要使用逆波蘭式？為什么要使用逆波蘭式？更易于計算機處理，表示簡潔、計算方便。更易于計算機處理，表示簡潔、計算方便。 逆波蘭記號的擴充用途逆波蘭記號的擴充用途i-iGoto LL jumpif E then S1 else S2ES1S2￥AnmnmA subs 逆波蘭式的復雜性：逆波蘭式的復雜性：壓棧的可能是地址（如變量賦值），不是值；壓棧的可能是地址（如變量

19、賦值），不是值；棧中不一定產(chǎn)生結(jié)果。棧中不一定產(chǎn)生結(jié)果。 逆波蘭式的計算機處理方法：逆波蘭式的計算機處理方法：自左向右掃描逆波蘭式，遇到運算對象入棧，遇到算自左向右掃描逆波蘭式，遇到運算對象入棧，遇到算符則將相應數(shù)目的運算對象出棧計算后結(jié)果入棧。符則將相應數(shù)目的運算對象出棧計算后結(jié)果入棧。三元式和樹形表示三元式和樹形表示n三元式的格式：三元式的格式：( (算符算符, , 第一運算對象第一運算對象, , 第二運算對象第二運算對象) )n如：如：a=ba=b* *c+bc+b* *d d 的三元式和樹形表示的三元式和樹形表示(1)(1) ( (* *, b, c), b, c)(2)(2) ( (

20、* *, b, d), b, d)(3)(3) (+,(1),(2)(+,(1),(2)(4)(4) (=,(3),a)(=,(3),a)=a+*bcbd四元式四元式n四元式的格式：四元式的格式：( (算符算符, , 第一運算對象第一運算對象, , 第二運算對象第二運算對象, , 結(jié)果結(jié)果) )n如：如：a=ba=b* *c+bc+b* *d d 的四元式表示如下的四元式表示如下(*, a, b, t1)(*, b, d, t2)(+, t1, t2, t3)(:=, t3, -, a)t1 := a*bt2 := b*dt3 := t1+t2a := t3或或n特點：利于代碼優(yōu)化和目標代碼生

21、成特點：利于代碼優(yōu)化和目標代碼生成 n特例：特例：goto Lgoto L 的四元式為的四元式為（jump,-,-,Ljump,-,-,L）if B rop C goto Lif B rop C goto L的四元式為的四元式為(jrop,B,C,L)(jrop,B,C,L) 8.4 8.4 簡單賦值語句的翻譯簡單賦值語句的翻譯說明：說明： 1 1） 表示表示idid所表示的單詞，用作語義變量所表示的單詞，用作語義變量2 2）lookup()lookup() 審查審查是否出現(xiàn)在符號表是否出現(xiàn)在符號表是：返回指向

22、該登錄項的指針是：返回指向該登錄項的指針否：返回否：返回 nilnil3 3）emitemit 將四元式輸出到中間文件（或目標文件）上將四元式輸出到中間文件（或目標文件）上4 4）newtempnewtemp 生成一臨時變量生成一臨時變量5 5）E.placeE.place 存放存放 E E值的變量名在符號表的登錄項值的變量名在符號表的登錄項 若變量為臨時變量，則直接存放一整數(shù)碼若變量為臨時變量，則直接存放一整數(shù)碼 8.4 8.4 簡單賦值語句的翻譯簡單賦值語句的翻譯例例3 3 將將賦值語句翻譯成四元式賦值語句翻譯成四元式的語義描述：的語義描述：nS S id := Eid := E nE E

23、 E E1 1 + + E E2 2nE E E E1 1 * * E E2 2nE E -E-E1 1nE E (E(E1 1) )(1)(1)E E ididS id := E P:=lookup () ;if P nil then emit( P,“:=”,E.place);elseerror(); (2) EE1+E2 E.place:= newtemp; emit(E.place,“:=”, E1.place,“+”,E2.place); (3) EE1*E2 E.place:= newtemp; emit(E.place,“:=”, E1.place,“*”,E2.p

24、lace);(4) E-E1 E.place=newtemp; emit(E.place,:=,-,E1.place);(5) E(E1) E.place=newtemp; emit(E.place,:=,E1.place);(6) Eid p:=lookup(); if (p!=nil) E.place=p; else error();8.5 8.5 布爾表達式的翻譯布爾表達式的翻譯1 1、布爾表達式的作用：、布爾表達式的作用：計算邏輯值計算邏輯值 （返回真（返回真 / / 假假 ）控制流語句中的條件表達式控制流語句中的條件表達式 if() thenwhile() 2 2、布爾

25、表達式的文法布爾表達式的文法 EE and E EE or EEnot EEid rop idEtrueEfalse3 3、布爾表達式的計算方法：、布爾表達式的計算方法：一步一步計算出式中各部分真假，最終算一步一步計算出式中各部分真假，最終算出整個表達式的值出整個表達式的值采用優(yōu)化措施，只計算部分表達式值即可采用優(yōu)化措施，只計算部分表達式值即可 例如：例如：a and b/a為為0時，時，b無論是什么表達無論是什么表達式的值都為式的值都為0a or b/a為為1時，時，b無論是什么表達無論是什么表達式的值都為式的值都為1 8.5 布爾表達式的翻譯布爾表達式的翻譯例如例如 a or b and

26、not ca or b and not c 對應的四元式對應的四元式(1) (1) (not,c,-,t1)(not,c,-,t1)(2) (2) (and,b,t1,t2)(and,b,t1,t2)(3) (3) (or,a,t2,t3)(or,a,t2,t3)布爾表達式的翻譯布爾表達式的翻譯Enot E1E.true := E1.false;E.codebegin := E1.codebegin;E.false := E1.true; (2) EE1 and E2backpatch(E1.true, E2.codebegin);E.codebegin := E1.codebegin;E.t

27、rue := E2.true;E.false := merge(E1.false, E2.false);(3) EE1 or E2backpatch(E1.false, E2.codebegin);E.codebegin := E1.codebegin;E.true := merge(E1.true, E2.true);E.false := E2.false;布爾表達式譯為四元式的語義描述：布爾表達式譯為四元式的語義描述：(4) E(E1)E.true := E1.true;E.codebegin := E1.codebegin;E.false := E1.false; (5) Eid1 ro

28、p id2E.true := nextstat;E.codebegin := nextstat;E.false := nextstat + 1;emit(if,id1.place,rop,id2.place,goto,);emit(goto,-);(6) EidE.true := nextstat;E.codebegin := nextstat;E.false := nextstat + 1;emit(if,id1.place,goto,);emit(goto,-);控制語句控制語句 S S if E then Sif E then S1 1 else Selse S2 2 E.falseE 的代碼的代碼 E.trueE.false: S2的代碼的代碼got