語(yǔ)法制導(dǎo)翻譯技術(shù)及中間代碼生成

本章主要介紹：語(yǔ)法制導(dǎo)翻譯法的基本思想常見(jiàn)的幾種中間代碼的形式各種不同語(yǔ)法結(jié)構(gòu)的語(yǔ)法制導(dǎo)翻譯技術(shù)第五章語(yǔ)法制導(dǎo)翻譯技術(shù)和

中間代碼生成靜態(tài)語(yǔ)義審查

審查每個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義,即驗(yàn)證語(yǔ)法結(jié)構(gòu)合法的程序,是否真正有意義。5.1概述如果靜態(tài)語(yǔ)義正確,語(yǔ)義處理則要執(zhí)行真正的翻譯,即生成程序的某種中間代碼的形式或直接生成目標(biāo)代碼。執(zhí)行真正的翻譯(1)屬性對(duì)文法的每一個(gè)符號(hào),引進(jìn)一些屬性,這些屬性代表與文法符號(hào)相關(guān)的信息,如類(lèi)型、值、存儲(chǔ)位置等。與屬性相關(guān)的信息,即屬性值,可以在語(yǔ)法分析過(guò)程中計(jì)算和傳遞。1.屬性文法5.2屬性文法屬性分為兩類(lèi):綜合屬性其計(jì)算規(guī)則按“自下而上”方式進(jìn)行,即規(guī)則左部符號(hào)的某些屬性根據(jù)其右部符號(hào)的屬性和(或)自己的其他屬性計(jì)算而得。屬性加工的過(guò)程即是語(yǔ)義的處理過(guò)程。綜合屬性和繼承屬性。E→E(1)+E(2){E.val=E(1).val+E(2).val}5.2屬性文法繼承屬性其計(jì)算規(guī)則按“自上而下”方式進(jìn)行,即規(guī)則右部符號(hào)的某些屬性根據(jù)其左部符號(hào)的屬性和(或)右部其他符號(hào)的某些屬性計(jì)算而得。D→TL

{L.in=T.type}T→int{T.type=integer}T→real{T.type=real}L→L(1),id{L(1).in=L.in;Fill(id.entry,L.in)}L→id{Fill(id.entry,L.in)}5.2屬性文法(2)屬性文法為文法的每一個(gè)規(guī)則配備的計(jì)算屬性的計(jì)算規(guī)則,稱(chēng)為語(yǔ)義規(guī)則(描述語(yǔ)義處理的加工動(dòng)作)。屬性文法包含一個(gè)上下文無(wú)關(guān)文法和一系列語(yǔ)義規(guī)則。語(yǔ)義規(guī)則:屬性加工的過(guò)程即是語(yǔ)義的處理過(guò)程5.2屬性文法語(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ǔ)義處理。E→E(1)+E(2){E.val=E(1).val+E(2).val}5.3語(yǔ)法制導(dǎo)翻譯概述(語(yǔ)義子程序)

描述了一個(gè)產(chǎn)生式所對(duì)應(yīng)的翻譯工作。語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作不僅指明了該產(chǎn)生式所產(chǎn)生符號(hào)串的意義，而且還根據(jù)這種意義規(guī)定了對(duì)應(yīng)的加工動(dòng)作（如查填各類(lèi)表格、改變編譯程序的某些變量的值、打印各種錯(cuò)誤信息及生成中間代碼等），從而完成預(yù)定的翻譯工作。5.3語(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.3語(yǔ)法制導(dǎo)翻譯概述為文法每一產(chǎn)生式設(shè)計(jì)相應(yīng)的求值的語(yǔ)義描述(語(yǔ)義動(dòng)作)：例如，設(shè)有簡(jiǎn)單算術(shù)表達(dá)式的文法：E→E＋E|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.3語(yǔ)法制導(dǎo)翻譯概述E.val=47E.val=8E.val=40E.val=7E.val=5+5*871.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*5EEEEE5.3語(yǔ)法制導(dǎo)翻譯概述語(yǔ)法制導(dǎo)翻譯技術(shù)分為：自底向上語(yǔ)法制導(dǎo)翻譯自頂向下語(yǔ)法制導(dǎo)翻譯5.3語(yǔ)法制導(dǎo)翻譯概述LR分析制導(dǎo)的具體實(shí)現(xiàn)方法:為文法的每一個(gè)產(chǎn)生式設(shè)計(jì)相應(yīng)的語(yǔ)義動(dòng)作為文法構(gòu)造LR分析表5.3語(yǔ)法制導(dǎo)翻譯概述擴(kuò)充LR分析棧，以便存放文法符號(hào)對(duì)應(yīng)的語(yǔ)義值語(yǔ)義值棧狀態(tài)棧文法符號(hào)棧

S0$—

S1X1X1.val

SkXkXk.val.........修改總控程序:查分析表,當(dāng)用某產(chǎn)生式歸約時(shí),調(diào)用相應(yīng)的語(yǔ)義動(dòng)作5.3語(yǔ)法制導(dǎo)翻譯概述例如，設(shè)有簡(jiǎn)單算術(shù)表達(dá)式的文法：E→E＋E|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}為文法每一產(chǎn)生式設(shè)計(jì)相應(yīng)的語(yǔ)義動(dòng)作

(求值的語(yǔ)義描述)：5.3語(yǔ)法制導(dǎo)翻譯概述2.為上述文法構(gòu)造LR分析表如下圖：90狀態(tài)ACTIONGOTO+digit*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc5.3語(yǔ)法制導(dǎo)翻譯概述自下而上語(yǔ)法制導(dǎo)翻譯法的特點(diǎn):語(yǔ)義分析棧與語(yǔ)法分析棧同步操作當(dāng)棧頂形成句柄執(zhí)行歸約時(shí)，調(diào)用相應(yīng)的語(yǔ)義動(dòng)作若將其翻譯成某種中間代碼,如何給出相應(yīng)的語(yǔ)義描述?5.3語(yǔ)法制導(dǎo)翻譯概述編譯中常見(jiàn)的中間語(yǔ)言:逆波蘭式（后綴式）三元式樹(shù)形表示四元式5.4中間語(yǔ)言逆波蘭式

逆波蘭式除去了原表達(dá)式中的括號(hào)，并將運(yùn)算對(duì)象寫(xiě)在前面，運(yùn)算符寫(xiě)在后面，因而又稱(chēng)為后綴式。例如：逆波蘭式a*bab*(a+b)*(c+d)ab+cd+*中綴表達(dá)式5.4.1逆波蘭式逆波蘭式表示法同中綴表示法相比其優(yōu)點(diǎn)是:不再有括號(hào),且運(yùn)算符出現(xiàn)的順序體現(xiàn)了中綴表達(dá)式的運(yùn)算順序2.易于計(jì)算機(jī)處理5.4.1逆波蘭式逆波蘭式ab+c*的處理過(guò)程如下圖：baT1cT1T25.4.1逆波蘭式逆波蘭形式可以推廣到其他語(yǔ)法結(jié)構(gòu)：賦值語(yǔ)句V=E逆波蘭式VE=條件語(yǔ)句逆波蘭式ifES1;elseS2ES1S2￥5.4.1逆波蘭式LR分析制導(dǎo)生成逆波蘭式：

給出算術(shù)表達(dá)式翻譯到逆波蘭式的語(yǔ)義描述中間代碼采取何種形式或計(jì)值根據(jù)各種語(yǔ)法成份的語(yǔ)義,給出翻譯得到的代碼結(jié)構(gòu)的形式5.4.1逆波蘭式LR分析制導(dǎo)生成逆波蘭式例如:賦值語(yǔ)句V=E計(jì)算E值的代碼將E值存放到V中的代碼其代碼結(jié)構(gòu):(3)給出從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法例如，簡(jiǎn)單算術(shù)表達(dá)的文法：E→E＋E|E*E|(E)|i源結(jié)構(gòu)a+b*c目標(biāo)結(jié)構(gòu)abc*+LR分析制導(dǎo)生成逆波蘭式E→E＋E|E*E|(E)|i1.E→E(1)＋E(2)

{print+}2.E→E(1)*E(2)

{print*}3.E→(E(1)){空}4.E→i{printi}0.E'→E{空}E(1).code||E(2).code||+E(1).code||E(2).code||*LR分析制導(dǎo)生成逆波蘭式2.為上述文法構(gòu)造LR分析表如下圖：LR分析制導(dǎo)生成逆波蘭式90狀態(tài)ACTIONGOTO+i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc三元式主要由三部分組成：（OP，arg1,arg2）其中OP是運(yùn)算符，arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對(duì)象。當(dāng)OP是一目運(yùn)算時(shí)，常常將運(yùn)算對(duì)象定義為arg1。5.4.2三元式和樹(shù)形表示例如a+b*c的三元式序列：(1)(*bc)(2)(+a(1))運(yùn)算對(duì)象是指向符號(hào)表的某一項(xiàng)或指向三元式表的某一項(xiàng)。5.4.2三元式和樹(shù)形表示1.三元式出現(xiàn)的順序和語(yǔ)法成份的計(jì)值順序相一致。三元式的特點(diǎn)：2.三元式之間的聯(lián)系是通過(guò)指示器實(shí)現(xiàn)的。5.4.2三元式和樹(shù)形表示間接三元式(1)間接三元式表:用來(lái)存放各三元式本身。(2)間接碼表:按執(zhí)行各三元式的順序,依次列出各三元式在三元式表中的位置。注意:間接三元式表中不存放重復(fù)的三元式。5.4.2三元式和樹(shù)形表示例如語(yǔ)句X=(A+B)*CY=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.4.2三元式和樹(shù)形表示樹(shù)形表示A*B+C*D+C*A*BD末端結(jié)點(diǎn)表示一個(gè)運(yùn)算對(duì)象,每一個(gè)內(nèi)結(jié)點(diǎn)表示一個(gè)一元或二元運(yùn)算符。樹(shù)形表示是三元式的翻版(3)+(1)*(2)*CABD5.4.2三元式和樹(shù)形表示四元式主要由四部分組成：（OP，arg1,arg2,result）其中OP是運(yùn)算符，arg1,arg2分別是第一和第二兩個(gè)運(yùn)算對(duì)象。當(dāng)OP是一目運(yùn)算時(shí)，常常將運(yùn)算對(duì)象定義為arg1。5.4.3四元式例如X＝a*b＋c/d的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)5.4.3四元式2.四元式之間的聯(lián)系是通過(guò)臨時(shí)變量實(shí)現(xiàn)的，這樣易于調(diào)整和變動(dòng)四元式。1.四元式出現(xiàn)的順序和語(yǔ)法成份的計(jì)值順序相一致。四元式的特點(diǎn)：3.便于優(yōu)化處理。5.4.3四元式result:＝arg1OParg2

三地址語(yǔ)句:語(yǔ)句中是三個(gè)量的賦值語(yǔ)句,每個(gè)量占一個(gè)地址。三地址代碼形式定義為：5.4.3四元式例如X＝a*b＋c/d的四元式序列：(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)相應(yīng)的三地址語(yǔ)句序列為：（1）T1＝a*b（2）T2＝c/d（3）T3＝T1＋T2

（4）X＝T3

5.4.4四元式的翻譯簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯LR分析制導(dǎo)生成四元式例如A→i＝EE→E＋E∣E*E∣(E)|i1.給出算術(shù)表達(dá)式和賦值語(yǔ)句翻譯到四元式的語(yǔ)義描述A→i＝EE→E＋E∣E*E∣(E)|i源結(jié)構(gòu)目標(biāo)結(jié)構(gòu)（1）T1＝a*b（2）T2＝c/d（3）T3＝T1＋T2

（4）X＝T3

X＝a*b＋c/d簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯語(yǔ)義函數(shù)emit（T＝arg1OParg2）

功能是生成一個(gè)三地址語(yǔ)句，并送到輸出文件中。語(yǔ)義函數(shù)newtemp()

功能是產(chǎn)生一個(gè)新的臨時(shí)變量名字，并回送新的臨時(shí)變量名的整數(shù)碼。如T1，T2等。簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯(2)不進(jìn)符號(hào)表，臨時(shí)變量單詞值部分用整數(shù)碼表示。(1)送到符號(hào)表。對(duì)臨時(shí)變量有兩種不同的處理方法:簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯語(yǔ)義過(guò)程Lookup（）

功能是審查是否出現(xiàn)在符號(hào)表中，在則返回其指針，否則返回NULL。語(yǔ)義變量E.place

表示存放非終結(jié)符E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量名的整數(shù)碼。簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯利用以上定義的語(yǔ)義變量和函數(shù)等，寫(xiě)出每一個(gè)規(guī)則式的語(yǔ)義動(dòng)作如下：1.A→i＝E

{p=Lookup();if(P!=NULL)emit(p’＝’E.place);elseerror()}簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯2.E→E(1)＋E(2)3.E→E(1)*E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}{E.place＝newtemp();emit(E.place’＝’E(1).place’*’E(2).place)}簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯4.E→（E(1)）{E.place＝E(1).place；}5.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯簡(jiǎn)單算術(shù)表達(dá)式和賦值語(yǔ)句

到四元式的翻譯90狀態(tài)ACTIONGOTO+i*()$ES2S12S8S7S6S5S3S8S6S5r5r5r5r5r2r2r2r3r4r3r4r4r3r41234567814910acc2.為文法構(gòu)造LR分析表如下圖

101112AS6S5S6S5:=r1S8S711 1.簡(jiǎn)單算術(shù)表達(dá)式的逆波蘭式和四元式的表示例如–a+b*(–c+d)的逆波蘭式a@bc@d+*+本章小結(jié)t1=@a

t2=@c

t3=t2+dt5=t1+t4例–a+b*(–c+d)的四元式

t4=b*t3本章小結(jié)i↑(i/(i–i))的逆波蘭式

i↑(i/(i–i))的四元式

t1=i–i

t2=i/t1t3=i↑t2iiii–/↑例如：本章小結(jié) 2.編譯中常用的中間代碼:逆波蘭式四元式三元式樹(shù)形表示 3.什么是語(yǔ)法制導(dǎo)翻譯法在語(yǔ)法分析過(guò)程中，依隨分析的過(guò)程，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序(語(yǔ)義規(guī)則描述的語(yǔ)義處理的加工動(dòng)作)進(jìn)行翻譯的方法。本章小結(jié) 4.采用自下而上的語(yǔ)法制導(dǎo)翻譯法語(yǔ)義動(dòng)作的設(shè)計(jì)（1）搞清楚源結(jié)構(gòu)和目標(biāo)結(jié)構(gòu)（2）自下而上的語(yǔ)法制導(dǎo)翻譯特點(diǎn)：棧頂形成句柄，歸約時(shí)執(zhí)行相應(yīng)語(yǔ)義動(dòng)作（3）給出從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法本章小結(jié)例1.設(shè)文法及其相應(yīng)的語(yǔ)義動(dòng)作如下:S→bTc{print“1”}S→a{print“2”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}采用自下而上語(yǔ)法制導(dǎo)翻譯,給出輸入串bR/bTc/bSc/ac的翻譯結(jié)果本章小結(jié)分析:首先對(duì)輸入串

bR/bTc/bSc/ac畫(huà)出語(yǔ)法樹(shù):ScTbRS/R/RS/RcTbaScTbRS再考慮歸約時(shí)執(zhí)行相應(yīng)語(yǔ)義動(dòng)作本章小結(jié)S→bTc{print“1”}S→a{print“2”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}14翻譯結(jié)果為:53142431本章小結(jié)ScTbRS/R/RS/RcTbaScTbRSR→R/SS→bTcS→aT→R