編譯原理第5版-課件匯 劉銘 第5-10章 語法制導翻譯技術(shù) 中間代碼生成 -并行編譯技術(shù)基本常識

源程序語法樹

中間代碼

目標代碼語義分析第5章語法制導翻譯技術(shù)

中間代碼生成本章主要介紹：基本思想幾種中間代碼的形式各種語法結(jié)構(gòu)的語法制翻譯第5章語法制導翻譯技術(shù)中間代碼生成語義分析的任務：靜態(tài)語義審查審查每個語法結(jié)構(gòu)的靜態(tài)語義,即驗證語法結(jié)構(gòu)合法的程序,是否真正有意義。5.1概述例如:表達式A+B*C對運算對象進行類型檢查;對變量進行先定義后使用檢查;執(zhí)行真正的翻譯如果靜態(tài)語義正確,則要執(zhí)行真正的翻譯:生成程序的中間代碼或直接生成目標代碼。5.1概述多數(shù)編譯程序進行語義分析的方法：語法制導翻譯法語法制導翻譯法：使用屬性文法為工具來描述程序設計語言的語義。5.1概述1.屬性文法(1)屬性對文法的每一個符號,引進一些屬性,這些屬性代表與文法符號相關(guān)的信息,如類型、值、存儲位置等。與屬性相關(guān)的信息,即屬性值,可以在語法分析過程中計算和傳遞。5.2屬性文法屬性加工的過程即是語義的處理過程。屬性分為兩類:綜合屬性和繼承屬性。綜合屬性按“自下而上”方式計算：即規(guī)則左部符號的某些屬性根據(jù)其右部符號的屬性和(或)自己的其他屬性計算而得。繼承屬性按“自上而下”方式計算：即規(guī)則右部符號的某些屬性根據(jù)其左部符號的屬性和(或)右部其他符號的某些屬性計算而得。5.2屬性文法(2)屬性文法屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則。語義規(guī)則:為文法的每一個規(guī)則配備的計算屬性的計算規(guī)則,稱為語義規(guī)則(描述語義處理的加工動作)。語義規(guī)則附在文法的每個產(chǎn)生式上,在語法分析過程中,執(zhí)行語義規(guī)則描述的動作,從而實現(xiàn)語義處理。5.2屬性文法5.3語法制導翻譯概述S→……{……}………A→xy{……}………

a1a2a3…aiai+1…an語義處理的加工動作語法制導翻譯法使用屬性文法為工具來說明程序設計語言的語義。語法制導翻譯法的基本思想：為文法的每個產(chǎn)生式都配備一個語義動作或語義子程序。語法分析的過程中，每當使用一條產(chǎn)生式進行推導或歸約時，就執(zhí)行相應產(chǎn)生式的語義動作,從而實現(xiàn)語義處理。5.3語法制導翻譯概述語義動作(語義子程序)描述了一個產(chǎn)生式所對應的翻譯工作。產(chǎn)生式只能產(chǎn)生符號串,并沒有指明所產(chǎn)生符號串的意義,僅僅是一些符號串的集合。5.3語法制導翻譯概述語義動作不僅指明了該產(chǎn)生式所產(chǎn)生符號串的意義，而且還根據(jù)這種意義規(guī)定了對應的加工動作（如查填各類表格、改變編譯程序的某些變量的值、打印各種錯誤信息及生成中間代碼等），從而完成預定的翻譯工作。5.3語法制導翻譯概述語法制導翻譯法在語法分析過程中，依隨分析的過程，根據(jù)每個產(chǎn)生式所對應的語義子程序(或語義規(guī)則描述的語義處理的加工動作)進行翻譯的方法。5.3語法制導翻譯概述例如，設有簡單算術(shù)表達式的文法：

E→E＋E|E*E|(E)|digit為文法每一產(chǎn)生式設計相應的求值的語義描述(語義動作)：5.3語法制導翻譯概述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＝digit.lexval}{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*5EEEEE語法制導翻譯技術(shù)分為：5.3語法制導翻譯概述自底向上語法制導翻譯自頂向下語法制導翻譯重點介紹自底向上語法制導翻譯。LR分析制導的具體實現(xiàn)方法:為文法的每一個產(chǎn)生式設計相應的語義動作為文法構(gòu)造LR分析表5.3語法制導翻譯概述擴充LR分析棧，以便存放文法符號對應的語義值5.3語法制導翻譯概述語義值棧狀態(tài)棧文法符號棧S0$

—S1X1X1.valSkXkXk.val.........修改總控程序:1.查分析表2.當歸約時,調(diào)用規(guī)則相應的語義程序5.3語法制導翻譯概述例如，設有簡單算術(shù)表達式的文法：

E→E＋E|E*E|(E)|digit為文法每一產(chǎn)生式設計相應的語義動作(求值的語義描述)：5.3語法制導翻譯概述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＝digit.lexval}2.為上述文法構(gòu)造LR分析表如下圖：

5.3語法制導翻譯概述90狀態(tài)ACTIONGOTO+digit*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc根據(jù)前表，用LR語法制導翻譯法得到表達式7+8*5的計值過程，如下圖：5.3語法制導翻譯概述步驟狀態(tài)棧語義棧符號棧輸入符號棧主要動作1_2030$_$7301_7$E4014_7_$E+50143_7_$E+87+8*5$S3+8*5$+8*5$8*5$*5$r4S4S3r44.E→digit{E.val＝digit.lexval}5.3語法制導翻譯概述步驟狀態(tài)棧語義棧符號棧輸入符號棧主要動作6_7_87014750147$E+E_7_8$E+E*8014753_7_8_$E+E*59014758_7_8_5$E+E*E100147_7_40$E+E*5$S55$$$$S3r4r2r11101_47$E$acc1.E→E+E{E.val＝E(1).val+E(2).val}自下而上語法制導翻譯法的特點:當棧頂形成句柄執(zhí)行規(guī)約時，調(diào)用相應的語義動作語義分析棧與語法分析棧同步操作如何給出相應的語義描述?5.3語法制導翻譯概述編譯中常見的中間語言:5.4中間語言逆波蘭式（后綴式）三元式樹形表示四元式逆波蘭式

逆波蘭式除去了原表達式中的括號，并將運算對象寫在前面，運算符寫在后面，因而又稱為后綴式。例如：5.4.1逆波蘭式逆波蘭式a*bab*(a+b)*(c+d)ab+cd+*中綴表達式逆波蘭式表示法同中綴表示法相比優(yōu)點？5.4.1逆波蘭式1.不再有括號,且運算符出現(xiàn)的順序體現(xiàn)了中綴表達式的運算順序2.易于計算機處理5.4.1逆波蘭式一般表達式計值時，要處理兩類符號，一類是運算對象，另一類是運算符，通常用兩個工作棧分別處理。但處理用逆波蘭式表示的表達式只用一個工作棧。

5.4.1逆波蘭式計算機自左到右順序掃描逆蘭波式:a若當前符號是運算對象,則進棧;b若當前符號是運算符:設為K元運算，則將棧頂?shù)腒個元素依次取出，同時進行K元運算，并將運算結(jié)果置于棧頂，c表達式處理完畢時，其計算結(jié)果自然呈現(xiàn)在棧頂。5.4.1逆波蘭式逆波蘭式ab+c*的處理過程如下圖：5.4.1逆波蘭式baT1cT1T2逆波蘭形式可以推廣到其他語法結(jié)構(gòu)：5.4.1逆波蘭式：賦值語句V=E逆波蘭式VE=條件語句ifES1;elseS2ES1S2￥LR分析制導生成逆波蘭式：

給出算術(shù)表達式翻譯到逆波蘭式的語義描述首先搞清楚生成什么樣的中間代碼或計值根據(jù)各種語法成份的語義,搞清楚它們應翻譯成什么形式的代碼結(jié)構(gòu)5.4.1逆波蘭式LR分析制導生成逆波蘭式：例如:賦值語句V=E計算E值的代碼

將E值存放到V中的代碼其代碼結(jié)構(gòu):例如:LR分析制導生成逆波蘭式：條件語句ifES1;elseS2

其代碼結(jié)構(gòu):計算E值的代碼S2的代碼S1的代碼FT(3)給出從源結(jié)構(gòu)到目標結(jié)構(gòu)的變換方法LR分析制導生成逆波蘭式：例如，簡單算術(shù)表達的文法：

給出算術(shù)表達式翻譯到逆波蘭式的語義描述E→E＋E|E*E|(E)|i源結(jié)構(gòu)

a+b*c目標結(jié)構(gòu)

abc*+E→E＋E|E*E|(E)|iLR分析制導生成逆波蘭式：1.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||*2.為上述文法構(gòu)造LR分析表如下圖：

LR分析制導生成逆波蘭式：0狀態(tài)ACTIONGOTO+i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r31234567891678acc3.算術(shù)表達式a+b*c翻譯到逆波蘭式的過程：

LR分析制導生成逆波蘭式：狀態(tài)棧符號棧輸入串輸出區(qū)030$$a01$E014$E+0143$E+ba+b*c$+b*c$+b*c$b*c$*c$aaa4.E→i{{printi}LR分析制導生成逆波蘭式：014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E*c$abc$$$$abababcabc*01$E$abc*+狀態(tài)棧符號棧輸入串輸出區(qū)acc2.E→E(1)*E(2){{print*}1.E→E(1)+E(2){print+}三元式主要由三部分組成：（OP，arg1,arg2）其中OP是運算符，arg1,arg2分別是第一和第二兩個運算對象。當OP是一目運算時，常常將運算對象定義為arg1。5.4.2三元式和樹形表示例如a+b*c的三元式序列：5.4.2三元式和樹形表示(1)(*bc)(2)(+a(1))運算對象是指向符號表的某一項或指向三元式表的某一項。三元式的特點：5.4.2三元式和樹形表示1.三元式出現(xiàn)的順序和語法成份的計值順序相一致。2.三元式之間的聯(lián)系是通過指示器實現(xiàn)的。間接三元式(1)間接三元式表:用來存放各三元式本身。(2)間接碼表:按執(zhí)行各三元式的順序,依次列出各三元式在三元式表中的位置。注意:間接三元式表中不存放重復的三元式。5.4.2三元式和樹形表示例如

語句5.4.2三元式和樹形表示X=(A+B)*C

Y=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))樹形表示A*B+C*D5.4.2三元式和樹形表示+C*A*BD末端結(jié)點表示一個運算對象,每一個內(nèi)結(jié)點表示一個一元或二元運算符。樹形表示是三元式的翻版(3)+(1)*(2)*CABD四元式主要由四部分組成：（OP，arg1,arg2,result）其中OP是運算符，arg1,arg2分別是第一和第二兩個運算對象。當OP是一目運算時，常常將運算對象定義為arg1。5.4.3四元式例如X＝a*b＋c/d的四元式序列：四元式的第四個分量result是編譯程序為存放中間運算結(jié)果而臨時引進的變量，常稱為臨時變量，如Ti，也可以是用戶自定義變量，如X。5.4.3四元式(1)(*,a,b,T1)(2)(/,c,d,T2)(3)(+,T1,T2,T3)(4)(=,T3,-,X

)四元式的特點：5.4.4四元式2.四元式之間的聯(lián)系是通過臨時變量實現(xiàn)的，這樣易于調(diào)整和變動四元式。1.四元式出現(xiàn)的順序和語法成份的計值順序相一致。3.便于優(yōu)化處理。編譯系統(tǒng)中，有時將四元式表示成另一種更直觀，更易理解的形式——三地址代碼或三地址語句。5.4.4四元式result:＝arg1OParg2三地址語句:語句中是三個量的賦值語句,每個量占一個地址。三地址代碼形式定義為：例如X＝a*b＋c/d的四元式序列：5.4.4四元式的翻譯：(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

LR分析制導生成四元式簡單算術(shù)表達式和賦值語句到四元式的翻譯：例如A→i＝EE→E＋E∣E*E∣(E)|i1.給出算術(shù)表達式和賦值語句翻譯到四元式的語義描述A→i＝EE→E＋E∣E*E∣(E)|i簡單算術(shù)表達式和賦值語句到四元式的翻譯：源結(jié)構(gòu)目標結(jié)構(gòu)（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()功變量能是產(chǎn)生一個新的臨時變量名字，并回送新的臨時名的整數(shù)碼。如T1，T2等。簡單算術(shù)表達式和賦值語句到四元式的翻譯：對臨時變量有兩種不同的處理方法:簡單算術(shù)表達式和賦值語句到四元式的翻譯：(2)不進符號表，臨時變量單詞值部分用整數(shù)碼表示。(1)送到符號表。語義過程Lookup（）

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

表示存放非終結(jié)符E值的變量名在符號表中的入口地址或臨時變量名的整數(shù)碼。簡單算術(shù)表達式和賦值語句到四元式的翻譯：利用以上定義的語義變量和函數(shù)等，寫出每一個規(guī)則式的語義動作如下：簡單算術(shù)表達式和賦值語句到四元式的翻譯：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)簡單算術(shù)表達式和賦值語句到四元式的翻譯：{E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}{E.place＝newtemp();emit(E.place’＝’E(1).place’*’E(2).place)}簡單算術(shù)表達式和賦值語句到四元式的翻譯：4.E→（E(1)）{E.place＝E(1).place；}5.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}2.為文法構(gòu)造LR分析表如下圖：

簡單算術(shù)表達式和賦值語句到四元式的翻譯：90狀態(tài)ACTIONGOTO+i*()$ES3S9S5S4S2S3S2S3S5S4S2S5S2S3r4r4r4r4r1r1r1r2r3r2r3r3r2r2r3123456781678acc3.算術(shù)表達式a+b*c翻譯到三地址語句的過程：

簡單算術(shù)表達式和賦值語句到四元式的翻譯：030$$a01$E014$E+0143$E+b－a－a－－a－－狀態(tài)棧符號棧語義棧輸入串a(chǎn)+b*c$+b*c$+b*c$b*c$*c$－－－變量在符號表的入口用變量本身表示簡單算術(shù)表達式和賦值語句到四元式的翻譯：*c$c$$$$$t1=b*ct2=a+t1

狀態(tài)棧符號棧語義棧輸入串014750147$E+E$E+E*014753$E+E*c014758$E+E*E0147$E+E01$E－a－b－－－a－b－c－a－t1－a－b－－a－b－t2acc簡單算術(shù)表達式和賦值語句到四元式的翻譯：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)}一.布爾表達式的文法

布爾表達式到四元式的翻譯

●計算邏輯值程序設計語言中布爾表達式有兩個作用:

●用作控制語句中的條件式布爾表達式是由布爾算符(∧、∨和)施于布爾變量或關(guān)系表達式而成。

對某些語言，如PL/1，允許更通用的表達式。其中，布爾算符、算術(shù)算符和關(guān)系算符可施于任何類型的表達式，并不區(qū)別布爾值和算術(shù)值。

布爾表達式到四元式的翻譯簡單起見，只考慮文法生成的布爾表達式:文法如下：布爾表達式到四元式的翻譯

E→E(1)∨E(2)

E→E(1)∧E(2)

E→

E(1)

E→(E(1))

E→i(1)ropi(2)

E→true

E→false

E→i二.布爾表達式的計值方法布爾表達式到四元式的翻譯1.如同計算算術(shù)表達式一樣,步步計算出各部分真、假值,最后計算出整個表達式的值。2.根據(jù)布爾運算的特殊性,采取某種優(yōu)化措施,可避免計算整個表達式的值。布爾表達式到四元式的翻譯

A∨B解釋成

A∧B解釋成

A解釋成ifAthentrueelseBifAthenBelsefalseifAthenfalseelsetrue三.布爾表達式的翻譯方法1.同翻譯算術(shù)表達式一樣,翻譯布爾表達式。布爾表達式到四元式的翻譯1.E→E(1)∨E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∨’E(2).place)}2.E→E(1)∧E(2){E.place＝newtemp()；emit(E.place’＝’E(1).place’∧’E(2).place)}布爾表達式到四元式的翻譯3.E→(E(1)){E.place＝E(1).place；}4.E→i(1)ropi(2){E.place＝newtemp()；emit(‘if’i(1).placerop.opi(2).place‘goto’next+3);emit(E.place’＝’‘0’);emit(gotonext+2);emit(E.place’＝’‘1’);}布爾表達式到四元式的翻譯5.E→true

{E.place＝newtemp()；emit(E.place’＝’‘1’)}{E.place＝newtemp()；emit(E.place’＝’‘0’)}6.E→false

或{E.place＝i.place；}6.E→i

例布爾表達式a=b∨c∧d對應如下四元式序列:布爾表達式到四元式的翻譯101ifa=bgoto104102t1=0103goto105104t1=1105t2=c∧d106t3=t1∨

t2

2.控制語句中布爾表達式的翻譯布爾表達式到四元式的翻譯條件語句的語法為:根據(jù)條件語句的語義,條件語句的代碼結(jié)構(gòu)為:ifEthenS(1)elseS(2)E的代碼S(1)的代碼S(2)的代碼Jumpout

out:

真

假

E是布爾表達式,根據(jù)布爾運算的特殊性,布爾表達式的目標結(jié)構(gòu)為:布爾表達式到四元式的翻譯假E(1)的代碼∨E(2)的代碼真S(1)S(2)真假真E(1)的代碼∧E(2)的代碼假S(2)S(1)假真真出口表示布爾表達式E為真時控制流向的轉(zhuǎn)移目標假出口表示布爾表達式E為假時控制流向的轉(zhuǎn)移目標(1)真出口和假出口:布爾表達式到四元式的翻譯(2)作為條件轉(zhuǎn)移的E,把E翻譯成的代碼是一串條件轉(zhuǎn)或無條件轉(zhuǎn)的四元式布爾表達式到四元式的翻譯對于E為aropb的形式生成代碼為:ifaropbgoto真出口goto假出口例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:布爾表達式到四元式的翻譯(q)100ifa<bgoto104101goto102102ifc<dgoto104103goto(p+1)104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)E(1)的真出口為104,E(1)的假出口為102E(2)的真出口為104,E(2)的假出口為(p+1)E的真出口為104,E的假出口為(p+1)……布爾表達式的真、假出口在產(chǎn)生對應四元式時能填寫嗎？布爾表達式到四元式的翻譯例如E(1)的真出口為104如何知道？只能分析到后面才能得到！布爾表達式到四元式的翻譯E.tr:記錄表達式E所對應的四元式需回填真出口的四元式的地址所構(gòu)成的鏈E.fa:記錄表達式E所對應的四元式需回填假出口的四元式的地址所構(gòu)成的鏈(3)設置兩個語義變量:例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:布爾表達式到四元式的翻譯(q)100ifa<bgoto104101goto102102ifc<dgoto104103goto(p+1)104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)……E(1).tr=100,

E(1).fa=101E(2).tr=102,

E(2).fa=103E(1)∨E(2)歸約E時,E.fa=103;E.tr=100和102所構(gòu)成的鏈布爾表達式到四元式的翻譯(4)鏈結(jié)函數(shù)和回填函數(shù):merg(p1,p2):把以p1,p2為鏈首的兩條鏈合并為一,返回合并后的鏈首布爾表達式到四元式的翻譯布爾表達式到四元式的翻譯r1(× × × 0)q1(× × × r1)q2(× × × r2)p1(× × × q1)r2(× × × 0)p2(× × × q2)p1merg(intp1,intp2)布爾表達式到四元式的翻譯}{ifp2=0return(p1);else{p=p2;

while(四元式p的第四分量內(nèi)容不為0)

p=四元式p的第四分量內(nèi)容;

把p1填進四元式p的第四分量;

return(p2);

}merg(intp1,intp2)布爾表達式到四元式的翻譯}{ifp2=0return(p1);else{p=p2;

while(四元式p的第四分量內(nèi)容不為0)

p=四元式p的第四分量內(nèi)容;

把p1填進四元式p的第四分量;

return(p2);

}100102102例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:布爾表達式到四元式的翻譯(q)100ifa<bgoto0101goto102102ifc<dgoto100

103goto(p+1)104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)……bp(intp,intt):

將p所鏈結(jié)的每個四元式的第四區(qū)分量都回填t;布爾表達式到四元式的翻譯bp(intp,intt)布爾表達式到四元式的翻譯}{q=p;while(q!=0){r=四元式q的第四分量內(nèi)容;

把t填進四元式q的第四分量;

q=r;

}1021041000102100例如語句ifa<b∨c<dthenS(1)elseS(2)

的四元式為:布爾表達式到四元式的翻譯(q)100ifa<bgoto104101goto102102ifc<dgoto104

103goto(p+1)104(關(guān)于S(1)

的四元式)……(p)goto(q)(p+1)(關(guān)于S(2)

的四元式)……(5)為及時回填轉(zhuǎn)移地址,使用語義變量E.code記錄表達式E的第一個四元式語句序號。布爾表達式到四元式的翻譯(6)定義語義變量next為四元式表指針。E(1).code=100E(2).code=102E.code=100布爾表達式語義動作的設計布爾表達式到四元式的翻譯1.E→E(1)∨E(2){bp(E(1).fa,E(2).code)；E.code=E(1).code;E.tr=merg(E(1).tr,E(2).tr);E.fa=E(2).fa;}布爾表達式語義動作的設計布爾表達式到四元式的翻譯2.E→E(1)∧E(2){bp(E(1).tr,E(2).code)；E.code=E(1).code;E.tr=E(2).tr;E.fa=merg(E(1).fa,E(2).fa);}布爾表達式語義動作的設計布爾表達式到四元式的翻譯3.E→(E(1)){E.code=E(1).code;E.tr=E(1).tr;E.fa=E(1).fa;}布爾表達式語義動作的設計布爾表達式到四元式的翻譯4.E→i(1)ropi(2){E.tr=next;E.code=next;E.fa=next+1;emit(ifi(1).placerop.opi(2).placegoto_);emit(goto_);}布爾表達式語義動作的設計布爾表達式到四元式的翻譯5.E→true{E.tr=next;E.code=next;emit(goto_);}布爾表達式語義動作的設計布爾表達式到四元式的翻譯6.E→false{E.fa=next;E.code=next;emit(goto_);}布爾表達式語義動作的設計布爾表達式到四元式的翻譯5.E→i{E.tr=next;E.fa=next+1;E.code=next;emit(ifi.placegoto-);emit(goto_);}5.E→true6.E→false例如布爾表達式a<b∨c<d的翻譯過程如下:布爾表達式到四元式的翻譯a<b∨c<d布爾表達式到四元式的翻譯E(1)∨c<d100ifa<bgoto0101goto0{E(1).tr=100;E(1).fa=101;

E(1).code=100;}E(1)∨E(2)

102ifc<dgoto0103goto0{E(2).tr=102;E(2).fa=103;

E(2).code=102;}布爾表達式到四元式的翻譯E{bp(E(1).fa,E(2).code)=bp(101,102);

E.fa=E(2).fa=103;E.tr=merg(E(1).tr,E(2).tr)=merg(100,102)=102;E.code=E(1).code=100}100ifa<bgoto0101goto0102ifc<dgoto100103goto0102E(1)∨E(2)

歸約為E布爾表達式

a<b∨c<d布爾表達式到四元式的翻譯102ifc<dgoto100103goto0100ifa<bgoto0101goto102E.tr=102E.fa=103程序設計語言中，程序中的每個名字（變量名）都必須在使用前進行說明。說明語句的功能就是告知編譯程序每一個變量的類型信息。

翻譯說明語句時,設計的語義動作應將變量的類型信息填入符號表中。簡單說明語句的翻譯簡單說明語句文法簡單說明語句的翻譯<namelist>→<namelist>,id|idD→integer<namelist>│real<namelist>上面的文法在進行歸約時，按自下而上制導翻譯時:1.會將所有名字id先歸約為一個名字表namelist;2.再將namelist中所有名字的性質(zhì)登錄在符號表里。問題:上面必須用一個隊列來保存namelist中的所有名字。能否優(yōu)化一下:遇到一個名字，能立刻采用某規(guī)則歸約，直接到符號表中進行查找，而無需占用額外空間保存namelist中名字的信息簡單說明語句的翻譯修改前面的文法，實現(xiàn)剛才的優(yōu)化要求：D→D(1)，id│integerid│realid簡單說明語句的翻譯（1）函數(shù)FILL(id，A)的功能是把名字id和性質(zhì)A登錄在符號表中。并對修改后的文法，設計相應的語義動作如下：（2）設置非終結(jié)符D的語義變量D.ATT,記錄說明語句所規(guī)定的相關(guān)名字性質(zhì)。簡單說明語句的翻譯（1）D→integerid（2）D→realid（3）D→D(1),id{FILL(id,int);D.ATT＝int}{FILL(id,real);D.ATT=real}{FILL(id,D(1).ATT);D.ATT=D(1).ATT}1.簡單算術(shù)表達式的逆波蘭式和四元式的表示本章小結(jié)例如–a+b*(–c+d)的逆波蘭式a@bc@d+*+例–a+b*(–c+d)的四元式本章小結(jié)t1=@a

t2=@c

t3=t2+dt5=t1+t4

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

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

t1=i–i

t2=i/t1t3=i↑t2iiii–/↑2.

編譯中常用的中間代碼:本章小結(jié)逆波蘭式四元式三元式樹形表示 3.什么是語法制導翻譯法在語法分析過程中，依隨分析的過程，根據(jù)每個產(chǎn)生式所對應的語義子程序(語義規(guī)則描述的語義處理的加工動作)進行翻譯的方法。4.采用自下而上的語法制導翻譯法語義動作的設計本章小結(jié)（1）搞清楚源結(jié)構(gòu)和目標結(jié)構(gòu)（2）自下而上的語法制導翻譯特點：棧頂形成句柄，歸約時執(zhí)行相應語義動作（3）給出從源結(jié)構(gòu)到目標結(jié)構(gòu)的變換方法例1.設文法及其相應的語義動作如下:本章小結(jié)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的翻譯結(jié)果分析:首先對輸入串

bR/bTc/bSc/ac畫出語法樹:本章小結(jié)ScTbRS/R/RS/RcTbaScTbRS再考慮歸約時執(zhí)行相應語義動作本章小結(jié)ScTbRS/R/RS/RcTbaScTbRSS→bTc{print“1”}S→a{print“2”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}14翻譯結(jié)果為:53142431輸入是bR/bTc/bSc/ac輸出為:本章小結(jié)ScTbRS/R/RS/RcTbaScTbRSR→R/SS→bTcS→aT→RR→S1453142431給出相應語義動作(翻譯方案){print“1”}{print“2”}{print“3”}{print“4”}{print“5”}例2簡單算術(shù)表達式求值的語義描述本章小結(jié)例如，設有簡單算術(shù)表達式的文法：

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＝digit.lexval}例3簡單算術(shù)表達式翻譯到四元式的語義描述本章小結(jié)例如，設有簡單算術(shù)表達式的文法：

E→E＋E|E*E|(E)|i1.E→E(1)＋E(2)2.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é)3.E→（E(1)）{E.place＝E(1).place；}4.E→i{p＝Lookup();if(p!=NULL)E.place＝p;elseerror();}本章小結(jié)第6章符號表的組織與管理編譯過程中，始終涉及到對一些語法符號的處理，需要用到這些語法符號的相關(guān)屬性。為了在需要的時候能找到這些語法成分及其相關(guān)屬性，必須使用一些表格保存這些語法成分及其相關(guān)屬性，這些表格就是符號表。第6章符號表的組織與管理符號表是編譯程序中主要的數(shù)據(jù)結(jié)構(gòu)之一。本章主要介紹符號表的作用符號表的組織符號表的建立和查找6.1符號表的作用與生成期符號表的作用符號表用來存放程序語言中出現(xiàn)的有關(guān)標識符的屬性和特征。符號表在整個編譯期間的作用歸納為以下幾個方面：將標識符的名字及屬性登錄在符號表中6.1符號表的作用與生成期在分析說明語句時，編譯程序根據(jù)說明語句信息將標識符的相應屬性如標識符的類型：實型，整型，布爾型等；標識符的種屬：數(shù)組名，變量名，過程名，函數(shù)名等;標識符的作用域：全局變量或局部變量等信息登錄到符號表中。6.1符號表的作用與生成期輔助上下文語義的正確性檢查如對運算對象和運算符進行類型檢查,對變量進行先定義后使用檢查等。通過符號表中記錄的屬性可進行上述語義檢查。6.1符號表的作用與生成期輔助目標代碼生成在目標代碼生成階段，符號表是數(shù)據(jù)存儲分配的依據(jù)。要形成能運行的目標代碼，需要對程序中引用的標識符分配存儲單元，而存儲單元的分配與標識符屬性相關(guān)，與屬性相關(guān)的信息可通過查符號表獲取。6.1符號表的作用與生成期符號表的生成期符號表的建立可以開始于詞法分析階段，也可以放到語法、語義階段，但符號表的使用有時會延續(xù)到目標代碼的運行階段（如數(shù)組下標地址計算的需要等）。6.2符號表的內(nèi)容符號表中一般要保存以下信息：1.標識符的名字2.標識符有關(guān)的信息：(1)類型信息包括種類（常量、變量、數(shù)組、標號或函數(shù)等）、屬性（整型、實型、字符型、布爾型等）6.2符號表的內(nèi)容

數(shù)組包括維數(shù)、界差、上下界、計算下標地址時涉及的常量等，放在數(shù)組信息向量表（內(nèi)情向量表）中。

函數(shù)或過程包括參數(shù)的個數(shù)、類型、次序、是否允許遞歸等。6.2符號表的內(nèi)容(2)地址碼

常量或簡單變量一般是該量在數(shù)據(jù)區(qū)所占單元的絕對地址或相對地址。

數(shù)組是該數(shù)組在數(shù)據(jù)區(qū)中的首地址。

函數(shù)或過程是該函數(shù)或過程的分程序入口地址。6.2符號表的內(nèi)容(3)層次信息對于分程序嵌套或過程嵌套結(jié)構(gòu)型程序設計語言，還應包括每個標識符所屬分程序（過程）的層次。(4)行號信息有些程序設計語言需要保存標識符在源程序中的行號，包括說明行和引用行。6.3符號表的組織一個編譯程序，從詞法分析、語法分析、語義分析到代碼生成的整個過程中，符號表是連貫上下文進行語義檢查、語義處理、生成代碼和存儲分配的主要依據(jù)，因此符號表的組織直接關(guān)系到這些語義功能的實現(xiàn)和語義處理的時空效率。6.3符號表的組織符號表的表格形式名字欄存放標識符的名字，信息欄存放名字相關(guān)屬性。名字欄信息欄……6.3符號表的組織符號表的總體組織1.編譯程序按名字的不同屬性構(gòu)造出多個符號表。如常量表、變量名表等。符號表結(jié)構(gòu)相同，表項等長。不便管理。2.編譯程序把語言中的所有名字組織在一張符號表中。符號表便于管理，但表結(jié)構(gòu)復雜且表項不等長。6.3符號表的組織3.折衷方式即按名字屬性相似程度分類構(gòu)造出多個符號表。符號表管理復雜性折衷。6.3符號表的組織名字和標識符的區(qū)別在程序設計語言中，凡以字母開頭的字母數(shù)字序列都是標識符。當給予某個標識符以確切的含義后，這個標識符就叫做一個名字。也就是說標識符是一個沒有意義的字符序列，而名字有確切的意義。在程序語言中標識符可以是一個變量的名字或一個函數(shù)的名字。例如area,作為標識符，它沒有任何意思，但作為名字，可以表示變量名或函數(shù)名等。6.3符號表的組織一個名字代表一個存儲單元，該存儲單元的內(nèi)容為該名字的值，同時名字還有屬性（即類型和作用域等）符號表的數(shù)據(jù)結(jié)構(gòu)可以是線性符號表、也可以是樹結(jié)構(gòu)、散列表或桶等。6.4符號表的構(gòu)造和查找在整個編譯期間，對于符號表的操作一般可歸納為下列五類：(1)對給定名字，查詢此名是否已在表中。(2)往表中填入一個新的名字。(3)對給定名字，訪問它的某些信息。(4)對給定名字，往表中填寫或更新它的某些信息。(5)刪除一個或一組無用的表項。6.4符號表的構(gòu)造和查找1.符號表的構(gòu)造方法線性法、二分法及散列法。線性法：是按名字出現(xiàn)的先后順序填寫各表項。二分法：造表時是將名字攔按名字的大小順序排列。散列法：構(gòu)造一個散列函數(shù)將所得的函數(shù)值求整或求余得到表項在表中位置。NameInformationa……b……i……j……6.4符號表的構(gòu)造和查找ijbaibaj6.4符號表的構(gòu)造和查找2.符號表的查找算法符號表的查找算法與該符號表的構(gòu)造方法密切相關(guān)即有順序查找、折半查找和雜湊查找算法。本章小結(jié)1.符號表的作用符號表用來存放程序語言中出現(xiàn)的有關(guān)標識符的屬性和特征。(1)將標識符的名字及屬性登錄在符號表中(2)輔助上下文語義的正確性檢查(3)輔助目標代碼生成本章小結(jié)2.標識符和名字的區(qū)別在程序設計語言中，凡以字母開頭的字母數(shù)字序列都是標識符。當給予某個標識符以確切的含義后，這個標識符就叫做一個名字。本章小結(jié)也就是說標識符是一個沒有意義的字符序列，而名字有確切的意義。在程序語言中標識符可以是一個變量的名字或一個函數(shù)的名字。例如area,作為標識符，它沒有任何意思，但作為名字，可以表示變量名或函數(shù)名等。

本章小結(jié)3.符號表的查找符號表查找算法與該符號表的構(gòu)造方法密切相關(guān)即有順序查找、折半查找和雜湊查找算法。第7章代碼優(yōu)化本章主要介紹：優(yōu)化基本概念基本塊內(nèi)的局部優(yōu)化2025/2/191457.1優(yōu)化概述什么是代碼優(yōu)化？對程序?qū)嵤└鞣N等價變換,使得變換后程序能生成高效率的目標代碼。高效率的目標代碼是指：目標代碼占用的存儲空間少目標代碼運行時間短代碼優(yōu)化的原則1.等價原則：保證等價性。2.有效原則：有明顯的效果。3.合算原則：較低的代價取得較好的優(yōu)化效果。2025/2/19146代碼優(yōu)化的種類：根據(jù)是否涉及具體的計算機分為:與機器有關(guān)的優(yōu)化(優(yōu)化工作主要在目標代碼級上進行)

對寄存器的優(yōu)化

多處理機的優(yōu)化

特殊指令的優(yōu)化等與機器無關(guān)的優(yōu)化(優(yōu)化工作主要在中間代碼級上進行)7.1優(yōu)化概述2025/2/191477.1優(yōu)化概述2025/2/19148根據(jù)優(yōu)化對象所涉及的程序范圍分為:局部優(yōu)化循環(huán)優(yōu)化全局優(yōu)化局部優(yōu)化：局限于程序基本塊范圍內(nèi)的一種優(yōu)化。

合并已知量

刪除公共子表達式(刪除多余的運算)

刪除無用賦值循環(huán)優(yōu)化:是指對循環(huán)中的代碼進行優(yōu)化。

代碼外提

刪除歸納變量

強度削弱全局優(yōu)化:是在整個程序范圍內(nèi)進行的優(yōu)化,需進行數(shù)據(jù)流分析,花費代價很高。S=0；for(i=1;i<=20;i++)S=S+A[i]*B[i]；優(yōu)化處理例如設有一個計算兩個向量內(nèi)積的源程序段:7.1優(yōu)化概述2025/2/19149說明:<A[I]>=<A[1]>+I－1=addr(A)－1+Iaddr(A)－1

T2地址計算的不變部分I

T1地址計算的可變部分用T2[T1]表示數(shù)組元素的地址若一個機器字有四個字節(jié),按字節(jié)編址:T1=4*IT2=addr(A)－4*1(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/19150刪除公共子表達式

(刪除多余運算)公共子表達式是指在一個基本塊內(nèi)計算結(jié)果相同的子表達式。(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/19151(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=4*I(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B2(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=T1(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/191522.代碼外提是指將循環(huán)中的不變運算提到循環(huán)體之外。(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=T1(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/19153(1)S=0(2)I=1(3)T1=4*I(4)T2=addr(A)－4(5)T3=T2[T1](6)T4=T1(7)T5=addr(B)－4(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/19154(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B23.強度削弱是指在不改變運算結(jié)果的前提下，將程序中執(zhí)行時間長的運算替換成執(zhí)行時間短的運算。

對計算機上的二進制算術(shù)運算，作加法一般比作乘法的速度快。7.1優(yōu)化概述2025/2/19155(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifI≤20goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7(11)I=I+1(12)ifI≤20goto(3)B1B27.1優(yōu)化概述2025/2/191564.變換循環(huán)控制條件

(刪除歸納變量)在B2中存在變量T與循環(huán)控制變量I保持線性關(guān)系，則可由T取代I,因此對三地址語句(12)中的循環(huán)控制條件I≤20T1≤80(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifI≤20goto(5)B1B27.1優(yōu)化概述2025/2/19157(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifI≤20goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7

I=I+1×(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/191587.1優(yōu)化概述5.合并已知量已知量是指，常數(shù)或在編譯時就能確定其值的變量。合并已知量是指，若參加運算的兩個對象在編譯時都是已知量，則可以在編譯時直接計算出它們的運算結(jié)果，不必生成目標。2025/2/19159(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1×(3')T1=T1+4(12)ifT1≤80goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)

T1=4*I(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1×(3')T1=T1+4(12)ifT1≤80goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1(8)

T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifT1≤80goto(5)B1B27.1優(yōu)化概述2025/2/191607.1優(yōu)化概述6.復寫傳播是指盡量不引用那些在程序中僅僅只傳遞信息而不改變其值，也不影響其運行結(jié)果的變量。2025/2/19161(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1(8)T6=T5[T4](9)T7=T3*T6(10)S=S+T7I=I+1(3')T1=T1+4(12)ifT1≤80goto(5)B1B2(1)S=0I=1(4)T2=addr(A)－4(7)T5=addr(B)－4(3)T1=4(5)T3=T2[T1](6)T4=T1×(8)T6=T5[T1](9)T7=T3*T6(10)