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

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

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

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

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

5、的 加工動(dòng)作 語(yǔ)法制導(dǎo)翻譯法使用屬性文法為工具 來(lái)說(shuō)明程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 (2) 語(yǔ)法制導(dǎo)翻譯法語(yǔ)法制導(dǎo)翻譯法 在語(yǔ)法分析過(guò)程中，依隨分析的過(guò)程， 根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序(或 語(yǔ)義規(guī)則描述的語(yǔ)義處理的加工動(dòng)作)進(jìn) 行翻譯的方法。 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 為文法每一產(chǎn)生式設(shè)計(jì)相應(yīng)的求值的語(yǔ)義 描述(語(yǔ)義動(dòng)作)： 例如，設(shè)有簡(jiǎn)單算術(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章 語(yǔ)法制導(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章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 逆波蘭式逆波蘭式 逆波蘭式除去了原表達(dá)式中的括號(hào)， 并將運(yùn)算對(duì)象寫在前面，運(yùn)算符寫在后 面，因而又稱為后綴式后綴式。 例如：逆波蘭式 a*bab* (a+b)*(c+d)ab+cd+* 中綴表達(dá)式 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 逆波蘭式表示法同中綴表示法相比其 優(yōu)點(diǎn)是: 不再有括號(hào),且運(yùn)算符出現(xiàn)的順序體 現(xiàn)了中綴表達(dá)式 的運(yùn)算順序 2. 易于計(jì)算機(jī)處理 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 一般表達(dá)式計(jì)值時(shí)，要處理兩類符 號(hào)，一類是運(yùn)算對(duì)象，另一類是運(yùn)算符， 通常用兩個(gè)

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

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

10、元式之間的聯(lián)系是通過(guò)指示器 實(shí)現(xiàn)的。 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 間接三元式 (1) 間接三元式表: 用來(lái)存放各三元式本身。 (2) 間接碼表: 按執(zhí)行各三元式的順序,依次 列出各三元式在三元式表中的位置。 注意注意 : 間接三元式表中不存放重復(fù)的間接三元式表中不存放重復(fù)的 三元式。三元式。 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 例如 語(yǔ)句 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章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 樹形表示 A * B + C*D + C * A * BD 末端結(jié)點(diǎn)表示一個(gè)運(yùn)算對(duì)象, 每一個(gè)內(nèi) 結(jié)點(diǎn)表示一個(gè)一元或二元運(yùn)算符。 樹形表示是三元式的翻版 (3)+ (1)*(2)* CABD 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 四元式四元式主

12、要由四部分組成： （OP，arg1, arg2, result） 其中OP是運(yùn)算符， arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對(duì)象。 當(dāng)OP是一目運(yùn)算時(shí)，常常將運(yùn)算對(duì)象定義 為arg1。 第5章 語(yǔ)法制導(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章 語(yǔ)法制導(dǎo)翻譯

13、技術(shù)和中間代碼生成 2. 四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí) 現(xiàn)的，這樣易于調(diào)整和變動(dòng)四元式。 1. 四元式出現(xiàn)的順序和語(yǔ)法成份的計(jì)值 順序相一致。 四元式的特點(diǎn)： 3. 便于優(yōu)化處理。 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 四元式還可以表示條件的轉(zhuǎn)移 (if ab goto 0) (goto 0) 編譯系統(tǒng)中，有時(shí)將四元式表示成另一 種更直觀，更易理解的形式三地址代 碼或三地址語(yǔ)句。 result : arg1 OP arg2 三地址語(yǔ)句三地址語(yǔ)句:語(yǔ)句中是三個(gè)量的賦值語(yǔ)句, 每個(gè)量占一個(gè)地址。 三地址代碼形式定義為： 第5章 語(yǔ)法制導(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)的三地址語(yǔ)句序列為： （1）T1a*b （2）T2c/d （3）T3T1T2 （4）XT3 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 例1. a + b * ( c + d )的逆波蘭式 a bc d + * + 第5章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 t1= a t2= c t3= t2 + d t5= t1+ t4 a + b * ( c + d )的四元式表示 t4= b* t3 第5章 語(yǔ)法制導(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章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 語(yǔ)義函數(shù) emit（Targ1 OP arg2） 功能是生成一個(gè)三地址語(yǔ)句，并送 到輸出文件中。 語(yǔ)義函數(shù) newtemp( ) 功能是產(chǎn)生一個(gè)新的臨時(shí)變量名字， 并回送新的臨時(shí)變量名的整數(shù)碼。 如T1，T2等。 5.5.1 簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯 (2) 不進(jìn)符號(hào)表，臨時(shí)變量單詞值部 分用整數(shù)碼表示。 (1) 送到符號(hào)表。 對(duì)臨時(shí)變量有兩種不同的處理方法: 第

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

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章 語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代 碼生成 5. Ai=E p Lookup (); if (p != NULL) emit(pE.place; ) else error( ); 5.5.2布爾表達(dá)式到四元式的翻譯 一.布爾表達(dá)式的文法 計(jì)算邏輯值 程序設(shè)計(jì)語(yǔ)言中布爾表達(dá)式有兩個(gè)作用: 用作控制語(yǔ)句中的條件式 布爾表達(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 對(duì)應(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. 控制語(yǔ)句中布爾表達(dá)式的翻譯 條件語(yǔ)句的語(yǔ)法為: 根據(jù)條件語(yǔ)句的語(yǔ)義,條件語(yǔ)句的代

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)或無(wú)條件轉(zhuǎn)的四元式 對(duì)于E為 a

22、 rop b 的形式生成代碼為: if a rop b goto 真出口 goto 假出口 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式的真、假出口不能在產(chǎn)生其 四元式的同時(shí)得知 E.true: 記錄表達(dá)式 E 所對(duì)應(yīng)的四元式需 回填真出口的四元式的地址所構(gòu)成的鏈 E.false: 記錄表達(dá)式 E 所對(duì)應(yīng)的四元式 需回 填假出口的四元式的地址所構(gòu)成的鏈 (3) 設(shè)置兩個(gè)語(yǔ)義變量: 布爾表達(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)移地址, 使用語(yǔ)義變量 E. bcode 記錄表達(dá)式E的第一個(gè)四元式 語(yǔ)句序號(hào)。 (6) 定義語(yǔ)義變量 nextq 為四元式表指針。 布爾表達(dá)式到四元式的翻譯 布爾表達(dá)式語(yǔ)義動(dòng)作的設(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á)式語(yǔ)義動(dòng)作的設(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á)式語(yǔ)義動(dòng)作的設(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)