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

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

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

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

4、述了語義處理的加工動作。 目前流行的語義描述和語義處理的 方法主要是屬性文法和語法制導(dǎo)翻譯方 法。 第5章 語法制導(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)翻譯概述 為文法的每個(gè)產(chǎn)生式都配備一個(gè)語義 動作或語義子程序。 在語法分析的過程中，每當(dāng)使用一條 產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行相應(yīng) 產(chǎn)生式的語義動作, 從而實(shí)現(xiàn)語義處理。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 (1) 語法制導(dǎo)翻譯法 的基本思想 S Axy a1 a2 a3 ai ai+1 an 語義處理

5、的 加工動作 語法制導(dǎo)翻譯法使用屬性文法為工具 來說明程序設(shè)計(jì)語言的語義。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 (2) 語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法 在語法分析過程中，依隨分析的過程， 根據(jù)每個(gè)產(chǎn)生式所對應(yīng)的語義子程序(或 語義規(guī)則描述的語義處理的加工動作)進(jìn) 行翻譯的方法。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 為文法每一產(chǎn)生式設(shè)計(jì)相應(yīng)的求值的語義 描述(語義動作)： 例如，設(shè)有簡單算術(shù)表達(dá)式的文法： EEE | E*E | (E) | digit 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

6、(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章 語法制導(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 = 47 E.val = 8 E.val = 40 E.val = 7 E.val = 5 + 5 * 8 7 E E E E

7、E 5.4 編譯中常用的中間代碼: 逆波蘭式四元式 三元式樹形表示 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 逆波蘭式逆波蘭式 逆波蘭式除去了原表達(dá)式中的括號， 并將運(yùn)算對象寫在前面，運(yùn)算符寫在后 面，因而又稱為后綴式后綴式。 例如：逆波蘭式 a*bab* (a+b)*(c+d)ab+cd+* 中綴表達(dá)式 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 逆波蘭式表示法同中綴表示法相比其 優(yōu)點(diǎn)是: 不再有括號,且運(yùn)算符出現(xiàn)的順序體 現(xiàn)了中綴表達(dá)式 的運(yùn)算順序 2. 易于計(jì)算機(jī)處理 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 一般表達(dá)式計(jì)值時(shí)，要處理兩類符 號，一類是運(yùn)算對象，另一類是運(yùn)算符， 通常用兩個(gè)

8、工作棧分別處理。但處理用 逆波蘭式表示的表達(dá)式卻只用一個(gè)工作 棧。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 當(dāng)計(jì)算機(jī)自左到右順序掃描逆蘭波 式時(shí)，若當(dāng)前符號是運(yùn)算對象則進(jìn)棧， 若當(dāng)前符號是運(yùn)算符，設(shè)為K元運(yùn)算符， 則將棧頂?shù)腒個(gè)元素依次取出，同時(shí)進(jìn) 行K元運(yùn)算，并將運(yùn)算結(jié)果置于棧頂， 表達(dá)式處理完畢時(shí)，其計(jì)算結(jié)果自然呈 現(xiàn)在棧頂。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 逆波蘭式ab+c*的處理過程如下圖： b aT1 c T1T2 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 逆波蘭形式可以推廣到其他語法結(jié)構(gòu)： 賦值語句 V=E 逆波蘭式 VE= 條件語句逆波蘭式 if E S1 ; els

9、e S2ES1S2￥ 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 三元式和樹形表示 三元式三元式主要由三部分組成： （OP，arg1, arg2） 其中OP是運(yùn)算符， arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對象。 當(dāng)OP是一目運(yùn)算時(shí)，常常將運(yùn)算對象定 義為arg1。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 例如 a+b*c 的 三元式序列： (1) ( * , b , c ) (2) ( + , a , (1) ) 運(yùn)算對象是指向符號表的某一項(xiàng)或指向 三元式表的某一項(xiàng)。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 1. 三元式出現(xiàn)的順序和語法成份的 計(jì)值順序相一致。 三元式的特點(diǎn)： 2. 三

10、元式之間的聯(lián)系是通過指示器 實(shí)現(xiàn)的。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 間接三元式 (1) 間接三元式表: 用來存放各三元式本身。 (2) 間接碼表: 按執(zhí)行各三元式的順序,依次 列出各三元式在三元式表中的位置。 注意注意 : 間接三元式表中不存放重復(fù)的間接三元式表中不存放重復(fù)的 三元式。三元式。 第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

11、) (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ù)和中間代 碼生成 樹形表示 A * B + C*D + C * A * BD 末端結(jié)點(diǎn)表示一個(gè)運(yùn)算對象, 每一個(gè)內(nèi) 結(jié)點(diǎn)表示一個(gè)一元或二元運(yùn)算符。 樹形表示是三元式的翻版 (3)+ (1)*(2)* CABD 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 四元式四元式主

12、要由四部分組成： （OP，arg1, arg2, result） 其中OP是運(yùn)算符， arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對象。 當(dāng)OP是一目運(yùn)算時(shí)，常常將運(yùn)算對象定義 為arg1。 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 四元式的第四個(gè)分量result是編譯程序 為存放中間運(yùn)算結(jié)果而臨時(shí)引進(jìn)的變量， 常稱為臨時(shí)變量，如Ti，也可以是用戶 自定義變量，如X。 例如 X a*bc/d 的 四元式序列： (1) ( *, a, b, T1 ) (2) ( /, c, d, T2 ) (3) ( +, T1, T2, T3 ) (4) ( =, T3, - -, X ) 第5章 語法制導(dǎo)翻譯

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

14、四元式序列： (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ù)和中間代 碼生成 t1= a t2= c t3= t2 + d t5= t1+ t4 a + b * ( c + d )的四元式表示 t4= b* t3 第5章 語法制導(dǎo)翻譯技

15、術(shù)和中間代 碼生成 i( i /( i i ) )的逆波蘭式 i( i /( i i ) )的四元式 t1= i i t2= i / t1 t3= i t2 i i i i / 例2. 第5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 語義函數(shù) emit（Targ1 OP arg2） 功能是生成一個(gè)三地址語句，并送 到輸出文件中。 語義函數(shù) newtemp( ) 功能是產(chǎn)生一個(gè)新的臨時(shí)變量名字， 并回送新的臨時(shí)變量名的整數(shù)碼。 如T1，T2等。 5.5.1 簡單算術(shù)表達(dá)式和賦值語句的翻譯 (2) 不進(jìn)符號表，臨時(shí)變量單詞值部 分用整數(shù)碼表示。 (1) 送到符號表。 對臨時(shí)變量有兩種不同的處理方法: 第

16、5章 語法制導(dǎo)翻譯技術(shù)和中間代 碼生成 語義過程 Lookup（） 功能是審查是否出現(xiàn)在符號表中， 在則返回其指針，否則返回NULL。 語義變量 E.place 表示存放非終結(jié)符E值的變量名在符號 表中的入口地址或臨時(shí)變量名的整數(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).place ) E.place newtemp( ); emit(E.placeE(1).place*E(2).place ) 第5章 語法

17、制導(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布爾表達(dá)式到四元式的翻譯 一.布爾表達(dá)式的文法 計(jì)算邏輯值 程序設(shè)計(jì)語言中布爾表達(dá)式有兩個(gè)作用: 用作控制語句中的條件式 布爾表達(dá)式是由布爾算符(、和) 施于布爾變量或關(guān)系

18、表達(dá)式而成。 布爾表達(dá)式到四元式的翻譯 E E (1) E (2) E E (1) E (2) E E (1) E ( E (1) ) E i (1) rop i (2) E i 布爾表達(dá)式到四元式的翻譯 二. 布爾表達(dá)式的計(jì)值方法 1. 如同計(jì)算算術(shù)表達(dá)式一樣,步步計(jì) 算出各部分真、假值,最后計(jì)算出整個(gè)表 達(dá)式的值。 2. 根據(jù)布爾運(yùn)算的特殊性,采取某種 優(yōu)化措施,可避免計(jì)算整個(gè)表達(dá)式的值。 布爾表達(dá)式到四元式的翻譯 AB 解釋成 AB 解釋成 A 解釋成 if A then true else B if A then B else false if A then false else tr

19、ue 三. 布爾表達(dá)式的翻譯方法 1. 同翻譯算術(shù)表達(dá)式一樣,翻譯布爾表達(dá)式。 布爾表達(dá)式到四元式的翻譯 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 i (2) E.place newtemp( )； emit (if i (1).place ro

20、p.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 布爾表達(dá)式到四元式的翻譯 例如布爾表達(dá)式 a = bc d 對應(yīng)如 下四元式序列: 101 if a = b goto 104 102 t1= 0 103 goto 105 104 t1= 1 105 t2= c d 106 t3 = t1 t2 布爾表達(dá)式到四元式的翻譯 2. 控制語句中布爾表達(dá)式的翻譯 條件語句的語法為: 根據(jù)條件語句的語義,條件語句的代

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

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

23、t ) : 將 p 所鏈結(jié)的每個(gè)四元式的第四 區(qū)分量都回填 t ; 布爾表達(dá)式到四元式的翻譯 為及時(shí)回填轉(zhuǎn)移地址, 使用語義變量 E. bcode 記錄表達(dá)式E的第一個(gè)四元式 語句序號。 (6) 定義語義變量 nextq 為四元式表指針。 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式語義動作的設(shè)計(jì) 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 ; 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式語義動作的設(shè)計(jì) 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 ) ; 布爾表達(dá)式語義動作的設(shè)計(jì) 3. E E (1) E.bcode= E(1).bcode ; E.true=E(1). false ; E.false= E(1). true ; 布爾表達(dá)式到四元式的翻譯 4. E ( E (1)