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

語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成第一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三第5章語(yǔ)法制導(dǎo)翻譯技術(shù)和中間代碼生成要求明確語(yǔ)義分析的任務(wù)明確屬性文法和語(yǔ)法制導(dǎo)翻譯的含義明確自底向上和自頂向下語(yǔ)法制導(dǎo)翻譯的區(qū)別和特點(diǎn)明確生成中間代碼的目的，中間代碼的幾種形式

教學(xué)目標(biāo)第二頁(yè)，共八十三頁(yè)，編輯于2023年，星期三屬性文法語(yǔ)法制導(dǎo)翻譯法的基本思想常見的中間代碼各種不同語(yǔ)法結(jié)構(gòu)的語(yǔ)法制導(dǎo)翻譯技術(shù)教學(xué)內(nèi)容第三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三詞法分析，語(yǔ)法分析：解決單詞和語(yǔ)言成分的識(shí)別及詞法和語(yǔ)法結(jié)構(gòu)的檢查。語(yǔ)法結(jié)構(gòu)可形式化地用一組產(chǎn)生式來描述。給定一組產(chǎn)生式，我們能夠很容易地將其分析器構(gòu)造出來。本章要介紹的是語(yǔ)義分析和中間代碼生成技術(shù)。程序語(yǔ)言中間代碼目標(biāo)代碼翻譯翻譯第四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三根據(jù)語(yǔ)義規(guī)則對(duì)識(shí)別出的各種語(yǔ)法成分析其含義，進(jìn)行初步翻譯，生成相應(yīng)的中間代碼或直接生成目標(biāo)代碼。第一，審查每個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義，即檢查語(yǔ)法結(jié)構(gòu)合法的程序是否真正有意義。也稱靜態(tài)語(yǔ)義檢查。（類型檢查、控制流的檢查、一致性檢查、相關(guān)名字的檢查）第二，如果靜態(tài)語(yǔ)義正確，語(yǔ)義處理則要執(zhí)行真正的翻譯，要么生成中間代碼，要么生成實(shí)際的目標(biāo)代碼。（說明性語(yǔ)句：填符號(hào)表；可執(zhí)行性語(yǔ)句：生成中間代碼）

語(yǔ)義分析的任務(wù)第五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三①類型檢查。②控制流檢查，確?？刂普Z(yǔ)句有合法的轉(zhuǎn)向點(diǎn)。例如，C語(yǔ)言中的break語(yǔ)句使控制跳離包括該語(yǔ)句的最小的switch，while或for語(yǔ)句。如果不存在包括它的這樣的語(yǔ)句，則應(yīng)報(bào)錯(cuò)。靜態(tài)語(yǔ)義檢查第六頁(yè)，共八十三頁(yè)，編輯于2023年，星期三靜態(tài)語(yǔ)義檢查③一致性檢查。很多情況下要求對(duì)象只能被定義一次。例如，Ｃ語(yǔ)言中規(guī)定一個(gè)標(biāo)識(shí)符在同一作用域中只能被說明一次，同一case語(yǔ)句的標(biāo)號(hào)不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等。④相關(guān)名字檢查。有的語(yǔ)言中有時(shí)規(guī)定，同一名字必須出現(xiàn)兩次或多次。例如，Ada語(yǔ)言中，循環(huán)或程序塊可以有一個(gè)名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，如同語(yǔ)句括號(hào)一般，編譯程序必須檢查它們的配對(duì)情況。第七頁(yè)，共八十三頁(yè)，編輯于2023年，星期三附加了一組屬性和運(yùn)算（語(yǔ)義）規(guī)則的文法

5.2屬性文法文法符號(hào)X的屬性t常用X.t來表示語(yǔ)義規(guī)則是根據(jù)產(chǎn)生式所蘊(yùn)涵的語(yǔ)義操作建立起來的，并與語(yǔ)義分析的目標(biāo)有關(guān)不同的產(chǎn)生式對(duì)應(yīng)不同的語(yǔ)義規(guī)則不同的分析目標(biāo)也對(duì)應(yīng)不同的語(yǔ)義規(guī)則

1.屬性的表示2.語(yǔ)義規(guī)則的表示語(yǔ)義信息語(yǔ)義之間的關(guān)系靜態(tài)語(yǔ)義檢查、符號(hào)表操作、代碼生成及打印各種錯(cuò)誤信息

第八頁(yè)，共八十三頁(yè)，編輯于2023年，星期三屬性文法屬性文法的形式定義：AG：AG=（G，V，E）G:上下文無關(guān)文法;V:屬性的有窮集合;每一個(gè)屬性與某一個(gè)文法符號(hào)相關(guān)聯(lián)；用文法符號(hào)·屬性表示E:表示屬性的斷言或謂詞的有窮集合(語(yǔ)義規(guī)則);每一個(gè)斷言與文法的某個(gè)產(chǎn)生式相關(guān)聯(lián))屬性:綜合屬性(自下而上傳遞信息)、繼承屬性（自上而下傳遞信息)第九頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

非終結(jié)符E、T及F都有一個(gè)綜合屬性val,符號(hào)i有一個(gè)綜合屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語(yǔ)義規(guī)則EE1+TET

TT1*FTFF(E)Fi

E.val=E1.val+T.valE.val=T.val

T.val=T1.valF.valT.val=F.valF.val=E.val

F.val=i.lexval產(chǎn)生式例5.1第十頁(yè)，共八十三頁(yè)，編輯于2023年，星期三語(yǔ)法制導(dǎo)翻譯的過程語(yǔ)法制導(dǎo)翻譯：將語(yǔ)義規(guī)則與語(yǔ)法規(guī)則相結(jié)合，在語(yǔ)法分析的過程中通過執(zhí)行語(yǔ)義動(dòng)作，計(jì)算語(yǔ)義屬性值，從而完成預(yù)定的翻譯工作。第十一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三自底向上語(yǔ)法制導(dǎo)翻譯自頂向下語(yǔ)法制導(dǎo)翻譯語(yǔ)法制導(dǎo)翻譯的實(shí)現(xiàn)第十二頁(yè)，共八十三頁(yè)，編輯于2023年，星期三語(yǔ)法制導(dǎo)翻譯分為兩種處理方法：（1）語(yǔ)法制導(dǎo)定義（自底向上）：對(duì)每個(gè)產(chǎn)生式編制一個(gè)語(yǔ)義子程序，在進(jìn)行語(yǔ)法分析的過程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序?qū)崿F(xiàn)語(yǔ)義檢查與翻譯。這種實(shí)現(xiàn)方案隱藏了其中語(yǔ)義規(guī)則的計(jì)算次序等實(shí)現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。（2）翻譯方案（自頂向下）：在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語(yǔ)義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語(yǔ)義動(dòng)作。這是一種動(dòng)作與分析交錯(cuò)的實(shí)現(xiàn)方案。第十三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三輸入符號(hào)串

分析樹

執(zhí)行語(yǔ)義規(guī)則

翻譯結(jié)果翻譯步驟（２）從分析樹得到描述結(jié)點(diǎn)屬性間依賴關(guān)系的依賴圖，由依賴圖得到語(yǔ)義規(guī)則的計(jì)算次序

（1）分析輸入符號(hào)串，建立分析語(yǔ)法樹（３）進(jìn)行語(yǔ)義規(guī)則的計(jì)算，得到翻譯結(jié)果

第十四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三語(yǔ)法制導(dǎo)定義對(duì)每個(gè)產(chǎn)生式編制一個(gè)語(yǔ)義子程序在進(jìn)行語(yǔ)法分析的過程中，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序?qū)崿F(xiàn)語(yǔ)義檢查與翻譯綜合屬性繼承屬性自底向上傳遞信息自頂向下（自左向右）傳遞信息第十五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

print(E.val)打印由E產(chǎn)生的算術(shù)表達(dá)式的值，可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。

LEEE1+TET

TT1*FTFF(E)Fiprint(E.val)

E.val=E1.val+T.valE.val=T.val

T.val=T1.valF.val

T.val=F.valF.val=E.valF.val=i.lexval例5.２綜合屬性語(yǔ)義規(guī)則產(chǎn)生式第十六頁(yè)，共八十三頁(yè)，編輯于2023年，星期三一個(gè)結(jié)點(diǎn)的綜合屬性值是其子結(jié)點(diǎn)的某些屬性來決定的２+3*4的注釋分析樹通常使用自底向上的分析方法在每個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則來計(jì)算綜合屬性值當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，就調(diào)用相應(yīng)的語(yǔ)義子程序從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算只含有綜合屬性的語(yǔ)法制導(dǎo)定義稱為S屬性定義第十七頁(yè)，共八十三頁(yè)，編輯于2023年，星期三S屬性定義與自底向上翻譯LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算LR分析器增加屬性值（語(yǔ)義）棧

首先，為文法的每條規(guī)則設(shè)計(jì)相應(yīng)的語(yǔ)義子程序；增加一個(gè)語(yǔ)義信息棧；在語(yǔ)法分析的同時(shí)做語(yǔ)義處理：即在用某一個(gè)產(chǎn)生式進(jìn)行規(guī)約的同時(shí)，調(diào)用相應(yīng)的語(yǔ)義子程序完成所用規(guī)則的語(yǔ)義動(dòng)作，并將每次動(dòng)作后的值保存在語(yǔ)義棧中翻譯步驟第十八頁(yè)，共八十三頁(yè)，編輯于2023年，星期三計(jì)算表達(dá)式2+3*5第十九頁(yè)，共八十三頁(yè)，編輯于2023年，星期三狀態(tài)ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5G[E]：1E→E+T2E→T3T→T*F4T→F5F→(E)6F→ii+i*i第二十頁(yè)，共八十三頁(yè)，編輯于2023年，星期三表達(dá)式2+3*5的歸約過程步驟狀態(tài)棧語(yǔ)義棧符號(hào)棧輸入串動(dòng)作00_$2+3*5$S5105__$2

+3*5$r6203_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第二十一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三步驟狀態(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$S510016975_2_3__$E+T*5$r61101697(10)_2_3_5$E+T*F$r3120169_2_15$E+T$r11301_17$E$acc第二十二頁(yè)，共八十三頁(yè)，編輯于2023年，星期三注意句柄歸約在先，語(yǔ)義動(dòng)作調(diào)用在后歸約時(shí)，棧內(nèi)句柄各符號(hào)的語(yǔ)義信息與句柄及同時(shí)出棧，整個(gè)句柄所表示的語(yǔ)義信息則賦給相應(yīng)產(chǎn)生式左部非終結(jié)符號(hào)的語(yǔ)義變量，并讓該非終結(jié)符號(hào)及語(yǔ)義信息同時(shí)入棧第二十三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三生成中間代碼的目的(1)便于優(yōu)化(2)便于移植(3)邏輯結(jié)構(gòu)清晰常見的中間代碼形式：后綴式三地址代碼（四元式、三元式和間接三元式）圖形（抽象語(yǔ)法樹、有向無環(huán)圖）

中間代碼：一種介于源語(yǔ)言和目標(biāo)語(yǔ)言之間的中間語(yǔ)言形式5.３中間代碼第二十四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三中綴表示后綴表示

a+bab+

a+b*cabc*+

(a+b)*cab+c*a:=b*c+b*dabc*bd*+:=特點(diǎn)1、運(yùn)算對(duì)象出現(xiàn)的順序和原有順序（從左到右）相同2、運(yùn)算符按實(shí)際計(jì)算順序（從左到右）出現(xiàn)3、運(yùn)算符緊跟在運(yùn)算對(duì)象的后面出現(xiàn)，且沒有括號(hào)優(yōu)點(diǎn)：簡(jiǎn)明、便于計(jì)值后綴式第二十五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三分別給出下列表達(dá)式的后綴表示1.-a+b*(-c+d)2.X:=-(a+b)/(c-d)-(a+b*c)3.a=c∧b=d4.a≤b+c∧a>d∨a+b≠ea-bc-d+*+Xab+-cd-/abc*+-:=ac=bd=∧abc+≤ad>∧ab+e≠∨第二十六頁(yè)，共八十三頁(yè)，編輯于2023年，星期三逆波蘭表示法（后綴式）特點(diǎn)：運(yùn)算符直接寫在其運(yùn)算對(duì)象之后。不再有括號(hào)運(yùn)算對(duì)象出現(xiàn)的次序未變求值過程簡(jiǎn)單，宜于用棧實(shí)現(xiàn)后綴式的計(jì)算用一個(gè)棧實(shí)現(xiàn)。一般的計(jì)算過程是：自左至右掃描后綴式，每碰到運(yùn)算量就把它推進(jìn)棧。每碰到k目運(yùn)算符就把它作用于棧頂?shù)膋個(gè)項(xiàng)，并用運(yùn)算結(jié)果代替這k個(gè)項(xiàng)。第二十七頁(yè)，共八十三頁(yè)，編輯于2023年，星期三三地址代碼１．種類（1）x=yopz形式的賦值語(yǔ)句，其中op是二元運(yùn)算符。（2）x=opy形式的賦值語(yǔ)句，其中op是一元運(yùn)算符。（3）x=y形式的賦值語(yǔ)句。（4）無條件轉(zhuǎn)移語(yǔ)句gotoL，表示下一個(gè)要執(zhí)行的語(yǔ)句是標(biāo)號(hào)為L(zhǎng)的語(yǔ)句。（5）條件轉(zhuǎn)移語(yǔ)句ifxropygotoL中，rop為關(guān)系運(yùn)算符，如果x和y滿足關(guān)系rop，就轉(zhuǎn)而執(zhí)行標(biāo)號(hào)為L(zhǎng)的語(yǔ)句，否則順序執(zhí)行下一個(gè)語(yǔ)句。第二十八頁(yè)，共八十三頁(yè)，編輯于2023年，星期三（6）過程調(diào)用語(yǔ)句paramx和callp,n。源程序中的過程調(diào)用語(yǔ)句p(x1，x2，…，xn)可以產(chǎn)生如下的三地址代碼：paramx1paramx2…paramxncallp,n其中n為實(shí)參個(gè)數(shù)。過程返回語(yǔ)句形如returny，其中y為過程返回的一個(gè)值。

第二十九頁(yè)，共八十三頁(yè)，編輯于2023年，星期三（7）變址賦值：x=y[i]，把從y開始的第i個(gè)存儲(chǔ)單元的值賦給x。x[i]=y，把y的值賦給x開始的第i個(gè)存儲(chǔ)單元。其中，x，y和i都代表數(shù)據(jù)對(duì)象。（8）地址和指針賦值：x=&y，把y的地址賦給x。x=y，把y指示的地址單元中的內(nèi)容賦給x。x=y，把x指向的存儲(chǔ)單元的值置為y。第三十頁(yè)，共八十三頁(yè)，編輯于2023年，星期三2．具體實(shí)現(xiàn)四元式操作符操作數(shù)1操作數(shù)2結(jié)果結(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í)變量，由四元式優(yōu)化比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4第三十一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三操作符左操作符數(shù)右操作數(shù)表達(dá)式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三個(gè)三元式中的操作數(shù)(1)(2)表示第(1)和第(2)條三元式的計(jì)算結(jié)果。三元式第三十二頁(yè)，共八十三頁(yè)，編輯于2023年，星期三例：A=B+C*D/EF=C*D三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)*,C,D(6)=,F,(1)

不便于代碼優(yōu)化：刪除某些三元式后可能需作一系列的修改三元式(1)*,C,D(2)/,(1),E(3)+,B,(2)(4)=,A,(3)(5)=,F,(1)間接三元式執(zhí)行順序(1)(2)(3)(4)(1)(5)三元式的執(zhí)行次序用另一張表表示,優(yōu)化時(shí)三元式可以不變，僅僅改變其執(zhí)行順序表第三十三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三圖形表示法無循環(huán)有向圖(DirectedAcyclicGraph，簡(jiǎn)稱DAG)對(duì)表達(dá)式中的每個(gè)子表達(dá)式，DAG中都有一個(gè)結(jié)點(diǎn)一個(gè)內(nèi)部結(jié)點(diǎn)代表一個(gè)操作符，它的孩子代表操作數(shù)在一個(gè)DAG中代表公共子表達(dá)式的結(jié)點(diǎn)具有多個(gè)父結(jié)點(diǎn)第三十四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三例：x=y+yz+yz

抽象語(yǔ)法樹圖形表示有向無環(huán)圖第三十五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三表達(dá)式a+(-b)*c的三元式

(1)(@,b,_);單目運(yùn)算，運(yùn)算對(duì)象2為空

(2)(*,(1),c)(3)(+,a,(2))第三十六頁(yè)，共八十三頁(yè)，編輯于2023年，星期三三元式X=a+b*cY=d-b*c三元式表(1)(*,b,c)(2)(+,a,(1))(3)(=,x,(2))(4)(_,d,(1))(5)(=,y,(4))第三十七頁(yè)，共八十三頁(yè)，編輯于2023年，星期三四元式

(三地址代碼）

X=a*b+c*d的四元式序列三地址代碼(1)(*,a,b,T1)(1)T1=a*b(2)(*,c,d,T2)(2)T2=c*d(3)(+,T1,T2,T3)(3)T3=T1+T2(4)(=,T3,_,X)(4)X=T3第三十八頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

a:=b*(-c)+b*(-c)的圖表示法

assigna+*buminuscDAGassigna+*buminusc抽象語(yǔ)法樹*buminusc第三十九頁(yè)，共八十三頁(yè)，編輯于2023年，星期三抽象語(yǔ)法樹對(duì)應(yīng)的代碼：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5assigna+*buminusc抽象語(yǔ)法樹*buminusc第四十頁(yè)，共八十三頁(yè)，編輯于2023年，星期三DAG對(duì)應(yīng)的代碼：T1:=-cT2:=b*T1T5:=T2+T2a:=T5assigna+*buminuscDAG抽象語(yǔ)法樹對(duì)應(yīng)的代碼：

T1:=-c T2:=b*T1

T3:=-c T4:=b*T3 T5:=T2+T4

a:=T5第四十一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

屬性翻譯文法的應(yīng)用

綜合屬性與自下而上定值

每個(gè)非終結(jié)符的屬性值都是根據(jù)位于其下面那些符號(hào)的屬性值來確定的，即按一種自下而上的方式來確定的。繼承屬性和自上而下定值

非終結(jié)符的屬性值或者根據(jù)其上層非終結(jié)符的屬性來確定或者根據(jù)產(chǎn)生式右部其它符號(hào)的屬性來確定。這種屬性值是根據(jù)自上而下方式確定的。第四十二頁(yè)，共八十三頁(yè)，編輯于2023年，星期三自底向上的語(yǔ)法制導(dǎo)翻譯自底向上的語(yǔ)法制導(dǎo)翻譯方法是在自底向上的語(yǔ)法分析過程中逐步實(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)生式的改造等）第四十三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三算術(shù)表達(dá)式和賦值語(yǔ)句的翻譯翻譯步驟：（1）分析文法的特點(diǎn)；（2）設(shè)計(jì)一系列的語(yǔ)義變量、定義語(yǔ)義過程、語(yǔ)義函數(shù)；（3）設(shè)計(jì)每一條規(guī)則的語(yǔ)義子程序；（4）增加一個(gè)語(yǔ)義信息棧，構(gòu)造LR分析表;(5)語(yǔ)法分析同時(shí)語(yǔ)義處理.第四十四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三例：有文法G[A]：1.A→i:=E2.E→E+T∣T3.T→T*F∣F4.F→－P5.P→i∣(E)

簡(jiǎn)單算術(shù)表達(dá)式的計(jì)值順序與四元式出現(xiàn)的順序相同,因此目標(biāo)代碼的順序(結(jié)構(gòu))為:(1)先生成E的代碼(一系列順序執(zhí)行的四元式)(2)把E的值賦給變量i(表達(dá)式的結(jié)果賦給賦值語(yǔ)句的左變量)第四十五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三引入語(yǔ)義變量,語(yǔ)義過程和語(yǔ)義函數(shù)(1)語(yǔ)義變量E.place:表示存放E值的變量名在符號(hào)表中的入口地址或臨時(shí)變量的整數(shù)碼.(2)語(yǔ)義函數(shù)newtemp():申請(qǐng)一個(gè)臨時(shí)單元,存放中間結(jié)果;(3)語(yǔ)義過程emit(T=arg1oparg2):產(chǎn)生一條四元式,并添入四元式表中;(4)語(yǔ)義過程lookup():審查是否出現(xiàn)在符號(hào)表中,在:返回地址,不在:返回NULL;(5)語(yǔ)義函數(shù)entry(i):回送標(biāo)識(shí)符i在符號(hào)表中的入口地址.第四十六頁(yè)，共八十三頁(yè)，編輯于2023年，星期三表達(dá)式的語(yǔ)義動(dòng)作設(shè)計(jì)1.A→i:=E{emit(entry(i)=E.place}2.E→E1+T{E.place=newtemp(),emit(E.place)=E1.place+T.place}3.E→T{E.place=newtemp(),emit(E.place=T.place)}4.T→T1*F{T.place=newtemp(),emit(T.place)=T1.place*F.place}5.T→F{T.place=newtemp(),emit(T.place=F.place)}第四十七頁(yè)，共八十三頁(yè)，編輯于2023年，星期三6.F→_P{F.place=newtemp(),emit(F.place)=@P.place}7.P→(E){P.place=newtemp(),emit(P.place=E.place)}8.P→i{P.place=newtemp(),emit(P.place=Entry(i))}第四十八頁(yè)，共八十三頁(yè)，編輯于2023年，星期三例如:表達(dá)式X:=a+b*(c-d)的翻譯K+1:T1:=c-dK+2:T2=b*T1K+3:T3:=a+T2K+4:X:=T3(-,c,d,T1)(*,b,T1,T2)(+,a,T2,T3)(:=,T3,_,X)第四十九頁(yè)，共八十三頁(yè)，編輯于2023年，星期三布爾表達(dá)式的翻譯布爾表達(dá)式是由布爾運(yùn)算符(and,or,not)作用于布爾變量(或常數(shù))或關(guān)系表達(dá)式而形成的。布爾表達(dá)式的作用：用作控制語(yǔ)句中的條件：if-then、while、repeat等邏輯賦值句中的邏輯運(yùn)算第五十頁(yè)，共八十三頁(yè)，編輯于2023年，星期三布爾表達(dá)式到四元式的翻譯

文法：EEEEEE(E)idEropE

其中，(and)、(or)、(not)為布爾（邏輯）運(yùn)算符；rop為關(guān)系運(yùn)算符（>，≥，，≤，=，≠）；id為布爾（邏輯）變量或布爾（邏輯）常數(shù)；EropE為關(guān)系表達(dá)式。布爾表達(dá)式的求值方法：①通過逐步計(jì)算出各部分的值來計(jì)算整個(gè)表達(dá)式。②利用布爾運(yùn)算符的性質(zhì)計(jì)算其值第五十一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三布爾表達(dá)式作為控制語(yǔ)句中的條件式作用是用于選擇下一個(gè)執(zhí)行點(diǎn)

whileEdoS1E的作用是選擇S1執(zhí)行,還是跳過S1語(yǔ)句,執(zhí)行S1后面的語(yǔ)句E有兩個(gè)出口:真:S1語(yǔ)句假:S1后面的語(yǔ)句第五十二頁(yè)，共八十三頁(yè)，編輯于2023年，星期三While語(yǔ)句的目標(biāo)結(jié)構(gòu)

假E的代碼真

whilleS1的代碼

doJMPW.headW.head第五十三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三布爾初等量(布爾變量和關(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)ifEgotoLi(jumpt,E,_,Li)

(jnz,A,_,Li)(2)ifE1ropE2gotoLi(jumpθ,E1,E2,Li)

(jrop,E1,E2,Li)例:(j<,a,b,p)(3)gotoLj(jumpLj)(j,_,_,Lj)第五十四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三舉例:ifa<bthenA:=x+y的四元式序列

ifa<bgotoLi(真出口)gotoLj(假出口)Li:S的第一個(gè)四元式…S的最后一個(gè)四元式Lj:S后面的語(yǔ)句(1)ifa<bgoto(3)(2)goto(5)(3)T1:=x+y(4)A:=T1(5)第五十五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

多因子組成的布爾表達(dá)式的翻譯例:ifa<b∨cthenS1elseS2分析結(jié)果如下:當(dāng)a<b為真,執(zhí)行S1,不需要計(jì)算c的值當(dāng)a<b為假,計(jì)算c的值,c為真:執(zhí)行S1,為假:執(zhí)行S2當(dāng)a<b與c分別為真時(shí),程序轉(zhuǎn)向一致,真出口相同(S1)當(dāng)a<b與c分別為假時(shí),程序轉(zhuǎn)向一致,假出口相同(S2)第五十六頁(yè)，共八十三頁(yè)，編輯于2023年，星期三ifa<b∨cthenS1elseS2的四元式序列(1)ifa<bgotoS1的第一條語(yǔ)句(5)(2)goto(3)(3)ifcgotoS1的第一條語(yǔ)句(5)(4)gotoS2的第一條語(yǔ)句(p+1(5)關(guān)于S1的四元式序列

…

(p)Gotoq(p+1)關(guān)于S2的四元式序列

…

(q)后繼四元式目標(biāo)結(jié)構(gòu)E的代碼TFS1的代碼JUMPSS2的代碼S（后繼語(yǔ)句）第五十七頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

ifEthenS1elseS2

的四元式序列(1)ifEgoto(3)(2)goto(S2的第一個(gè)四元式)(p+1)(3)關(guān)于S1的四元式序列……(p)gotor(執(zhí)行完S1后轉(zhuǎn)出)(p+1)關(guān)于S2的四元式序列……(r)后繼四元式第五十八頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

whileEdoS1的四元式序列(1)ifEgoto(3)(2)goto(S1后面的語(yǔ)句)(p+1)(3)關(guān)于S1的四元式序列……(p)goto(1)(p+1)后繼四元式第五十九頁(yè)，共八十三頁(yè)，編輯于2023年，星期三真出口鏈、假出口鏈、回填（Backparch)在多個(gè)因子組成的布爾表達(dá)式中，可能有多個(gè)因子的真出口或假出口的轉(zhuǎn)移去向相同，但又不能立刻知道具體轉(zhuǎn)向位置。把轉(zhuǎn)移方向相同的四元式鏈在一起，一旦發(fā)現(xiàn)具體轉(zhuǎn)移目標(biāo)，就回填。真出口用Etrue來表示。假出口用Efalse來表示。回填Backparch（g,t)將t填入由g所指向的四元式的結(jié)果部分第六十頁(yè)，共八十三頁(yè)，編輯于2023年，星期三ifa<b∨cthenS1elseS2

的真假出口回填描述(1)ifa<bgoto0/E的真出口Etrue有待回填(2)goto(3)/*回填E的第一個(gè)假出口(3)ifcgoto(1)/*（3）是E的真出口鏈(4)goto0/*E的假出口Efalse有待回填(5)關(guān)于S1的四元式序列/*此時(shí)回填真出口Etrue

…

(p)goto0/*有待回填q的位置(p+1)關(guān)于S2的四元式序列/*此時(shí)回填假出口Efalse

…

(q)后繼四元式/*此時(shí)回填q第六十一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三語(yǔ)法制導(dǎo)翻譯中使用的公共變量、過程和函數(shù)

guad:四元式指針(表示四元式的編號(hào)或地址)GEN(X):生成一條四元式,把它放到四元式表的尾部,(和前面介紹的emit功能相同)Nextguad:指向下一個(gè)即將形成的四元式的編號(hào),其初值為1,執(zhí)行一次GEN(X),Nextguad自動(dòng)加1;merg（p1,p2)函數(shù)將以p1,p2為鏈?zhǔn)椎膬蓚€(gè)四元式合并為一,返回合并后的鏈?zhǔn)椎诹?yè)，共八十三頁(yè)，編輯于2023年，星期三條件語(yǔ)句的翻譯

基本思路：①先對(duì)定義它的文法進(jìn)行改造，以便能在相應(yīng)處添加上語(yǔ)義子程序；②根據(jù)它的語(yǔ)義，設(shè)計(jì)出相應(yīng)語(yǔ)義子程序的動(dòng)作。第六十三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

if語(yǔ)句的文法S→ifEthenS1S→ifEthenS1elseS2(E是轉(zhuǎn)移條件)對(duì)ifEthenS1elseS2,其Etrue直到掃描到then,產(chǎn)生S1的第一個(gè)四元式序號(hào)時(shí),才能將該標(biāo)號(hào)作為E的真鏈填入到Etrue,而Efalse

直到掃描到else,產(chǎn)生S2的第一個(gè)四元式序號(hào)時(shí),才得到Efalse的值。第六十四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三if語(yǔ)句文法的改造(1)C→ifEthen(2)T→CS1else(3)S→TS2(4)S→CS1目標(biāo)結(jié)構(gòu)如右圖T.chainS1.chainE.true

E.falseelseIf

thenS1的代碼

JUMP0E的代碼C.chainS2.chainS2的代碼S.chain第六十五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三if語(yǔ)句的語(yǔ)義動(dòng)作(1)C→ifEthen{backpatch(Etrue,

Nextguad),C.chain=Efalse}

當(dāng)用產(chǎn)生式ifEthen進(jìn)行歸約時(shí),生成了條件E的代碼,E的假出口不能回填,通過非終結(jié)符C向后傳遞,所以引入C.chain鏈.第六十六頁(yè)，共八十三頁(yè)，編輯于2023年，星期三if語(yǔ)句的語(yǔ)義動(dòng)作(2)T→CS1else{q:=

Nextguad,emit(goto0)Backpatch(C.chain,Nextguad),T.chain=merg(S1.chain,q)}當(dāng)用產(chǎn)生式T→CS1else歸約時(shí),S1的代碼已經(jīng)形成,回填E的假出口即C.chain。此時(shí)S2

的代碼尚未形成,S1的轉(zhuǎn)出鏈和JMP轉(zhuǎn)向相同,合并為一,通過T向后傳遞.第六十七頁(yè)，共八十三頁(yè)，編輯于2023年，星期三if語(yǔ)句的語(yǔ)義動(dòng)作(3)S→TS2{S.chain:=merg(T.chain,S2.chain)}(4)S→CS1{S.chain:=merg(C.chain,S1.chain)第六十八頁(yè)，共八十三頁(yè)，編輯于2023年，星期三IfA∧B∧C＞DthenifA＜BthenF:=1elseF:=0elseG:=G+1采用then與else的最近匹配原則(三地址指令)(1)ifAgoto(3)(2)goto0(13)(3)ifBgoto(5)(4)goto(2)(13)(5)ifC＞Dgoto(7)(6)goto(4)(13)(7)ifA＜Bgoto(9)(8)goto0(11)(9)F:=1(10)goto0(15)(11)F:=0(12)goto(10)(15)(13)T:=G+1(14)G:=T(15)第六十九頁(yè)，共八十三頁(yè)，編輯于2023年，星期三IfA∧B∧C＞DthenifA＜BthenF:=1elseF:=0elseG:=G+1四元式形式代碼(1)(jnz,A,_,(3))(2)(j,_,_,0)(13)(3)(jnz,B,_,(5)(4)(j,_,_,(2))(13)(5)(j>,C,D,(7))(6)(j,_,_,(4))(13)(7)(j<,A,B,(9))(8)(j,_,_,0)(11)(9)(:=,1,_,F)(10)(j,_,_,0)(15)(11)(:=,0,_,F)(12)(j,_,_,(10))(15)(13)(+,G,1,T)(14)(:=,T,_,G)(15)第七十頁(yè)，共八十三頁(yè)，編輯于2023年，星期三While語(yǔ)句的翻譯文法:G[S]S→whileEdoS

文法改造為:S→CS1C→WEdoW→while

Etrue

S1chainEfalse

do

假E的代碼

真whilleS1的代碼JMPW.headW.headC.chain第七十一頁(yè)，共八十三頁(yè)，編輯于2023年，星期三While語(yǔ)句的語(yǔ)義動(dòng)作（1）W→while{W.head:=

Nextguad;}當(dāng)用W→while歸約時(shí),Nextguad記下E的第一個(gè)四元式的位置,保留在Wguad中。（2）C→WEdo{backpatch(Etrue,Nextguad,C.chain=Efalse,C.head=W.head}當(dāng)使用C→WEdo進(jìn)行歸約時(shí),E的代碼已經(jīng)生成有兩個(gè)出口Etrue和Efalse,掃描完do后,可以回填Etrue,而Efalse要到S1語(yǔ)句全部生成后才能回填,因此為待填信息,由C向后傳遞。第七十二頁(yè)，共八十三頁(yè)，編輯于2023年，星期三While語(yǔ)句的語(yǔ)義動(dòng)作（3）SCS1

{Backpatch(S1chain,C.head);S.chain:=C.chain;GEN(goto,W.head);當(dāng)用上式進(jìn)行歸約時(shí)，S1語(yǔ)句全部產(chǎn)生，while語(yǔ)句結(jié)束應(yīng)返回，因此產(chǎn)生四元式（gotow.head),同時(shí)回填Efalse第七十三頁(yè)，共八十三頁(yè)，編輯于2023年，星期三

whilea>0∧b>0do

ifx>ythenb:=b-1elsea:=a-1

假設(shè)四元式序列從100開始編號(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)109(j,a,1,T2)110(:=,T2,_.a)111(j,_,_,100)112第七十四頁(yè)，共八十三頁(yè)，編輯于2023年，星期三文法G[S]:S→SaA︱AA→AbB︱BB→cSd︱e(1)證明AacAbcBaAdbed是文法的一個(gè)句型.(2)請(qǐng)寫出該句型的所有短語(yǔ)、素短語(yǔ)及句柄。（3）為文法G[S]的產(chǎn)生式構(gòu)造相應(yīng)的翻譯子程序，使句型AacAbcBaAdbed經(jīng)該翻譯方案翻譯后，輸出為131042521430。第七十五頁(yè)，共八十三頁(yè)，編輯于2023年，星期三文法及相應(yīng)的翻譯方案如下:S→bTc{print”1”}S→a{prin