語法制導翻譯技術及中間代碼生成

本章主要介紹：語法制導翻譯法的基本思想常見的幾種中間代碼的形式各種不同語法結構的語法制導翻譯技術第五章語法制導翻譯技術和

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

審查每個語法結構的靜態(tài)語義,即驗證語法結構合法的程序,是否真正有意義。5.1概述如果靜態(tài)語義正確,語義處理則要執(zhí)行真正的翻譯,即生成程序的某種中間代碼的形式或直接生成目標代碼。執(zhí)行真正的翻譯(1)屬性對文法的每一個符號,引進一些屬性,這些屬性代表與文法符號相關的信息,如類型、值、存儲位置等。與屬性相關的信息,即屬性值,可以在語法分析過程中計算和傳遞。1.屬性文法5.2屬性文法屬性分為兩類:綜合屬性其計算規(guī)則按“自下而上”方式進行,即規(guī)則左部符號的某些屬性根據(jù)其右部符號的屬性和(或)自己的其他屬性計算而得。屬性加工的過程即是語義的處理過程。綜合屬性和繼承屬性。E→E(1)+E(2){E.val=E(1).val+E(2).val}5.2屬性文法繼承屬性其計算規(guī)則按“自上而下”方式進行,即規(guī)則右部符號的某些屬性根據(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)屬性文法為文法的每一個規(guī)則配備的計算屬性的計算規(guī)則,稱為語義規(guī)則(描述語義處理的加工動作)。屬性文法包含一個上下文無關文法和一系列語義規(guī)則。語義規(guī)則:屬性加工的過程即是語義的處理過程5.2屬性文法語法制導翻譯法的基本思想

為文法的每個產生式都配備一個語義動作或語義子程序。在語法分析的過程中，每當使用一條產生式進行推導或歸約時，就執(zhí)行相應產生式的語義動作,從而實現(xiàn)語義處理。E→E(1)+E(2){E.val=E(1).val+E(2).val}5.3語法制導翻譯概述(語義子程序)

描述了一個產生式所對應的翻譯工作。語義動作語義動作不僅指明了該產生式所產生符號串的意義，而且還根據(jù)這種意義規(guī)定了對應的加工動作（如查填各類表格、改變編譯程序的某些變量的值、打印各種錯誤信息及生成中間代碼等），從而完成預定的翻譯工作。5.3語法制導翻譯概述語法制導翻譯法在語法分析過程中，依隨分析的過程，根據(jù)每個產生式所對應的語義子程序(語義規(guī)則描述的語義處理的加工動作)進行翻譯的方法。5.3語法制導翻譯概述為文法每一產生式設計相應的求值的語義描述(語義動作)：例如，設有簡單算術表達式的文法：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語法制導翻譯概述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語法制導翻譯概述語法制導翻譯技術分為：自底向上語法制導翻譯自頂向下語法制導翻譯5.3語法制導翻譯概述LR分析制導的具體實現(xiàn)方法:為文法的每一個產生式設計相應的語義動作為文法構造LR分析表5.3語法制導翻譯概述擴充LR分析棧，以便存放文法符號對應的語義值語義值棧狀態(tài)棧文法符號棧

S0$—

S1X1X1.val

SkXkXk.val.........修改總控程序:查分析表,當用某產生式歸約時,調用相應的語義動作5.3語法制導翻譯概述例如，設有簡單算術表達式的文法：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}為文法每一產生式設計相應的語義動作

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

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

給出算術表達式翻譯到逆波蘭式的語義描述中間代碼采取何種形式或計值根據(jù)各種語法成份的語義,給出翻譯得到的代碼結構的形式5.4.1逆波蘭式LR分析制導生成逆波蘭式例如:賦值語句V=E計算E值的代碼將E值存放到V中的代碼其代碼結構:(3)給出從源結構到目標結構的變換方法例如，簡單算術表達的文法：E→E＋E|E*E|(E)|i源結構a+b*c目標結構abc*+LR分析制導生成逆波蘭式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分析制導生成逆波蘭式2.為上述文法構造LR分析表如下圖：LR分析制導生成逆波蘭式90狀態(tài)ACTIONGOTO+i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc三元式主要由三部分組成：（OP，arg1,arg2）其中OP是運算符，arg1,arg2分別是第一和第二兩個運算對象。當OP是一目運算時，常常將運算對象定義為arg1。5.4.2三元式和樹形表示例如a+b*c的三元式序列：(1)(*bc)(2)(+a(1))運算對象是指向符號表的某一項或指向三元式表的某一項。5.4.2三元式和樹形表示1.三元式出現(xiàn)的順序和語法成份的計值順序相一致。三元式的特點：2.三元式之間的聯(lián)系是通過指示器實現(xiàn)的。5.4.2三元式和樹形表示間接三元式(1)間接三元式表:用來存放各三元式本身。(2)間接碼表:按執(zhí)行各三元式的順序,依次列出各三元式在三元式表中的位置。注意:間接三元式表中不存放重復的三元式。5.4.2三元式和樹形表示例如語句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三元式和樹形表示樹形表示A*B+C*D+C*A*BD末端結點表示一個運算對象,每一個內結點表示一個一元或二元運算符。樹形表示是三元式的翻版(3)+(1)*(2)*CABD5.4.2三元式和樹形表示四元式主要由四部分組成：（OP，arg1,arg2,result）其中OP是運算符，arg1,arg2分別是第一和第二兩個運算對象。當OP是一目運算時，常常將運算對象定義為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)系是通過臨時變量實現(xiàn)的，這樣易于調整和變動四元式。1.四元式出現(xiàn)的順序和語法成份的計值順序相一致。四元式的特點：3.便于優(yōu)化處理。5.4.3四元式result:＝arg1OParg2

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

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

（4）X＝T3

5.4.4四元式的翻譯簡單算術表達式和賦值語句

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

（4）X＝T3

X＝a*b＋c/d簡單算術表達式和賦值語句

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

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

功能是產生一個新的臨時變量名字，并回送新的臨時變量名的整數(shù)碼。如T1，T2等。簡單算術表達式和賦值語句

到四元式的翻譯(2)不進符號表，臨時變量單詞值部分用整數(shù)碼表示。(1)送到符號表。對臨時變量有兩種不同的處理方法:簡單算術表達式和賦值語句

到四元式的翻譯語義過程Lookup（）

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

表示存放非終結符E值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼。簡單算術表達式和賦值語句

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

{p=Lookup();if(P!=NULL)emit(p’＝’E.place);elseerror()}簡單算術表達式和賦值語句

到四元式的翻譯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)}簡單算術表達式和賦值語句

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

到四元式的翻譯簡單算術表達式和賦值語句

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

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

t2=@c

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

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

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

t1=i–i

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

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