編譯原理第5章語義分析和中間代碼產(chǎn)生課件

第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2022/11/241第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2022/11/221第五章語義分析的任務(wù)：根據(jù)語法成分的結(jié)構(gòu)，分析其含義，并用一種內(nèi)部形式（中間代碼）或直接用目標(biāo)語言表示出來。具體：靜態(tài)語義檢查和翻譯包括：類型檢查（操作符是否相容，例如%） 控制流檢查（break是否有switch和for,while） 一致性檢查（inta;floata;） 相關(guān)名字檢查、等等2022/11/242第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生語義分析的任務(wù)：根據(jù)語法成分的結(jié)構(gòu)，分析其含義，并用一種內(nèi)部§5.1屬性文法

一、屬性一、屬性：一般用來描述客觀存在的事物或人的特性。例如，學(xué)生的姓名、年齡、性別等；商品的顏色、重量、單價等。編譯技術(shù)中用屬性來描述計算機(jī)處理對象的特征。例如：X.Type,X.Place,X.val等分別描述X的類型，存儲位置、值等不同的特征。 屬性分兩類： 綜合屬性：一般用于“自下而上”傳遞信息。 繼承屬性：一般用于“自上而下”傳遞信息。2022/11/243第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生§5.1屬性文法

一、屬性一、屬性：一般用來描述客觀二、屬性文法

對于某個壓縮了的上下文無關(guān)文法，當(dāng)為每個文法符號引進(jìn)一組屬性，且讓該文法中的重寫規(guī)則附加以語義規(guī)則時，稱該上下文無關(guān)文法為屬性文法。

形式定義：一個屬性文法形式上定義為一個三元組AG,AG=(G,V,E)。其中G表示一個上下文無關(guān)文法；V表示屬性的有窮集；E表示屬性的斷言或謂詞的有窮集。2022/11/244第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生二、屬性文法 對于某個壓縮了的上下文無關(guān)文法，當(dāng)為每個文法三、綜合屬性

從語法分析樹的角度來看，如果一個結(jié)點(diǎn)的某一屬性，其值由子結(jié)點(diǎn)的屬性之值來計算，則稱該屬性為綜合屬性。

綜合屬性用于“自下而上”傳遞信息。2022/11/245第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生三、綜合屬性 2022/11/225第五章語法制導(dǎo)翻譯和中例1：算術(shù)表達(dá)式求值的屬性文法。規(guī)則式 語義規(guī)則1.L→E print(E.val)2.E→E1+T E.val:=E1.val+T.val3.E→T E.val:=T.val4.T→T1*F T.val:=T1.val*F.val5.T→F T.val:=F.val6.F→(E) F.val:=E.val7.F→digit F.val:=digit.lexval

與規(guī)則式關(guān)聯(lián)的每一個語義規(guī)則的左部符號E,T,F等的屬性值的計算由右部非終結(jié)符決定，這種屬性稱為綜合屬性。2022/11/246第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生例1：算術(shù)表達(dá)式求值的屬性文法。與規(guī)則式關(guān)聯(lián)的每一個LE.val=19F.val=5+T.val=4T.val=15F.val=4digit.lexval=4E.val=15T.val=3digit.lexval=5F.val=3digit.lexval=3*n求：3*5+42022/11/247第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生LE.val=19F.val=5+T.val=4T.val=四、繼承屬性 語法樹分析中，若一個結(jié)點(diǎn)的某個屬性之值由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和/或父結(jié)點(diǎn)的屬性之值來計算，則此結(jié)點(diǎn)的屬性稱為繼承屬性。 繼承屬性用于“自上而下”傳遞信息。2022/11/248第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生四、繼承屬性2022/11/228第五章語法制導(dǎo)翻譯和中間代例2、說明語句中簡單變量類型信息的屬性文法。 規(guī)則式 語義規(guī)則 1.D→TL L.in:=T.type 2.T→int T.type:=integer 3.T→real T.type:=real 4.L→L1,id L1.in:=L.in addtype(id.entry,L.in) 5.L→id addtype(id.entry,L.in)過程addtype把每一個標(biāo)識符id的類型信息(由L.in繼承)登錄在符號表的相關(guān)項(xiàng)id.entry中。DTLintL,ididT有一個綜合屬性type，其值為integer或real。L.in由T.type確定后逐步傳遞到下邊有關(guān)結(jié)點(diǎn)使用。這種屬性稱為繼承屬性。2022/11/249第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生例2、說明語句中簡單變量類型信息的屬性文法。過程addtyp五、屬性的初始值①終結(jié)符號只有綜合屬性，它們由詞法分析器提供。②非終結(jié)符號既有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。2022/11/2410第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生五、屬性的初始值2022/11/2210第五章語法制導(dǎo)翻譯和§5.2

語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法的基本思想：對文法的每一條產(chǎn)生式，設(shè)計語義子程序。在語法分析的過程中，當(dāng)使用一條產(chǎn)生式推導(dǎo)或歸約時，調(diào)用該語義子程序進(jìn)行屬性計算，完成預(yù)定的翻譯工作。

語法制導(dǎo)翻譯法：在語法分析的過程中，依隨分析過程，根據(jù)每個產(chǎn)生式添加的語義動作進(jìn)行翻譯的方法。2022/11/2411第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生§5.2語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法的基本思想：對文法的每語義子程序語義子程序也稱為翻譯子程序，語義動作。它描述了有關(guān)產(chǎn)生式所對應(yīng)的翻譯工作。語義動作一方面指出了產(chǎn)生式所對應(yīng)的符號串的意義；另一方面又按照這種意義規(guī)定了對應(yīng)的屬性計算加工動作。 語義動作： 查填各種表格 計算某變量的值 生成某種中間代碼 打印錯誤信息等等2022/11/2412第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生語義子程序語義子程序也稱為翻譯子程序，語義動作。它描述了有關(guān)LR分析制導(dǎo)的具體實(shí)現(xiàn)方法1、為文法產(chǎn)生式設(shè)計語義子程序。2、為文法構(gòu)造一張無沖突的LR分析表。3、修改總控程序，歸約時調(diào)用語義子程序。4、擴(kuò)充LR分析棧，用來存放各文法符號對應(yīng)的語義信息。例如：(1).E→E1+E2 {E.val=E1.val+E2.val}(2).E→E1*E2 {E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}2022/11/2413第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生LR分析制導(dǎo)的具體實(shí)現(xiàn)方法1、為文法產(chǎn)生式設(shè)計語義子程序。2#2022/11/2414第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生#2022/11/2214第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生擴(kuò)充的LR分析棧：???S0???#???-狀態(tài)棧文法符號棧語義值棧E.val=7E.val=1+E.val=61E.val=2*E.val=323(1).E→E1+E2

{E.val=E1.val+E2.val}(2).E→E1*E2

{E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}2022/11/2415第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生擴(kuò)充的LR分析棧：???狀態(tài)棧文法符號棧語義值棧E.val=步驟狀態(tài)棧語義棧符號棧輸入符號動作10-#1+2*3#S3203-#1+2*3#r4301-1#E+2*3#S44014-1-#E+2*3#S350143-1-#E+2*3#R460147-1-2#E+E*3#S5701475-1-2#E+E*3#S38014753-1-2-#E+E*3#R49014758-1-2-3#E+E*E#R2100147-1-6#E+E#R11101-7#E#acc2022/11/2416第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生步驟狀態(tài)棧語義棧符號棧輸入符號動作10-#1+2*3#S32§5.3中間語言常用的中間語言有:一、逆波蘭式二、三元式與間接三元式三、樹形表示法四、四元式2022/11/2417第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生§5.3中間語言常用的中間語言有:2022/11/2217一、逆波蘭式1、逆波蘭式（后綴式）：每一運(yùn)算符都置于其運(yùn)算對象之后。（無括號表達(dá)式）

中綴表示 后綴表示

A*B AB* A+B*C ABC*+ (A+B)*(C+D) AB+CD+*

(a==0&&b>3)||(e&&x!=y) a0==b3>&&exy!=&&|| 2022/11/2418第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生一、逆波蘭式1、逆波蘭式（后綴式）：每一運(yùn)算符都置于其運(yùn)算對2、LR分析制導(dǎo)生成逆波蘭式文法：0 E′→E {空}1 E→E(1)+E(2) {print+}2 E→E(1)*E(2) {print*}3 E→(E(1)) {空}4 E→i {printi}步驟狀態(tài)棧符號棧輸入符號輸出區(qū)10#a+b*c#203#a+b*c#301#E+b*c#a4014#E+b*c#a50143#E+b*c#a60147#E+E*c#ab701475#E+E*c#ab8014753#E+E*c#ab9014758#E+E*E#abc100147#E+E#abc*1101#E#abc*+2022/11/2419第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2、LR分析制導(dǎo)生成逆波蘭式文法：步驟狀態(tài)棧符號棧輸入符號輸二、三元式與間接三元式一般形式：（op，AG1，AG2）例如：a:=-b*(c+d)三元式為：①（－，b，

）②（+，c，d）③（*，①，②）④（:=，③，a）2022/11/2420第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生二、三元式與間接三元式一般形式：（op，AG1，AG2）2間接三元式例如：語句 X:=(A+B)*C Y:=D^(A+B)間接代碼⑴⑵⑶⑴⑷⑸opAG1AG2⑴+AB⑵*⑴C⑶:=X⑵⑷^D⑴⑸:=Y⑷2022/11/2421第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生間接三元式例如：語句 X:=(A+B)*C間接代碼⑴⑵⑶⑴⑷三、樹形表示法抽象語法樹：在語法樹中去掉那些對翻譯不必要的信息，從而獲得更有效的源程序中間表示。這種變換后的語法樹稱為抽象語法樹。+* 43 5 3*5+4的抽象語法樹

2022/11/2422第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生三、樹形表示法抽象語法樹：在語法樹中去掉那些對翻譯不必要的信樹形表示

A*B+C*D+C*A*BD末端結(jié)點(diǎn)表示一個運(yùn)算對象,每一個內(nèi)結(jié)點(diǎn)表示一個一元或二元運(yùn)算符。樹形表示是三元式的翻版(3)+(1)*(2)*CABD2022/11/2423第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生樹形表示A*B+C*D+C*A*B四、四元式

一般形式：(op，AG1，AG2，result)

直觀形式：result:=AG1opAG2例如：求x:=a+b*c的四元式。(*，b，c，T1) 直觀式： T1:=b*c(+，a，T1，T2) T2:=a+T1(:=，T2，，x) x:=T22022/11/2424第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生四、四元式 一般形式：(op，AG1，AG2，result

采用自下而上的語法制導(dǎo)翻譯法語義動作的設(shè)計（1）搞清楚源結(jié)構(gòu)和目標(biāo)結(jié)構(gòu)（2）自下而上的語法制導(dǎo)翻譯特點(diǎn)：棧頂形成句柄，歸約時執(zhí)行相應(yīng)語義動作（3）給出從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法§5.8自底向上語法制導(dǎo)翻譯2022/11/2425第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生采用自下而上的語法制導(dǎo)翻譯法語義動例.設(shè)文法及其相應(yīng)的語義動作如下:S→a{print“2”}S→bTc{print“1”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}采用自下而上語法制導(dǎo)翻譯,給出輸入串bR/bTc/bSc/ac的翻譯結(jié)果2022/11/2426第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生例.設(shè)文法及其相應(yīng)的語義動作如下:S→a分析:首先對輸入串bR/bTc/bSc/ac畫出語法樹:ScTbRS/R/RS/RcTbaScTbRS再考慮歸約時執(zhí)行相應(yīng)語義動作2022/11/2427第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生分析:首先對輸入串ScTbRS/R/RS/RcTbaSScTbRS/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é)果為:531424312022/11/2428第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生ScTbRS/R/RS/RcTbaScTbRSS→b一、簡單算術(shù)表達(dá)式和賦值語句的翻譯定義幾個過程和函數(shù)：lookup()：檢查是否出現(xiàn)在符號表中，如果在，則返回其指針；否則，返回NULL表示沒有找到。emit（result:=AG1opAG2）：產(chǎn)生一個四元式，并填入四元式表中。newtemp()：該函數(shù)返回一個新的臨時變量。2022/11/2429第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生一、簡單算術(shù)表達(dá)式和賦值語句的翻譯定義幾個過程和函數(shù)：202文法：P2161.S→i=E{p＝Lookup();if(p==NULL)error();elseemit(p’＝’E.place}2.E→E(1)＋E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}3.E→E(1)*E(2){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();}2022/11/2430第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生文法：P2162022/11/2230第五章語法制導(dǎo)翻譯和中 算術(shù)表達(dá)式a+b*c翻譯到三地址語句的過程：

030$$a01$E014$E+0143$E+b－a－a－－a－－狀態(tài)棧符號棧語義棧輸入串a(chǎn)+b*c$+b*c$+b*c$b*c$*c$－－－2022/11/2431第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生 算術(shù)表達(dá)式a+b*c翻譯到三地址語句的過程：030$$a*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－t2acc2022/11/2432第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生*c$c$$$$$t1=b*c二、布爾表達(dá)式的翻譯 1、E→E∨E 2、E→E∧E 3、E→E 4、E→(E) 5、E→idropid 6、E→id2022/11/2433第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生二、布爾表達(dá)式的翻譯 1、E→E∨E 2022/111、類似算術(shù)表達(dá)式的翻譯方法 （求每個因子，再求表達(dá)式的值）例如： 布爾表達(dá)式： a∨b∧c

三地址序列： T1:=c T2:=b∧T1 T3:=a∨T22022/11/2434第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生1、類似算術(shù)表達(dá)式的翻譯方法 （求每個因子，再求表達(dá)式的值）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＝newtemp()；emit(E.place’＝’’’

E(1).place}4.E→(E(1)){E.place＝E(1).place；}5.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’);}6.E→i

{E.place＝i.place；}2022/11/2435第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生1.E→E(1)∨E(2)2022/11/223EE∨Ea<bE∧Ec<de<f2022/11/2436第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生E2022/11/2236第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2、根據(jù)布爾表達(dá)式的特殊性采取某種優(yōu)化措施A∨B ifAthentrunelseBA∧B ifAthenBelsefalseA ifAthenfalseelsetrue①對非終結(jié)符E賦予兩個出口真出口：布爾表達(dá)式為真時，需轉(zhuǎn)移的四元式地址。假出口：布爾表達(dá)式為假時，需轉(zhuǎn)移的四元式地址。2022/11/2437第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2、根據(jù)布爾表達(dá)式的特殊性采取某種優(yōu)化措施A∨B if②設(shè)置兩個語義變量：E.ture:用來記錄表達(dá)式E對應(yīng)的四元式需回填真出口的四元式的地址所構(gòu)成的鏈。E.false:用來記錄表達(dá)式E對應(yīng)的四元式需回填假出口的四元式的地址所構(gòu)成的鏈。③定義三個函數(shù)：2022/11/2438第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生②設(shè)置兩個語義變量：2022/11/2238第五章語法制導(dǎo)翻鏈接函數(shù)merge(P1,P2)：把以P1和P2為鏈?zhǔn)椎膬蓷l鏈合并為一，返回合并后的鏈?zhǔn)祝ó?dāng)P2=0時，返回P1;當(dāng)P2≠0時，返回P2）。

intmerge(intP1,intP2){ intP; if(!P2)returnP1; else{ P=P2; while(P.result<>0) P=P.result; P.result=P1; returnP2;}2022/11/2439第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生鏈接函數(shù)merge(P1,P2)：把以P1和P2為鏈?zhǔn)椎幕靥詈瘮?shù)backpatch(p,t)：把p所鏈接的每個四元式的第四分量都回填為t。 voidBP(intp,intt){ intq=p; while(q){ intq1=q.result; q.result=t; q=q1; } return; }建鏈函數(shù)makelist(i)：創(chuàng)建一個僅含i的新鏈表。2022/11/2440第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生回填函數(shù)backpatch(p,t)：把p所鏈接的每④定義三種四元式：(jnz,a,-,p) ifagotop(當(dāng)a為真時轉(zhuǎn)向第p四元式）(jrop,x,y,p) ifxropygotop(j,-,-,p) gotop(無條件轉(zhuǎn)向第p四元式)⑤四元式表的指針nextquad（nextq）：每執(zhí)行一次emit后，nextq自動加1。⑥E.code：為及時回填轉(zhuǎn)移地址,使用語義變量E.code記錄表達(dá)式E的第一個四元式語句序號。2022/11/2441第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生④定義三種四元式：2022/11/2241第五章語法制導(dǎo)翻譯1.E→i {E.tr=next; E.fa=next+1; E.code=next;emit(ifi.placegoto-);emit(goto_);}2.E→i(1)ropi(2){E.tr=next; E.code=next; E.fa=next+1;emit(ifi(1).placerop.opi(2).placegoto_); emit(goto_);

}3.E→(E(1)){E.code=E(1).code; E.tr=E(1).tr; E.fa=E(1).fa; }4.E→E(1)

{E.tr=E(1).fa; E.fa=E(1).tr; }5.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;}6.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); }2022/11/2442第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生1.E→i 2022/11/2242第五章語法制導(dǎo)翻譯例如布爾表達(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;}2022/11/2443第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生例如布爾表達(dá)式a<b∨c<d的翻譯過程如下:E

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<dgoto100103goto0E(1)∨E(2)

歸約為E2022/11/2444第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生E{bp(E(1).fa,E(2).code)=102ifc<dgoto100103goto0100ifa<bgoto0101goto102布爾表達(dá)式

a<b∨c<d

E.tr=102E.fa=1032022/11/2445第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生102ifc<dgoto100103g三、控制語句的翻譯S→ifEthenMSNelseMSN→εM→εS→ifEthenMSS→whileMEdoMSS→beginLendS→AL→L;MSL→S2022/11/2446第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生三、控制語句的翻譯S→ifEthenMSNel2022/11/2447第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2022/11/2247第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2022/11/2448第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2022/11/2248第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生1042022/11/2449第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生1042022/11/2249第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2022/11/2450第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2022/11/221第五章語義分析的任務(wù)：根據(jù)語法成分的結(jié)構(gòu)，分析其含義，并用一種內(nèi)部形式（中間代碼）或直接用目標(biāo)語言表示出來。具體：靜態(tài)語義檢查和翻譯包括：類型檢查（操作符是否相容，例如%） 控制流檢查（break是否有switch和for,while） 一致性檢查（inta;floata;） 相關(guān)名字檢查、等等2022/11/2451第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生語義分析的任務(wù)：根據(jù)語法成分的結(jié)構(gòu)，分析其含義，并用一種內(nèi)部§5.1屬性文法

一、屬性一、屬性：一般用來描述客觀存在的事物或人的特性。例如，學(xué)生的姓名、年齡、性別等；商品的顏色、重量、單價等。編譯技術(shù)中用屬性來描述計算機(jī)處理對象的特征。例如：X.Type,X.Place,X.val等分別描述X的類型，存儲位置、值等不同的特征。 屬性分兩類： 綜合屬性：一般用于“自下而上”傳遞信息。 繼承屬性：一般用于“自上而下”傳遞信息。2022/11/2452第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生§5.1屬性文法

一、屬性一、屬性：一般用來描述客觀二、屬性文法

對于某個壓縮了的上下文無關(guān)文法，當(dāng)為每個文法符號引進(jìn)一組屬性，且讓該文法中的重寫規(guī)則附加以語義規(guī)則時，稱該上下文無關(guān)文法為屬性文法。

形式定義：一個屬性文法形式上定義為一個三元組AG,AG=(G,V,E)。其中G表示一個上下文無關(guān)文法；V表示屬性的有窮集；E表示屬性的斷言或謂詞的有窮集。2022/11/2453第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生二、屬性文法 對于某個壓縮了的上下文無關(guān)文法，當(dāng)為每個文法三、綜合屬性

從語法分析樹的角度來看，如果一個結(jié)點(diǎn)的某一屬性，其值由子結(jié)點(diǎn)的屬性之值來計算，則稱該屬性為綜合屬性。

綜合屬性用于“自下而上”傳遞信息。2022/11/2454第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生三、綜合屬性 2022/11/225第五章語法制導(dǎo)翻譯和中例1：算術(shù)表達(dá)式求值的屬性文法。規(guī)則式 語義規(guī)則1.L→E print(E.val)2.E→E1+T E.val:=E1.val+T.val3.E→T E.val:=T.val4.T→T1*F T.val:=T1.val*F.val5.T→F T.val:=F.val6.F→(E) F.val:=E.val7.F→digit F.val:=digit.lexval

與規(guī)則式關(guān)聯(lián)的每一個語義規(guī)則的左部符號E,T,F等的屬性值的計算由右部非終結(jié)符決定，這種屬性稱為綜合屬性。2022/11/2455第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生例1：算術(shù)表達(dá)式求值的屬性文法。與規(guī)則式關(guān)聯(lián)的每一個LE.val=19F.val=5+T.val=4T.val=15F.val=4digit.lexval=4E.val=15T.val=3digit.lexval=5F.val=3digit.lexval=3*n求：3*5+42022/11/2456第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生LE.val=19F.val=5+T.val=4T.val=四、繼承屬性 語法樹分析中，若一個結(jié)點(diǎn)的某個屬性之值由該結(jié)點(diǎn)的兄弟結(jié)點(diǎn)和/或父結(jié)點(diǎn)的屬性之值來計算，則此結(jié)點(diǎn)的屬性稱為繼承屬性。 繼承屬性用于“自上而下”傳遞信息。2022/11/2457第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生四、繼承屬性2022/11/228第五章語法制導(dǎo)翻譯和中間代例2、說明語句中簡單變量類型信息的屬性文法。 規(guī)則式 語義規(guī)則 1.D→TL L.in:=T.type 2.T→int T.type:=integer 3.T→real T.type:=real 4.L→L1,id L1.in:=L.in addtype(id.entry,L.in) 5.L→id addtype(id.entry,L.in)過程addtype把每一個標(biāo)識符id的類型信息(由L.in繼承)登錄在符號表的相關(guān)項(xiàng)id.entry中。DTLintL,ididT有一個綜合屬性type，其值為integer或real。L.in由T.type確定后逐步傳遞到下邊有關(guān)結(jié)點(diǎn)使用。這種屬性稱為繼承屬性。2022/11/2458第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生例2、說明語句中簡單變量類型信息的屬性文法。過程addtyp五、屬性的初始值①終結(jié)符號只有綜合屬性，它們由詞法分析器提供。②非終結(jié)符號既有綜合屬性也可有繼承屬性，文法開始符號的所有繼承屬性作為屬性計算前的初始值。2022/11/2459第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生五、屬性的初始值2022/11/2210第五章語法制導(dǎo)翻譯和§5.2

語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法的基本思想：對文法的每一條產(chǎn)生式，設(shè)計語義子程序。在語法分析的過程中，當(dāng)使用一條產(chǎn)生式推導(dǎo)或歸約時，調(diào)用該語義子程序進(jìn)行屬性計算，完成預(yù)定的翻譯工作。

語法制導(dǎo)翻譯法：在語法分析的過程中，依隨分析過程，根據(jù)每個產(chǎn)生式添加的語義動作進(jìn)行翻譯的方法。2022/11/2460第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生§5.2語法制導(dǎo)翻譯法語法制導(dǎo)翻譯法的基本思想：對文法的每語義子程序語義子程序也稱為翻譯子程序，語義動作。它描述了有關(guān)產(chǎn)生式所對應(yīng)的翻譯工作。語義動作一方面指出了產(chǎn)生式所對應(yīng)的符號串的意義；另一方面又按照這種意義規(guī)定了對應(yīng)的屬性計算加工動作。 語義動作： 查填各種表格 計算某變量的值 生成某種中間代碼 打印錯誤信息等等2022/11/2461第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生語義子程序語義子程序也稱為翻譯子程序，語義動作。它描述了有關(guān)LR分析制導(dǎo)的具體實(shí)現(xiàn)方法1、為文法產(chǎn)生式設(shè)計語義子程序。2、為文法構(gòu)造一張無沖突的LR分析表。3、修改總控程序，歸約時調(diào)用語義子程序。4、擴(kuò)充LR分析棧，用來存放各文法符號對應(yīng)的語義信息。例如：(1).E→E1+E2 {E.val=E1.val+E2.val}(2).E→E1*E2 {E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}2022/11/2462第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生LR分析制導(dǎo)的具體實(shí)現(xiàn)方法1、為文法產(chǎn)生式設(shè)計語義子程序。2#2022/11/2463第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生#2022/11/2214第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生擴(kuò)充的LR分析棧：???S0???#???-狀態(tài)棧文法符號棧語義值棧E.val=7E.val=1+E.val=61E.val=2*E.val=323(1).E→E1+E2

{E.val=E1.val+E2.val}(2).E→E1*E2

{E.val=E1.val*E2.val}(3).E→(E1) {E.val=E1.val}(4).E→digit {E.val=lex.digit}2022/11/2464第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生擴(kuò)充的LR分析棧：???狀態(tài)棧文法符號棧語義值棧E.val=步驟狀態(tài)棧語義棧符號棧輸入符號動作10-#1+2*3#S3203-#1+2*3#r4301-1#E+2*3#S44014-1-#E+2*3#S350143-1-#E+2*3#R460147-1-2#E+E*3#S5701475-1-2#E+E*3#S38014753-1-2-#E+E*3#R49014758-1-2-3#E+E*E#R2100147-1-6#E+E#R11101-7#E#acc2022/11/2465第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生步驟狀態(tài)棧語義棧符號棧輸入符號動作10-#1+2*3#S32§5.3中間語言常用的中間語言有:一、逆波蘭式二、三元式與間接三元式三、樹形表示法四、四元式2022/11/2466第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生§5.3中間語言常用的中間語言有:2022/11/2217一、逆波蘭式1、逆波蘭式（后綴式）：每一運(yùn)算符都置于其運(yùn)算對象之后。（無括號表達(dá)式）

中綴表示 后綴表示

A*B AB* A+B*C ABC*+ (A+B)*(C+D) AB+CD+*

(a==0&&b>3)||(e&&x!=y) a0==b3>&&exy!=&&|| 2022/11/2467第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生一、逆波蘭式1、逆波蘭式（后綴式）：每一運(yùn)算符都置于其運(yùn)算對2、LR分析制導(dǎo)生成逆波蘭式文法：0 E′→E {空}1 E→E(1)+E(2) {print+}2 E→E(1)*E(2) {print*}3 E→(E(1)) {空}4 E→i {printi}步驟狀態(tài)棧符號棧輸入符號輸出區(qū)10#a+b*c#203#a+b*c#301#E+b*c#a4014#E+b*c#a50143#E+b*c#a60147#E+E*c#ab701475#E+E*c#ab8014753#E+E*c#ab9014758#E+E*E#abc100147#E+E#abc*1101#E#abc*+2022/11/2468第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2、LR分析制導(dǎo)生成逆波蘭式文法：步驟狀態(tài)棧符號棧輸入符號輸二、三元式與間接三元式一般形式：（op，AG1，AG2）例如：a:=-b*(c+d)三元式為：①（－，b，

）②（+，c，d）③（*，①，②）④（:=，③，a）2022/11/2469第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生二、三元式與間接三元式一般形式：（op，AG1，AG2）2間接三元式例如：語句 X:=(A+B)*C Y:=D^(A+B)間接代碼⑴⑵⑶⑴⑷⑸opAG1AG2⑴+AB⑵*⑴C⑶:=X⑵⑷^D⑴⑸:=Y⑷2022/11/2470第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生間接三元式例如：語句 X:=(A+B)*C間接代碼⑴⑵⑶⑴⑷三、樹形表示法抽象語法樹：在語法樹中去掉那些對翻譯不必要的信息，從而獲得更有效的源程序中間表示。這種變換后的語法樹稱為抽象語法樹。+* 43 5 3*5+4的抽象語法樹

2022/11/2471第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生三、樹形表示法抽象語法樹：在語法樹中去掉那些對翻譯不必要的信樹形表示

A*B+C*D+C*A*BD末端結(jié)點(diǎn)表示一個運(yùn)算對象,每一個內(nèi)結(jié)點(diǎn)表示一個一元或二元運(yùn)算符。樹形表示是三元式的翻版(3)+(1)*(2)*CABD2022/11/2472第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生樹形表示A*B+C*D+C*A*B四、四元式

一般形式：(op，AG1，AG2，result)

直觀形式：result:=AG1opAG2例如：求x:=a+b*c的四元式。(*，b，c，T1) 直觀式： T1:=b*c(+，a，T1，T2) T2:=a+T1(:=，T2，，x) x:=T22022/11/2473第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生四、四元式 一般形式：(op，AG1，AG2，result

采用自下而上的語法制導(dǎo)翻譯法語義動作的設(shè)計（1）搞清楚源結(jié)構(gòu)和目標(biāo)結(jié)構(gòu)（2）自下而上的語法制導(dǎo)翻譯特點(diǎn)：棧頂形成句柄，歸約時執(zhí)行相應(yīng)語義動作（3）給出從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法§5.8自底向上語法制導(dǎo)翻譯2022/11/2474第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生采用自下而上的語法制導(dǎo)翻譯法語義動例.設(shè)文法及其相應(yīng)的語義動作如下:S→a{print“2”}S→bTc{print“1”}T→R{print“3”}R→R/S{print“4”}R→S{print“5”}采用自下而上語法制導(dǎo)翻譯,給出輸入串bR/bTc/bSc/ac的翻譯結(jié)果2022/11/2475第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生例.設(shè)文法及其相應(yīng)的語義動作如下:S→a分析:首先對輸入串bR/bTc/bSc/ac畫出語法樹:ScTbRS/R/RS/RcTbaScTbRS再考慮歸約時執(zhí)行相應(yīng)語義動作2022/11/2476第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生分析:首先對輸入串ScTbRS/R/RS/RcTbaSScTbRS/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é)果為:531424312022/11/2477第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生ScTbRS/R/RS/RcTbaScTbRSS→b一、簡單算術(shù)表達(dá)式和賦值語句的翻譯定義幾個過程和函數(shù)：lookup()：檢查是否出現(xiàn)在符號表中，如果在，則返回其指針；否則，返回NULL表示沒有找到。emit（result:=AG1opAG2）：產(chǎn)生一個四元式，并填入四元式表中。newtemp()：該函數(shù)返回一個新的臨時變量。2022/11/2478第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生一、簡單算術(shù)表達(dá)式和賦值語句的翻譯定義幾個過程和函數(shù)：202文法：P2161.S→i=E{p＝Lookup();if(p==NULL)error();elseemit(p’＝’E.place}2.E→E(1)＋E(2){E.place＝newtemp();emit(E.place’＝’E(1).place’＋’E(2).place)}3.E→E(1)*E(2){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();}2022/11/2479第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生文法：P2162022/11/2230第五章語法制導(dǎo)翻譯和中 算術(shù)表達(dá)式a+b*c翻譯到三地址語句的過程：

030$$a01$E014$E+0143$E+b－a－a－－a－－狀態(tài)棧符號棧語義棧輸入串a(chǎn)+b*c$+b*c$+b*c$b*c$*c$－－－2022/11/2480第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生 算術(shù)表達(dá)式a+b*c翻譯到三地址語句的過程：030$$a*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－t2acc2022/11/2481第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生*c$c$$$$$t1=b*c二、布爾表達(dá)式的翻譯 1、E→E∨E 2、E→E∧E 3、E→E 4、E→(E) 5、E→idropid 6、E→id2022/11/2482第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生二、布爾表達(dá)式的翻譯 1、E→E∨E 2022/111、類似算術(shù)表達(dá)式的翻譯方法 （求每個因子，再求表達(dá)式的值）例如： 布爾表達(dá)式： a∨b∧c

三地址序列： T1:=c T2:=b∧T1 T3:=a∨T22022/11/2483第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生1、類似算術(shù)表達(dá)式的翻譯方法 （求每個因子，再求表達(dá)式的值）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＝newtemp()；emit(E.place’＝’’’

E(1).place}4.E→(E(1)){E.place＝E(1).place；}5.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’);}6.E→i

{E.place＝i.place；}2022/11/2484第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生1.E→E(1)∨E(2)2022/11/223EE∨Ea<bE∧Ec<de<f2022/11/2485第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生E2022/11/2236第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2、根據(jù)布爾表達(dá)式的特殊性采取某種優(yōu)化措施A∨B ifAthentrunelseBA∧B ifAthenBelsefalseA ifAthenfalseelsetrue①對非終結(jié)符E賦予兩個出口真出口：布爾表達(dá)式為真時，需轉(zhuǎn)移的四元式地址。假出口：布爾表達(dá)式為假時，需轉(zhuǎn)移的四元式地址。2022/11/2486第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生2、根據(jù)布爾表達(dá)式的特殊性采取某種優(yōu)化措施A∨B if②設(shè)置兩個語義變量：E.ture:用來記錄表達(dá)式E對應(yīng)的四元式需回填真出口的四元式的地址所構(gòu)成的鏈。E.false:用來記錄表達(dá)式E對應(yīng)的四元式需回填假出口的四元式的地址所構(gòu)成的鏈。③定義三個函數(shù)：2022/11/2487第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生②設(shè)置兩個語義變量：2022/11/2238第五章語法制導(dǎo)翻鏈接函數(shù)merge(P1,P2)：把以P1和P2為鏈?zhǔn)椎膬蓷l鏈合并為一，返回合并后的鏈?zhǔn)祝ó?dāng)P2=0時，返回P1;當(dāng)P2≠0時，返回P2）。

intmerge(intP1,intP2){ intP; if(!P2)returnP1; else{ P=P2; while(P.result<>0) P=P.result; P.result=P1; returnP2;}2022/11/2488第五章語法制導(dǎo)翻譯和中間代碼產(chǎn)生鏈接函數(shù)merge(P1,P2)：把以P1和P2為鏈?zhǔn)椎幕靥詈瘮?shù)backpatch(p,t)：把p所鏈接的每個四元式的第四分量都回填為t。 voidBP(intp,intt){ intq=p; while(q){