版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、第八章第八章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成語(yǔ)法制導(dǎo)翻譯和中間代碼生成學(xué)習(xí)目標(biāo):學(xué)習(xí)目標(biāo):v掌握:掌握:常見(jiàn)語(yǔ)法成分的中間代碼形式;常見(jiàn)語(yǔ)法成分的中間代碼形式;常見(jiàn)語(yǔ)法成分的屬性文法或翻譯方案常見(jiàn)語(yǔ)法成分的屬性文法或翻譯方案v理解:理解:屬性文法、語(yǔ)法制導(dǎo)翻譯方法屬性文法、語(yǔ)法制導(dǎo)翻譯方法目標(biāo)程序目標(biāo)程序源程序源程序詞法分析詞法分析語(yǔ)法分析語(yǔ)法分析語(yǔ)義分析語(yǔ)義分析中間代碼生成中間代碼生成代碼優(yōu)化代碼優(yōu)化目標(biāo)代碼生成目標(biāo)代碼生成表格管理表格管理出錯(cuò)處理出錯(cuò)處理語(yǔ)義分析基礎(chǔ)語(yǔ)義分析基礎(chǔ)語(yǔ)義分析的內(nèi)容語(yǔ)義分析的內(nèi)容 主要是類型相容檢查,有以下幾種:主要是類型相容檢查,有以下幾種:1) 各種條件表達(dá)式的類
2、型是不是各種條件表達(dá)式的類型是不是boolean型?型?2) 運(yùn)算符的分量類型是否相容?運(yùn)算符的分量類型是否相容?3) 賦值語(yǔ)句的左右部的類型是否相容?賦值語(yǔ)句的左右部的類型是否相容?4) 形參和實(shí)參的類型是否相容形參和實(shí)參的類型是否相容?5) 下標(biāo)表達(dá)式的類型是否為所允許的類型?下標(biāo)表達(dá)式的類型是否為所允許的類型?6) 函數(shù)說(shuō)明中的函數(shù)類型和返回值的類型是否一函數(shù)說(shuō)明中的函數(shù)類型和返回值的類型是否一致?致?其它語(yǔ)義檢查:其它語(yǔ)義檢查:1)VE中的中的V是不是變量,而且是數(shù)組類型?是不是變量,而且是數(shù)組類型?2)V.i中的中的V是不是變量,而且是記錄類型?是不是變量,而且是記錄類型?i是不是不
3、是該記錄的域名?是該記錄的域名?3)x+f()中的中的f是不是函數(shù)名?形參個(gè)數(shù)和實(shí)參個(gè)是不是函數(shù)名?形參個(gè)數(shù)和實(shí)參個(gè)數(shù)是否一致?數(shù)是否一致?4)每個(gè)使用性標(biāo)識(shí)符是否都有聲明?有無(wú)標(biāo)識(shí)符每個(gè)使用性標(biāo)識(shí)符是否都有聲明?有無(wú)標(biāo)識(shí)符的重復(fù)聲明?的重復(fù)聲明?在語(yǔ)義分析同時(shí)產(chǎn)生中間代碼,在這種模式下,在語(yǔ)義分析同時(shí)產(chǎn)生中間代碼,在這種模式下,語(yǔ)義分析的主要功能如下:語(yǔ)義分析的主要功能如下:語(yǔ)義審查語(yǔ)義審查在掃描聲明部分時(shí)構(gòu)造標(biāo)識(shí)符的符號(hào)表在掃描聲明部分時(shí)構(gòu)造標(biāo)識(shí)符的符號(hào)表在掃描語(yǔ)句部分時(shí)產(chǎn)生中間代碼在掃描語(yǔ)句部分時(shí)產(chǎn)生中間代碼語(yǔ)義分析方法語(yǔ)義分析方法語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯方法方法使用使用屬性文法屬性文法
4、為工具來(lái)說(shuō)明程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。為工具來(lái)說(shuō)明程序設(shè)計(jì)語(yǔ)言的語(yǔ)義。8.1屬性文法屬性文法8.2語(yǔ)法制導(dǎo)翻譯概論語(yǔ)法制導(dǎo)翻譯概論8.3中間代碼形式中間代碼形式8.4基本語(yǔ)言成分的自下而上語(yǔ)法制導(dǎo)翻譯基本語(yǔ)言成分的自下而上語(yǔ)法制導(dǎo)翻譯8.5自上而下的語(yǔ)法制導(dǎo)翻譯自上而下的語(yǔ)法制導(dǎo)翻譯8.1 8.1 屬性文法屬性文法( (Attribute Grammar)Attribute Grammar)屬性屬性對(duì)文法的每一個(gè)符號(hào),引進(jìn)一些屬性,這些屬性對(duì)文法的每一個(gè)符號(hào),引進(jìn)一些屬性,這些屬性代表與文法符號(hào)相關(guān)的信息,如類型、值、存儲(chǔ)代表與文法符號(hào)相關(guān)的信息,如類型、值、存儲(chǔ)位置等。位置等。語(yǔ)義規(guī)則語(yǔ)義規(guī)則為文
5、法的每一個(gè)產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)為文法的每一個(gè)產(chǎn)生式配備的計(jì)算屬性的計(jì)算規(guī)則,稱為語(yǔ)義規(guī)則。則,稱為語(yǔ)義規(guī)則。屬性文法是帶屬性的一種文法屬性文法是帶屬性的一種文法它的主要思想:它的主要思想:首先對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào);首先對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào);其次對(duì)于每個(gè)產(chǎn)生式寫出計(jì)算屬性值的語(yǔ)義規(guī)則其次對(duì)于每個(gè)產(chǎn)生式寫出計(jì)算屬性值的語(yǔ)義規(guī)則屬性文法的形式定義屬性文法的形式定義一個(gè)屬性文法是一個(gè)三元組一個(gè)屬性文法是一個(gè)三元組, ,A A(G, V, F)(G, V, F) G G是一個(gè)上下文無(wú)關(guān)文法;是一個(gè)上下文無(wú)關(guān)文法; V V是屬性的有窮集;是屬性的有窮集; F F是關(guān)于屬
6、性的斷言的有窮集。是關(guān)于屬性的斷言的有窮集。說(shuō)明:說(shuō)明:1.1. 每個(gè)每個(gè)屬性屬性與文法符號(hào)相聯(lián),與文法符號(hào)相聯(lián),N.tN.t表示文法符號(hào)表示文法符號(hào)N N的的屬性屬性t t。屬性值屬性值又稱又稱語(yǔ)義值語(yǔ)義值。存儲(chǔ)屬性值的變量。存儲(chǔ)屬性值的變量又稱又稱語(yǔ)義變量語(yǔ)義變量。2.2. 每個(gè)斷言與文法的某個(gè)產(chǎn)生式相聯(lián),寫在每個(gè)斷言與文法的某個(gè)產(chǎn)生式相聯(lián),寫在 內(nèi)。內(nèi)。屬性的斷言又稱屬性的斷言又稱語(yǔ)義規(guī)則語(yǔ)義規(guī)則,它所描述的工作可以,它所描述的工作可以包括屬性計(jì)算、靜態(tài)語(yǔ)義檢查、符號(hào)表的操作、包括屬性計(jì)算、靜態(tài)語(yǔ)義檢查、符號(hào)表的操作、代碼生成等,有時(shí)寫成函數(shù)或過(guò)程段。代碼生成等,有時(shí)寫成函數(shù)或過(guò)程段。例
7、例 完成類型檢查的屬性文法完成類型檢查的屬性文法1)1) E ET T1 1+T+T2 2TT1 1.t.tint AND Tint AND T2 2.t.tintint2)2) E ET T1 1 or T or T2 2TT1 1.t.tbool AND Tbool AND T2 2.t.tboolbool3)3) T TnumnumT.t :T.t :intint4)4) T TtruetrueT.t :T.t :boolbool5)5) T TfalsefalseT.t :T.t :boolbool 屬性的分類:屬性的分類:1.1. 綜合屬性綜合屬性: 從語(yǔ)法樹(shù)的角度來(lái)看,如果一個(gè)結(jié)點(diǎn)
8、的某一從語(yǔ)法樹(shù)的角度來(lái)看,如果一個(gè)結(jié)點(diǎn)的某一屬性值是由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值計(jì)算來(lái)屬性值是由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值計(jì)算來(lái)的,則稱該屬性為綜合屬性。的,則稱該屬性為綜合屬性。 內(nèi)在屬性是綜合屬性。內(nèi)在屬性是綜合屬性。 用于用于“自下而上自下而上”傳遞信息傳遞信息2.2. 繼承屬性繼承屬性 從語(yǔ)法樹(shù)的角度來(lái)看,若一個(gè)結(jié)點(diǎn)的某一屬?gòu)恼Z(yǔ)法樹(shù)的角度來(lái)看,若一個(gè)結(jié)點(diǎn)的某一屬性值是由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和(或)父結(jié)點(diǎn)性值是由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和(或)父結(jié)點(diǎn)的屬性值計(jì)算來(lái)的,則稱該屬性為繼承屬性。的屬性值計(jì)算來(lái)的,則稱該屬性為繼承屬性。 用于用于“自上而下自上而下”傳遞信息傳遞信息說(shuō)明:說(shuō)明:v終結(jié)符終結(jié)符只有綜合
9、屬性,它們由詞法分析器提供只有綜合屬性,它們由詞法分析器提供v非終結(jié)符非終結(jié)符既有綜合屬性也有繼承屬性,但既有綜合屬性也有繼承屬性,但文法開(kāi)文法開(kāi)始符始符沒(méi)有繼承屬性沒(méi)有繼承屬性例例 簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法1) LE Print(E.val) 2) EE1+T E.val :E1.val +T.val 3) ET E.val :T.val 4) TT1*F T.val :T1.val * F.val 5) TF T.val :F.val 6) F(E) F.val :E.val 7) Fdigit F.val :digit.lexval E.val、T.val
10、、F.val都是綜合屬性都是綜合屬性終結(jié)符終結(jié)符digit只有綜合屬性,它的值由詞法分析提供只有綜合屬性,它的值由詞法分析提供例例 描述變量類型說(shuō)明的屬性文法描述變量類型說(shuō)明的屬性文法1) DTL L.type:T.type 2) Tint T.type:int 3) Treal T.type:real 4) LL1,id L1.type:L.type;addtype( id.entry,L.type )5) Lid addtype( id.entry,L.type ) id1DTLL1id2,intL.type是繼承屬性是繼承屬性T.type是綜合屬性是綜合屬性 int id1,id2的語(yǔ)法
11、樹(shù)的語(yǔ)法樹(shù):用用表示屬性的傳遞情況表示屬性的傳遞情況8.2 語(yǔ)法制導(dǎo)翻譯概論語(yǔ)法制導(dǎo)翻譯概論1.語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯基本思想:基本思想:在語(yǔ)法分析過(guò)程中,隨著分析的步步進(jìn)展,每當(dāng)在語(yǔ)法分析過(guò)程中,隨著分析的步步進(jìn)展,每當(dāng)使用一條產(chǎn)生式進(jìn)行使用一條產(chǎn)生式進(jìn)行推導(dǎo)推導(dǎo)(對(duì)于自上而下分析)(對(duì)于自上而下分析)或或歸約歸約(對(duì)于自下而上分析),就執(zhí)行該產(chǎn)生式(對(duì)于自下而上分析),就執(zhí)行該產(chǎn)生式所對(duì)應(yīng)的所對(duì)應(yīng)的語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作,完成相應(yīng)的翻譯工作。,完成相應(yīng)的翻譯工作。語(yǔ)法制導(dǎo)翻譯法不論對(duì)語(yǔ)法制導(dǎo)翻譯法不論對(duì)自上而下分析自上而下分析或或自下而上自下而上分析分析都適用都適用例例 簡(jiǎn)單算術(shù)表達(dá)式求值的屬
12、性文法簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法1)EE1+T E.val :E1.val +T.val 2)ET E.val :T.val 3)TT1*digit T.val :T1.val * digit.lexval 4)Tdigit T.val :digit.lexval 2+3*5的語(yǔ)法樹(shù):的語(yǔ)法樹(shù):EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上語(yǔ)法制導(dǎo)翻譯過(guò)程:自下而上語(yǔ)法制導(dǎo)翻譯過(guò)程:一旦語(yǔ)法分析確認(rèn)輸入符號(hào)串是一個(gè)句子,它的值也同時(shí)由一旦語(yǔ)法分析確認(rèn)輸入符號(hào)串是一個(gè)句子,它的值也同時(shí)由語(yǔ)義規(guī)則計(jì)算出來(lái)語(yǔ)義規(guī)則計(jì)算出來(lái)2. 語(yǔ)法制導(dǎo)翻
13、譯的實(shí)現(xiàn)途徑語(yǔ)法制導(dǎo)翻譯的實(shí)現(xiàn)途徑以自下而上(以自下而上( LR分析)的語(yǔ)法制導(dǎo)翻譯來(lái)說(shuō)明分析)的語(yǔ)法制導(dǎo)翻譯來(lái)說(shuō)明 將將LR分析器能力擴(kuò)大,增加在歸約后調(diào)用語(yǔ)義規(guī)分析器能力擴(kuò)大,增加在歸約后調(diào)用語(yǔ)義規(guī)則的功能則的功能 增加語(yǔ)義棧,語(yǔ)義值放到與符號(hào)棧同步操作的語(yǔ)增加語(yǔ)義棧,語(yǔ)義值放到與符號(hào)棧同步操作的語(yǔ)義棧中,多項(xiàng)語(yǔ)義值可設(shè)多個(gè)語(yǔ)義棧義棧中,多項(xiàng)語(yǔ)義值可設(shè)多個(gè)語(yǔ)義棧 ,棧結(jié)構(gòu)為:棧結(jié)構(gòu)為:狀態(tài)棧狀態(tài)棧符號(hào)棧符號(hào)棧語(yǔ)義棧語(yǔ)義棧SmXmXm.valS1X1X1.valS0#-例例 簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法簡(jiǎn)單算術(shù)表達(dá)式求值的屬性文法1)L Eprint(E.val)2)EE1+T E.val
14、:E1.val +T.val 3)ET E.val :T.val 4)TT1*digit T.val :T1.val * digit.lexval 5)Tdigit T.val :digit.lexval 狀態(tài)狀態(tài)ACTION GOTO d+*#ET0S3 12 1S4 acc2r3 S5r3 33r5r5 r54S3 75S6 6 r4r4 r47r2S5r2S5*5#E+-2-0146acc#-0101r2#E+-2-01497712GOTOr4S6r5S3S4r3r5S3Action#E+T*5- 2-3-501475685#E+T*-2-3-014757*5#E+3-2- 301435
15、3*5#E+-2-01443*5#-033*5#-023*5#2- 203123*5#-00剩余輸入串剩余輸入串符號(hào)棧符號(hào)棧語(yǔ)義棧語(yǔ)義棧狀態(tài)棧狀態(tài)棧步驟步驟分析并計(jì)算分析并計(jì)算23*5的過(guò)程如下的過(guò)程如下:22T12E73T7T15117EL E EE1+T ETTT1*digit Tdigit8.3 中間代碼的形式中間代碼的形式定義:定義:中間代碼是一種復(fù)雜性介于源程序語(yǔ)言和機(jī)器中間代碼是一種復(fù)雜性介于源程序語(yǔ)言和機(jī)器語(yǔ)言之間的一種表示形式。語(yǔ)言之間的一種表示形式。使用中間代碼的好處:使用中間代碼的好處:中間代碼與具體機(jī)器無(wú)關(guān)中間代碼與具體機(jī)器無(wú)關(guān)對(duì)中間代碼進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化對(duì)中間代碼進(jìn)行
16、與機(jī)器無(wú)關(guān)的優(yōu)化形式:形式:逆波蘭記號(hào)、三元式、間接三元式、四元式和逆波蘭記號(hào)、三元式、間接三元式、四元式和樹(shù)形表示樹(shù)形表示8.3.1 逆波蘭記號(hào)逆波蘭記號(hào) 逆波蘭表示法逆波蘭表示法將運(yùn)算對(duì)象寫在前面,把運(yùn)算符寫在后面,將運(yùn)算對(duì)象寫在前面,把運(yùn)算符寫在后面,因而也稱后綴式。因而也稱后綴式。例如:例如:程序設(shè)計(jì)語(yǔ)言中的表示程序設(shè)計(jì)語(yǔ)言中的表示 逆波蘭表示逆波蘭表示a+bab+a+b*c abc * +(a+b)*cab+c *后綴式的計(jì)算機(jī)處理后綴式的計(jì)算機(jī)處理后綴式的最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理后綴式的最大優(yōu)點(diǎn)是易于計(jì)算機(jī)處理處理過(guò)程:處理過(guò)程:從左到右掃描后綴式,每碰到運(yùn)算對(duì)象就推進(jìn)棧;從左到右
17、掃描后綴式,每碰到運(yùn)算對(duì)象就推進(jìn)棧;碰到運(yùn)算符就從棧頂彈出相應(yīng)目數(shù)的運(yùn)算對(duì)象施碰到運(yùn)算符就從棧頂彈出相應(yīng)目數(shù)的運(yùn)算對(duì)象施加運(yùn)算,并把結(jié)果推進(jìn)棧。最后的結(jié)果留在棧加運(yùn)算,并把結(jié)果推進(jìn)棧。最后的結(jié)果留在棧頂。頂。 bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例:表達(dá)式例:表達(dá)式bc*d的后綴式的后綴式 bcd*+的計(jì)值過(guò)程的計(jì)值過(guò)程逆波蘭表示法的擴(kuò)充逆波蘭表示法的擴(kuò)充逆波蘭表示法很容易擴(kuò)充到表達(dá)式以外的范圍逆波蘭表示法很容易擴(kuò)充到表達(dá)式以外的范圍 例如:例如:語(yǔ)句語(yǔ)句逆波蘭表示逆波蘭表示備注備注a:=b+cabc+:=:=看作二目運(yùn)算符看作二目運(yùn)算符GOTO LL ju
18、mpjump看成一目運(yùn)看成一目運(yùn)算符,表示算符,表示GOTOIf E then S1 else S2ES1S2¥把¥把¥ 看成三目運(yùn)看成三目運(yùn)算符,表示算符,表示if then else8.3.2 三元式和樹(shù)形表示三元式和樹(shù)形表示三元式三元式(算符算符op,第一個(gè)運(yùn)算對(duì)象第一個(gè)運(yùn)算對(duì)象ARG1,第二個(gè)運(yùn)算對(duì)象第二個(gè)運(yùn)算對(duì)象ARG2)說(shuō)明:說(shuō)明:三元式的某些運(yùn)算對(duì)象是另一三元式的某些運(yùn)算對(duì)象是另一個(gè)三元式的編號(hào)(代表其結(jié)果)個(gè)三元式的編號(hào)(代表其結(jié)果)一目算符只需選用一個(gè)運(yùn)算對(duì)一目算符只需選用一個(gè)運(yùn)算對(duì)象(象(ARG1)多目算符可用連續(xù)幾個(gè)三元式多目算符可用連續(xù)幾個(gè)三元式表示表示例:例: a :
19、b*c+b*d表示為表示為 (1) (* ,b,c)(2) (* ,b,d)(3) (+ ,(1),(2)(4) (:,(3),a)間接三元式間接三元式和三元式類似,只是合并相同的三元式,并和三元式類似,只是合并相同的三元式,并在三元式后面加一列執(zhí)行序列在三元式后面加一列執(zhí)行序列例:例: a :b*c+b*c表示為表示為 (1) (* ,b,c)(2) (* ,b,c)(3) (+ ,(1),(2)(4) (:,(3),a)(1) (* ,b,c)(2) (+ ,(1),(1)(3) (:,(2),a)執(zhí)行序列執(zhí)行序列(1)()(1)()(2)(3)三元式序列三元式序列間接三元式序列間接三元式
20、序列樹(shù)形表示樹(shù)形表示二目運(yùn)算對(duì)應(yīng)二叉子樹(shù),多目運(yùn)算對(duì)應(yīng)多叉子二目運(yùn)算對(duì)應(yīng)二叉子樹(shù),多目運(yùn)算對(duì)應(yīng)多叉子樹(shù),但通常通過(guò)引入新結(jié)點(diǎn)表示成二叉子樹(shù)。樹(shù),但通常通過(guò)引入新結(jié)點(diǎn)表示成二叉子樹(shù)。例如:例如:a:b*c+b*d 表示成表示成:=a+*bcbd8.3.3 四元式四元式四元式表示四元式表示四元式是一種比較普遍采用的中間代碼形式四元式是一種比較普遍采用的中間代碼形式(算符算符op,ARG1,ARG2,運(yùn)算結(jié)果運(yùn)算結(jié)果RESULT)例如:例如:a:b*c+b*d的四元式表示如下:的四元式表示如下: 1) (*,b,c,t1 )2) (*,b,d,t2 )3) (+,t1,t2,t3 )4) (:, t
21、3 ,a ) 其中其中t i(i1,2,3)是編譯程序引入的臨時(shí)變量是編譯程序引入的臨時(shí)變量四元式的優(yōu)點(diǎn):四元式的優(yōu)點(diǎn):四元式比三元式更便于優(yōu)化。四元式比三元式更便于優(yōu)化。優(yōu)化要求改變運(yùn)算順序或刪除某些運(yùn)算,引起編號(hào)優(yōu)化要求改變運(yùn)算順序或刪除某些運(yùn)算,引起編號(hào)的變化。的變化。三元式通過(guò)編號(hào)引用中間結(jié)果,編號(hào)的變化引起麻三元式通過(guò)編號(hào)引用中間結(jié)果,編號(hào)的變化引起麻煩;四元式通過(guò)臨時(shí)變量引用中間結(jié)果,編號(hào)變化煩;四元式通過(guò)臨時(shí)變量引用中間結(jié)果,編號(hào)變化無(wú)影響。無(wú)影響。四元式對(duì)生成目標(biāo)代碼有利。四元式對(duì)生成目標(biāo)代碼有利。四元式表示很類似于三地址指令,很容易轉(zhuǎn)換成機(jī)四元式表示很類似于三地址指令,很容易
22、轉(zhuǎn)換成機(jī)器代碼。器代碼。 例如:例如:a:b*c+b*d的四元式表示如下:的四元式表示如下: 1) (*,b,c,t1 )2) (:=, t1,t2 )3) (*,b,d,t3 )4) (+,t1,t3,t4 )5) (:,t4 ,a ) 例如:例如:a:b*c+b*d的三元式表示如下:的三元式表示如下: 1) (*,b,c )2) (:=, 1), 2))3) (*,b,d)4) (+,1),3) )5) (:,4), a ) 四元式的另一種表示四元式的另一種表示有時(shí)為了更直觀,把四元式寫成簡(jiǎn)單賦值形式有時(shí)為了更直觀,把四元式寫成簡(jiǎn)單賦值形式或更易理解的形式或更易理解的形式四元式四元式直觀形
23、式直觀形式(1)()( * , b , c , t1)(1) t1:b*c(2)()( * , b , d , t2)(2) t2:b*d(3)()( +, t1 , t2 , t3)(3) t3:t1+t2(4)()(:, t3 , a)(4) a:t3( jump,,L)goto L( jrop, B,C,L)if B rop C goto L8.4 基本語(yǔ)言成分的自下而上語(yǔ)法制導(dǎo)翻譯基本語(yǔ)言成分的自下而上語(yǔ)法制導(dǎo)翻譯8.4.1 簡(jiǎn)單賦值語(yǔ)句的翻譯簡(jiǎn)單賦值語(yǔ)句的翻譯8.4.2 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯8.4.3 控制結(jié)構(gòu)的翻譯控制結(jié)構(gòu)的翻譯8.4.4 簡(jiǎn)單說(shuō)明語(yǔ)句的翻譯簡(jiǎn)單說(shuō)明語(yǔ)句
24、的翻譯8.4.1 簡(jiǎn)單賦值語(yǔ)句的翻譯簡(jiǎn)單賦值語(yǔ)句的翻譯簡(jiǎn)單賦值語(yǔ)句簡(jiǎn)單賦值語(yǔ)句是指不含復(fù)雜數(shù)據(jù)類型(如數(shù)組,記錄等)的是指不含復(fù)雜數(shù)據(jù)類型(如數(shù)組,記錄等)的賦值語(yǔ)句。賦值語(yǔ)句。賦值語(yǔ)句的語(yǔ)義審查包括:賦值語(yǔ)句的語(yǔ)義審查包括:1. 每個(gè)使用性標(biāo)識(shí)符是否都有聲明?每個(gè)使用性標(biāo)識(shí)符是否都有聲明?2. 運(yùn)算符的分量類型是否相容?運(yùn)算符的分量類型是否相容?3. 賦值語(yǔ)句的左右部的類型是否相容?賦值語(yǔ)句的左右部的類型是否相容?賦值語(yǔ)句的翻譯目標(biāo):賦值語(yǔ)句的翻譯目標(biāo):在賦值語(yǔ)句右部表達(dá)式產(chǎn)生的四元式序列后加在賦值語(yǔ)句右部表達(dá)式產(chǎn)生的四元式序列后加一條賦值四元式一條賦值四元式1屬性和語(yǔ)義規(guī)則中用到的變量、過(guò)
25、程和函數(shù)屬性和語(yǔ)義規(guī)則中用到的變量、過(guò)程和函數(shù)屬性:屬性:用用表示單詞表示單詞id的名字。的名字。用用E.place表示存放表示存放E值的變量名在符號(hào)表的入口地址值的變量名在符號(hào)表的入口地址或臨時(shí)變量編碼?;蚺R時(shí)變量編碼。變量、函數(shù)和過(guò)程變量、函數(shù)和過(guò)程:用用nextstat變量給出在輸出序列中下一個(gè)四元式的序號(hào)變量給出在輸出序列中下一個(gè)四元式的序號(hào)用用lookup()函數(shù)審查函數(shù)審查是否出現(xiàn)在符是否出現(xiàn)在符號(hào)表中,是則返回號(hào)表中,是則返回id的入口地址,否則返回的入口地址,否則返回nil。用用emit過(guò)程向輸出序列輸出一個(gè)四元式,過(guò)程向輸出序列輸出一
26、個(gè)四元式,emit每調(diào)用每調(diào)用一次,一次,nextstat的值增加的值增加1用用newtemp函數(shù)生成臨時(shí)變量,每次調(diào)用生成一個(gè)新函數(shù)生成臨時(shí)變量,每次調(diào)用生成一個(gè)新的臨時(shí)變量,如的臨時(shí)變量,如t1, t2 , 用用error過(guò)程進(jìn)行錯(cuò)誤處理。過(guò)程進(jìn)行錯(cuò)誤處理。 (1) Sid:E p:lookup ( ) ; if pnil then emit (:, E.place , - , p ) else error 2簡(jiǎn)單賦值語(yǔ)句的翻譯(假定變量只有一種類型)簡(jiǎn)單賦值語(yǔ)句的翻譯(假定變量只有一種類型)(2)EE1+E2 E.place:newtemp ; emit ( + , E1
27、.place , E2.place , E.place ) 此情況下的語(yǔ)義審查只有:此情況下的語(yǔ)義審查只有:每個(gè)使用性標(biāo)識(shí)符是否都有聲明?每個(gè)使用性標(biāo)識(shí)符是否都有聲明?(4)EE1 E.place:newtemp ; emit ( , E1.place , - , E.place ) (5)E(E1)E.place:newtemp ; E.place:E1.place (6)Eid p:lookup ( ) ; if pnil then E.place:p else error (3)EE1*E2 E.place:newtemp ; emit ( * , E1.place ,
28、E2.place , E.place ) 例例 翻譯賦值語(yǔ)句翻譯賦值語(yǔ)句A:B+C (A、B、C為標(biāo)識(shí)符為標(biāo)識(shí)符id)E1.placePBE2.placePCE.placet1;(, PB ,PC , t1)(:, t1 , - , PA)SA:=EBE1+E2C(為了直觀,用為了直觀,用PB和和PC分別表示分別表示B和和C在符號(hào)表的入在符號(hào)表的入口地址口地址) 表達(dá)式中可能出現(xiàn)不同類型的變量和常量表達(dá)式中可能出現(xiàn)不同類型的變量和常量 語(yǔ)義審查包括:語(yǔ)義審查包括:1. 每個(gè)使用性標(biāo)識(shí)符是否都有聲明?每個(gè)使用性標(biāo)識(shí)符是否都有聲明?2. 運(yùn)算符的分量類型是否相容?運(yùn)算符的分量類型是否相容?若不接受
29、不同類型的運(yùn)算對(duì)象混合運(yùn)算,則應(yīng)指出錯(cuò)誤;若不接受不同類型的運(yùn)算對(duì)象混合運(yùn)算,則應(yīng)指出錯(cuò)誤;若接受混合運(yùn)算則要進(jìn)行類型轉(zhuǎn)換處理。若接受混合運(yùn)算則要進(jìn)行類型轉(zhuǎn)換處理。 例例:假定表達(dá)式可以有混合運(yùn)算,:假定表達(dá)式可以有混合運(yùn)算,id可以是整型可以是整型和實(shí)型,且當(dāng)兩個(gè)不同類型的和實(shí)型,且當(dāng)兩個(gè)不同類型的id進(jìn)行運(yùn)算時(shí)先把進(jìn)行運(yùn)算時(shí)先把整型整型id轉(zhuǎn)換成實(shí)型,再進(jìn)行運(yùn)算。轉(zhuǎn)換成實(shí)型,再進(jìn)行運(yùn)算。用用E.type表示表示E的類型信息,其值為的類型信息,其值為int或或real。用用 +i , *i 表示整型運(yùn)算,用表示整型運(yùn)算,用 +r , *r 表示實(shí)型運(yùn)算。表示實(shí)型運(yùn)算。用一目算符用一目算符 i
30、tr 表示將整型量轉(zhuǎn)換成實(shí)型量的運(yùn)算。表示將整型量轉(zhuǎn)換成實(shí)型量的運(yùn)算。3 簡(jiǎn)單賦值語(yǔ)句的四元式翻簡(jiǎn)單賦值語(yǔ)句的四元式翻譯譯E.place:newtemp ;if E1.typeint AND E2.typeint thenbegin emit ( +i , E1.place , E2.place , E.place) ; E.type:int endelse if E1.typereal AND E2.typereal thenbegin emit ( +r , E1.place , E2.place , E.place ) ; E.type:real end else if E1.typei
31、nt then begin t:newtemp ; emit ( itr , E1.place , - , t ) ; emit ( +r , t , E2.place , E.place ) ; E.type:real end else begin t:newtemp ; emit ( itr , E2.place , - , t ) ; emit ( +r , E1.place , t , E.place ) ; E.type:real end ;產(chǎn)生式產(chǎn)生式EE1+E2的包含類型屬性的語(yǔ)義規(guī)則為:的包含類型屬性的語(yǔ)義規(guī)則為:E.place=newtemp ;if (E1.type=int
32、 & E2.type=int) emit ( +i , E1.place , E2.place , E.place) ; E.type=intelse if (E1.type=real & E2.type=real) emit ( +r , E1.place , E2.place , E.place ) ; E.type:real else if (E1.type=int) t=newtemp ; emit ( itr , E1.place , - , t ) ; emit ( +r , t , E2.place , E.place ) ; E.type=real else t=newtemp
33、 ; emit ( itr , E2.place , - , t ) ; emit ( +r , E1.place , t , E.place ) ; E.type=real ;產(chǎn)生式產(chǎn)生式EE1+E2的包含類型屬性的語(yǔ)義規(guī)則為:的包含類型屬性的語(yǔ)義規(guī)則為:屬性文法的構(gòu)造屬性文法的構(gòu)造屬性:根據(jù)語(yǔ)義處理的需要,設(shè)計(jì)文法符號(hào)的相屬性:根據(jù)語(yǔ)義處理的需要,設(shè)計(jì)文法符號(hào)的相應(yīng)屬性(包括:屬性的個(gè)數(shù)和屬性的符號(hào)表示)應(yīng)屬性(包括:屬性的個(gè)數(shù)和屬性的符號(hào)表示)語(yǔ)義規(guī)則:滿足語(yǔ)義處理的要求,并生成相應(yīng)的語(yǔ)義規(guī)則:滿足語(yǔ)義處理的要求,并生成相應(yīng)的中間代碼中間代碼8.4.2 布爾表達(dá)式的翻譯布爾表達(dá)式的翻譯1
34、. 布爾表達(dá)式的作用與結(jié)構(gòu)布爾表達(dá)式的作用與結(jié)構(gòu)布爾表達(dá)式的兩個(gè)作用:布爾表達(dá)式的兩個(gè)作用: 計(jì)算邏輯值計(jì)算邏輯值 作為控制語(yǔ)句作為控制語(yǔ)句(如如if-then,while)的條件表達(dá)式的條件表達(dá)式布爾表達(dá)式的語(yǔ)法:布爾表達(dá)式的語(yǔ)法: or | and | not | () | true | false(布爾表達(dá)式)布爾表達(dá)式) relop | () (關(guān)系表達(dá)式)關(guān)系表達(dá)式) op | - | () | id | num (算術(shù)表達(dá)式)算術(shù)表達(dá)式)其中:其中:relop是是關(guān)系算符關(guān)系算符(如如, , =)op是是算術(shù)算符算術(shù)算符(+ , - , * , / )只考慮如下形式的布爾表達(dá)式的翻
35、譯只考慮如下形式的布爾表達(dá)式的翻譯EE or E | E and E | not E | (E ) | id rop id |true|false布 爾 算 符布 爾 算 符 的 優(yōu) 先 順 序 ( 從 高 到 低 ) 為 :的 優(yōu) 先 順 序 ( 從 高 到 低 ) 為 :notandor,且且and和和or都服從左結(jié)合,都服從左結(jié)合,not服服從右結(jié)合從右結(jié)合關(guān)系算符關(guān)系算符的優(yōu)先級(jí)都相同,而且高于任何布爾的優(yōu)先級(jí)都相同,而且高于任何布爾算符,低于任何算術(shù)算符。算符,低于任何算術(shù)算符。2.布爾表達(dá)式的計(jì)算方法:布爾表達(dá)式的計(jì)算方法:采用兩種方法:數(shù)值表示的采用兩種方法:數(shù)值表示的直接計(jì)算直
36、接計(jì)算與邏輯表示與邏輯表示的的短路計(jì)算短路計(jì)算直接計(jì)算與算術(shù)表達(dá)式計(jì)算方法基本相同直接計(jì)算與算術(shù)表達(dá)式計(jì)算方法基本相同如:如:1 or 0 and 1=1 or 0=1短路計(jì)算即布爾表達(dá)式計(jì)算到某一部分就可以得短路計(jì)算即布爾表達(dá)式計(jì)算到某一部分就可以得到結(jié)果,而無(wú)需對(duì)布爾表達(dá)式進(jìn)行完全計(jì)算??傻浇Y(jié)果,而無(wú)需對(duì)布爾表達(dá)式進(jìn)行完全計(jì)算??梢杂靡杂胕f-then-else來(lái)解釋來(lái)解釋A or B if A then 1 else BA and Bif A then B else 0not Aif A then 0 else 1 3.直接計(jì)算的語(yǔ)法制導(dǎo)翻譯直接計(jì)算的語(yǔ)法制導(dǎo)翻譯對(duì)關(guān)系表達(dá)式,如對(duì)關(guān)系表
37、達(dá)式,如ab,可翻譯成如下固定的三可翻譯成如下固定的三地址代碼序列:地址代碼序列:(1) (j,a,b,(4)(2) (:=,0,- ,t1)(3) (jump, - ,- ,(5)(4) (:=,1,- ,t1)(5) 如:如:A or B and not C被翻譯成:被翻譯成:(not,C,- ,t1)(and, B,t1,t2)(or,A,t2,t3)PC直接計(jì)算的翻譯方案直接計(jì)算的翻譯方案(1)EE1 or E2 E.place :newtemp ; emit ( or , E1.place , E2.place , E.place ) (2)EE1 and E2 E.place :n
38、ewtemp ; emit ( and , E1.place , E2.place , E.place ) (3)Enot E1 E.place :newtemp ; emit ( not , E1.place , E.place ) (4)E(E1) E.place :E1.place (5)Eid1 rop id2 E.place :newtemp ; emit (jrop , id1.place , id2.place , nextstat+3 ) ; emit ( :, 0 , E.place ) ; emit ( jump , nextstat+2 ) ; emit ( :, 1 ,
39、 E.place ) (6)Etrue E.place:newtemp;emit(:=,1,- ,E.place) (7)EfalseE.place:=newtemp;emit(:=,0,- ,E.place) 例:布爾表達(dá)式例:布爾表達(dá)式ab or cf的翻譯的翻譯E.place=t5E1.place=t1E2.place=t4E2.place=t3E1.place=t2EE1E2E1E2oranda bc f(1)(j, a, b, (4)(2)(:=, 0, - , t1)(3)(jump,- ,- ,(5)(4)(:=, 1, - , t1)(5)(j, e, f, (12)(10)(
40、:=, 0, - , t3)(11)(jump,- ,- ,(13)(12)(:=, 1, - , t3)(13)(and, t2, t3, t4)(14)(or, t1, t4, t5)4.作為條件控制的布爾表達(dá)式的翻譯作為條件控制的布爾表達(dá)式的翻譯基本翻譯方法基本翻譯方法當(dāng)布爾表達(dá)式用于控制條件時(shí),并不需要計(jì)算表當(dāng)布爾表達(dá)式用于控制條件時(shí),并不需要計(jì)算表達(dá)式的值,而是一旦確定了表達(dá)式為真或?yàn)榧?,達(dá)式的值,而是一旦確定了表達(dá)式為真或?yàn)榧伲蛯⒖刂妻D(zhuǎn)向相應(yīng)的代碼序列。就將控制轉(zhuǎn)向相應(yīng)的代碼序列。S2 的代碼的代碼S1 的代碼的代碼E的代碼的代碼E.false E.true if E then
41、S1 else S2為布爾表達(dá)式為布爾表達(dá)式E引入兩個(gè)新的引入兩個(gè)新的屬性:屬性:E.true:表達(dá)式的真出口,表達(dá)式的真出口,它指向表達(dá)式為真時(shí)的轉(zhuǎn)向它指向表達(dá)式為真時(shí)的轉(zhuǎn)向E.false:表達(dá)式的假出口,表達(dá)式的假出口,它指向表達(dá)式為假時(shí)的轉(zhuǎn)向它指向表達(dá)式為假時(shí)的轉(zhuǎn)向把把E翻譯成下述形式的條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移的四翻譯成下述形式的條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移的四元式序列:元式序列:1.( jnz , A , - , p )若若A為真,則轉(zhuǎn)向四元式為真,則轉(zhuǎn)向四元式p2.( jrop , A , B , p )若若A rop B為真,則轉(zhuǎn)向四元式為真,則轉(zhuǎn)向四元式p3.( jump , - , - ,
42、 p )無(wú)條件轉(zhuǎn)向四元式無(wú)條件轉(zhuǎn)向四元式p(1) ( jnz , A , - , 5 )A的真出口為的真出口為5(2) ( jump , - , - , 3 )A的假出口為的假出口為3(3) ( j , B , D , 5 )BD的真出口為的真出口為5(4) (jump , - , - , p+1 )BD的假出口為的假出口為(p+1)(5) (關(guān)于關(guān)于S1的四元式序列的四元式序列)(p)( jump , - , - , q )跳過(guò)跳過(guò)S2的代碼段的代碼段(p+1) (關(guān)于關(guān)于S2的四元式序列的四元式序列)(q)(1) - (4)是布爾式是布爾式A or BD 翻譯產(chǎn)生的代碼,全部是條翻譯產(chǎn)生的
43、代碼,全部是條件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移四元式,沒(méi)有布爾運(yùn)算。件轉(zhuǎn)移和無(wú)條件轉(zhuǎn)移四元式,沒(méi)有布爾運(yùn)算。例:例:if A or BD then S1 else S2翻譯成如下四元式序列翻譯成如下四元式序列具體說(shuō)明如下:具體說(shuō)明如下:用用E.true和和E.false 分別表示分別表示E的的“真真”和和“假假”出出口轉(zhuǎn)移目標(biāo),在翻譯口轉(zhuǎn)移目標(biāo),在翻譯E時(shí)并未能確定。時(shí)并未能確定。對(duì)于對(duì)于E為為 a rop b 形式,生成代碼如下:形式,生成代碼如下:( jrop , a , b , E.true )( jump , E.false )以結(jié)構(gòu)圖表示:以結(jié)構(gòu)圖表示:E的代碼的代碼E.falseE.true對(duì)于
44、對(duì)于E為為 E1 or E2的形式,生成代碼結(jié)構(gòu)如下:的形式,生成代碼結(jié)構(gòu)如下:E1.的代碼的代碼E2.的代碼的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true若若E1為真,則可知為真,則可知E為真,即為真,即E1的真出口和的真出口和E的真出口一樣;的真出口一樣;若若E1為假,則必須計(jì)算為假,則必須計(jì)算E2,因此因此E1的假出口應(yīng)是的假出口應(yīng)是E2代碼的第代碼的第一個(gè)四元式序號(hào);一個(gè)四元式序號(hào);E2的真出口和假出口分別與的真出口和假出口分別與E的真出口和假出口一樣的真出口和假出口一樣E1.的代碼的代碼E2.的代碼的代碼E1.falseE2.falseE
45、.falseE1.trueE2.trueE.true對(duì)于對(duì)于E為為 E1 and E2的形式,生成代碼結(jié)構(gòu)如下:的形式,生成代碼結(jié)構(gòu)如下:對(duì)于對(duì)于E為為 not E1形式,只需調(diào)換形式,只需調(diào)換E1的真假出口,的真假出口,即可得到即可得到E的真假出口。的真假出口。例:例:E 為為 ab or cf ,翻譯為四元式序列:翻譯為四元式序列:(1) (j, a,b,E.true)(2) (jump, - ,- ,(3)(3) (j, e ,f ,E.true)(6) (jump, - ,- ,E.false)真假出口的拉鏈與回填真假出口的拉鏈與回填原因原因在把布爾式翻譯成一串條件轉(zhuǎn)和無(wú)條件轉(zhuǎn)四元在把
46、布爾式翻譯成一串條件轉(zhuǎn)和無(wú)條件轉(zhuǎn)四元式時(shí),真假出口未能在生成四元式時(shí)確定;而式時(shí),真假出口未能在生成四元式時(shí)確定;而且多個(gè)四元式可能有相同的出口且多個(gè)四元式可能有相同的出口說(shuō)明:說(shuō)明:E.true和和E.false不能在不能在產(chǎn)生四元式的同時(shí)確定,產(chǎn)生四元式的同時(shí)確定,要等將來(lái)目標(biāo)明確時(shí)再要等將來(lái)目標(biāo)明確時(shí)再回填,為此要記錄這些回填,為此要記錄這些要回填的四元式。要回填的四元式。通常采用通常采用“拉鏈拉鏈”的辦的辦法,把需要回填法,把需要回填E.true的四元式拉成一條的四元式拉成一條“真真”鏈,把需要回填鏈,把需要回填E.false的四元式拉成一條的四元式拉成一條“假假”鏈。鏈。if ab
47、or cf then S1 else S2翻譯為四元式序列:翻譯為四元式序列:(1) (j , a ,b ,(7)(2) (jump, - ,- ,(3)(3) (j , e ,f ,(7)(6) (jump, - ,- ,(p+1) (7) (關(guān)于關(guān)于S1的四元式的四元式)(p) (jump, - ,- ,q)(p+1) (關(guān)于關(guān)于S2的四元式的四元式) (q)拉鏈方式:拉鏈方式:則鏈接成為:則鏈接成為:(10) goto (True) (20) goto (10) (30) goto (20)把地址(把地址(30)作為鏈?zhǔn)?,地址()作為鏈?zhǔn)?,地址?0)作為鏈尾)作為鏈尾, True為為真
48、真鏈尾標(biāo)志。鏈尾標(biāo)志。四元式的第四個(gè)區(qū)段存放鏈指針。四元式的第四個(gè)區(qū)段存放鏈指針。E.true 和和E.false用于存放用于存放“真真”鏈和鏈和“假假”鏈的鏈的鏈?zhǔn)祖準(zhǔn)住H粲兴脑叫蛄校喝粲兴脑叫蛄校?10) goto E.true (20) goto E.true (30) goto E.true 為了完成拉鏈和回填工作,設(shè)計(jì)以下語(yǔ)義變量和為了完成拉鏈和回填工作,設(shè)計(jì)以下語(yǔ)義變量和過(guò)程(函數(shù)):過(guò)程(函數(shù)):1) 函數(shù)函數(shù)merge ( p1, p2 ) 用于把用于把P1和和P2為鏈?zhǔn)椎膬蔀殒準(zhǔn)椎膬蓷l鏈合并成條鏈合并成1條,返回合并后的鏈?zhǔn)字?。條,返回合并后的鏈?zhǔn)字怠F渌惴椋寒?dāng)其算法為
49、:當(dāng)P2為空鏈時(shí),返回為空鏈時(shí),返回P1;當(dāng)當(dāng)P2不為空不為空鏈時(shí),把鏈時(shí),把P2的鏈尾第四區(qū)段改為的鏈尾第四區(qū)段改為P1,返回返回P2。2) 過(guò)程過(guò)程backpatch ( p , t ) 用于把鏈?zhǔn)子糜诎焰準(zhǔn)譖所鏈接的每所鏈接的每個(gè)四元式的第四區(qū)段都填為轉(zhuǎn)移目標(biāo)個(gè)四元式的第四區(qū)段都填為轉(zhuǎn)移目標(biāo)t。3) 語(yǔ)義變量語(yǔ)義變量E.codebegin表示表達(dá)式表示表達(dá)式E的第一個(gè)四元的第一個(gè)四元式的序號(hào)。式的序號(hào)。 1)EE1 or E2 E.codebegin:E1.codebegin ;backpatch ( E1.false , E2.codebegin ) ;E.true:merge ( E
50、1.true , E2.true ) ; E.false:E2.false 自下而上分析中布爾表達(dá)式的一種翻譯方案自下而上分析中布爾表達(dá)式的一種翻譯方案2) EE1 and E2 E.codebegin:E1.codebigin ;backpatch ( E1.true , E2.codebegin ) ;E.true:E2.true ; E.false:merge ( E1.fasle , E2.false ) 3) Enot E1 E.codebegin:E1.codebigin ;E.true:E1.false ; E.false:E1.true 4)E(E1) E.codebegin:
51、E1.codebegin ;E.true:E1.true ; E.false:E1.false 5) Eid1 rop id2 E.codebegin:nextstat ; E.true:nextstat ; E.false:nextstat+1; emit ( jrop , id1.place , id2.place , true ) ; emit ( jump , false ) 6) Etrue E.codebegin:nextstat ; E.true:nextstat ;E.false:Nil;emit ( jump ,true ) 7) Efalse E.codebegin:nex
52、tstat ; E.false:nextstat ;E.true:Nil;emit ( jump ,false ) 例例 ab or cd and ef 的翻譯過(guò)程的翻譯過(guò)程假定四元式編號(hào)從假定四元式編號(hào)從100開(kāi)始,開(kāi)始,即開(kāi)始時(shí)即開(kāi)始時(shí)nextstat100EE1orE2E1andE2abcdefE1.begin=100E1.true=100E1.false=101E1.begin=102E1.true=102E1.false=103E2.begin=104E2.true=104E2.false=105E2.begin=102E2.true=104E2.false=103,105=105E
53、.begin=100E.true=100,104=104E.false=105100 : ( j , a , b , true )101: ( jump ,false )102: ( j , c , d , true )103: ( jump , fase )104: ( j , e , f , true )105: ( jump ,false )102 ( j , c , d ,104)105 ( jump ,103)101( jump,102)104 (j , e , f ,100)最終結(jié)果:最終結(jié)果:100:( j , a , b , true )101:( jump,102) 102:
54、( j , c , d , 104) 103:( jump, false ) 104:( j , e , f , 100) 105:( jump,103) “真真”鏈?zhǔn)祖準(zhǔn)譋.true104 , “假假”鏈?zhǔn)祖準(zhǔn)譋.false105。8.4.3 控制結(jié)構(gòu)的翻譯控制結(jié)構(gòu)的翻譯以以if 語(yǔ)句,語(yǔ)句,while語(yǔ)句為例說(shuō)明控制語(yǔ)句的翻譯方法語(yǔ)句為例說(shuō)明控制語(yǔ)句的翻譯方法S if E then Sif語(yǔ)句語(yǔ)句| if E then S else Sif語(yǔ)句語(yǔ)句| while E do Swhile語(yǔ)句語(yǔ)句| begin L end 復(fù)合語(yǔ)句復(fù)合語(yǔ)句| A賦值語(yǔ)句賦值語(yǔ)句A id:=EL L ; S語(yǔ)句
55、序列語(yǔ)句序列| S 語(yǔ)句語(yǔ)句 條件轉(zhuǎn)移語(yǔ)句的共同特點(diǎn)是:根據(jù)布爾表達(dá)式取值,條件轉(zhuǎn)移語(yǔ)句的共同特點(diǎn)是:根據(jù)布爾表達(dá)式取值,分別執(zhí)行不同的語(yǔ)句序列。分別執(zhí)行不同的語(yǔ)句序列。問(wèn)題問(wèn)題:不同的語(yǔ)句序列結(jié)束后,如何使控制轉(zhuǎn)向語(yǔ)句:不同的語(yǔ)句序列結(jié)束后,如何使控制轉(zhuǎn)向語(yǔ)句的結(jié)束。例如:的結(jié)束。例如:if E1 then if E2 then S1 else S2 else S3E1=1E2=1S1S2S3endstartYesNoYesNo參照布爾表達(dá)式的翻譯方參照布爾表達(dá)式的翻譯方法,對(duì)非終結(jié)符法,對(duì)非終結(jié)符S(和和L),設(shè)立語(yǔ)義變量設(shè)立語(yǔ)義變量S.CHAIN(和和L.CHAIN ),用于記用于記住需
56、要在翻譯完住需要在翻譯完S(L)后回后回填轉(zhuǎn)移目標(biāo)的一串四元式填轉(zhuǎn)移目標(biāo)的一串四元式1. 代碼結(jié)構(gòu)代碼結(jié)構(gòu)E的代碼的代碼S1 的代碼的代碼E.false E.true S1.CHAIN S.CHAIN qif E then S1 代碼結(jié)構(gòu)代碼結(jié)構(gòu)qif E then S1 else S2 代碼結(jié)構(gòu)代碼結(jié)構(gòu)S2 的代碼的代碼Jump outS1 的代碼的代碼E的代碼的代碼S.CHAIN E.false E.true S1.CHAIN S2.CHAIN out:E.true qwhile E do S1 代碼結(jié)構(gòu)代碼結(jié)構(gòu)Jump beginS1 的代碼的代碼E 的代碼的代碼S.CHAIN E.fa
57、lse begin:S1.CHAIN2文法的改寫文法的改寫 原因:在自下而上的語(yǔ)法制導(dǎo)翻譯中,語(yǔ)義動(dòng)作的原因:在自下而上的語(yǔ)法制導(dǎo)翻譯中,語(yǔ)義動(dòng)作的執(zhí)行是在使用產(chǎn)生式進(jìn)行歸約之后,并不允許在產(chǎn)執(zhí)行是在使用產(chǎn)生式進(jìn)行歸約之后,并不允許在產(chǎn)生式的中間執(zhí)行。為了能及時(shí)地執(zhí)行語(yǔ)義動(dòng)作(比生式的中間執(zhí)行。為了能及時(shí)地執(zhí)行語(yǔ)義動(dòng)作(比如回填轉(zhuǎn)移目標(biāo)),需對(duì)源文法改寫如回填轉(zhuǎn)移目標(biāo)),需對(duì)源文法改寫 方法:在需要執(zhí)行語(yǔ)義動(dòng)作的地方把產(chǎn)生式分段,方法:在需要執(zhí)行語(yǔ)義動(dòng)作的地方把產(chǎn)生式分段,引入新的非終結(jié)符來(lái)表示它引入新的非終結(jié)符來(lái)表示它 需要改寫的產(chǎn)生式:需要改寫的產(chǎn)生式:1) 把把 Sif E then S
58、1改寫成改寫成Cif E then (回填回填E.true)SC S12) 把把 Sif E then S1 else S2改寫成改寫成Cif E then (回填回填E.true)TpC S1 else (產(chǎn)生無(wú)條件轉(zhuǎn)移,產(chǎn)生無(wú)條件轉(zhuǎn)移, 并回填并回填E.false) STp S23) 把把 Swhile E do S3 改寫成改寫成 Wwhile (記住入口記住入口) WdW E do (回填回填E.true) S Wd S3 (產(chǎn)生無(wú)條件轉(zhuǎn)移產(chǎn)生無(wú)條件轉(zhuǎn)移 返回循環(huán)入口返回循環(huán)入口)4) 把把 LL ; S改寫成改寫成LsL ; (回填前一語(yǔ)句的出口回填前一語(yǔ)句的出口)LLs S改寫后的
59、文法改寫后的文法(1) S C S1(2) S Tp S2(3) S Wd S3(4) S begin L end(5) S A (6) L Ls S(7) L S(8) C if E then(9) Tp C S1 else(10) W while(11) Wd W E do(12) Ls L ; 源文法:源文法:S if E then SS if E then S else SS while E do SS begin L end S AL L ; SL S(8)(1)(8)(9)(2)(10)(11)(3)(4)(5)(12)(6)(7)3安排語(yǔ)義動(dòng)作安排語(yǔ)義動(dòng)作Cif E then b
60、ackpatch ( E.true , nextstat ) ; C.CHAIN:=E.false SC S1/* if E then S1 */ S.CHAIN:merge ( C.CHAIN , S1.CHAIN ) TpC S1 else/* if E then S1 else */ q:=nextstat ; emit ( jump,false ) ;/*S1執(zhí)行完,跳離整個(gè)執(zhí)行完,跳離整個(gè)if語(yǔ)句語(yǔ)句*/backpatch ( C.CHAIN , nextstat ) ;Tp.CHAIN:merge ( q , S1.CHAIN ) STp S2/* if E then S1 els
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 1白鷺說(shuō)課稿-2024-2025學(xué)年五年級(jí)上冊(cè)語(yǔ)文統(tǒng)編版
- 科技驅(qū)動(dòng)家居新潮流
- 外匯互換合同(2篇)
- 2024馬鈴薯種植基地生態(tài)環(huán)境監(jiān)測(cè)合同3篇
- 全新辦理協(xié)議離婚程序下載
- 2024招投標(biāo)與合同管理實(shí)務(wù)操作與案例分析心得總結(jié)3篇
- 臨時(shí)用工合同范本
- 海邊異國(guó)游記的故事征文
- 2024年綠色能源管理合同
- 14 當(dāng)沖突發(fā)生(說(shuō)課稿)-部編版(五四制)道德與法治四年級(jí)上冊(cè)
- 2025年度愛(ài)讀書學(xué)長(zhǎng)定制化閱讀計(jì)劃合同2篇
- 2025年首都機(jī)場(chǎng)集團(tuán)公司招聘筆試參考題庫(kù)含答案解析
- 保健品購(gòu)銷合同2025年
- 2024版光伏發(fā)電項(xiàng)目承包經(jīng)營(yíng)權(quán)轉(zhuǎn)讓合同范本3篇
- 實(shí)習(xí)終止及解除協(xié)議書
- 河南省信陽(yáng)市浉河區(qū)9校聯(lián)考2024-2025學(xué)年八年級(jí)上學(xué)期12月月考地理試題(含答案)
- 中國(guó)冠心病康復(fù)循證實(shí)踐指南(2024版)解讀
- 2024-2030年中國(guó)再生水行業(yè)發(fā)展前景預(yù)測(cè)規(guī)劃分析報(bào)告
- 城市公益性公墓建設(shè)項(xiàng)目施工組織設(shè)計(jì)
- 2022-2024年江蘇中考語(yǔ)文試題匯編:名著閱讀(教師版)
- 2024年秋季新人教版七年級(jí)上冊(cè)數(shù)學(xué)全冊(cè)教案
評(píng)論
0/150
提交評(píng)論