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

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

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

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

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

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

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

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

分析樹

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

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

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

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

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

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

中間代碼：一種介于源語言和目標語言之間的中間語言形式5.３中間代碼第24頁，共83頁，2023年，2月20日，星期日中綴表示后綴表示

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

第29頁，共83頁，2023年，2月20日，星期日（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。第30頁，共83頁，2023年，2月20日，星期日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第31頁，共83頁，2023年，2月20日，星期日操作符左操作符數(shù)右操作數(shù)表達式的三元式：w*x+(y+z)(1)*,w,x(2)+,y,z(3)+,(1),(2)第三個三元式中的操作數(shù)(1)(2)表示第(1)和第(2)條三元式的計算結(jié)果。三元式第32頁，共83頁，2023年，2月20日，星期日例：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í)行順序表第33頁，共83頁，2023年，2月20日，星期日圖形表示法無循環(huán)有向圖(DirectedAcyclicGraph，簡稱DAG)對表達式中的每個子表達式，DAG中都有一個結(jié)點一個內(nèi)部結(jié)點代表一個操作符，它的孩子代表操作數(shù)在一個DAG中代表公共子表達式的結(jié)點具有多個父結(jié)點第34頁，共83頁，2023年，2月20日，星期日例：x=y+yz+yz

抽象語法樹圖形表示有向無環(huán)圖第35頁，共83頁，2023年，2月20日，星期日表達式a+(-b)*c的三元式

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

(2)(*,(1),c)(3)(+,a,(2))第36頁，共83頁，2023年，2月20日，星期日三元式X=a+b*cY=d-b*c三元式表(1)(*,b,c)(2)(+,a,(1))(3)(=,x,(2))(4)(_,d,(1))(5)(=,y,(4))第37頁，共83頁，2023年，2月20日，星期日四元式

(三地址代碼）

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第38頁，共83頁，2023年，2月20日，星期日

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

assigna+*buminuscDAGassigna+*buminusc抽象語法樹*buminusc第39頁，共83頁，2023年，2月20日，星期日抽象語法樹對應(yīng)的代碼：

T1:=-c T2:=b*T1

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

a:=T5assigna+*buminusc抽象語法樹*buminusc第40頁，共83頁，2023年，2月20日，星期日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第41頁，共83頁，2023年，2月20日，星期日

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

綜合屬性與自下而上定值

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

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

簡單算術(shù)表達式的計值順序與四元式出現(xiàn)的順序相同,因此目標代碼的順序(結(jié)構(gòu))為:(1)先生成E的代碼(一系列順序執(zhí)行的四元式)(2)把E的值賦給變量i(表達式的結(jié)果賦給賦值語句的左變量)第45頁，共83頁，2023年，2月20日，星期日引入語義變量,語義過程和語義函數(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):回送標識符i在符號表中的入口地址.第46頁，共83頁，2023年，2月20日，星期日表達式的語義動作設(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)}第47頁，共83頁，2023年，2月20日，星期日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))}第48頁，共83頁，2023年，2月20日，星期日例如:表達式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)第49頁，共83頁，2023年，2月20日，星期日布爾表達式的翻譯布爾表達式是由布爾運算符(and,or,not)作用于布爾變量(或常數(shù))或關(guān)系表達式而形成的。布爾表達式的作用：用作控制語句中的條件：if-then、while、repeat等邏輯賦值句中的邏輯運算第50頁，共83頁，2023年，2月20日，星期日布爾表達式到四元式的翻譯

文法：EEEEEE(E)idEropE

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

whileEdoS1E的作用是選擇S1執(zhí)行,還是跳過S1語句,執(zhí)行S1后面的語句E有兩個出口:真:S1語句假:S1后面的語句第52頁，共83頁，2023年，2月20日，星期日While語句的目標結(jié)構(gòu)

假E的代碼真

whilleS1的代碼

doJMPW.headW.head第53頁，共83頁，2023年，2月20日，星期日布爾初等量(布爾變量和關(guān)系表達式)的目標結(jié)構(gòu)

由兩個轉(zhuǎn)移四元式構(gòu)成,一個表示真出口Li,另一個表示假出口Lj,設(shè)E是一布爾變量,它的目標結(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)第54頁，共83頁，2023年，2月20日，星期日舉例: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)第55頁，共83頁，2023年，2月20日，星期日

多因子組成的布爾表達式的翻譯例:ifa<b∨cthenS1elseS2分析結(jié)果如下:當a<b為真,執(zhí)行S1,不需要計算c的值當a<b為假,計算c的值,c為真:執(zhí)行S1,為假:執(zhí)行S2當a<b與c分別為真時,程序轉(zhuǎn)向一致,真出口相同(S1)當a<b與c分別為假時,程序轉(zhuǎn)向一致,假出口相同(S2)第56頁，共83頁，2023年，2月20日，星期日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)后繼四元式目標結(jié)構(gòu)E的代碼TFS1的代碼JUMPSS2的代碼S（后繼語句）第57頁，共83頁，2023年，2月20日，星期日

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)后繼四元式第58頁，共83頁，2023年，2月20日，星期日

whileEdoS1的四元式序列(1)ifEgoto(3)(2)goto(S1后面的語句)(p+1)(3)關(guān)于S1的四元式序列……(p)goto(1)(p+1)后繼四元式第59頁，共83頁，2023年，2月20日，星期日真出口鏈、假出口鏈、回填（Backparch)在多個因子組成的布爾表達式中，可能有多個因子的真出口或假出口的轉(zhuǎn)移去向相同，但又不能立刻知道具體轉(zhuǎn)向位置。把轉(zhuǎn)移方向相同的四元式鏈在一起，一旦發(fā)現(xiàn)具體轉(zhuǎn)移目標，就回填。真出口用Etrue來表示。假出口用Efalse來表示。回填Backparch（g,t)將t填入由g所指向的四元式的結(jié)果部分第60頁，共83頁，2023年，2月20日，星期日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第61頁，共83頁，2023年，2月20日，星期日語法制導(dǎo)翻譯中使用的公共變量、過程和函數(shù)

guad:四元式指針(表示四元式的編號或地址)GEN(X):生成一條四元式,把它放到四元式表的尾部,(和前面介紹的emit功能相同)Nextguad:指向下一個即將形成的四元式的編號,其初值為1,執(zhí)行一次GEN(X),Nextguad自動加1;merg（p1,p2)函數(shù)將以p1,p2為鏈首的兩個四元式合并為一,返回合并后的鏈首第62頁，共83頁，2023年，2月20日，星期日條件語句的翻譯

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

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

直到掃描到else,產(chǎn)生S2的第一個四元式序號時,才得到Efalse的值。第64頁，共83頁，2023年，2月20日，星期日if語句文法的改造(1)C→ifEthen(2)T→CS1else(3)S→TS2(4)S→CS1目標結(jié)構(gòu)如右圖T.chainS1.chainE.true

E.falseelseIf

thenS1的代碼

JUMP0E的代碼C.chainS2.chainS2的代碼S.chain第65頁，共83頁，2023年，2月20日，星期日if語句的語義動作(1)C→ifEthen{backpatch(Etrue,

Nextguad),C.chain=Efalse}

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

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

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

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

Etrue

S1chainEfalse

do

假E的代碼

真whilleS1的代碼JMPW.headW.headC.chain第71頁，共83頁，2023年，2月20日，星期日While語句的語義動作（1）W→while{W.head:=

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

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

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第74頁，共83頁，2023年，2月20日，星期日文法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。第75頁，共83頁，2023年，2月20日，星期日文法及相應(yīng)的翻譯方案如下:S→bTc{print”1”}S→a{p