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

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

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

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

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

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

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

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

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

9、2022-6-3010編編 譯譯 原原 理理2022年6月30日 非終結(jié)符非終結(jié)符E E、T T及及F F都有一個(gè)綜合屬性都有一個(gè)綜合屬性val,val,符號(hào)符號(hào)i i有一個(gè)綜合屬性。有一個(gè)綜合屬性。 某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)中同一非終結(jié)符多次出現(xiàn)語(yǔ)語(yǔ) 義義 規(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-6-30112022-6-3011編編 譯譯 原原 理理2022年6月30日語(yǔ)法制導(dǎo)翻譯的過(guò)程語(yǔ)法制導(dǎo)翻譯的過(guò)程語(yǔ)法制導(dǎo)翻譯：語(yǔ)法制導(dǎo)翻譯：將將語(yǔ)義規(guī)則語(yǔ)義規(guī)則與與語(yǔ)法規(guī)則語(yǔ)法規(guī)則相結(jié)合，在相結(jié)合，在語(yǔ)法分析語(yǔ)法分析的過(guò)程中通過(guò)執(zhí)行的過(guò)程中通過(guò)執(zhí)行語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作，計(jì)算語(yǔ)義屬，計(jì)算語(yǔ)義屬性值，從而完成預(yù)定的翻譯工作。性值，從而完成預(yù)定的翻譯工作。 2022-6-30122022-6-3012編編 譯譯 原原 理理2022年6月30日自底向上語(yǔ)自底向上語(yǔ)法制導(dǎo)翻譯法制導(dǎo)翻譯自頂向下語(yǔ)自頂向下語(yǔ)法制導(dǎo)翻譯法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯的實(shí)現(xiàn)語(yǔ)法制導(dǎo)翻譯的實(shí)現(xiàn)2022-6-30132022-6-

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

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

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

14、022-6-3016編編 譯譯 原原 理理2022年6月30日 print(E.val)print(E.val)打印由打印由E E產(chǎn)生的算術(shù)表達(dá)式的值，產(chǎn)生的算術(shù)表達(dá)式的值，可認(rèn)為這條規(guī)則定義了可認(rèn)為這條規(guī)則定義了L L的一個(gè)的一個(gè)虛屬性虛屬性。 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.綜合屬性綜合屬性語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則產(chǎn)生式產(chǎn)生式2022-6-30172022

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

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

17、序完成所用規(guī)則的語(yǔ)義動(dòng)作，并將每次動(dòng)作后的值保存在語(yǔ)用規(guī)則的語(yǔ)義動(dòng)作，并將每次動(dòng)作后的值保存在語(yǔ)義棧中義棧中翻譯步驟翻譯步驟計(jì)算表達(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的歸約過(guò)程步驟狀態(tài)棧 語(yǔ)義棧符號(hào)棧輸入串動(dòng)作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)棧 語(yǔ)義棧符號(hào)棧輸入串動(dòng)作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注意注意 句柄歸約在先，語(yǔ)義動(dòng)作調(diào)用在后 歸約時(shí)，棧內(nèi)句

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

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

21、022-6-30262022-6-3026編編 譯譯 原原 理理2022年6月30日分別給出下列表達(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-6-30272022-6-3027編編 譯譯 原原 理理2022年6月30日逆波蘭表示法（后綴式）逆波蘭表示法（后綴式）特點(diǎn)：運(yùn)算符直接寫在其運(yùn)算對(duì)象之后。 不再有括號(hào) 運(yùn)算對(duì)象出現(xiàn)的次序未變 求值過(guò)程簡(jiǎn)單，宜于用棧實(shí)現(xiàn)后綴式的計(jì)

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

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

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

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

26、比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T42022-6-30322022-6-3032編編 譯譯 原原 理理2022年6月30日操作符操作符 左操作符數(shù)左操作符數(shù) 右操作數(shù)右操作數(shù) 表達(dá)式的三元式：表達(dá)式的三元式：w*x+(y+z)(1) *, w, x(2) +, y, z(3) +, (1), (2) 第三個(gè)三元第三個(gè)三元式中的操作數(shù)式中的操作數(shù)(1)(2)表示第表示第(1)和第和第(2)條三元式的計(jì)條三元式的計(jì)算結(jié)果。算結(jié)果。三三元式元式2022-6-30332022-6-3033編編 譯譯 原原 理理2022年6月30日例：例： A=B+C*D/E F=C*

27、D三元式三元式(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)化時(shí)三元式可以不優(yōu)化時(shí)三元式可以不變，僅僅改變其

28、執(zhí)行順序表變，僅僅改變其執(zhí)行順序表2022-6-30342022-6-3034編編 譯譯 原原 理理2022年6月30日?qǐng)D形表示法圖形表示法 無(wú)循環(huán)有向圖無(wú)循環(huán)有向圖(Directed Acyclic Graph(Directed Acyclic Graph，簡(jiǎn)稱，簡(jiǎn)稱DAG)DAG) 對(duì)表達(dá)式中的每個(gè)子表達(dá)式，對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAGDAG中都有一個(gè)中都有一個(gè)結(jié)點(diǎn)結(jié)點(diǎn) 一個(gè)一個(gè)內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn)代表一個(gè)代表一個(gè)操作符操作符，它的孩子代表，它的孩子代表操作數(shù)操作數(shù) 在一個(gè)在一個(gè)DAGDAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)個(gè)父結(jié)點(diǎn)2022-6-30352

29、022-6-3035編編 譯譯 原原 理理2022年6月30日例：例：x = y +y z + y z 抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)圖形表示圖形表示有向無(wú)環(huán)圖有向無(wú)環(huán)圖表達(dá)式a+(-b)*c的三元式 (1) (,b,_);單目運(yùn)算，運(yùn)算對(duì)象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)T

30、2=c*d(3)(+,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抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)*buminusc抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)對(duì)應(yīng)的代碼：對(duì)應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5assigna+*buminusc抽象語(yǔ)法樹(shù)抽象語(yǔ)法樹(shù)*buminuscDAG對(duì)應(yīng)的代碼：對(duì)應(yīng)的代碼： T1:=-cT2:=b*T1T5:=T2+T2a

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

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

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

34、i:=Eemit(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.pla

35、ce=newtemp(), 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á)式 是由布爾運(yùn)算符(and,or,not)作用于布爾變量(或常數(shù))或關(guān)系表達(dá)式而形成的。 布爾表達(dá)式的作用： 用作控制語(yǔ)句中的條件：if-then、 while、repeat

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

37、結(jié)構(gòu) 假E的代碼 真 whilleS1的代碼 doJMP W.headW.head布爾初等量(布爾變量和關(guān)系表達(dá)式)的目標(biāo)結(jié)構(gòu) 由兩個(gè)轉(zhuǎn)移四元式構(gòu)成,一個(gè)表示真出口Li,另一個(gè)表示假出口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的四元式序列

38、if ab goto Li (真出口) goto Lj (假出口) Li:S的第一個(gè)四元式 S的最后一個(gè)四元式 Lj:S 后面的語(yǔ)句 (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,不需要計(jì)算c的值 當(dāng)ab為假,計(jì)算c的值,c為真:執(zhí)行S1,為假:執(zhí)行S2 當(dāng)ab與c分別為真時(shí),程序轉(zhuǎn)向一致,真出口相同(S1) 當(dāng)ab與c分別為假時(shí),程序轉(zhuǎn)向一致,假出口相同(S2)if ab c then S1 elseS2的四

39、元式序列(1) if ab goto S1的第一條語(yǔ)句 (5)(2) goto (3)(3) if c goto S1的第一條語(yǔ)句 (5)(4) goto S2的第一條語(yǔ)句 ( 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（后繼語(yǔ)句） if E then S1 else S2的四元式序列 (1) if E goto (3) (2) goto (S2的第一個(gè)四元式) (p+1) (3)關(guān)于S1的四元式序列 (p) goto r (執(zhí)行完S1后轉(zhuǎn)出) (p+1)關(guān)于S2的四元式序列

40、 (r) 后繼四元式 while E do S1的四元式序列 (1) if E goto (3) (2)goto ( S1后面的語(yǔ)句) (p+1) (3)關(guān)于S1的四元式序列 (p) goto (1) (p+1) 后繼四元式真出口鏈、假出口鏈、回填（Backparch) 在多個(gè)因子組成的布爾表達(dá)式中，可能有多個(gè)因子的真出口或假出口的轉(zhuǎn)移去向相同，但又不能立刻知道具體轉(zhuǎn)向位置。 把轉(zhuǎn)移方向相同的四元式鏈在一起，一旦發(fā)現(xiàn)具體轉(zhuǎn)移目標(biāo)，就回填。 真出口用E Etruetrue來(lái)表示。 假出口用E Efalsefalse來(lái)表示。 回填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開(kāi)始編號(hào) 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