第5章語法制導(dǎo)翻譯技術(shù)和中間代碼生成

1、2022-2-2512022-2-251編編 譯譯 原原 理理2022年2月25日S.PO.P語義分析、生成中間代碼語義分析、生成中間代碼生成目標(biāo)程序生成目標(biāo)程序代碼優(yōu)化代碼優(yōu)化語法分析程序語法分析程序詞法分析程序詞法分析程序錯錯誤誤處處理理符符號號表表管管理理2022-2-2522022-2-252編編 譯譯 原原 理理2022年2月25日第第5 5章章語法制導(dǎo)翻譯技術(shù)和中間代碼生成語法制導(dǎo)翻譯技術(shù)和中間代碼生成 要求明確語義分析的要求明確語義分析的任務(wù)任務(wù) 明確明確屬性文法屬性文法和和語法制導(dǎo)翻譯語法制導(dǎo)翻譯的含義的含義 明確明確自底向上和自頂向下自底向上和自頂向下語法制導(dǎo)翻譯的語法制導(dǎo)翻

2、譯的區(qū)別和特點區(qū)別和特點 明確明確生成中間代碼的目的，中間代碼的幾生成中間代碼的目的，中間代碼的幾種形式種形式教學(xué)目標(biāo)教學(xué)目標(biāo)2022-2-2532022-2-253編編 譯譯 原原 理理2022年2月25日 屬性文法屬性文法 語法制導(dǎo)翻譯法的基本思想語法制導(dǎo)翻譯法的基本思想 常見的中間代碼常見的中間代碼 各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)教學(xué)內(nèi)容教學(xué)內(nèi)容2022-2-2542022-2-254編編 譯譯 原原 理理2022年2月25日詞法分析，語法分析詞法分析，語法分析：解決單詞和語言成分的識別：解決單詞和語言成分的識別及詞法和語法結(jié)構(gòu)的檢查。語法結(jié)構(gòu)可形式

3、化地用及詞法和語法結(jié)構(gòu)的檢查。語法結(jié)構(gòu)可形式化地用一組產(chǎn)生式來描述。給定一組產(chǎn)生式，我們能夠很一組產(chǎn)生式來描述。給定一組產(chǎn)生式，我們能夠很容易地將其分析器構(gòu)造出來。容易地將其分析器構(gòu)造出來。本章要介紹的是本章要介紹的是語義分析和中間代碼生成技術(shù)語義分析和中間代碼生成技術(shù)。程序語言中間代碼目標(biāo)代碼程序語言中間代碼目標(biāo)代碼翻譯翻譯翻譯翻譯2022-2-2552022-2-255編編 譯譯 原原 理理2022年2月25日根據(jù)語義規(guī)則對識別出的各種語法成分析其含義，根據(jù)語義規(guī)則對識別出的各種語法成分析其含義，進(jìn)行初步翻譯，生成相應(yīng)的中間代碼或直接生成目進(jìn)行初步翻譯，生成相應(yīng)的中間代碼或直接生成目標(biāo)代碼

4、。標(biāo)代碼。第一，審查每個語法結(jié)構(gòu)的靜態(tài)語義，即檢查語法結(jié)構(gòu)合法第一，審查每個語法結(jié)構(gòu)的靜態(tài)語義，即檢查語法結(jié)構(gòu)合法的程序是否真正有意義。也稱靜態(tài)語義檢查。的程序是否真正有意義。也稱靜態(tài)語義檢查。（類型檢查、（類型檢查、控制流的檢查、一致性檢查、相關(guān)名字的檢查）控制流的檢查、一致性檢查、相關(guān)名字的檢查）第二，如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，第二，如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，要么生成中間代碼，要么生成實際的目標(biāo)代碼。（要么生成中間代碼，要么生成實際的目標(biāo)代碼。（說明性語說明性語句：填符號表；可執(zhí)行性語句：生成中間代碼）句：填符號表；可執(zhí)行性語句：生成中間代碼） 語義

5、分析的任務(wù)語義分析的任務(wù)2022-2-2562022-2-256編編 譯譯 原原 理理2022年2月25日類型檢查類型檢查。控制流檢查控制流檢查，確?？刂普Z句有合法的轉(zhuǎn)向點。例，確保控制語句有合法的轉(zhuǎn)向點。例如，如，C語言中的語言中的break語句使控制跳離包括該語句的語句使控制跳離包括該語句的最小的最小的switch，while或或for語句。如果不存在包括它語句。如果不存在包括它的這樣的語句，則應(yīng)報錯。的這樣的語句，則應(yīng)報錯。靜態(tài)語義檢查靜態(tài)語義檢查2022-2-2572022-2-257編編 譯譯 原原 理理2022年2月25日靜態(tài)語義檢查靜態(tài)語義檢查一致性檢查一致性檢查。很多情況下要求

6、對象只能被定義一。很多情況下要求對象只能被定義一次。例如，語言中規(guī)定一個標(biāo)識符在同一作用域中次。例如，語言中規(guī)定一個標(biāo)識符在同一作用域中只能被說明一次，同一只能被說明一次，同一case語句的標(biāo)號不能相同，枚語句的標(biāo)號不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等。舉類型的元素不能重復(fù)出現(xiàn)等。相關(guān)名字檢查相關(guān)名字檢查。有的語言中有時規(guī)定，同一名字。有的語言中有時規(guī)定，同一名字必須出現(xiàn)兩次或多次。例如，必須出現(xiàn)兩次或多次。例如，Ada語言中，循環(huán)或程語言中，循環(huán)或程序塊可以有一個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)序塊可以有一個名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，如同語句括號一般，編譯程序必須檢查它們的配尾，

7、如同語句括號一般，編譯程序必須檢查它們的配對情況。對情況。2022-2-2582022-2-258編編 譯譯 原原 理理2022年2月25日附加了一組附加了一組屬性屬性和和運算（語義）規(guī)則運算（語義）規(guī)則的的文法文法 5.2 屬性文法屬性文法文法符號文法符號X的屬性的屬性t常用常用X.t來表示來表示 語義規(guī)則是根據(jù)產(chǎn)生式所語義規(guī)則是根據(jù)產(chǎn)生式所蘊(yùn)涵的語義蘊(yùn)涵的語義操作建立起來的，操作建立起來的，并與并與語義分析的目標(biāo)語義分析的目標(biāo)有關(guān)有關(guān)不同的不同的產(chǎn)生式產(chǎn)生式對應(yīng)不同的語義規(guī)則對應(yīng)不同的語義規(guī)則不同的不同的分析目標(biāo)分析目標(biāo)也對應(yīng)不同的語義規(guī)則也對應(yīng)不同的語義規(guī)則 1. 屬性的表示屬性的表示2

8、.語義規(guī)則語義規(guī)則的表示的表示語義信息語義信息語義之間的關(guān)系語義之間的關(guān)系靜態(tài)語義檢查、符號靜態(tài)語義檢查、符號表操作、代碼生成及表操作、代碼生成及打印各種錯誤信息打印各種錯誤信息 2022-2-2592022-2-259編編 譯譯 原原 理理2022年2月25日屬性文法屬性文法 屬性文法的形式定義： AG： AG=（G，V，E） G:上下文無關(guān)文法; V:屬性的有窮集合;每一個屬性與某一個文法符號相關(guān)聯(lián)；用文法符號屬性表示 E:表示屬性的斷言或謂詞的有窮集合(語義規(guī)則);每一個斷言與文法的某個產(chǎn)生式相關(guān)聯(lián)) 屬性:綜合屬性(自下而上傳遞信息)、繼承屬性（自上而下傳遞信息)2022-2-2510

9、2022-2-2510編編 譯譯 原原 理理2022年2月25日 非終結(jié)符非終結(jié)符E E、T T及及F F都有一個綜合屬性都有一個綜合屬性val,val,符號符號i i有一個綜合屬性。有一個綜合屬性。 某些非終結(jié)符加下標(biāo)是為了區(qū)分一個產(chǎn)生式某些非終結(jié)符加下標(biāo)是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)中同一非終結(jié)符多次出現(xiàn)語語 義義 規(guī)規(guī) 則則E E1+TE T T T1 * FT FF (E)F i E.val=E1.val+T.valE.val=T.val T.val=T1.val F.valT.val=F.valF.val=E.val F.val=i.lexval產(chǎn)生式產(chǎn)生式例例5.15.

10、12022-2-25112022-2-2511編編 譯譯 原原 理理2022年2月25日語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯：語法制導(dǎo)翻譯：將將語義規(guī)則語義規(guī)則與與語法規(guī)則語法規(guī)則相結(jié)合，在相結(jié)合，在語法分析語法分析的過程中通過執(zhí)行的過程中通過執(zhí)行語義動作語義動作，計算語義屬，計算語義屬性值，從而完成預(yù)定的翻譯工作。性值，從而完成預(yù)定的翻譯工作。 2022-2-25122022-2-2512編編 譯譯 原原 理理2022年2月25日自底向上語自底向上語法制導(dǎo)翻譯法制導(dǎo)翻譯自頂向下語自頂向下語法制導(dǎo)翻譯法制導(dǎo)翻譯語法制導(dǎo)翻譯的實現(xiàn)語法制導(dǎo)翻譯的實現(xiàn)2022-2-25132022-2-

11、2513編編 譯譯 原原 理理2022年2月25日語法制導(dǎo)翻譯分為兩種語法制導(dǎo)翻譯分為兩種處理方法處理方法：（1）語法制導(dǎo)定義（自底向上）：）語法制導(dǎo)定義（自底向上）：對每個產(chǎn)生式編制一個語義子程序，在進(jìn)行語法分析的過對每個產(chǎn)生式編制一個語義子程序，在進(jìn)行語法分析的過程中，程中，當(dāng)一個產(chǎn)生式獲得匹配時當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯。這種實現(xiàn)方案隱藏了其中語義規(guī)序?qū)崿F(xiàn)語義檢查與翻譯。這種實現(xiàn)方案隱藏了其中語義規(guī)則的計算次序等實現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。則的計算次序等實現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。（2）翻譯方案（自頂向下）：）翻譯方案（自頂向下

12、）：在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進(jìn)程，執(zhí)行遇到的語義動作。這是一種析的進(jìn)程，執(zhí)行遇到的語義動作。這是一種動作與分析交動作與分析交錯錯的實現(xiàn)方案。的實現(xiàn)方案。2022-2-25142022-2-2514編編 譯譯 原原 理理2022年2月25日輸入符號串輸入符號串 分析樹分析樹執(zhí)行執(zhí)行語義規(guī)則語義規(guī)則 翻譯結(jié)果翻譯結(jié)果翻譯步驟翻譯步驟（）從分析樹得到描述結(jié)點屬性間依賴關(guān)系的（）從分析樹得到描述結(jié)點屬性間依賴關(guān)系的依賴圖依賴圖，由，由依賴圖得到語義規(guī)則的依賴圖得到語義規(guī)則的計算次序計算次序 （1）分析輸入符號串，建立）分析

13、輸入符號串，建立分析語法樹分析語法樹（）進(jìn)行語義規(guī)則的計算，得到翻譯結(jié)果（）進(jìn)行語義規(guī)則的計算，得到翻譯結(jié)果 2022-2-25152022-2-2515編編 譯譯 原原 理理2022年2月25日語法制導(dǎo)定義語法制導(dǎo)定義對每個產(chǎn)生式編制一個對每個產(chǎn)生式編制一個語義子程序語義子程序在進(jìn)行語法分析的過程中，在進(jìn)行語法分析的過程中，當(dāng)一個產(chǎn)生式獲得匹配時當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯綜合屬性綜合屬性繼承屬性繼承屬性自底向上自底向上傳遞信息傳遞信息自頂向下（自左自頂向下（自左向右）向右）傳遞信息傳遞信息2022-2-25162

14、022-2-2516編編 譯譯 原原 理理2022年2月25日 print(E.val)print(E.val)打印由打印由E E產(chǎn)生的算術(shù)表達(dá)式的值，產(chǎn)生的算術(shù)表達(dá)式的值，可認(rèn)為這條規(guī)則定義了可認(rèn)為這條規(guī)則定義了L L的一個的一個虛屬性虛屬性。 L EE E1+TE T T T1 * FT FF (E)F iprint(E.val) E.val=E1.val+T.valE.val=T.val T.val=T1.val F.val T.val=F.valF.val=E.valF.val=i.lexval例例5.5.綜合屬性綜合屬性語語 義義 規(guī)規(guī) 則則產(chǎn)生式產(chǎn)生式2022-2-25172022

15、-2-2517編編 譯譯 原原 理理2022年2月25日 一個結(jié)點的綜合屬性一個結(jié)點的綜合屬性值是其值是其子結(jié)點子結(jié)點的某些的某些屬性來決定的屬性來決定的+3+3* *4 4的注釋分析樹的注釋分析樹通常使用通常使用自底向上自底向上的分析方法的分析方法在在每個結(jié)點每個結(jié)點處使用語義規(guī)則處使用語義規(guī)則來計算綜合屬性值來計算綜合屬性值當(dāng)一個當(dāng)一個產(chǎn)生式獲得匹配產(chǎn)生式獲得匹配時，時，就調(diào)用相應(yīng)的語義子程序就調(diào)用相應(yīng)的語義子程序從從葉結(jié)點到根結(jié)點葉結(jié)點到根結(jié)點進(jìn)行計算進(jìn)行計算 只含有只含有綜合屬性綜合屬性的語法制的語法制導(dǎo)定義稱為導(dǎo)定義稱為S S屬性定義屬性定義2022-2-25182022-2-251

16、8編編 譯譯 原原 理理2022年2月25日S屬性定義與自底向上翻譯屬性定義與自底向上翻譯 LRLR分析器可以改造為一個翻譯器，在對輸入串分析器可以改造為一個翻譯器，在對輸入串進(jìn)行語法分析的同時對屬性進(jìn)行計算進(jìn)行語法分析的同時對屬性進(jìn)行計算 LRLR分析器增加分析器增加屬性值（語義）棧屬性值（語義）棧 首先，為文法的每條規(guī)則設(shè)計相應(yīng)的語義子程序；首先，為文法的每條規(guī)則設(shè)計相應(yīng)的語義子程序；增加一個語義信息棧；增加一個語義信息棧；在語法分析的同時做語義處理：即在用某一個產(chǎn)生在語法分析的同時做語義處理：即在用某一個產(chǎn)生式進(jìn)行規(guī)約的同時，調(diào)用相應(yīng)的語義子程序完成所式進(jìn)行規(guī)約的同時，調(diào)用相應(yīng)的語義子程

17、序完成所用規(guī)則的語義動作，并將每次動作后的值保存在語用規(guī)則的語義動作，并將每次動作后的值保存在語義棧中義棧中翻譯步驟翻譯步驟計算表達(dá)式2+3*5狀態(tài)狀態(tài)ACTIONGOTOi+* *()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5GE：1 EE+T2 ET3 TT*F4 TF5 F(E)6 Fii+i*i表達(dá)式2+3*5的歸約過程步驟狀態(tài)棧 語義棧符號棧輸入串動作00_ $2+3*5$S5105_ _$2 +3*5$r6203_ 2$F

18、 +3*5$r4302_ 2$T +3*5$r2401_ 2$E +3*5$S65016_ 2 _ $E+ 3*5$S560165_ 2 _ _$E+3 *5$r6步驟狀態(tài)棧 語義棧符號棧輸入串動作70163_ 2 _ 3$E+F *5$r480169_ 2 _ 3$E+T *5 $S7901697_ 2 _ 3 _$E+T* 5 $S510 016975 _ 2 _ 3 _ _$E+T*5$ r61101697(10)_ 2 _ 3 _ 5$E+T*F$ r312 0169_ 2 _ 15$E+T$ r113 01_ 17$E$ acc注意注意 句柄歸約在先，語義動作調(diào)用在后 歸約時，棧內(nèi)句

19、柄各符號的語義信息與句柄及同時出棧，整個句柄所表示的語義信息則賦給相應(yīng)產(chǎn)生式左部非終結(jié)符號的語義變量，并讓該非終結(jié)符號及語義信息同時入棧2022-2-25242022-2-2524編編 譯譯 原原 理理2022年2月25日生成中間代碼的生成中間代碼的目的目的(1)便于優(yōu)化便于優(yōu)化(2)便于移植便于移植(3)邏輯結(jié)構(gòu)清晰邏輯結(jié)構(gòu)清晰常見的中間代碼常見的中間代碼形式形式：后綴式后綴式三地址代碼三地址代碼（四元式、三元式和間接三元式（四元式、三元式和間接三元式 ）圖形圖形（抽象語法樹、有向無環(huán)圖）（抽象語法樹、有向無環(huán)圖） 中間代碼：一種介于中間代碼：一種介于源語言和目標(biāo)語言之間源語言和目標(biāo)語言之間

20、的中間語言形式的中間語言形式5.5.中間代碼中間代碼2022-2-25252022-2-2525編編 譯譯 原原 理理2022年2月25日中綴表示中綴表示后綴表示后綴表示a+b ab+a+b*c abc*+(a+b)*c ab+c*a:=b*c+b*d abc*bd*+:=特點特點1、運算對象出現(xiàn)的順序和原有順序（從左到右）相同、運算對象出現(xiàn)的順序和原有順序（從左到右）相同2、運算符按實際計算順序（從左到右）出現(xiàn)、運算符按實際計算順序（從左到右）出現(xiàn)3、運算符緊跟在運算對象的后面出現(xiàn)，且沒有括號、運算符緊跟在運算對象的后面出現(xiàn)，且沒有括號優(yōu)點：簡明、便于計值優(yōu)點：簡明、便于計值 后綴式后綴式2

21、022-2-25262022-2-2526編編 譯譯 原原 理理2022年2月25日分別給出下列表達(dá)式的后綴表示分別給出下列表達(dá)式的后綴表示1. -a+b*(-c+d)2. X:=-(a+b)/(c-d)-(a+b*c)3. a=c b=d4. ab+c ada+bea-bc-d+*+Xab+-cd-/abc*+-:=ac= bd=abc+ ad ab+e 2022-2-25272022-2-2527編編 譯譯 原原 理理2022年2月25日逆波蘭表示法（后綴式）逆波蘭表示法（后綴式）特點：運算符直接寫在其運算對象之后。 不再有括號 運算對象出現(xiàn)的次序未變 求值過程簡單，宜于用棧實現(xiàn)后綴式的計

22、算用一個棧實現(xiàn)。一般的計算過程是：自左至右掃描后綴式，每碰到運算量就把它推進(jìn)棧。每碰到k目運算符就把它作用于棧頂?shù)膋個項，并用運算結(jié)果代替這k個項。2022-2-25282022-2-2528編編 譯譯 原原 理理2022年2月25日三地址代碼三地址代碼種類種類（1）x = y op z形式的賦值語句，其中形式的賦值語句，其中op是二元運算符。是二元運算符。（2）x = op y形式的賦值語句，其中形式的賦值語句，其中op是一元運算符。是一元運算符。（3）x = y形式的賦值語句。形式的賦值語句。（4）無條件轉(zhuǎn)移語句）無條件轉(zhuǎn)移語句goto L，表示下一個要執(zhí)行的語句是，表示下一個要執(zhí)行的語句

23、是標(biāo)號為標(biāo)號為L的語句。的語句。（5）條件轉(zhuǎn)移語句）條件轉(zhuǎn)移語句if x rop y goto L中，中，rop為關(guān)系運算符，為關(guān)系運算符，如果如果x和和y滿足關(guān)系滿足關(guān)系rop，就轉(zhuǎn)而執(zhí)行標(biāo)號為，就轉(zhuǎn)而執(zhí)行標(biāo)號為L的語句，否則的語句，否則順序執(zhí)行下一個語句。順序執(zhí)行下一個語句。2022-2-25292022-2-2529編編 譯譯 原原 理理2022年2月25日（6）過程調(diào)用語句）過程調(diào)用語句param x 和和call p , n。源程序中的過程。源程序中的過程調(diào)用語句調(diào)用語句p(x1，x2，xn)可以產(chǎn)生如下的三地址代碼：可以產(chǎn)生如下的三地址代碼：param x1param x2 par

24、am xncall p, n其中其中n為實參個數(shù)。過程返回語句形如為實參個數(shù)。過程返回語句形如return y，其中，其中y為為過程返回的一個值。過程返回的一個值。 2022-2-25302022-2-2530編編 譯譯 原原 理理2022年2月25日（7）變址賦值：）變址賦值：x= yi，把從，把從y開始的第開始的第i個存儲單元的值賦給個存儲單元的值賦給x。xi= y，把，把y的值賦給的值賦給x開始的第開始的第i個存儲單元。個存儲單元。其中，其中，x，y和和i都代表數(shù)據(jù)對象。都代表數(shù)據(jù)對象。（8）地址和指針賦值：）地址和指針賦值：x=&y，把，把y的地址賦給的地址賦給x。x= y，把，把y指

25、示的地址單元中的內(nèi)容賦給指示的地址單元中的內(nèi)容賦給x。 x = y，把，把x指向的存儲單元的值置為指向的存儲單元的值置為y。2022-2-25312022-2-2531編編 譯譯 原原 理理2022年2月25日2具體實現(xiàn)具體實現(xiàn)四元式四元式操作符操作符 操作數(shù)操作數(shù)1 操作數(shù)操作數(shù)2 結(jié)果結(jié)果結(jié)果：通常是由編譯引進(jìn)的臨時變量結(jié)果：通常是由編譯引進(jìn)的臨時變量例例: X=(A+B)*(C+D)-E+, A, B, T1+, C, D, T2*, T1, T2, T3-, T3, E, T4=, T4, 一一, XT1,T2,T3,T4為臨時變量，為臨時變量，由四元式優(yōu)化比較方便由四元式優(yōu)化比較方便

26、T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T42022-2-25322022-2-2532編編 譯譯 原原 理理2022年2月25日操作符操作符 左操作符數(shù)左操作符數(shù) 右操作數(shù)右操作數(shù) 表達(dá)式的三元式：表達(dá)式的三元式：w*x+(y+z)(1) *, w, x(2) +, y, z(3) +, (1), (2) 第三個三元第三個三元式中的操作數(shù)式中的操作數(shù)(1)(2)表示第表示第(1)和第和第(2)條三元式的計條三元式的計算結(jié)果。算結(jié)果。三三元式元式2022-2-25332022-2-2533編編 譯譯 原原 理理2022年2月25日例：例： A=B+C*D/E F=C*D三元式

27、三元式(1) *, C, D(2) / , (1), E(3) +, B, (2) (4) =, A, (3)(5) *, C, D(6) =, F, (1)不便于代碼優(yōu)化：刪不便于代碼優(yōu)化：刪除某些三元式后可能除某些三元式后可能需作一系列的修改需作一系列的修改 三元式三元式(1) *, C, D(2) / , (1), E(3) +, B, (2) (4) =, A, (3)(5) =, F, (1)間接三元式間接三元式執(zhí)行順序執(zhí)行順序(1)(2)(3)(4)(1)(5)三元式的執(zhí)行次序用另一張三元式的執(zhí)行次序用另一張表表示表表示, 優(yōu)化時三元式可以不優(yōu)化時三元式可以不變，僅僅改變其執(zhí)行順序

28、表變，僅僅改變其執(zhí)行順序表2022-2-25342022-2-2534編編 譯譯 原原 理理2022年2月25日圖形表示法圖形表示法 無循環(huán)有向圖無循環(huán)有向圖(Directed Acyclic Graph(Directed Acyclic Graph，簡稱，簡稱DAG)DAG)對表達(dá)式中的每個子表達(dá)式，對表達(dá)式中的每個子表達(dá)式，DAGDAG中都有一個中都有一個結(jié)點結(jié)點一個一個內(nèi)部結(jié)點內(nèi)部結(jié)點代表一個代表一個操作符操作符，它的孩子代表，它的孩子代表操作數(shù)操作數(shù)在一個在一個DAGDAG中代表公共子表達(dá)式的結(jié)點具有多中代表公共子表達(dá)式的結(jié)點具有多個父結(jié)點個父結(jié)點2022-2-25352022-2-2

29、535編編 譯譯 原原 理理2022年2月25日例：例：x = y +y z + y z 抽象語法樹抽象語法樹圖形表示圖形表示有向無環(huán)圖有向無環(huán)圖表達(dá)式a+(-b)*c的三元式 (1) (,b,_);單目運算，運算對象2為空 (2) (*,(1),c) (3) (+,a,(2)三元式 X=a+b*c Y=d-b*c 三元式表(1)(*,b,c)(2)(+,a,(1)(3)(=,x,(2)(4)(_,d,(1)(5)(=,y,(4)四元式 (三地址代碼） X=a*b+c*d的四元式序列 三地址代碼(1)(* ,a,b,T1) (1)T1=a*b(2)(*, c,d,T2) (2)T2=c*d(3

30、)(+,T1,T2,T3) (3)T3=T1+T2(4)(=,T3,_,X) (4)X=T3 a:=ba:=b* *(-c)+b(-c)+b* *(-c)(-c)的圖表示法的圖表示法 assigna+*buminuscDAGassigna+*buminusc抽象語法樹抽象語法樹*buminusc抽象語法樹抽象語法樹對應(yīng)的代碼：對應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象語法樹抽象語法樹*buminuscDAG對應(yīng)的代碼：對應(yīng)的代碼： T1:=-cT2:=b*T1T5:=T2+T2a:=T5ass

31、igna+*buminuscDAG抽象語法樹抽象語法樹對應(yīng)的代碼：對應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5 屬性翻譯文法的應(yīng)用 綜合屬性與自下而上定值綜合屬性與自下而上定值 每個非終結(jié)符的屬性值都是根據(jù)位于其下面那些符號的屬性值來確定的，即按一種自下而上的方式來確定的。 繼承屬性和自上而下定值繼承屬性和自上而下定值 非終結(jié)符的屬性值或者根據(jù)其上層非終結(jié)符的屬性來確定或者根據(jù)產(chǎn)生式右部其它符號的屬性來確定。這種屬性值是根據(jù)自上而下方式確定的。 自底向上的語法制導(dǎo)翻譯 自底向上的語法制導(dǎo)翻譯方法是在自底向上的語法分析過程中逐步實現(xiàn)語

32、義規(guī)則的翻譯方法。在實現(xiàn)時注意以下幾點：（1）自底向上的翻譯的特點，棧的操作，對產(chǎn)生式的要求等（2）各種程序語句的目標(biāo)結(jié)構(gòu)（3）從源結(jié)構(gòu)到目標(biāo)結(jié)構(gòu)的變換方法（包括對產(chǎn)生式的改造等）算術(shù)表達(dá)式和賦值語句的翻譯 翻譯步驟： （1）分析文法的特點； （2）設(shè)計一系列的語義變量、定義語義過程、語義函數(shù)； （3）設(shè)計每一條規(guī)則的語義子程序； （4）增加一個語義信息棧，構(gòu)造LR分析表; (5)語法分析同時語義處理. 例： 有文法GA： 1.Ai:=E 2.E E+TT 3.T T*FF 4.F P 5.P i (E) 簡單算術(shù)表達(dá)式的計值順序與四元式出現(xiàn)的順序相同,因此目標(biāo)代碼的順序(結(jié)構(gòu))為:(1)先生

33、成E的代碼(一系列順序執(zhí)行的四元式)(2)把E的值賦給變量i(表達(dá)式的結(jié)果賦給賦值語句的左變量) 引入語義變量,語義過程和語義函數(shù)(1)語義變量E.place:表示存放E值的變量名在符號表中的入口地址或臨時變量的整數(shù)碼.(2)語義函數(shù)newtemp():申請一個臨時單元,存放中間結(jié)果;(3)語義過程emit(T=arg1 op arg2):產(chǎn)生一條四元式,并添入四元式表中;(4)語義過程lookup():審查是否出現(xiàn)在符號表中,在:返回地址,不在:返回NULL;(5)語義函數(shù)entry(i):回送標(biāo)識符i在符號表中的入口地址.表達(dá)式的語義動作設(shè)計 1. Ai:=Eemi

34、t(entry(i)=E.place 2. E E1+TE.place=newtemp(), emit(E.place)=E1.place+T.place 3.E T E.place=newtemp(), emit(E.place=T.place) 4. T T1*FT.place=newtemp(), emit(T.place)=T1.place*F.place 5. T F T.place=newtemp(), emit(T.place=F.place) 6.F _P F.place=newtemp(), emit(F.place)=P.place 7.P (E) P.place=newt

35、emp(), emit(P.place=E.place) 8.P iP.place=newtemp(), emit(P.place=Entry(i)例如:表達(dá)式X:=a+b*(c-d)的翻譯 K+1: T1:=c-d K+2: T2=b*T1 K+3: T3:=a+T2 K+4: X:=T3 (-,c,d,T1) (*,b,T1,T2) (+,a,T2,T3) (:=,T3,_,X)布爾表達(dá)式的翻譯 布爾表達(dá)式 是由布爾運算符(and,or,not)作用于布爾變量(或常數(shù))或關(guān)系表達(dá)式而形成的。 布爾表達(dá)式的作用： 用作控制語句中的條件：if-then、 while、repeat等 邏輯賦值句

36、中的邏輯運算布爾表達(dá)式到四元式的翻譯布爾表達(dá)式到四元式的翻譯 文法：EEEEEE(E)idE rop E 其中，(and)、(or)、(not)為布爾（邏輯）運算符；rop為關(guān)系運算符（，=，）；id為布爾（邏輯）變量或布爾（邏輯）常數(shù)；E rop E為關(guān)系表達(dá)式。 布爾表達(dá)式的求值方法： 通過逐步計算出各部分的值來計算整個表達(dá)式。 利用布爾運算符的性質(zhì)計算其值 布爾表達(dá)式作為控制語句中的條件式 作用是用于選擇下一個執(zhí)行點 while E do S1 E的作用是選擇S1執(zhí)行,還是跳過S1語句,執(zhí)行S1后面的語句 E有兩個出口: 真:S1語句 假:S1后面的語句While語句的目標(biāo)結(jié)構(gòu) 假E的代

37、碼 真 whilleS1的代碼 doJMP W.headW.head布爾初等量(布爾變量和關(guān)系表達(dá)式)的目標(biāo)結(jié)構(gòu) 由兩個轉(zhuǎn)移四元式構(gòu)成,一個表示真出口Li,另一個表示假出口Lj,設(shè)E是一布爾變量, 它的目標(biāo)結(jié)構(gòu)為: (1) if E goto Li (jumpt , E,_, Li ) (jnz,A,_, Li) (2) if E1 rop E2 goto Li (jump ,E1 ,E2 ,Li) (jrop,E1,E2, Li) 例:(j,a,b,p) (3) goto Lj (jump Lj ) (j,_,_, Lj )舉例:if ab then A:=x+y的四元式序列 if ab g

38、oto Li (真出口) goto Lj (假出口) Li:S的第一個四元式 S的最后一個四元式 Lj:S 后面的語句 (1) if ab goto (3) (2) goto (5) (3)T1:=x+y (4)A:=T1 (5) 多因子組成的布爾表達(dá)式的翻譯例: if ab c then S1 else S2 分析結(jié)果如下: 當(dāng)ab為真,執(zhí)行S1,不需要計算c的值 當(dāng)ab為假,計算c的值,c為真:執(zhí)行S1,為假:執(zhí)行S2 當(dāng)ab與c分別為真時,程序轉(zhuǎn)向一致,真出口相同(S1) 當(dāng)ab與c分別為假時,程序轉(zhuǎn)向一致,假出口相同(S2)if ab c then S1 elseS2的四元式序列(1)

39、 if ab goto S1的第一條語句 (5)(2) goto (3)(3) if c goto S1的第一條語句 (5)(4) goto S2的第一條語句 ( p+1(5) 關(guān)于S1的四元式序列 (p) Goto q(p+1)關(guān)于S2的四元式序列 (q)后繼四元式 目標(biāo)結(jié)構(gòu)E的代碼 TFS1的代碼JUMP SS2的代碼S（后繼語句） if E then S1 else S2的四元式序列 (1) if E goto (3) (2) goto (S2的第一個四元式) (p+1) (3)關(guān)于S1的四元式序列 (p) goto r (執(zhí)行完S1后轉(zhuǎn)出) (p+1)關(guān)于S2的四元式序列 (r) 后繼

40、四元式 while E do S1的四元式序列 (1) if E goto (3) (2)goto ( S1后面的語句) (p+1) (3)關(guān)于S1的四元式序列 (p) goto (1) (p+1) 后繼四元式真出口鏈、假出口鏈、回填（Backparch) 在多個因子組成的布爾表達(dá)式中，可能有多個因子的真出口或假出口的轉(zhuǎn)移去向相同，但又不能立刻知道具體轉(zhuǎn)向位置。 把轉(zhuǎn)移方向相同的四元式鏈在一起，一旦發(fā)現(xiàn)具體轉(zhuǎn)移目標(biāo)，就回填。 真出口用E Etruetrue來表示。 假出口用E Efalsefalse來表示。 回填BackparchBackparch（g,t)g,t)將t填入由g所指向的四元式的結(jié)果部分if ab c then S1 elseS2的真假出口回填描述(1) if a,C,D,(7) (6)(j,_,_,(4) (13) (7)(j0b0 do if xy then b:=b-1 else a:=a-1 假設(shè)四元式序列從100開始編號 100（j,a,0,102) 101 (j,_,_,0) (112) 102 (j,b,0,104) 103 (j,_,_,101) (112) 104 (j,x,y,106) 105 (j,_,_,0) (109) 106 (-,b,1,T1) 107 (:=,T1,_,b) 108 (j,_,_,100) 10