中間代碼翻譯

中間代碼翻譯1*第1頁，共70頁，2023年，2月20日，星期日靜態(tài)語義檢查和中間代碼產(chǎn)生在編譯程序中的位置如圖所示：語法分析器靜態(tài)檢查器中間代碼產(chǎn)生器優(yōu)化器2*第2頁，共70頁，2023年，2月20日，星期日

雖然源程序可以直接翻譯為目標(biāo)語言代碼，但是通常編譯程序還是采用了獨(dú)立于機(jī)器的、復(fù)雜性介于源語言與機(jī)器語言之間的中間語言。這樣做的好處是：（1）便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化；（2）使編譯程序改變目標(biāo)機(jī)更容易；（3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，以中間語言為界面，編譯前端和后端的接口更清晰。3*第3頁，共70頁，2023年，2月20日，星期日§1.語義分析概述一、語義分析的任務(wù)審查每一個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法正確的結(jié)構(gòu)是否有意義。 如：賦值語句：x:=x+y,左邊變量類型與右邊變量類型是否一致。在語義正確的基礎(chǔ)上生成一種中間代碼或目標(biāo)代碼。4*第4頁，共70頁，2023年，2月20日，星期日

二、語義分析的范圍1.確定類型：確定標(biāo)識(shí)符所關(guān)聯(lián)的數(shù)據(jù)類型。2.類型檢查：按語言的類型規(guī)則，檢查運(yùn)算的合法性與運(yùn)算分量類型的一致性，必要時(shí)作類型轉(zhuǎn)換。3.識(shí)別含義：根據(jù)語言的語義定義（形式或非形式），識(shí)別程序中各構(gòu)造成分組合到一起的含義，并作相應(yīng)的語義處理（生成中間代碼或目標(biāo)代碼）。5*第5頁，共70頁，2023年，2月20日，星期日4.控制流檢查：控制流語句必須轉(zhuǎn)移到合法的地方。

如C中，break語句規(guī)定跳出最內(nèi)層的循環(huán)或switch語句。5.一致性檢查：在很多場(chǎng)合要求對(duì)象只能被說明一次。如：pascal語言規(guī)定同一個(gè)標(biāo)識(shí)符在一個(gè)分程序中只能被說明一次等。6.相關(guān)名字檢查：如：Ada，循環(huán)或塊可以有一個(gè)名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭或結(jié)尾。編譯程序必須檢查這兩個(gè)地方用的名字是否相同。其它：如名字的作用域分析等也是語義分析的工作。6*第6頁，共70頁，2023年，2月20日，星期日三、語義描述工具和語義分析方法語義描述工具目前流行：用屬性文法作為描述語義的工具。語義分析方法 根據(jù)描述屬性文法的語義規(guī)則的方式不同分為：語法制導(dǎo)定義翻譯方案7*第7頁，共70頁，2023年，2月20日，星期日屬性文法

形式定義：一個(gè)屬性文法是一個(gè)三元組A=(G,V,F)

其中：G為一個(gè)上下文無關(guān)文法；

V表示屬性的有窮集合；

F表示屬性的斷言或謂詞的有窮集。語義規(guī)則 在對(duì)文法符號(hào)屬性處理過程中，為文法的每一產(chǎn)生式定義一組屬性的計(jì)算規(guī)則，稱為語義規(guī)則。8*第8頁，共70頁，2023年，2月20日，星期日

3.語法制導(dǎo)翻譯

所謂語法制導(dǎo)翻譯是指：對(duì)文法中的每個(gè)產(chǎn)生式都附加上一個(gè)語義動(dòng)作或語義子程序。伴隨著語法分析，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行相應(yīng)產(chǎn)生式的語義動(dòng)作（包括：查填表格，改變變量的求值，診察與報(bào)告錯(cuò)誤，生成中間代碼等），從而完成預(yù)定的翻譯工作。

自底向上的語法制導(dǎo)翻譯自頂向下的語法制導(dǎo)翻譯9*第9頁，共70頁，2023年，2月20日，星期日§2.幾種常用的中間語言形式一、逆波蘭表示法

波蘭表示是波蘭邏輯學(xué)家J·盧卡西維奇于1929年提出的一種既不須考慮優(yōu)先關(guān)系、又不用括號(hào)的一種表示表達(dá)式的方法（前綴式），在計(jì)算機(jī)出現(xiàn)以后，這種表示方法顯出了巨大的優(yōu)越性。后人為了紀(jì)念他，就用其祖國名字來命名這種表示方法?，F(xiàn)在我們要介紹的剛好是另一種波蘭表示形式，稱為后綴式，即運(yùn)算符在后。例：a+b→ab+a*(b+c)→abc+*-a+b*c→a@bc*+10*第10頁，共70頁，2023年，2月20日，星期日二、圖表示法

這里要介紹的圖表示包括DAG與我們前面介紹過的抽象語法樹。

1.無循環(huán)有向圖（DAG）

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)，而在一棵抽象語法樹中公共子表達(dá)式被表示為重復(fù)的子樹。如下例：11*第11頁，共70頁，2023年，2月20日，星期日assigna+**buminusbuminusccassigna+*buminusca:=b*-c+b*-c的圖表示法抽象語法樹DAG12*第12頁，共70頁，2023年，2月20日，星期日

2.再來看A*B+C*D的樹、后綴式后綴式：AB*CD*+

不難看出，后綴式實(shí)際上是抽象語法樹的線性表示形式（后序表示）；

+**ABCD13*第13頁，共70頁，2023年，2月20日，星期日

3.樹表示的翻譯法：例：產(chǎn)生式語義動(dòng)作

(1)E→E1opE2{E.val:=NODE(op,E1.val,E2.val)}

(2)E→(E1){E.val:=E1.val}(3)E→-E1{E.val:=UNARY(@E1.val)}

(4)E→i{E.val:=LEAF(i)}建立一棵新樹，以O(shè)P為根，以E1.val,E2.val為左右枝。返回指向樹根的指針。與NODE相似，只不過是單枝。建立以i.LEXCAL為標(biāo)志的葉結(jié)，回送的是結(jié)點(diǎn)i的地址。14*第14頁，共70頁，2023年，2月20日，星期日三、三元式

1.三元式由三個(gè)部分組成：

算符：OP

第一運(yùn)算分量：ARG1

第二運(yùn)算分量：ARG2

2.各種語句都可表示成一組三元式例1：OPARG1ARG2x+y*z(1)*yz(2)+x(1)

這兒實(shí)際實(shí)現(xiàn)時(shí)x,y,z也都是指示器，指向這些變量在符號(hào)表中的位置。算符OP一般用整數(shù)編碼，而且可以加進(jìn)一些諸如類型之類的信息。指示器----指向（1）在表格中的位置15*第15頁，共70頁，2023年，2月20日，星期日對(duì)于一目運(yùn)算符，我們可以規(guī)定只用ARG1，而多目運(yùn)算符可以用若干條相繼的三元式來表示。

OPARG1ARG2

例2：-x+y*z(1)@x--(2)*yz(3)+(1)(2)

例3：賦值語句的三元式表示

OPARG1ARG2A:=x+y*z(1)*yz(2)+x(1)(3):=A(2)16*第16頁，共70頁，2023年，2月20日，星期日 樹、后綴式與三元式OPARG1ARG2(1)*AB(2)*CD(3)+(1)(2)后綴式：AB*CD*+

后綴式實(shí)際上是抽象語法樹的線性表示形式（后序表示）；樹是三元式的翻版，每個(gè)三元式對(duì)應(yīng)一棵（二叉）子樹，最后的三元式對(duì)應(yīng)樹根。+**ABCD17*第17頁，共70頁，2023年，2月20日，星期日

3.語法制導(dǎo)產(chǎn)生三元式

(1)E→E1opE2

我們用E.val表示一個(gè)指示器，它或指向有關(guān)符號(hào)表的某項(xiàng)，或指向三元式表的某項(xiàng)，于是其語義子程序?yàn)椋?/p>

{E.val:=TRIP(OP,E1.val,E2.val)}

這兒TRIP(OP,ARG1,ARG2)是一個(gè)語義過程，它產(chǎn)生(OP,ARG1,ARG2)并放入三元式表中，返回三元式在表中的位置。

18*第18頁，共70頁，2023年，2月20日，星期日

(2)E→i{E.val:=Entry(i)}

這兒ENTRY是一個(gè)語義過程，它查找i在符號(hào)表中的位置。若用LOOKUP(NAME)函數(shù)表示對(duì)NAME查找符號(hào)表，找到則返回表項(xiàng)位置，找不到則返回NULL。于是可如下實(shí)現(xiàn)：詞法分析器掃描到標(biāo)識(shí)符i時(shí)送回（種別碼，i值），語法分析器把i放入語義變量i.LEXCAL中，這時(shí)就可以調(diào)用ENTRY過程：19*第19頁，共70頁，2023年，2月20日，星期日

FUNCTIONENTRY(NAME)BEGINENTRY:=LOOKUP(NAME);IFENTRY=NULLTHEN

ERROR;END由于三元式的計(jì)算過程跟先后順序密切相關(guān)，這就給優(yōu)化帶來麻煩，所以一般不直接使用三元式。20*第20頁，共70頁，2023年，2月20日，星期日

4.間接三元式在三元式的基礎(chǔ)上附加一張指示器表─間接碼表，按運(yùn)算的先后順序列出有關(guān)三元式在三元式表中的位置。這種表示方法稱為間接三元式。例：語句X:=(A+B)*C;Y:=D↑(A+B)的間接三元式OPARG1ARG2(1)+AB(2)*(1)C(3):=X(2)(4)↑D(1)(5):=Y(4)間接碼表（1）（2）（3）（1）（4）（5）21*第21頁，共70頁，2023年，2月20日，星期日

有了間接碼表后，一方面相同的三元式就無須重復(fù)填進(jìn)表中，節(jié)約了空間；另一方面，當(dāng)在代碼優(yōu)化過程中需要調(diào)整運(yùn)算順序時(shí)，只需重新安排間接碼表，無須改動(dòng)三元式。當(dāng)然這樣一來，語義規(guī)則中應(yīng)添加產(chǎn)生間接碼表的動(dòng)作，并且向三元式表中每填入一個(gè)三元式前，必須先查看一下此式是否已經(jīng)在表中出現(xiàn)過。22*第22頁，共70頁，2023年，2月20日，星期日四、四元式

一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)：op,arg1,arg2及result。它實(shí)際上就是一條三地址的指令。例：A+B*(C-D)-E/F↑G的四元式為：

OPARG1ARG2RESULT

①-CDT1②*BT1T2③+AT2T3④↑FGT4⑤/ET4T5⑥-T3T5T623*第23頁，共70頁，2023年，2月20日，星期日規(guī)定凡只有一個(gè)運(yùn)算量時(shí)只用ARG1。以上的Ti都是臨時(shí)變量，其處理方法可以像用戶自定義變量一樣進(jìn)符號(hào)表，也可以直接用某種整數(shù)碼表示。OPARG1ARG2RESULT(1)@B--T1(2)+CDT2(3)*T1T2T3(4):=T3--A賦值語句A:=-B*(C+D)填倒順序也可式之間的聯(lián)系與三元式不同（通過指示器），它是通過臨時(shí)變量，所以更動(dòng)四元式很容易，這就為優(yōu)化提供了方便，因?yàn)椴粻砍兜礁淖冎甘酒鞯膯栴}。從以上例子可以看出，四元式出現(xiàn)的順序和表達(dá)式計(jì)值順序一樣，但四元24*第24頁，共70頁，2023年，2月20日，星期日例：將語句:ifAVB<Dtheni:=i+1elsei:=i-1寫成四元式。(1)(<,B,D,T1)(2)(V,A,T1,T2) (3)(BMZ,T2,_,(7))(4)(+,i,1,T3) (5)(:=,T3,,i) (6)(JMP,_,_,(9))(7)(-,I,1,T4) (8)(:=,T4,_,i) (9)三地址代碼：(1)T1:=B<D(2)T2:=AVT1(3)ifT2goto(7)(4)T3:=i-1 (5)i:=T3

(6)goto(9)(7)T4:=i+1 (8)i:=T4

(9)有時(shí)將四元式表示成更直觀的形式－三地址代碼三地址代碼形式：

x:=aopb(賦值形式)與賦值語句的區(qū)別：其右邊最多只能有一個(gè)運(yùn)算符。25*第25頁，共70頁，2023年，2月20日，星期日參考書中推薦的三地址指令形式：賦值語句x:=yopz，

x:=opy，

x:=y無條件轉(zhuǎn)移gotoL條件轉(zhuǎn)移ifxrelopygotoL過程調(diào)用paramx和callp,n過程返回

returny索引賦值x:=y[i]和x[i]:=y地址和指針賦值x:=&y，x:=y和x:=y26*第26頁，共70頁，2023年，2月20日，星期日§3.某些語句的四元式及翻譯

一、說明語句的翻譯

程序語言中的說明語句都是給編譯程序提供信息的，諸如類型、維數(shù)、每維的界種類等，因此一般不生成目標(biāo)，只是在編譯時(shí)把有關(guān)信息填入相應(yīng)表格即可。為局部名字建立符號(hào)表?xiàng)l目為它分配存儲(chǔ)單元符號(hào)表中包含名字的類型和分配給它的存儲(chǔ)單元的相對(duì)地址等信息

27*第27頁，共70頁，2023年，2月20日，星期日

1.簡(jiǎn)單說明句：用一個(gè)基本字來定義一串名字，其語法描述一般為：

D→integernamelist∣realnamelistnamelist→namelist,i∣i

直接用這種文法來制導(dǎo)翻譯有點(diǎn)麻煩，就是只能在把所有名字規(guī)約成namelist之后才能把性質(zhì)登記到符號(hào)表中。這就意味著在掃描名字時(shí)，應(yīng)把名字用一個(gè)隊(duì)列（或棧）保存起來，然后再處理。實(shí)際上，我們可以對(duì)文法稍做改動(dòng)，就可以免去建立隊(duì)列或棧的過程。修改文法如下：

D→D,i∣integeri∣reali

28*第28頁，共70頁，2023年，2月20日，星期日例：integeri1,i2,i3詞法分析后：inti1,i2,i3(07,-)(06,‘i1’)(12,-)語法分析：s5i2s0s1s2#inti1s0s3#Ds4,DDLR分析器語義動(dòng)作：{FILL(ENTRY(i2),D1·ATT);D·ATT:=D1·ATT}D→D1,i2語義動(dòng)作：{FILL(ENTRY(i1),int);D·ATT:=int}D→integeri1此處的ENTRY過程參見前面29*第29頁，共70頁，2023年，2月20日，星期日

2.數(shù)組說明：遇到數(shù)組說明，應(yīng)把有關(guān)信息收集到一個(gè)“內(nèi)情向量”表格之中，每個(gè)數(shù)組對(duì)應(yīng)一個(gè)“內(nèi)情向量”。例如，array[l1:u1,l2:u2,…,ln:un]的內(nèi)情向量為：

di=ui-li+1所求地址:

D=CONSPART+VARPARTCONSPART=a-C

C=(…((l1d2+l2)d3+l3)d4+…)+ln-1)dn+lnl1u1d1l2u2d2………lnundnnCtypea維數(shù)類型數(shù)組首址30*第30頁，共70頁，2023年，2月20日，星期日顯然，內(nèi)情向量的大小完全由維數(shù)決定。一般來說，像FORTRAN,ALGOL,PASCAL等語言的程序，其內(nèi)情向量在編譯時(shí)完全可以確定了。關(guān)于內(nèi)情向量的填寫，編譯時(shí)完全可以做了，而且是只在編譯時(shí)使用，故可以把它安排成符號(hào)表的一部分，無須帶到目標(biāo)程序運(yùn)行階段。但有時(shí)為了處理方便，也一起帶到目標(biāo)程序中。

對(duì)動(dòng)態(tài)數(shù)組，則編譯時(shí)開辟出信息向量表區(qū)，同時(shí)應(yīng)有填寫信息向量的目標(biāo)指令，我們可以用如下一個(gè)子程序來處理。該程序的入口參數(shù)為維數(shù)n，界限序列l(wèi)1,u1,l2,u2,…,ln,un，以及類型type和數(shù)組首址。31*第31頁，共70頁，2023年，2月20日，星期日

BEGINi:=1;N:=1;C:=0;WHILEi<=nDOBEGINdi:=ui-li+1;N:=N*di;C:=C*di+li;

把li,ui,di填入內(nèi)情向量中;i:=i+1END;

申請(qǐng)N個(gè)單元的數(shù)組空間，令其首址為a;

把n,C,type和a填入內(nèi)情向量中

END；

其他記錄說明、過程說明的翻譯也大同小異，此處不再贅述。32*第32頁，共70頁，2023年，2月20日，星期日二、賦值語句的翻譯

1.簡(jiǎn)單算術(shù)表達(dá)式的賦值語句：所謂簡(jiǎn)單指不考慮數(shù)組元素、記錄、函數(shù)的引用等情況。對(duì)這種算術(shù)表達(dá)式和賦值語句的四元式我們已經(jīng)介紹過，現(xiàn)在就來看看如何翻譯。我們先來討論所有分量都是相同類型的情況，如都是整型。于是，我們可用如下的二義文法來進(jìn)行描述：

S→id:=EE→E1+E2∣E1*E2∣(E1)∣-E1∣id

33*第33頁，共70頁，2023年，2月20日，星期日語義動(dòng)作：

S→id:=E{p:=lookup();if(p!=nil)thenemit(p‘:=’E.place)elseerror}E→E1opE2{E.place:=newtemp;emit(E.place‘:=’E1.placeopE2.place)}E→-E1{E.place:=newtemp;emit(E.place‘:=’‘uminus’E1.place)}E→(E1){E.place:=E1.place}E→id{p:=lookup();if(p!=nil)thenE.place:=pelseerror}34*第34頁，共70頁，2023年，2月20日，星期日

2.類型轉(zhuǎn)換

實(shí)際上我們可以把類型信息反映到運(yùn)算符中，例如用+i,*i表示定點(diǎn)+、*，用+r,*r表示浮點(diǎn)+、*。有的程序設(shè)計(jì)語言允許混合運(yùn)算，有的不允許。如果不允許，則發(fā)現(xiàn)有類型不相同的運(yùn)算分量就應(yīng)該報(bào)錯(cuò)。如果允許，就要進(jìn)行類型轉(zhuǎn)換。按照慣例，整、實(shí)運(yùn)算要全部轉(zhuǎn)成實(shí)型。處理的方法就是：給每個(gè)非終結(jié)符添加一個(gè)類型信息，如我們用E.MODE表示E的類型，其值為r或者i。如此一來，關(guān)于E→E1opE2

的語義子程序也應(yīng)作相應(yīng)改動(dòng)，使其在必要時(shí)能產(chǎn)生對(duì)運(yùn)算分量進(jìn)行類型轉(zhuǎn)換的四元式。35*第35頁，共70頁，2023年，2月20日，星期日例：X:=Y+I*J其中X,Y為實(shí)型,I,J為整型

(*i,I,J,T1)

(itr,T1,--,T2)

加入一個(gè)類型轉(zhuǎn)換四元式

(+r,Y,T2,T3)(:=,T3,--,X)

語義動(dòng)作：對(duì)E→i來說，{E.place:=ENTRY(i)}現(xiàn)在應(yīng)加上E.MODE:=MODE(i);

而對(duì)E→E1opE2

，其語義子程序可以用如下流程圖來表示：36*第36頁，共70頁，2023年，2月20日，星期日T1:=newtempstartE1.MODE=int&E2.MODE=intE1.MODE=r&E2.MODE=rE1.MODE=intE.MODE:=rT2:=newtempemit(itr,E2.place,--,T2)emit(opr,E1.place,T2,T1)E.MODE:=rT2:=newtempemit(itr,E1.place,--,T2)emit(opr,T2,E2.place,T1)E.MODE:=intemit(opi,E1.place,E2.place,T1)E.MODE:=remit(opr,E1.place,E2.place,T1)endyyynnn37*第37頁，共70頁，2023年，2月20日，星期日

3.數(shù)組元素的引用

(1)一般考慮：數(shù)組元素的引用主要存在一個(gè)下標(biāo)地址的計(jì)算問題，這取決于數(shù)組在存儲(chǔ)器中的存放方式，故不同的存放方式會(huì)產(chǎn)生不同的中間代碼。以下我們以按行存放方式加以說明。前面說過，數(shù)組元素的地址D=CONSPART+VARPART而CONSPART=a-C,其中

C=(…((l1d2+l2)d3+l3)d4+…)+ln-1)dn+ln

靜態(tài)數(shù)組的信息向量在編譯過程中就可填寫，動(dòng)態(tài)數(shù)組的信息向量要在運(yùn)行時(shí)填。總而言之，待到引用數(shù)組元素時(shí)，實(shí)際上信息向量已經(jīng)完全填好，因此，我們要計(jì)算D是毫無問題的。38*第38頁，共70頁，2023年，2月20日，星期日

于是，我們可以把VARPART=(…((i1d2+i2)d3+i3)d4+…)+in-1)dn+in計(jì)算出來，放入臨時(shí)變量T中，并用T作“變址器”，把CONSPART=a-C計(jì)算出來，放入臨時(shí)變量T1中，并用T1作“基址”。這樣一來，對(duì)數(shù)組元素的引用可用變址方式進(jìn)行：D=T1[T]；進(jìn)而X:=T1[T]的四元式可寫為(=[],T1[T],--,X)，這兒=[]是“變址取數(shù)”操作。其實(shí)還可寫成：(=[],T1,T,X)。類似地，“變址存數(shù)”操作可寫成([]=,X,--,T1[T])，即XT1[T]。39*第39頁，共70頁，2023年，2月20日，星期日

(2)數(shù)組元素引用的翻譯首先對(duì)包含數(shù)組元素的賦值語句給出如下模式的文法：A→V:=EV→id[elist]|idelist→elist,E|EE→E+E|(E)|V

使用該文法計(jì)算VARPART不太方便，因?yàn)樵谡麄€(gè)elist的翻譯過程中隨時(shí)都需要知道數(shù)組名id的符號(hào)表入口，以獲得關(guān)于id的全部信息。為此我們把變量V的產(chǎn)生式改寫：

V→elist]|idelist→elist,E|id[E(1)elist:下標(biāo)表達(dá)式串;(2)E中只給出+，可認(rèn)為代表op;(3)該數(shù)組元素的定義是嵌套的這樣一來，每當(dāng)用elist→id[E規(guī)約時(shí)，elist就獲得了有關(guān)id的信息40*第40頁，共70頁，2023年，2月20日，星期日于是我們可以把含有數(shù)組元素的賦值語句的翻譯規(guī)則—對(duì)應(yīng)每個(gè)產(chǎn)生式的語義動(dòng)作—構(gòu)造出來了，下面還是看個(gè)例子先：設(shè)有說明arrayA[1:10,1:20]，給定賦值語句：

(1)X:=A[I,J];(2)A[I+2,J+1]:=M+N;

則(1)的四元式序列為：

(*,I,20,T)……i1d2(+,J,T,T)……i1d2+i2=VARPART=T(-,A,21,T1)……a-C=CONSPART=T1(=[],T1[T],--,T2)……T2:=T1[T](:=,T2,-,X)……X:=T241*第41頁，共70頁，2023年，2月20日，星期日

(2)的四元式序列為：(+,I,2,T2)……I+2(+,J,1,T3)……J+1(*,T2,20,T)……i1d2

(+,T3,T,T)……i1d2+i2=VARPART(-,A,21,T1)……a-C=CONSPART(+,M,N,T4)……M+N([]=,T4,--,T1[T])……M+NA[I+2,J+1]

參考書中給出了具體的翻譯模式，此處不再啰嗦。42*第42頁，共70頁，2023年，2月20日，星期日

三、控制流語句的翻譯

布爾表達(dá)式在高級(jí)程序語言中只出現(xiàn)在兩個(gè)方面：求邏輯值和作為各種控制語句的條件表達(dá)式。顯然對(duì)布爾表達(dá)式求值的四元式的翻譯，我們完全可以仿照算術(shù)表達(dá)式的翻譯來進(jìn)行。例如A∨B∧C=D可翻譯成如下四元式序列：(=,C,D,T1)(∧,B,T1,T2)(∨,A,T2,T3)但是對(duì)于控制語句中的條件表達(dá)式，我們還必須結(jié)合控制語句作進(jìn)一步的分析。43*第43頁，共70頁，2023年，2月20日，星期日

1.條件語句中布爾表達(dá)式的翻譯

出現(xiàn)在條件語句ifEthenS1elseS2中的布爾表達(dá)式E，它的作用僅在于控制對(duì)S1或S2的選擇,亦即提供“真”“假”出口，所以其值無需一直保留。E.codeS1.codegotoS.nextS2.codetoE.truetoE.falseE.true:E.false:S.next:44*第44頁，共70頁，2023年，2月20日，星期日

?于是我們可以采用一種優(yōu)化措施來處理，用一種遞推的方式來確定真假出口（短路）。如：A∨B可理解為ifAthentrueelseBA∧B可理解為ifAthenBelsefalse┐A可理解為ifAthenfalseelsetrue

A∨B∧C=D呢？根據(jù)這樣的思考，我們可以把作為控制條件的任何布爾表達(dá)式表示成僅含下列三種形式的四元式的序列：

(jnz,a,--,p)表示ifagotop(jrop,x,y,p)表示ifxropygotop(j,--,--,p)表示gotop45*第45頁，共70頁，2023年，2月20日，星期日例：ifA∨B∧C=DthenS1elseS2

的四元式：

1.(jnz,A,--,7)2.(j,--,--,3)3.(jnz,B,--,5)4.(j,--,--,p+1)5.(j=,C,D,7)6.(j,--,--,p+1)

7.(S1的四元式序列

……）

p.(j,--,--,q)

p+1.(S2的四元式序列

……)

q.……46*第46頁，共70頁，2023年，2月20日，星期日?到此為止看起來翻譯四元式序列似乎問題不大了，只要把有關(guān)描述文法寫出，再配上相應(yīng)的語義動(dòng)作就可以了。例如：E→E∨E|E∧E|┐E|(E)|i|iropi配上語義動(dòng)作。但是還有一個(gè)相當(dāng)麻煩的問題需要解決，就是有關(guān)轉(zhuǎn)移的四元式的第四部分（result）的轉(zhuǎn)移地址無法填寫（如上例中7，5，p+1等），因?yàn)樵谏稍撍脑降臅r(shí)候這個(gè)地址往往還是未知數(shù)。那么，該如何處理呢？47*第47頁，共70頁，2023年，2月20日，星期日想一下我們編寫程序的時(shí)候，對(duì)于gotoL，在L還不知道的情況下是如何處理的呢？我們并沒有因?yàn)長(zhǎng)還不知道就停滯不前，而是先記住該語句的位置而把L處空出來，一直到編寫到L時(shí)，再回過頭來找到goto把L的‘值’填上，那么該如何用算法實(shí)現(xiàn)這樣一個(gè)智能過程呢？★那就是“回填(backpatching)”！和棧的使用一樣，這也是一種非常巧妙的技巧。它把一個(gè)由跳轉(zhuǎn)指令組成的列表以綜合屬性的形式進(jìn)行傳遞。下面結(jié)合著“標(biāo)號(hào)”來具體說明一下：48*第48頁，共70頁，2023年，2月20日，星期日

2.標(biāo)號(hào)和無條件轉(zhuǎn)移的翻譯

(1)對(duì)于說明性出現(xiàn)的標(biāo)號(hào)，很容易處理：

L:S

當(dāng)這種語句被處理之后，標(biāo)號(hào)L被稱為“定義了”的。也就是，在符號(hào)表中，標(biāo)號(hào)L的“地址”欄將登記上語句S的第一個(gè)四元式的地址（編號(hào)）。

(2)對(duì)于先定義后應(yīng)用的無條件轉(zhuǎn)移(向后轉(zhuǎn)移的gotoL)，也很容易處理。對(duì)L查表得到它的定義地址p，就可生成gotoL的四元式(j,--,--,p)。49*第49頁，共70頁，2023年，2月20日，星期日

(3)對(duì)于先應(yīng)用后定義的情況(前向轉(zhuǎn)移gotoL)：

拉鏈返填:把所有以L為轉(zhuǎn)移目標(biāo)的四元式串在一起。鏈的首地址放在符號(hào)表中L的“地址”欄中。 建鏈的方法：若L尚未在符號(hào)表中出現(xiàn)，則把L填入表中，置L的“定義否”為“未”，把nextquad填進(jìn)L的地址欄中作為新鏈頭。然后產(chǎn)生四元式

(j,--,--,0),其中0為鏈末標(biāo)志；若L已在符號(hào)表出現(xiàn)但“定義否”為“未”，則把它的地址欄的編號(hào)q取出，把nextquad填進(jìn)該欄作新鏈頭，然后產(chǎn)生四元式(j,--,--,q)。一旦標(biāo)號(hào)L定義時(shí)，我們將根據(jù)這條鏈回填那些待填轉(zhuǎn)移目標(biāo)的四元式，直到某個(gè)四元式的地址部分為0（鏈尾）。如下圖：

50*第50頁，共70頁，2023年，2月20日，星期日名字類型…定義否地址…L標(biāo)號(hào)未r(r)(j,--,--,q)(q)(j,--,--,p)(p)(j,--,--,y)…(x)(j,--,--,0)未定義標(biāo)號(hào)的引用鏈符號(hào)表四元式51*第51頁，共70頁，2023年，2月20日，星期日?一般而言，假定用下面的產(chǎn)生式來定義帶標(biāo)號(hào)語句

S→labelSlabel→i:

那么，當(dāng)用label→i:進(jìn)行歸納時(shí)，應(yīng)作如下的語義動(dòng)作：

ⅰ.若i所指的標(biāo)示符(假定為L(zhǎng))不在符號(hào)表中時(shí)，則把它填入，置“類型”為“標(biāo)號(hào)”，“定義否”為“已”，“地址”為nextquad；

ⅱ.若L已在符號(hào)表中但“類型”不為“標(biāo)號(hào)”或“定義否”為“已”，則報(bào)錯(cuò)；

ⅲ.若L已在符號(hào)表中，則把標(biāo)志“未”改為“已”，然后把地址欄中的鏈頭（記為q）取出，同時(shí)把nextquad填在其中，最后執(zhí)行backpatch(q,nextquad)。52*第52頁，共70頁，2023年，2月20日，星期日當(dāng)然，這兒“拉鏈”和“返填”都要用一個(gè)子程序（函數(shù)過程）來處理?，F(xiàn)在返回到那些無法填寫轉(zhuǎn)移地址的四元式的處理上，它完全是按照如上講的方法進(jìn)行的。這就要記住每條四元式的編號(hào)。因?yàn)橛小罢?、假”出口的問題，所以對(duì)文法中的非終結(jié)符還要引進(jìn)兩個(gè)語義值，如E.TC,E.FC。建鏈在產(chǎn)生四元式的時(shí)候就可以做了，而返填必須在標(biāo)號(hào)定義后才能進(jìn)行。如對(duì)ifEthenS1elses2，當(dāng)掃描了then之后就可以返填E的“真”出口，因?yàn)檫@時(shí)已經(jīng)知道了S1的第一個(gè)四元式的編號(hào)了。但E的“假”出口還必須等到開始處理S2時(shí)才能返填。53*第53頁，共70頁，2023年，2月20日，星期日

3.循環(huán)與分情況語句的翻譯

(1)循環(huán)語句大多數(shù)程序語言中都有如下形式的循環(huán)句：

S→fori:=E1stepE2untilE3doS1

其語義各語言可能有所不同，主要區(qū)別在先判斷、后執(zhí)行還是先執(zhí)行、后判斷。按Algol語言的解釋：

i:=E1；

gotoover;

again:i:=i+E2;

over:ifi<=E3

then

beginS1;gotoagainend;54*第54頁，共70頁，2023年，2月20日，星期日于是為了產(chǎn)生四元式，描述文法改寫如下：

F1→fori:=E1F2→F1stepE2F3→F2untilE3S→F3doS1

根據(jù)前面的解釋，i在幾處都用到，故ENTRY(i)必須保留下來，而該文法正是基于這樣的考慮而寫出來的。于是語義動(dòng)作也就容易寫了：55*第55頁，共70頁，2023年，2月20日，星期日例如F1→fori:=E1

對(duì)應(yīng)的語義動(dòng)作:(1)產(chǎn)生四元式：emit(:=,E1.place,--,ENTRY(i));(2)保留ENTRY(i)：F1.place:=ENTRY(i);(3)因?yàn)間otoover的轉(zhuǎn)移地址暫時(shí)填不上，必須建鏈：F1.chain:=nextquad;(4)產(chǎn)生無條件轉(zhuǎn)移指令：emit(j,--,--,0);(5)保留again的地址：F1.quad:=nextquad;注意：在源程序的語句中，并沒有again，over這樣的標(biāo)號(hào)，因此也就沒有進(jìn)符號(hào)表的問題。56*第56頁，共70頁，2023年，2月20日，星期日

F2→F1stepE2:

(1)again的地址應(yīng)繼續(xù)保留：

F2.quad:=F1.quad;(2)i的符號(hào)表入口也要保留：

F2.place:=F1.place;(3)生成i:=i+E2的四元式：

emit(+,F1.place,E2.place,F1.place);(4)現(xiàn)在over的地址有了，可以返填了：

Backpatch(F1.chain,nextquad);57*第57頁，共70頁，2023年，2月20日，星期日

F3→F2untilE3：這是一個(gè)簡(jiǎn)單的條件句，需要注意兩個(gè)出口的問題。

(1)again的地址要繼續(xù)保留：F3.quad:=F2.quad;(2)為處理真出口，把四元式計(jì)數(shù)器的當(dāng)前值記錄下來：q:=nextquad;(3)產(chǎn)生四元式：emit(j≤,F2.place,E3.place,q+2);(4)假出口還不知道，則建鏈：F3.chain:=nextquad;

產(chǎn)生假出口的四元式：emit(j,--,--,0);58*第58頁，共70頁，2023年，2月20日，星期日

S→F3doS1：(1)產(chǎn)生四元式：emit(j,--,--,F3.quad);(2)若S1建鏈，則也有返填問題：Backpatch(S1.chain,F3.quad)(3)轉(zhuǎn)離循環(huán)的轉(zhuǎn)移目標(biāo)留待處理外層S時(shí)再返填，故要保留：S.chain:=F3.chain

用于改變程序控制流的語句還有：goto,break,continue,return等。思考：這些語句應(yīng)如何處理？59*第59頁，共70頁，2023年，2月20日，星期日

(2)分情況語句各種語言的分支語句不盡相同（case,switch等），這里我們假定其形式為左下所示：

caseEofC1:S1;C2:S2;…Cn-1:Sn-1;otherwise:Snend;T:=E;L1:ifT≠C1gotoL2;S1;gotonext;L2:ifT≠C2gotoL3;S2;gotonext;L3:…Ln:Sn;next:…可翻譯為60*第60頁，共70頁，2023年，2月20日，星期日

上述例子說明，在分支語句不是太多的情況下，我們可以將其翻譯為一連串的條件轉(zhuǎn)移語句，相對(duì)應(yīng)的語義動(dòng)作構(gòu)造起來就比較簡(jiǎn)單了。當(dāng)然，也可以采用更有效的方法進(jìn)行翻譯，比如構(gòu)造一張開關(guān)表，并構(gòu)造一個(gè)對(duì)E值查找開關(guān)表的循環(huán)程序。在運(yùn)行時(shí)，這個(gè)循環(huán)程序就對(duì)E值查開關(guān)表，一旦匹配上某個(gè)Ci，則轉(zhuǎn)去執(zhí)行相應(yīng)Si；若不匹配任何一個(gè)Ci，則執(zhí)行Sn。要