理學(xué)語法制導(dǎo)翻譯及中間代碼

§5.1

語法制導(dǎo)翻譯語法分析后的源程序語義處理中間代碼靜態(tài)語義審查：審查每個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法結(jié)構(gòu)合法的程序，是否真正有意義。如類型檢查。

語義處理是指兩個(gè)功能：動(dòng)態(tài)語義處理：如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，即，或者將源程序翻譯成程序的一種中間表示形式（中間代碼），或者將源程序翻譯成目標(biāo)代碼。

翻譯的任務(wù)：首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼。使用的方法：語法制導(dǎo)翻譯?；舅枷耄焊鶕?jù)翻譯的需要設(shè)置文法符號(hào)的屬性，以描述語法結(jié)構(gòu)的語義。即語法制導(dǎo)翻譯法使用屬性文法為工具來描述程序設(shè)計(jì)語言的語義。1、屬性文法(Syntax-directeddefinitions)(1)屬性

對(duì)文法的每一個(gè)符號(hào)，引進(jìn)一些屬性，這些屬性代表與文法符號(hào)相關(guān)的信息,，如類型、值、存儲(chǔ)位置等。屬性值，可以在語法分析過程中計(jì)算和傳遞。屬性分為兩類:屬性加工的過程即是語義的處理過程。綜合屬性和繼承屬性。綜合屬性：其計(jì)算規(guī)則按“自下而上”方式進(jìn)行，即規(guī)則左部符號(hào)的某些屬性根據(jù)其右部符號(hào)的屬性和(或)自己的其他屬性計(jì)算而得。在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性由該結(jié)點(diǎn)的子結(jié)點(diǎn)的屬性值確定。繼承屬性：其計(jì)算規(guī)則按“自上而下”方式進(jìn)行，即規(guī)則右部符號(hào)的某些屬性根據(jù)其左部符號(hào)的屬性和(或)右部其他符號(hào)的某些屬性計(jì)算而得。繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和（或）兄弟結(jié)點(diǎn)的某些屬性值來決定的。(2)屬性文法

屬性文法包含一個(gè)上下文無關(guān)文法和一系列語義規(guī)則。語義規(guī)則：為文法的每一個(gè)規(guī)則配備的計(jì)算屬性的計(jì)算規(guī)則，(描述語義處理的加工動(dòng)作)。

這些語義規(guī)則附在文法的每個(gè)產(chǎn)生式上，在語法分析過程中，執(zhí)行語義規(guī)則描述的動(dòng)作，從而實(shí)現(xiàn)語義處理。即：附在文法的每個(gè)產(chǎn)生式上的語義規(guī)則描述了語義處理的加工動(dòng)作。A＝（G，V，F(xiàn)），

G:是一個(gè)上下文無關(guān)文法

V:有窮的屬性集,每個(gè)屬性與文法的一終結(jié)符或非終結(jié)符相連。

F:關(guān)于屬性的屬性斷言或謂詞集.每個(gè)斷言與一個(gè)產(chǎn)生式相聯(lián)。一個(gè)斷言即一個(gè)語義規(guī)則，描述各屬性關(guān)系。屬性文法是一個(gè)三元組：

屬性文法的主要思想有兩點(diǎn)：

對(duì)于每個(gè)文法符號(hào)引進(jìn)相關(guān)的屬性符號(hào)；對(duì)于每個(gè)產(chǎn)生式寫出屬性值計(jì)算的規(guī)則。例如定義表達(dá)式的文法如下：

為文法符號(hào)E引進(jìn)屬性val表示E的值，記為E.val，語義規(guī)則以賦值語句的形式給出，附在每個(gè)產(chǎn)生式后。為了明確E的不同出現(xiàn)位置，用上角標(biāo)區(qū)別。終結(jié)符n的值是詞法分析程序提供的，這里用n.lex表示。下面給出屬性文法：

E

E1+E2{E.val:=E1.val+E2.val}E

(E1){E.val:=E1.val}E

n{E.val:=n.lex}E

E+E

E

(E)

E

n給出定義表達(dá)式值的屬性文法。例1表達(dá)式計(jì)算的語法制導(dǎo)定義

產(chǎn)生式語義規(guī)則LEprint(Eval)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val+FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexvaldigitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=2+digitlexval:=2Fval:=2Tval:=2Eval:=17L例2：輸入2＋3*5◆只有綜合屬性例2：變量說明的類型定義inta,b,c

產(chǎn)生式語義規(guī)則

DTLL

in:=T

typeTintTtype:=integerTrealTtype:=realLL1,idL1in:=Linaddtype(identry,Lin)Lidaddtype(identry,Lin)將L.in的屬性值置為該說明語句T指定的類型把每個(gè)標(biāo)識(shí)符的類型信息登錄在符號(hào)表相關(guān)項(xiàng)中（虛屬性）非終結(jié)符T有一綜合屬性type，它的值由關(guān)鍵字決定（int或real）。與產(chǎn)生式D→TL相聯(lián)的語義規(guī)則L.in:=T.type，將L.in的屬性值置為該說明語句指定的類型。屬性L.in被沿著語法樹下傳到下邊結(jié)點(diǎn)，與L產(chǎn)生式相聯(lián)的規(guī)則里使用了它。TLLid3Lid2Did1int,,1entry2entry3entry4type5in6in7in例如：inta,b,c◆具有繼承屬性的屬性文法2、語法制導(dǎo)翻譯只含有綜合屬性的稱為S－屬性文法綜合屬性可以在分析輸入符號(hào)串的同時(shí)采用自下而上的分析器來計(jì)算。分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來計(jì)算。S－屬性文法的翻譯器很容易建立。通?？山柚贚R分析器實(shí)現(xiàn)。

在語法分析過程中，依隨分析的過程，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語義子程序(或語義規(guī)則描述的語義處理的加工動(dòng)作)進(jìn)行翻譯的方法。ＬＲ分析器模型總控程序outputInput#ACTIONGOTOLR分析表?xiàng)顟B(tài)符號(hào)語義S1X1S0#－V1………S1XmVm例如：２＋３*５的分析和計(jì)值過程步驟動(dòng)作狀態(tài)棧語義棧(值棧)符號(hào)棧余留輸入串１）0－＃２＋3*５＃２）05－－＃2＋3*５＃３）r603－２＃Ｆ＋３*５＃４）r402－２＃Ｔ＋３*５＃５）r201－２＃Ｅ＋３*５＃６）016－２－＃Ｅ＋３*５＃７）0165－２－－＃Ｅ＋３*５＃８）r60163－２－３＃Ｅ＋Ｆ*５＃９）r40169－２－３＃Ｅ＋Ｔ*５＃１０）01697－２－３－＃Ｅ＋Ｔ*５＃１１）016975-２－３－－＃Ｅ＋Ｔ*５＃１２）r601697510－２－３－５＃Ｅ＋Ｔ*Ｆ#１３）ｒ３０１６９－２－（15）＃Ｅ＋Ｔ＃１４）ｒ１０１－（１７）＃Ｅ＃１５）接受§5.2

中間代碼形式

“中間代碼生成”程序的任務(wù)是：把經(jīng)過語法分析和語義分析而獲得的源程序中間表示翻譯為中間代碼表示。方法：語法制導(dǎo)翻譯。采用獨(dú)立于機(jī)器的中間代碼的好處：便于編譯系統(tǒng)的建立和編譯系統(tǒng)的移植；便于進(jìn)行獨(dú)立于機(jī)器的代碼優(yōu)化工作。中間代碼表示形式有：語法樹后綴式三地址代碼表示（三元式、四元式）1）后綴式表示：將運(yùn)算對(duì)象寫在前面，運(yùn)算符號(hào)寫在后面。a+b寫成ab+特點(diǎn)：①運(yùn)算符處于運(yùn)算量之后；②運(yùn)算符在表示式中出現(xiàn)的次序和計(jì)算的先后次序一致；③不用括號(hào)；④易于計(jì)算機(jī)處理表達(dá)式。利用棧自左至右掃描表達(dá)式后綴表示，碰到運(yùn)算對(duì)象入棧；碰到運(yùn)算符，則執(zhí)行相應(yīng)運(yùn)算（出棧），結(jié)果入棧，最后結(jié)果留在棧頂。

語法制導(dǎo)生成后綴式舉例：

E.code:=E1.code||E2.code|op|)E.code:=E1.codeE.code:=idE→E1opE2E→(E1)E→id

產(chǎn)生式語義規(guī)則”||”為捻接運(yùn)算，在機(jī)器內(nèi)實(shí)現(xiàn)是通過數(shù)組，利用post數(shù)組存放后綴式，k為下標(biāo)，初值為1。則：當(dāng)用產(chǎn)生式E→E1+E2

歸約句柄E1+E2

時(shí)，分別與E1、E2相關(guān)的后綴式子串E1.nptr、E2.nptr均已在post中，只需將運(yùn)算符“+”放入post即可。Post[p]:=“op”,p:=p+1Post[p]:=“id”,p:=p+1例：E→E+T{Post[p]:=“+”,p:=p+1}E→TT→T*F{}{Post[p]:=“*”,p:=p+1}T→FF→(E){}{}F→i

{Post[p]:=“i”,p:=p+1}a+b*c生成后綴式分析棧當(dāng)前符號(hào)余留輸入串操作后綴表示#a＋b*c＃移進(jìn)#a+b*c#歸約a#F+b*c#歸約#T+b*c#歸約#E+b*c#移進(jìn)#E+b*c#移進(jìn)#E+b*c#歸約ab#E+F*c#歸約#E+T*c#移進(jìn)#E+T*c#移進(jìn)#E+T*c#歸約abc#E+T*F#歸約abc*#E+T#歸約abc*+#E2）四元式

四元式：是一種更接近目標(biāo)代碼的中間代碼形式，由于該形式的中間代碼便于優(yōu)化處理，因此得到廣泛應(yīng)用?？捎靡环N“三地址語句”等價(jià)表示，一般形式為：（op，arg1，arg2，result）Op為運(yùn)算符；Arg1，arg2為兩個(gè)運(yùn)算對(duì)象：變量、常量、臨時(shí)變量；Result中存放運(yùn)算結(jié)果。①每個(gè)四元式只能有一個(gè)運(yùn)算符，因此一個(gè)復(fù)雜表達(dá)式可由多個(gè)四元式構(gòu)成的序列表示。例：A+B*C寫成：（*，B，C，T1）（+，A，T1，T2）②若op為一元、零元(無條件轉(zhuǎn)移)時(shí)，arg1、arg2可省略。③會(huì)引入一些臨時(shí)變量。注意！3）三元式

一般形式為：（i）（op，arg1，arg2）其中：(i)為三元式編碼，也代表了該式的運(yùn)算結(jié)果。

例：a:=-b*(c+d)其三元式表示寫成：（1）(-，b，

)

（2）(+，c，d)

（3）(*，(1)，(2))

（4）(:=，a，（3）)

特點(diǎn)：三元式比四元式空間少；三元式間的相互引用頻繁，因此不便于優(yōu)化。為此引入間接三元式。1、輔助函數(shù)：1）LOOKUP（name）：以name（變量名）查符號(hào)表，若在符號(hào)中，則將其表項(xiàng)位置（入口位置）作為L(zhǎng)OOKUP的值，否則，取值為null。2）ENTER（name）：在符號(hào)表中以名字name新登記一項(xiàng)，并將此項(xiàng)的位置作為enter值。§5.3簡(jiǎn)單賦值語句的翻譯3）ENTRY（name）：以name為名查、添符號(hào)表，描述為：functionentry(name){entry:=lookup(name);ifentry=nullthenentry:=enter(name)}對(duì)于先說明后使用的語言，若在翻譯表達(dá)式時(shí)，遇到的變量名不在表中，則程序出錯(cuò)。即ifentry=nullthenerror5）GEN（op，arg1，arg2，result）：產(chǎn)生一個(gè)四元式將它送入四元式表中，并以此四元式在四元式表中的位置作為返回值。4)Newtemp函數(shù)，產(chǎn)生一個(gè)新的臨時(shí)變量。返回值為標(biāo)識(shí)此臨時(shí)變量的整數(shù)碼。6)E.place屬性：表示存放E值的變量名在符號(hào)表的入口或整數(shù)碼（若E是臨時(shí)變量）。

S→id:=EGEN(:=，E.place，_，ENTRY(id)

)E→E1+E2E.place:=newtemp;GEN(+，E1.place，E2.place，E.place)E→E1*E2E.place:=newtemp;GEN(*，E1.place，E2.place，E.place)E→-E1E.place:=newtemp;GEN(-，E1.place，_

，E.place)

E→(E1)E.place:=E1.place;

E→idE.place:=ENTRY（id）

產(chǎn)生式語義規(guī)則實(shí)例2、賦值語句的屬性文法分析棧當(dāng)前符號(hào)余留輸入串語義棧place四元式#A:=B*(C+D)#A:=B*(C+D)A#A:=B*(C+D)A_#A:=B*(C+D)A_B，歸約#A:=E*(C+D)A_B#A:=E*(C+D)A_B_#A:=E*(C+D)A_B__#A:=E*(C+D)A_B__C,歸約#A:=E*(E+D)A_B__C#A:=E*(E+D)A_B__C_#A:=E*(E+D)#A_B__C_D,歸約#A:=E*(E+E)#A_B__C_D,歸約(+,C,D,T1)#A:=E*(E)A_B__T1#A:=E*(E)#A_B__T1_,歸約#A:=E*E#A_B_T1,歸約(*,T1,B,T2)#A:=E#A_T2,歸約(:=,T2,-,A)#E#ACC例如：A:=B*（C+D）文法

實(shí)際上：在表達(dá)式運(yùn)算中要考慮是否類型沖突，若有，需進(jìn)行類型轉(zhuǎn)換。S→id:=Eifid.type=int&E.type=int

thenGEN(:=，E.place，-，id.place)

Else

ifid.type=real&E.type=real

thenGEN(:=，E.place，-，id.place)

Elseifid.type=int&E.type=real

then{T:=newtemp;GEN(itr，id.place，-，T)GEN(:=，E.place，-，T)}

Elseifid.type=real&E.type=int

then{T:=newtemp;GEN(itr，E.place，-，T)GEN(:=，T，-，id.place)}產(chǎn)生式語義規(guī)則1、布爾表達(dá)式:

用布爾運(yùn)算符號(hào)（∧，∨，┐）作用到布爾變量或關(guān)系表達(dá)式上而組成的表達(dá)式?！舨紶柋磉_(dá)式的作用：

1.計(jì)算邏輯值，注意計(jì)算時(shí)的優(yōu)先級(jí)。

2.控制流語句，如if-then，if-then-else和while-do語句中的條件表達(dá)式◆本節(jié)考慮由如下文法生成的布爾表達(dá)式：

E→E∧E|E∨E|┐E|(E)|idropid|true|false§5.4布爾表達(dá)式的翻譯

方法一：用數(shù)值表示真假，對(duì)布爾表達(dá)式的求值可如同算術(shù)表達(dá)式求值一步步計(jì)算。例如：A∨B∧C，其四元式為:(∧，B，C，T1)(∨，A，T1，T2）

方法二：采取某種優(yōu)化措施。即將任何布爾表達(dá)式描述為等價(jià)的if-then-else結(jié)構(gòu)。例A∨B:ifAthentrueelseifBthentrueelsefalseA∧B：ifAthenifBthentrueelsefalseelsefalse┐A：ifAthenfalseelsetrue

方法一很容易寫出相應(yīng)的四元式，從而表示出每個(gè)產(chǎn)生式的語義動(dòng)作。2、布爾表達(dá)式的翻譯方法

方法二涉及如何翻譯if-then-else結(jié)構(gòu)的問題。3、作為條件控制的布爾式翻譯E.codeS1.codeE.true:S2.codeE.false:gotoS.next...S.next:toE.truetoE.false(a)if-then-elseif-then？1）條件語句ifEthenS1elseS2

E的作用在于控制對(duì)S1、S2的選擇，因此結(jié)果無需最終保留。通過程序的控制流，即用程序中控制轉(zhuǎn)移到達(dá)的位置來表示布爾表達(dá)式的值。對(duì)作為轉(zhuǎn)移條件的布爾式，其轉(zhuǎn)移可用下述三種四元式表示：(jnz，A，-，P)：若A為真(1或非0)則轉(zhuǎn)向第P四元式(jrop，A1，A2，P)：若A1ropA2為真，則轉(zhuǎn)向第P四元式(j，-，-，P)：無條件轉(zhuǎn)向P四元式例如：ifA∨B<DthenS1elseS2翻譯成四元式為：（1）(jnz，A，-，？)A的真出口（2）（j，-，-，？）A的假出口（3）（j<，B，D，?）B<D的真出口（4）（j，-，-，？）B<D的假出口（5）關(guān)于S1的四元式┆（P）（j，-，-，？）跳過S2的代碼段（P+1）關(guān)于S2的四元式┆（q）s2后的語句355P+1q(j>=,B,D,P+1)(3)(4)合并改寫(2)可刪除可優(yōu)化嗎？分析(1)~(4)是布爾式A∨B<D的代碼，他們?nèi)菞l件轉(zhuǎn)移或無條件轉(zhuǎn)移四元式，取代了原來的布爾運(yùn)算。A的真出口和B<D的真出口相同—(5)S1的第一個(gè)四元式(布爾式的真出口)A的假出口為B<D的第一個(gè)四元式。B<D的假出口是整個(gè)布爾式的假出口—S2的第一個(gè)四元式。(2)四元式可刪除，(3)、(4)也可合并—代碼優(yōu)化。翻譯布爾式時(shí)要解決的問題1、確定每個(gè)四元式的第四項(xiàng)，即轉(zhuǎn)向的位置——真假出口2、拉鏈、回填問題1：確定一個(gè)布爾表達(dá)式的真假出口E→E(1)∨E(2)

若E(1)為真，則E為真，因此E(1)的真出口是E的真出口

若E(1)為假，則計(jì)算E(2)∴

E(1)的假出口為E(2)的第一個(gè)四元式∴

E(2)的真假即為E的真假出口E1.TCE2.FCE1E2E.TCE2.TCE1.FCE.FCT，E為TF，E為FE→E(1)∧E(2):

若E(1)為假，則E為假，因此E(1)的假出口是E的假出口若E(1)為真，則計(jì)算E(2)∴

E(2)的真假即為E的真假出口∴

E(1)的真出口為E(2)的第一個(gè)四元式E1.FCE2.TCE1E2E.FCE2.FCE1.TCE.TCT，E為TF，E為FE→┐E(1)：

E(1)的真出口是E的假出口；E(1)的假出口是E的真出口。問題2：拉鏈、回填翻譯過程中常出現(xiàn)若干轉(zhuǎn)移四元式轉(zhuǎn)向同一目標(biāo)。但此目標(biāo)的具體位置未確定。將這些四元式用“拉鏈”的方法鏈接起來，用一指針指向鏈頭，在確定了目標(biāo)四元式后，再“回填”此鏈。對(duì)一個(gè)布爾表達(dá)式E，應(yīng)有兩條鏈：真出口鏈（T鏈）假出口鏈（F鏈）用屬性

E·TC，E·FC記錄。

（1）（jnz，A，-，0）（2）（j，-，-，0）（3）（j<，B，D，0）（4）（j，-，-，0）（5）關(guān)于S1的四元式┆（P）關(guān)于S2的四元式13

E·TC

E·FC拉鏈回填55P例：ifA∨B<DthenS1elseS2回填

為了方便對(duì)布爾式生成相應(yīng)的四元式，可對(duì)上述文法進(jìn)行改寫，以利于編制相應(yīng)的語義子程序。

E→E∧E|E∨E|┐E|(E）|idropid|idE∧→E∧E∨→E∨1）語義變量和語義過程為了實(shí)現(xiàn)“拉鏈”和“回填”及處理E·TC，E·FC，需定義如下變量和過程：4、布爾式四元式翻譯NXQ指示器——指示所要產(chǎn)生的下一個(gè)四元式序號(hào)(在四元式表中位置)，初值為1，每當(dāng)執(zhí)行一次GEN后，NXQ自動(dòng)加1；GEN（op，arg1，arg2，Result）

——同前，產(chǎn)生一個(gè)四元式送入四元式表中，并以此四元式在四元式表中位置作為返回值；MERGE（P1，P2）——拉鏈函數(shù)，把以P1、P2為鏈?zhǔn)椎膬蓷l鏈合并為一，作為函數(shù)值，回送合并后的鏈?zhǔn)?；BACKPATCH(P，t)——回填過程，把P所鏈接的每個(gè)四元式resule字段均填上t。2）每個(gè)產(chǎn)生式的語義子程序(1)E→id

{E·TC:=NXQ，E·FC:=NXQ+1GEN（jnz，entry(id)，-，0）

GEN（j，-，-，0）}(2)E→id1ropid2

{E·TC:=NXQ，E·FC:=NXQ+1GEN（jrop，entry(id1)，entry(id2)，-，0）

GEN（j，-，-，0）}(3)

E→(E1)

{E·TC:=E1·TC，E·FC:=E1·FC}(4)

E→┐E1{E·TC:=E1·FC，E·FC:=E1·TC}(5)E∧→E1∧{BACKPATCH(E1·TC，NXQ）

E∧

·FC:=E1·FC}(6)E→E∧E2{E·TC:=E2·TC，

E·FC:=MERGE(E∧·FC，E2·FC)}{E·FC:=E2·FC，

E·TC:=MERGE(E∨·TC，E2·TC)}(7)E∨→E1∨{BACKPATCH(E1·FC，NXQ）

E∨·TC:=E1·TC}(8)E→E∨E2例:重新考慮表達(dá)式a＜borc＜dande＜f

一棵作了注釋的分析樹如下圖所示E.T={100,104}E.F={103,105}E1.T={100}E1.F={101}E4.T={104}E4.F={103,105}ORa<bE2.T={102}E2.F={103}E3.T={104}E3.F={105}andc<edf<100:(j<，a，b，0)101:(j，-，-，0)102:(j＜，c，d，0)103:(j，-，-，0)104:(j＜，e，f，0)105:(j，-，-，0)104103拉鏈102100回填E.FC鏈?zhǔn)譋.TC鏈?zhǔn)譨＜borc＜dande＜f的四元式

回填拉鏈對(duì)于翻譯后最終歸約所得的E，具有兩個(gè)語義屬性E.TC、E.FC，分別指向?qū)?yīng)四元式序列的T鏈、F鏈，這兩個(gè)鏈的回填，需根據(jù)E所處的程序環(huán)境進(jìn)一步處理：注意

若E用于條件語句if-then-else時(shí)，則當(dāng)掃視到then時(shí)，應(yīng)以當(dāng)前NXQ值回填E的T鏈，對(duì)F鏈，則在掃視到else之后進(jìn)行。注意若E僅用于計(jì)算值，可引入臨時(shí)變量t表示E計(jì)算結(jié)果，拓廣文法S’→E，該產(chǎn)生式語義動(dòng)作為：NXQNXQ+1NXQ+2{t：=NEWTEMP；

BACKPATCH(E·TC，NXQ），

BACKPATCH(E·FC，NXQ+2），

GEN（:=，’1’，-，t），

GEN（j，-，-，0），

GEN（:=，’0’，-，t}常見控制語句文法G[S]：（1）S→ifEthenS

（2）|ifEthenSelseS

（3）|whileEdoS

（4）|beginLend

（5）|SA

（6）L→L；S

（7）|S§5.5控制語句的翻譯

S：語句 L：語句串

SA：賦值語句E：布爾表達(dá)式

例：ifEthenS1elseS2E.TC只有在掃描到then之后才能確定；

E.FC只有在處理了S1之后，到達(dá)else時(shí)才能明確。因此，E.FC應(yīng)傳遞下去，以便到達(dá)相應(yīng)的else回填。

布爾式E的兩項(xiàng)語義值E.TC，E.FC，分別指示尚待回填“真”、“假”出口的四元式。

另外，S1語句執(zhí)行后產(chǎn)生(j,-,-,0)，使控制離開整個(gè)if語句。其轉(zhuǎn)移目標(biāo)應(yīng)在S2后確定。若if語句有嵌套，則即使翻譯完S2，目標(biāo)位置可能仍無法確定。1、說明由此可知，轉(zhuǎn)移目標(biāo)的去向和語句所處的環(huán)境緊密相關(guān)。解決辦法：為非終結(jié)符S（和L）加上語義屬性chain，S.chain或L.chain指示一條鏈的鏈頭，該鏈將所有控制轉(zhuǎn)出內(nèi)層語句S的各個(gè)四元式連接(拉鏈)，在適當(dāng)時(shí)候進(jìn)行回填。對(duì)于while語句中的布爾式E，其假出口也將使控制離開整個(gè)while語句，同樣采用S.chain指示跳出while的鏈頭，待處理while語句的外層語句時(shí)回填。E.codeE.true:S1.code...toE.TtoE.F(S.chain)2、控制語句的翻譯(a)While-do語句結(jié)構(gòu)1）結(jié)構(gòu)分析E.codeS1.codeE.true:S2.codeE.false:gotoS.chain...S.chain:to

E.trueto

E.false(b)if-then-else語句結(jié)構(gòu)

為了在翻譯過程中及時(shí)進(jìn)行拉鏈或回填處理，將文法G[S]改寫為G’[S]：（1）C→ifEthen（2)TP→CSelse（3）S→CS（4）S→TPS（5）Ls→L;（6）L→LsS（7）L→S（8）W→while

（9）Wd→WEdo

（10）S→WdS（11）S→beginLend（12）S→SA在s1和s2間插入一個(gè)跳轉(zhuǎn)四元式用W.quad記錄當(dāng)前四元組的NXQ,為了跳回循環(huán)反填E的真出口，為下一個(gè)四元式。從；斷開，用S的第一個(gè)四元式反填。2）文法改寫（1）C→ifEthen（2）S→CS1

3）產(chǎn)生式語義子程序描述{backpatch（E.TC，NXQ）；

C.chain=E.FC}/*IF-THEN語句的出口為E.FC*/{S.chain=MERGE(C.chain，S1.chain)

}/*C出口與S1的出口一致，均為S出口，因此合并*/注意：語義值S.chain將暫時(shí)保留在語義棧中，后續(xù)歸約過程的適當(dāng)時(shí)候，它所指的鏈會(huì)被回填。/*C為條件子句*/（3）TP→CS1else

{q=NXQ;GEN(J,-,-,0);BACKPATCH(C.chain，NXQ);

/*else后第一個(gè)四元式*/TP.chain=MERGE(q，s1.chain)

}/*S1代碼執(zhí)行后，同樣出控制，與q的出口以及與TP出口一致*//*TP為真部子句*/C.codeS1.codeE.TCqE.FCTP.chain＝C.chain（4）S→

TPS2

（5）W→While（6）Wd→WEdo{S.chain=MERGE(TP.chain，s2.chain)}/*S2的出口和TP(整個(gè)if語句)出口是一致的*/{W.quad=NXQ}/*用W.quad屬性記錄while語句首位置*/{backpatch(E.TC，NXQ);Wd.chain=E.FC;Wd.quad=W.quad}/*對(duì)E.TC回填，E.FC為while出口，Wd.chain與Wd.quad需進(jìn)一步傳遞*//*Wd為while子句*/（7）S→Wd

S1（8）S→A{backpatch(S1.chain，Wd.quad);

/*S1執(zhí)行完后出口為while語句*/

GEN(J，-，-，Wd.quad);S.chain=Wd.chain;

}{

S.chain=0

}/*賦值語句不發(fā)生控制轉(zhuǎn)移，因此S的出口鏈為空鏈*/（9）L→S{L.chain=S.chain

}/*按此式歸約時(shí)，S的四元式已產(chǎn)生，由S.chain指示的四元式鏈的鏈頭傳遞給L.chain，以便適當(dāng)時(shí)機(jī)回填。*/（10）Ls→L；（11）L→LsS（12）S→beginLend{backpatch(L.chain=NXQ)}/*L的四元式已產(chǎn)生，并且已掃描到L的語句結(jié)束符；執(zhí)行完L后應(yīng)將控制轉(zhuǎn)移到分號(hào)后的語句。*/{L.chain=S.chain}

/*S后控制應(yīng)轉(zhuǎn)向的目標(biāo)尚待回填，故將有S.chain所指示的四元式鏈頭傳遞給L.chain。*/{S.chain=L.chain}例：將While(A<B)doIf(C<D)thenX:=Y+Z

翻譯成四元式。按照文法G’[S]，該語句的生成樹為：whileWEdoWdifEthenY+ZA<BCX:=ESSSC<D1、按W→While歸約{W.quad=NXQ}W.quadNXQ=100:分析語義，產(chǎn)生四元式2、E→id1ropid2

{E·TC:=NXQ，E·FC:=NXQ+1GEN（jrop，entry(id1)，entry(id2)，-，0）

GEN（j，-，-，0）}

（j<，A，B，0）W.quadE.TC=100:（j，－，－，0）E.FC=101:NXQ=102:3、

Wd→WE

do{backpatch(E.TC，NXQ);Wd.chain=E.FC;Wd.quad=W.quad}分析語義，產(chǎn)生四元式（j<，－，－，0）E.FC=101:NXQ=102:Wd.chainW.quad（j<，A，B，0）E.TC=100:Wd.quad1024、E→id1ropid2

{E·TC:=NXQ，E·FC:=NXQ+1GEN（jrop，entry(id1)，entry(id2)，-，0）

GEN（j，-，-，0）}

NXQ=102:（j<，A，B，0）W.quad100：（j<，－，－，0）E.FC=101:Wd.chainWd.quad102（j<，C，D，0）NXQ+1=103:E.TC（j，－，－，0）E.FCNXQ=104:分析語義，產(chǎn)生四元式5、C→ifEthen

{backpatch（E.TC，NXQ）；

C.chain=E.FC}

NXQ=102:（j<，A，B，0）W.quad100:（j<，－，－，0）E.FC=101:Wd.chainWd.quad102（j<，C，D，0）NXQ+1=103:E.TC（j，－，－，0）E.FCNXQ=104:104C.chain分析語義，產(chǎn)生四元式6、E→E1+E2

｛E.place:=newtemp;GEN(+，E1.place，E2.place，E.place)}7、AS→id:=E

｛GEN(:=，E.place，_，ENTRY(id)}/*賦值語句*/分析語義，產(chǎn)生四元式102:（j<，A，B，0）W.quad100：（j<，－，－，0）E.FC=101:Wd.chainWd.quad102（j<，C，D，104）NXQ+1=103:（j，－，－，0）E.FCNXQ=104:C.chain（＋，Y，Z，T）NXQ=106:105:（:=，T，－，X）8、S1→SA

{S1.chain=0}

/*賦值語句不發(fā)生控制轉(zhuǎn)移，因此S的出口鏈為空鏈*/9、S→CS1

｛S.chain=MERGE(C.chain，S1.chain)}分析語義，產(chǎn)生四元式102:（j<，A，B，0）W.quad100:（j<，－，－，0）E.FC=101:Wd.chainWd.quad102（j<，C，D，104）NXQ+1=103:（j，－，－，0