編譯原理第5章(語法制導(dǎo)翻譯技術(shù))-1

1、語義分析的任務(wù)：靜態(tài)語義審查靜態(tài)語義審查 審查每個語法結(jié)構(gòu)的靜態(tài)語義審查每個語法結(jié)構(gòu)的靜態(tài)語義,即驗證語法結(jié)構(gòu)合法的程序即驗證語法結(jié)構(gòu)合法的程序,是否是否真正有意義真正有意義。第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成5.1 概述例如: 表達式 A+B*C對運算對象進行類型檢查, 對變量進行先定義后使用檢查 如果靜態(tài)語義正確, 語義處理則要執(zhí)行真正的翻譯, 即生成程序的某種中間代碼的形式或直接生成目標(biāo)代碼。執(zhí)行真正的翻譯執(zhí)行真正的翻譯第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 目前多數(shù)編譯程序進行語義分析的方法是采用語法制導(dǎo)翻譯法采用語法制導(dǎo)翻譯法 。它不是一種形式系統(tǒng), 但它比較接近形式化。 語法制

2、導(dǎo)翻譯法使用屬性文法為工具來描述程序設(shè)計語言的語義。第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成(1) 屬性 對文法的每一個符號, 引進一些屬性, 這些屬性代表與文法符號相關(guān)的信息, 如類型、值、存儲位置等。與屬性相關(guān)的信息, 即屬性值,可以在語法分析過程中計算和傳遞。5.2 屬性文法第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成屬性分為兩類:綜合屬性其計算規(guī)則按“自下而上”方式進行, 即規(guī)則左部符號的某些屬性根據(jù)其右部符號的屬性和(或)自己的其他屬性計算而得。屬性加工的過程即是語義的處理過程。屬性加工的過程即是語義的處理過程。綜合屬性和繼承屬性。第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成繼承屬性其計算規(guī)則按“

3、自上而下”方式進行, 即規(guī)則右部符號的某些屬性根據(jù)其左部符號的屬性和(或)右部其他符號的某些屬性計算而得。第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成(2) 屬性文法 為文法的每一個規(guī)則配備的計算屬性的計算規(guī)則, 稱為語義規(guī)則(描述語義處理的加工動作) 。 屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則。語義規(guī)則:第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 這些語義規(guī)則附在文法的每個產(chǎn)生式上,在語法分析過程中, 執(zhí)行語義規(guī)則描述的動作, 從而實現(xiàn)語義處理。也就是說, 附在文法的每個產(chǎn)生式上語義規(guī)則描述了語義處理的加工動作。 目前流行的語義描述和語義處理的方法主要是屬性文法和語法制導(dǎo)翻譯方法。第5章 語法

4、制導(dǎo)翻譯技術(shù)和中間代碼生成 G： EE+T |T TT*F |F F(E)|i G： DTL Tinteger |real LL,id|id 5.3 語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概述 為文法的每個產(chǎn)生式都配備一個語義動作或語義子程序。 在語法分析的過程中，每當(dāng)使用一條產(chǎn)生式進行推導(dǎo)或歸約時，就執(zhí)行相應(yīng)產(chǎn)生式的語義動作, 從而實現(xiàn)語義處理。第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成(1) 語法制導(dǎo)翻譯法 的基本思想S Axy a1 a2 a3 ai ai+1 an語義處理的加工動作 語法制導(dǎo)翻譯法使用屬性文法為工具來說明程序設(shè)計語言的語義。第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成(2) 語法制導(dǎo)翻譯法

5、語法制導(dǎo)翻譯法 在語法分析過程中，依隨分析的過程，根據(jù)每個產(chǎn)生式所對應(yīng)的語義子程序(或語義規(guī)則描述的語義處理的加工動作)進行翻譯的方法。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成為文法每一產(chǎn)生式設(shè)計相應(yīng)的求值的語義描述(語義動作)： 例如，設(shè)有簡單算術(shù)表達式的文法： EEE | E*E | (E) | digit1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)*E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 7+8*5,3+8,6*5,第5章

6、語法制導(dǎo)翻譯技術(shù)和中間代碼生成1.E E(1)E(2) E.val E(1).val E(2).val 2.E E(1)*E(2) E.val E(1).val*E(2).val 3.E (E(1) E.val E(1).val 4.E digit E.val Lex.digit 句子 7+8*5 E.val = 47E.val = 8E.val = 40E.val = 7E.val = 5+5*87EEEEE5.4 編譯中常用的中間代碼:逆波蘭式四元式三元式樹形表示第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成逆波蘭式逆波蘭式 逆波蘭式除去了原表達式中的括號，并將運算對象寫在前面，運算符寫在后面，因

7、而又稱為后綴式后綴式。 例如：逆波蘭式a*bab*(a+b)*(c+d)ab+cd+*中綴表達式第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 逆波蘭式表示法同中綴表示法相比其優(yōu)點是:1. 不再有括號,且運算符出現(xiàn)的順序體 現(xiàn)了中綴表達式 的運算順序2. 易于計算機處理第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 一般表達式計值時，要處理兩類符號，一類是運算對象，另一類是運算符，通常用兩個工作棧分別處理。但處理用逆波蘭式表示的表達式卻只用一個工作棧。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 當(dāng)計算機自左到右順序掃描逆蘭波式時，若當(dāng)前符號是運算對象則進棧，若當(dāng)前符號是運算符，設(shè)為K元運算符，則將棧頂?shù)腒個元素

8、依次取出，同時進行K元運算，并將運算結(jié)果置于棧頂，表達式處理完畢時，其計算結(jié)果自然呈現(xiàn)在棧頂。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成逆波蘭式ab+c*的處理過程如下圖： baT1cT1T2第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成逆波蘭形式可以推廣到其他語法結(jié)構(gòu)： 賦值語句V=E逆波蘭式VE=條件語句逆波蘭式if E S1 ; else S2ES1S2￥第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成三元式和樹形表示三元式三元式主要由三部分組成： （OP，arg1, arg2） 其中OP是運算符， arg1,arg2分別是第一和第二兩個運算對象。 當(dāng)OP是一目運算時，常常將運算對象定義為arg1。 第5章

9、 語法制導(dǎo)翻譯技術(shù)和中間代碼生成例如 a+b*c 的 三元式序列： (1) ( * , b , c ) (2) ( + , a , (1) )運算對象是指向符號表的某一項或指向三元式表的某一項。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 1. 三元式出現(xiàn)的順序和語法成份的 計值順序相一致。 三元式的特點：2. 三元式之間的聯(lián)系是通過指示器 實現(xiàn)的。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成間接三元式(1) 間接三元式表: 用來存放各三元式本身。(2) 間接碼表: 按執(zhí)行各三元式的順序,依次 列出各三元式在三元式表中的位置。注意注意 : 間接三元式表中不存放重復(fù)的間接三元式表中不存放重復(fù)的 三元式。

10、三元式。第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 例如 語句 X= (A+B)*C Y= D(A+B)三元式序列(1) ( + , A , B )(2) ( * , (1) , C )(3) ( = , X , (2) )(5) ( , D , (4) )(4) ( + , A , B )(6) ( = , Y, (5) )間接三元式間接碼表三元式表(1)(2)(3)(1)(4)(5)(1) ( + , A , B )(2) ( * , (1) , C )(3) ( = , X , (2) )(4) ( , D , (1) )(5) ( = , Y, (4) )第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼

11、生成 樹形表示 A * B + C*D +C*A*BD 末端結(jié)點表示一個運算對象, 每一個內(nèi)結(jié)點表示一個一元或二元運算符。樹形表示是三元式的翻版(3)+(1)*(2)*CABD第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成四元式四元式主要由四部分組成： （OP，arg1, arg2, result） 其中OP是運算符， arg1,arg2分別是第一和第二兩個運算對象。 當(dāng)OP是一目運算時，常常將運算對象定義為arg1。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 四元式的第四個分量result是編譯程序為存放中間運算結(jié)果而臨時引進的變量，常稱為臨時變量，如Ti，也可以是用戶自定義變量，如X。 例如 X a

12、*bc/d 的 四元式序列：(1) ( *, a, b, T1 )(2) ( /, c, d, T2 )(3) ( +, T1, T2, T3 )(4) ( =, T3, - -, X )第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成2. 四元式之間的聯(lián)系是通過臨時變量實 現(xiàn)的，這樣易于調(diào)整和變動四元式。 1. 四元式出現(xiàn)的順序和語法成份的計值 順序相一致。 四元式的特點：3. 便于優(yōu)化處理。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成四元式還可以表示條件的轉(zhuǎn)移(if ab goto 0) (goto 0) 編譯系統(tǒng)中，有時將四元式表示成另一種更直觀，更易理解的形式三地址代碼或三地址語句。result :

13、 arg1 OP arg2 三地址語句三地址語句:語句中是三個量的賦值語句, 每個量占一個地址。 三地址代碼形式定義為：第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成例如 X a*bc/d 的 四元式序列：(1) ( *, a, b, T1 )(2) ( /, c, d, T2 )(3) ( +, T1, T2, T3 )(4) ( =, T3, - -, X )相應(yīng)的三地址語句序列為： （1）T1a*b （2）T2c/d （3）T3T1T2 （4）XT3 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成例1. a + b * ( c + d )的逆波蘭式 a bc d + * +第5章 語法制導(dǎo)翻譯技術(shù)和中間

14、代碼生成t1= a t2= c t3= t2 + dt5= t1+ t4 a + b * ( c + d )的四元式表示 t4= b* t3 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成i( i /( i i ) )的逆波蘭式 i( i /( i i ) )的四元式 t1= i i t2= i / t1t3= i t2i i i i /例2. 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成語義函數(shù) emit（Targ1 OP arg2） 功能是生成一個三地址語句，并送到輸出文件中。 語義函數(shù) newtemp( ) 功能是產(chǎn)生一個新的臨時變量名字，并回送新的臨時變量名的整數(shù)碼。如T1，T2等。 5.5.1 簡

15、單算術(shù)表達式和賦值語句的翻譯 (2) 不進符號表，臨時變量單詞值部 分用整數(shù)碼表示。 (1) 送到符號表。 對臨時變量有兩種不同的處理方法: 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成語義過程 Lookup（） 功能是審查是否出現(xiàn)在符號表中，在則返回其指針，否則返回NULL。 語義變量 E.place 表示存放非終結(jié)符E值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成 1. E E(1) E(2) 2. E E(1) * E(2) E.place newtemp( ); emit(E.placeE(1).placeE(2).pla

16、ce ) E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成3. E （E(1)） E.place E(1).place； 4. E i p Lookup (); if (p != NULL) E.place p; else error( ); 第5章 語法制導(dǎo)翻譯技術(shù)和中間代碼生成5. Ai=E p Lookup (); if (p != NULL) emit(pE.place; ) else error( ); 5.5.2布爾表達式到四元式的翻譯一.布爾表達式的文法

17、計算邏輯值程序設(shè)計語言中布爾表達式有兩個作用: 用作控制語句中的條件式布爾表達式是由布爾算符(、和)施于布爾變量或關(guān)系表達式而成。 布爾表達式到四元式的翻譯 E E (1) E (2) E E (1) E (2) E E (1) E ( E (1) ) E i (1) rop i (2) E i布爾表達式到四元式的翻譯 二. 布爾表達式的計值方法 1. 如同計算算術(shù)表達式一樣,步步計算出各部分真、假值,最后計算出整個表達式的值。 2. 根據(jù)布爾運算的特殊性,采取某種優(yōu)化措施,可避免計算整個表達式的值。布爾表達式到四元式的翻譯 AB 解釋成 AB 解釋成 A 解釋成if A then true

18、else Bif A then B else falseif A then false else true 三. 布爾表達式的翻譯方法 1. 同翻譯算術(shù)表達式一樣,翻譯布爾表達式。布爾表達式到四元式的翻譯 1. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 2. E E (1) E (2) E.place newtemp( )； emit ( E.placeE(1).placeE(2).place ) 3. E ( E (1) ) E.place E(1).place； 4. E i (1) rop

19、 i (2) E.place newtemp( )； emit (if i (1).place rop.op i (2).place goto nextq+3); emit ( E.place 0 ); emit ( goto nextq+2); emit ( E.place 1 ); E.place i . place； 5. E i 布爾表達式到四元式的翻譯例如布爾表達式 a = bc d 對應(yīng)如下四元式序列:101 if a = b goto 104102 t1= 0103 goto 105104 t1= 1105 t2= c d106 t3 = t1 t2 布爾表達式到四元式的翻譯2.

20、 控制語句中布爾表達式的翻譯條件語句的語法為:根據(jù)條件語句的語義,條件語句的代碼結(jié)構(gòu)為:if E then S(1) else S(2)E的代碼S(1)的代碼S(2)的代碼Jump out out: 真 假布爾表達式到四元式的翻譯 E是布爾表達式,根據(jù)布爾運算的特殊性,布爾表達式的目標(biāo)結(jié)構(gòu)為:假E(1)的代碼E(2)的代碼真S(1)S(2)真假真E(1)的代碼E(2)的代碼假S(2)S(1)假真 (1) 真出口和假出口:真出口表示布爾表達式E為真時控制流向的轉(zhuǎn)移目標(biāo)假出口表示布爾表達式E為假時控制流向的轉(zhuǎn)移目標(biāo)布爾表達式到四元式的翻譯(2) 作為條件轉(zhuǎn)移的E,把E翻譯成的代碼 是一串條件轉(zhuǎn)或無

21、條件轉(zhuǎn)的四元式對于E為 a rop b 的形式生成代碼為: if a rop b goto 真出口 goto 假出口布爾表達式到四元式的翻譯布爾表達式到四元式的翻譯布爾表達式的真、假出口不能在產(chǎn)生其四元式的同時得知E.true: 記錄表達式 E 所對應(yīng)的四元式需回填真出口的四元式的地址所構(gòu)成的鏈E.false: 記錄表達式 E 所對應(yīng)的四元式需回填假出口的四元式的地址所構(gòu)成的鏈(3) 設(shè)置兩個語義變量:布爾表達式到四元式的翻譯把以 p1, p2為鏈?zhǔn)椎膬蓷l鏈合并為一, 返回合并后的鏈?zhǔn)?4) 鏈結(jié)函數(shù)和回填函數(shù): merge (p1, p2) : backpatch ( int p, int

22、t ) : 將 p 所鏈結(jié)的每個四元式的第四區(qū)分量都回填 t ;布爾表達式到四元式的翻譯(5)為及時回填轉(zhuǎn)移地址, 使用語義變量 E. bcode 記錄表達式E的第一個四元式語句序號。(6) 定義語義變量 nextq 為四元式表指針。布爾表達式到四元式的翻譯布爾表達式語義動作的設(shè)計 1. E E (1) E (2) backpatch( E(1).false, E(2). bcode) ； E. bcode= E(1).bcode ; E.true=merge ( E(1).true, E(2).true ) ; E.false= E(2).false ;布爾表達式到四元式的翻譯布爾表達式語義動作的設(shè)計 2. E E (1) E (2) backpatch( E(1).true, E(2).bcode) ； E.bcode= E(1).bcode ; E.true= E(2).true ; E.false=merge( E(1).false, E(2).false ) ;布爾表達式語義動作的設(shè)計 3. E E (1) E.bcode= E(1).bcode ; E.true=E(1). false ; E.false= E(1). true ;布爾表達式到四元式的翻譯 4. E ( E (1) ) E.bcode=