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

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

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

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

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

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

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

非終結(jié)符E、T及F都有一個綜合屬性val,符號i有一個綜合屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語義規(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第十頁，共八十三頁，編輯于2023年，星期三語法制導(dǎo)翻譯的過程語法制導(dǎo)翻譯：將語義規(guī)則與語法規(guī)則相結(jié)合，在語法分析的過程中通過執(zhí)行語義動作，計算語義屬性值，從而完成預(yù)定的翻譯工作。第十一頁，共八十三頁，編輯于2023年，星期三自底向上語法制導(dǎo)翻譯自頂向下語法制導(dǎo)翻譯語法制導(dǎo)翻譯的實現(xiàn)第十二頁，共八十三頁，編輯于2023年，星期三語法制導(dǎo)翻譯分為兩種處理方法：（1）語法制導(dǎo)定義（自底向上）：對每個產(chǎn)生式編制一個語義子程序，在進行語法分析的過程中，當(dāng)一個產(chǎn)生式獲得匹配時，就調(diào)用相應(yīng)的語義子程序?qū)崿F(xiàn)語義檢查與翻譯。這種實現(xiàn)方案隱藏了其中語義規(guī)則的計算次序等實現(xiàn)細(xì)節(jié)，不必規(guī)定翻譯順序。（2）翻譯方案（自頂向下）：在產(chǎn)生式右部的適當(dāng)位置，插入相應(yīng)的語義動作，按照分析的進程，執(zhí)行遇到的語義動作。這是一種動作與分析交錯的實現(xiàn)方案。第十三頁，共八十三頁，編輯于2023年，星期三輸入符號串

分析樹

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

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

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

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

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

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

首先，為文法的每條規(guī)則設(shè)計相應(yīng)的語義子程序；增加一個語義信息棧；在語法分析的同時做語義處理：即在用某一個產(chǎn)生式進行規(guī)約的同時，調(diào)用相應(yīng)的語義子程序完成所用規(guī)則的語義動作，并將每次動作后的值保存在語義棧中翻譯步驟第十八頁，共八十三頁，編輯于2023年，星期三計算表達(dá)式2+3*5第十九頁，共八十三頁，編輯于2023年，星期三狀態(tài)ACTIONGOTOi+*()$ETF0S5S41231S6acc2r2S7r2r23r4r4r4r44S5S48235r6r6r6r66S5S4937S5S4108S6S119r1S7r1r110r3r3r3r311r5r5r5r5G[E]：1E→E+T2E→T3T→T*F4T→F5F→(E)6F→ii+i*i第二十頁，共八十三頁，編輯于2023年，星期三表達(dá)式2+3*5的歸約過程步驟狀態(tài)棧語義棧符號棧輸入串動作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第二十一頁，共八十三頁，編輯于2023年，星期三步驟狀態(tài)棧語義棧符號棧輸入串動作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第二十二頁，共八十三頁，編輯于2023年，星期三注意句柄歸約在先，語義動作調(diào)用在后歸約時，棧內(nèi)句柄各符號的語義信息與句柄及同時出棧，整個句柄所表示的語義信息則賦給相應(yīng)產(chǎn)生式左部非終結(jié)符號的語義變量，并讓該非終結(jié)符號及語義信息同時入棧第二十三頁，共八十三頁，編輯于2023年，星期三生成中間代碼的目的(1)便于優(yōu)化(2)便于移植(3)邏輯結(jié)構(gòu)清晰常見的中間代碼形式：后綴式三地址代碼（四元式、三元式和間接三元式）圖形（抽象語法樹、有向無環(huán)圖）

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

a+bab+

a+b*cabc*+

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

第二十九頁，共八十三頁，編輯于2023年，星期三（7）變址賦值：x=y[i]，把從y開始的第i個存儲單元的值賦給x。x[i]=y，把y的值賦給x開始的第i個存儲單元。其中，x，y和i都代表數(shù)據(jù)對象。（8）地址和指針賦值：x=&y，把y的地址賦給x。x=y，把y指示的地址單元中的內(nèi)容賦給x。x=y，把x指向的存儲單元的值置為y。第三十頁，共八十三頁，編輯于2023年，星期三2．具體實現(xiàn)四元式操作符操作數(shù)1操作數(shù)2結(jié)果結(jié)果：通常是由編譯引進的臨時變量例: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)化比較方便T1=A+BT2=C+DT3=T1+T2T4=T3-EX=T4第三十一頁，共八十三頁，編輯于2023年，星期三操作符左操作符數(shù)右操作數(shù)表達(dá)式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三個三元式中的操作數(shù)(1)(2)表示第(1)和第(2)條三元式的計算結(jié)果。三元式第三十二頁，共八十三頁，編輯于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)化時三元式可以不變，僅僅改變其執(zhí)行順序表第三十三頁，共八十三頁，編輯于2023年，星期三圖形表示法無循環(huán)有向圖(DirectedAcyclicGraph，簡稱DAG)對表達(dá)式中的每個子表達(dá)式，DAG中都有一個結(jié)點一個內(nèi)部結(jié)點代表一個操作符，它的孩子代表操作數(shù)在一個DAG中代表公共子表達(dá)式的結(jié)點具有多個父結(jié)點第三十四頁，共八十三頁，編輯于2023年，星期三例：x=y+yz+yz

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

(1)(@,b,_);單目運算，運算對象2為空

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

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

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

T1:=-c T2:=b*T1

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

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

T1:=-c T2:=b*T1

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

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

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

綜合屬性與自下而上定值

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

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

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

文法：EEEEEE(E)idEropE

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

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

假E的代碼真

whilleS1的代碼

doJMPW.headW.head第五十三頁，共八十三頁，編輯于2023年，星期三布爾初等量(布爾變量和關(guān)系表達(dá)式)的目標(biāo)結(jié)構(gòu)

由兩個轉(zhuǎn)移四元式構(gòu)成,一個表示真出口Li,另一個表示假出口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)第五十四頁，共八十三頁，編輯于2023年，星期三舉例:ifa<bthenA:=x+y的四元式序列

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

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

…

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

…

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

ifEthenS1elseS2

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

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

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

…

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

…

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

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

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

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

直到掃描到else,產(chǎn)生S2的第一個四元式序號時,才得到Efalse的值。第六十四頁，共八十三頁，編輯于2023年，星期三if語句文法的改造(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第六十五頁，共八十三頁，編輯于2023年，星期三if語句的語義動作(1)C→ifEthen{backpatch(Etrue,

Nextguad),C.chain=Efalse}

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

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

的代碼尚未形成,S1的轉(zhuǎn)出鏈和JMP轉(zhuǎn)向相同,合并為一,通過T向后傳遞.第六十七頁，共八十三頁，編輯于2023年，星期三if語句的語義動作(3)S→TS2{S.chain:=merg(T.chain,S2.chain)}(4)S→CS1{S.chain:=merg(C.chain,S1.chain)第六十八頁，共八十三頁，編輯于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)第六十九頁，共八十三頁，編輯于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)第七十頁，共八十三頁，編輯于2023年，星期三While語句的翻譯文法:G[S]S→whileEdoS

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

Etrue

S1chainEfalse

do

假E的代碼

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

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

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

whilea>0∧b>0do

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