語法制導(dǎo)翻譯技術(shù)和中間代碼生成PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1第第5 5章章語法制導(dǎo)翻譯技術(shù)和中間代碼生成語法制導(dǎo)翻譯技術(shù)和中間代碼生成要求明確語義分析的要求明確語義分析的任務(wù)任務(wù)明確明確屬性文法屬性文法和和語法制導(dǎo)翻譯語法制導(dǎo)翻譯的含義的含義明確明確自底向上和自頂向下自底向上和自頂向下語法制導(dǎo)翻譯語法制導(dǎo)翻譯的區(qū)別和特點(diǎn)的區(qū)別和特點(diǎn)明確明確生成中間代碼的目的，中間代碼的生成中間代碼的目的，中間代碼的幾種形式幾種形式教學(xué)目標(biāo)教學(xué)目標(biāo)第1頁/共80頁 屬性文法屬性文法 語法制導(dǎo)翻譯法的基本思想語法制導(dǎo)翻譯法的基本思想 常見的中間代碼常見的中間代碼 各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技各種不同語法結(jié)構(gòu)的語法制導(dǎo)翻譯技術(shù)術(shù)教學(xué)內(nèi)容教學(xué)內(nèi)容第2頁/共80頁詞

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

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

4、代碼）性語句：填符號表；可執(zhí)行性語句：生成中間代碼） 語義分析的任務(wù)語義分析的任務(wù)第4頁/共80頁類型檢查類型檢查?？刂屏鳈z查控制流檢查，確?？刂普Z句有合法的轉(zhuǎn)向點(diǎn)。例，確保控制語句有合法的轉(zhuǎn)向點(diǎn)。例如，如，C語言中的語言中的break語句使控制跳離包括該語句的語句使控制跳離包括該語句的最小的最小的switch，while或或for語句。如果不存在包括它語句。如果不存在包括它的這樣的語句，則應(yīng)報(bào)錯(cuò)。的這樣的語句，則應(yīng)報(bào)錯(cuò)。靜態(tài)語義檢查靜態(tài)語義檢查第5頁/共80頁靜態(tài)語義檢查靜態(tài)語義檢查一致性檢查一致性檢查。很多情況下要求對象只能被定義一。很多情況下要求對象只能被定義一次。例如，語言中規(guī)定一個(gè)標(biāo)

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

6、附加了一組附加了一組屬性屬性和和運(yùn)算（語義）規(guī)則運(yùn)算（語義）規(guī)則的的文法文法 5.2 屬性文法屬性文法文法符號文法符號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.語義規(guī)則語義規(guī)則的表示的表示語義信息語義信息語義之間的關(guān)語義之間的關(guān)系系靜態(tài)語義檢查、符號靜態(tài)語義檢查、符號表操作、代碼生成及表操作、代碼生成及

7、打印各種錯(cuò)誤信息打印各種錯(cuò)誤信息 第7頁/共80頁第8頁/共80頁 非終結(jié)符非終結(jié)符E E、T T及及F F都有一個(gè)綜合屬性都有一個(gè)綜合屬性val,val,符符號號i i有一個(gè)綜合屬性。有一個(gè)綜合屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(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)生式第9頁/共80

8、頁語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯：語法制導(dǎo)翻譯：將將語義規(guī)則語義規(guī)則與與語法規(guī)則語法規(guī)則相結(jié)合，在相結(jié)合，在語法分析語法分析的過程中通過執(zhí)行的過程中通過執(zhí)行語義動(dòng)作語義動(dòng)作，計(jì)算語義屬，計(jì)算語義屬性值，從而完成預(yù)定的翻譯工作。性值，從而完成預(yù)定的翻譯工作。 第10頁/共80頁語法制導(dǎo)翻譯分為兩種語法制導(dǎo)翻譯分為兩種處理方法處理方法：（1）自底向上語法制導(dǎo)翻譯：）自底向上語法制導(dǎo)翻譯：對每個(gè)產(chǎn)生式編制一個(gè)語義子程序，在進(jìn)行語法分析的對每個(gè)產(chǎn)生式編制一個(gè)語義子程序，在進(jìn)行語法分析的過程中，過程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語義子，就調(diào)用相應(yīng)的語義子

9、程序?qū)崿F(xiàn)語義檢查與翻譯。這種實(shí)現(xiàn)方案隱藏了其中語義程序?qū)崿F(xiàn)語義檢查與翻譯。這種實(shí)現(xiàn)方案隱藏了其中語義規(guī)則的計(jì)算次序等實(shí)現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。規(guī)則的計(jì)算次序等實(shí)現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。（2）自頂向下語法制導(dǎo)翻譯：）自頂向下語法制導(dǎo)翻譯：在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語義動(dòng)作，按照在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語義動(dòng)作。這是一種分析的進(jìn)程，執(zhí)行遇到的語義動(dòng)作。這是一種動(dòng)作與分析動(dòng)作與分析交錯(cuò)交錯(cuò)的實(shí)現(xiàn)方案。的實(shí)現(xiàn)方案。第11頁/共80頁語法制導(dǎo)定義語法制導(dǎo)定義對每個(gè)產(chǎn)生式編制一個(gè)對每個(gè)產(chǎn)生式編制一個(gè)語義子程序語義子程序在進(jìn)行語法分析的過程中，在進(jìn)行

10、語法分析的過程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯綜合屬性綜合屬性繼承屬性繼承屬性自底向上自底向上傳遞信息傳遞信息自頂向下（自左向自頂向下（自左向右）右）傳遞信息傳遞信息第12頁/共80頁第13頁/共80頁 ) )打印由打印由E E產(chǎn)生的算術(shù)表達(dá)式的值，可認(rèn)為這產(chǎn)生的算術(shù)表達(dá)式的值，可認(rèn)為這條規(guī)則定義了條規(guī)則定義了L L的一個(gè)的一個(gè)虛屬性虛屬性。 L EE E1+TE T T T1 * FT FF (E)F i) E.val=E1= T.val=T1.val =例例5.5.綜合屬性綜合屬性語語 義義

11、 規(guī)規(guī) 則則產(chǎn)生式產(chǎn)生式第14頁/共80頁一個(gè)結(jié)點(diǎn)的綜合屬性值是其一個(gè)結(jié)點(diǎn)的綜合屬性值是其子結(jié)點(diǎn)子結(jié)點(diǎn)的某些屬性來決定的的某些屬性來決定的+3+3* *4 4的注釋分析樹的注釋分析樹通常使用通常使用自底向上自底向上的分析方法的分析方法在在每個(gè)結(jié)點(diǎn)每個(gè)結(jié)點(diǎn)處使用語義規(guī)處使用語義規(guī)則來計(jì)算綜合屬性值則來計(jì)算綜合屬性值當(dāng)一個(gè)當(dāng)一個(gè)產(chǎn)生式獲得匹配產(chǎn)生式獲得匹配時(shí)時(shí)，就調(diào)用相應(yīng)的語義子程，就調(diào)用相應(yīng)的語義子程序序從從葉結(jié)點(diǎn)到根結(jié)點(diǎn)葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)進(jìn)行計(jì)算算 只含有只含有綜合屬性綜合屬性的語法制導(dǎo)定的語法制導(dǎo)定義稱為義稱為S S屬性定義屬性定義第15頁/共80頁S屬性定義與自底向上翻譯屬性定義與自底向

12、上翻譯 LRLR分析器可以改造為一個(gè)翻譯器，在對輸入串進(jìn)行分析器可以改造為一個(gè)翻譯器，在對輸入串進(jìn)行語法分析的同時(shí)對屬性進(jìn)行計(jì)算語法分析的同時(shí)對屬性進(jìn)行計(jì)算LRLR分析器增加分析器增加屬性值（語義）棧屬性值（語義）棧 1）為文法的每條規(guī)則設(shè)計(jì)相應(yīng)的語義子程序；）為文法的每條規(guī)則設(shè)計(jì)相應(yīng)的語義子程序；2）增加一個(gè)語義信息棧；）增加一個(gè)語義信息棧；3）在語法分析的同時(shí)做語義處理：即在用某一個(gè)）在語法分析的同時(shí)做語義處理：即在用某一個(gè)產(chǎn)生式進(jìn)行規(guī)約的同時(shí)，調(diào)用相應(yīng)的語義子程序產(chǎn)生式進(jìn)行規(guī)約的同時(shí)，調(diào)用相應(yīng)的語義子程序完成所用規(guī)則的語義動(dòng)作，并將每次動(dòng)作后的值完成所用規(guī)則的語義動(dòng)作，并將每次動(dòng)作后的值

13、保存在語義棧中保存在語義棧中翻譯步驟翻譯步驟第16頁/共80頁 2021年12月16日 第17頁/共80頁 2021年12月16日 狀態(tài)狀態(tài)ACTIONGOTOi+* *()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5GE：1 EE+T2 ET3 TT*F4 TF5 F(E)6 Fii+i*i第18頁/共80頁 2021年12月16日 步驟狀態(tài)棧 語義棧符號棧輸入串動(dòng)作00_ $2+3*5$S5105_ _$2 +3*5$r6203_

14、2$F +3*5$r4302_ 2$T +3*5$r2401_ 2$E +3*5$S65016_ 2 _ $E+ 3*5$S560165_ 2 _ _$E+3 *5$r6第19頁/共80頁 2021年12月16日 步驟狀態(tài)棧 語義棧符號棧輸入串動(dòng)作70163_ 2 _ 3$E+F *5$r480169_ 2 _ 3$E+T *5 $S7901697_ 2 _ 3 _$E+T* 5 $S510016975_ 2 _ 3 _ _$E+T*5$ r61101697(10)_ 2 _ 3 _ 5$E+T*F$ r3120169_ 2 _ 15$E+T$ r11301_ 17$E$ acc第20頁/共8

15、0頁 2021年12月16日 第21頁/共80頁生成中間代碼的生成中間代碼的目的目的(1)便于優(yōu)化便于優(yōu)化(2)便于移植便于移植(3)邏輯結(jié)構(gòu)清晰邏輯結(jié)構(gòu)清晰常見的中間代碼常見的中間代碼形式形式：后綴式后綴式三地址代碼三地址代碼（四元式、三元式和間接三元式（四元式、三元式和間接三元式 ）圖形圖形（抽象語法樹、有向無環(huán)圖）（抽象語法樹、有向無環(huán)圖） 中間代碼：一種介于中間代碼：一種介于源語言和目標(biāo)語言之間源語言和目標(biāo)語言之間的中間語言形式的中間語言形式5.5.中間代碼中間代碼第22頁/共80頁中綴表示中綴表示后綴表示后綴表示a+b ab+a+b*c abc*+(a+b)*c ab+c*a:=b*

16、c+b*d abc*bd*+:=特點(diǎn)特點(diǎn)1、運(yùn)算對象出現(xiàn)的順序和原有順序（從左到右）相同、運(yùn)算對象出現(xiàn)的順序和原有順序（從左到右）相同2、運(yùn)算符按實(shí)際計(jì)算順序（從左到右）出現(xiàn)、運(yùn)算符按實(shí)際計(jì)算順序（從左到右）出現(xiàn)3、運(yùn)算符緊跟在運(yùn)算對象的后面出現(xiàn)，且沒有括號、運(yùn)算符緊跟在運(yùn)算對象的后面出現(xiàn)，且沒有括號優(yōu)點(diǎn)：簡明、便于計(jì)值優(yōu)點(diǎn)：簡明、便于計(jì)值 后綴式后綴式第23頁/共80頁分別給出下列表達(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

17、*+-:=ac= bd=abc+ ad ab+e 第24頁/共80頁后綴式的計(jì)算用一個(gè)棧實(shí)現(xiàn)。一般的計(jì)算過程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。第25頁/共80頁三地址代碼三地址代碼種類種類（1）x = y op z形式的賦值語句，其中形式的賦值語句，其中op是二元運(yùn)算符。是二元運(yùn)算符。（2）x = op y形式的賦值語句，其中形式的賦值語句，其中op是一元運(yùn)算符。是一元運(yùn)算符。（3）x = y形式的賦值語句。形式的賦值語句。（4）無條件轉(zhuǎn)移語句）無條件轉(zhuǎn)移語句goto L，表示下一個(gè)要執(zhí)行的語句是，表示下一個(gè)要

18、執(zhí)行的語句是標(biāo)號為標(biāo)號為L的語句。的語句。（5）條件轉(zhuǎn)移語句）條件轉(zhuǎn)移語句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)號為，就轉(zhuǎn)而執(zhí)行標(biāo)號為L的語句，否的語句，否則順序執(zhí)行下一個(gè)語句。則順序執(zhí)行下一個(gè)語句。第26頁/共80頁（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 param xncall p, n其中其中n為實(shí)參個(gè)數(shù)。過程返回

19、語句形如為實(shí)參個(gè)數(shù)。過程返回語句形如return y，其中，其中y為為過程返回的一個(gè)值。過程返回的一個(gè)值。 第27頁/共80頁（7）變址賦值：）變址賦值：x= yi，把從，把從y開始的第開始的第i個(gè)存儲單元的值賦給個(gè)存儲單元的值賦給x。xi= y，把，把y的值賦給的值賦給x開始的第開始的第i個(gè)存儲單元。個(gè)存儲單元。其中，其中，x，y和和i都代表數(shù)據(jù)對象。都代表數(shù)據(jù)對象。（8）地址和指針賦值：）地址和指針賦值：x=&y，把，把y的地址賦給的地址賦給x。x= y，把，把y指示的地址單元中的內(nèi)容賦給指示的地址單元中的內(nèi)容賦給x。 x = y，把，把x指向的存儲單元的值置為指向的存儲單元的值置

20、為y。第28頁/共80頁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)化比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4第29頁/共80頁操作符操作符 左操作符數(shù)左操作符數(shù) 右操作數(shù)右操作數(shù) 表達(dá)式的三元式：表達(dá)式的三元式：w*x+(y+z)(

21、1) *, w, x(2) +, y, z(3) +, (1), (2) 第三個(gè)三元第三個(gè)三元式中的操作數(shù)式中的操作數(shù)(1)(2)表示第表示第(1)和第和第(2)條三元式的計(jì)條三元式的計(jì)算結(jié)果。算結(jié)果。三三元式元式第30頁/共80頁例：例： A=B+C*D/E F=C*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),

22、 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í)三元式可以不變，僅僅改變其執(zhí)行順序不變，僅僅改變其執(zhí)行順序表表第31頁/共80頁第32頁/共80頁例：例：x = y +y z + y z 抽象語法樹抽象語法樹圖形表示圖形表示有向無環(huán)圖有向無環(huán)圖第33頁/共80頁 2021年12月16日 第34頁/共80頁 2021年12月16日 第35頁/共80頁 2021年12月16日 第36頁/共80頁 2021年

23、12月16日 assigna+*buminuscDAGassigna+*buminusc抽象語法樹抽象語法樹*buminusc第37頁/共80頁 2021年12月16日 assigna+*buminusc抽象語法樹抽象語法樹*buminusc第38頁/共80頁 2021年12月16日 assigna+*buminuscDAG抽象語法樹抽象語法樹對應(yīng)的代碼：對應(yīng)的代碼： T1:=-c T2:=b*T1T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5第39頁/共80頁 2021年12月16日 第40頁/共80頁 2021年12月16日 第41頁/共80頁 2021年12月16日 第42頁/共80頁 2021年12月16日 第43頁/共80頁 2021年12月16日 第44頁/共80頁 2021年12月16日 第45頁/共80頁 2021年12月16日 第46頁/共80頁 2021年12月16日 第47頁/共80頁 2021年12月16日 第48頁/共80頁 2021年12月16日 第49頁/共80頁 2021年12月16日 假E的代碼 真 whilleS1的代碼 doJMP W.headW.head第50頁/共80頁 2021年12月16日 第51頁/共80頁 2021年1