第7講--中間代碼翻譯

1、CompilerPrinciples1第第七七講講 語義分析和語義分析和中間代碼產(chǎn)生中間代碼產(chǎn)生u語義分析概述語義分析概述u中間語言中間語言u(píng)幾種常用語句的翻譯幾種常用語句的翻譯CompilerPrinciples2 靜態(tài)語義檢查和中間代碼產(chǎn)生在編譯程序中的位置如圖所示：語法分析器靜態(tài)檢查器中間代碼產(chǎn)生器優(yōu)化器CompilerPrinciples3 雖然源程序可以直接翻譯為目標(biāo)語言代碼，但是通常編譯程序還是采用了獨(dú)立于機(jī)器的、復(fù)雜性介于源語言與機(jī)器語言之間的中間語言。這樣做的好處是： （1）便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化； （2）使編譯程序改變目標(biāo)機(jī)更容易； （3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡

2、單明確，以中間語言為界面，編譯前端和后端的接口更清晰。CompilerPrinciples41. 語義分析概述語義分析概述一、語義分析的任務(wù)一、語義分析的任務(wù)v審查每一個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法正確的結(jié)構(gòu)是否有意義。如：賦值語句：x:=x+y,左邊變量類型與右邊變量類型是否一致。v在語義正確的基礎(chǔ)上生成一種中間代碼或目標(biāo)代碼。CompilerPrinciples5 二、語義分析的范圍二、語義分析的范圍1.確定類型：確定標(biāo)識(shí)符所關(guān)聯(lián)的數(shù)據(jù)類型。2.類型檢查：按語言的類型規(guī)則，檢查運(yùn)算的合法性與運(yùn)算分量類型的一致性，必要時(shí)作類型轉(zhuǎn)換。3.識(shí)別含義：根據(jù)語言的語義定義（形式或非形式），識(shí)別程序

3、中各構(gòu)造成分組合到一起的含義，并作相應(yīng)的語義處理（生成中間代碼或目標(biāo)代碼）。CompilerPrinciples64.控制流檢查：控制流語句必須轉(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è)地方用的名字是否相同。其它：如名字的作用域分析等也是語義分析的工作。CompilerPrinciples7三、語義描述工具和語義分析方法三、語義描述工

4、具和語義分析方法v語義描述工具 目前流行：用屬性文法作為描述語義的工具。v語義分析方法根據(jù)描述屬性文法的語義規(guī)則的方式不同分為：n語法制導(dǎo)定義1.翻譯方案CompilerPrinciples8v屬性文法屬性文法形式定義：一個(gè)屬性文法是一個(gè)三元組A=(G,V,F) 其中：G為一個(gè)上下文無關(guān)文法； V 表示屬性的有窮集合； F表示屬性的斷言或謂詞的有窮集。v語義規(guī)則在對(duì)文法符號(hào)屬性處理過程中，為文法的每一產(chǎn)生式定義一組屬性的計(jì)算規(guī)則，稱為語義規(guī)則。CompilerPrinciples9 3.語法制導(dǎo)翻譯語法制導(dǎo)翻譯 所謂語法制導(dǎo)翻譯是指：對(duì)文法中的每個(gè)產(chǎn)生式都附加上一個(gè)語義動(dòng)作或語義子程序。伴隨著

5、語法分析，每當(dāng)使用一條產(chǎn)生式進(jìn)行推導(dǎo)或歸約時(shí)，就執(zhí)行相應(yīng)產(chǎn)生式的語義動(dòng)作（包括：查填表格，改變變量的求值，診察與報(bào)告錯(cuò)誤，生成中間代碼等），從而完成預(yù)定的翻譯工作。 自底向上的語法制導(dǎo)翻譯自頂向下的語法制導(dǎo)翻譯CompilerPrinciples102.2.幾種常用的中間語言形式幾種常用的中間語言形式 一、逆波蘭表示法一、逆波蘭表示法 波蘭表示是波蘭邏輯學(xué)家J盧卡西維奇于1929年提出的一種既不須考慮優(yōu)先關(guān)系、又不用括號(hào)的一種表示表達(dá)式的方法（前綴式），在計(jì)算機(jī)出現(xiàn)以后，這種表示方法顯出了巨大的優(yōu)越性。后人為了紀(jì)念他，就用其祖國名字來命名這種表示方法。現(xiàn)在我們要介紹的剛好是另一種波蘭表示形式，

6、稱為后綴式，即運(yùn)算符在后。 例： a+b ab+ a*(b+c) abc+* -a+b*c abc*+CompilerPrinciples11 二、圖表示法二、圖表示法 這里要介紹的圖表示圖表示包括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ù)的子樹。如下例：CompilerPrinciples12assigna+*buminusbum

7、inusccassigna+*buminusca:=ba:=b* *-c+b-c+b* *-c-c的圖表示法的圖表示法抽象語法樹DAGCompilerPrinciples13 2.再來看A*B+C*D的樹、后綴式后綴式：AB*CD*+ 不難看出，后綴式實(shí)際上是抽象語法樹的線性表示形式（后序表示）； +*ABCDCompilerPrinciples14 3.樹表示的翻譯法： 例： 產(chǎn)生式 語義動(dòng)作 (1)EE1 op E2 E.val:=NODE(op,E1.val,E2.val) (2)E(E1) E.val:=E1.val (3)E-E1 E.val:=UNARY(E1.val) (4)Ei

8、 E.val:=LEAF(i)建立一棵新樹，以建立一棵新樹，以O(shè)POP為根，為根，以以E1.val,E2.valE1.val,E2.val為左右枝。為左右枝。返回指向樹根的指針。返回指向樹根的指針。與與NODENODE相似，只相似，只不過是單枝。不過是單枝。建立以建立以i.LEXCALi.LEXCAL為標(biāo)為標(biāo)志的葉結(jié)，回送的是結(jié)志的葉結(jié)，回送的是結(jié)點(diǎn)點(diǎn)i i的地址。的地址。CompilerPrinciples15 三、三元式三、三元式 1.三元式由三個(gè)部分組成： 算符：OP 第一運(yùn)算分量：ARG1 第二運(yùn)算分量：ARG2 2.各種語句都可表示成一組三元式 例1： OP ARG1 ARG2 x+

9、y*z (1) * y z (2) + x (1) 這兒實(shí)際實(shí)現(xiàn)時(shí)x,y,z也都是指示器，指向這些變量在符號(hào)表中的位置。算符OP一般用整數(shù)編碼，而且可以加進(jìn)一些諸如類型之類的信息。 指示器-指向（1）在表格中的位置CompilerPrinciples16 對(duì)于一目運(yùn)算符，我們可以規(guī)定只用ARG1，而多目運(yùn)算符可以用若干條相繼的三元式來表示。 OP ARG1 ARG2 例2：-x+y*z (1) x - (2) * y z (3) + (1) (2) 例3：賦值語句的三元式表示 OP ARG1 ARG2 A:=x+y*z (1) * y z (2) + x (1) (3) := A (2)Com

10、pilerPrinciples17樹、后綴式與三元式 后綴式：AB*CD*+ 后綴式實(shí)際上是抽象語法樹的線性表示形式（后序表示）；樹是三元式的翻版，每個(gè)三元式對(duì)應(yīng)一棵（二叉）子樹，最后的三元式對(duì)應(yīng)樹根。+*ABCDCompilerPrinciples18 3.語法制導(dǎo)產(chǎn)生三元式 (1) EE1 op E2 我們用E.val表示一個(gè)指示器，它或指向有關(guān)符號(hào)表的某項(xiàng)，或指向三元式表的某項(xiàng)，于是其語義子程序?yàn)椋?E.val:=TRIP(OP,E1.val,E2.val) 這兒TRIP(OP,ARG1,ARG2)是一個(gè)語義過程，它產(chǎn)生(OP,ARG1,ARG2)并放入三元式表中，返回三元式在表中的位置

11、。 CompilerPrinciples19 (2)Ei 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過程： CompilerPrinciples20 FUNCTION ENTRY(NAME) BEGIN ENTRY:=LOOKUP(NAME); IF ENTRY=NULL THEN ERROR; END 由于三元式

12、的計(jì)算過程跟先后順序密切相關(guān)，這就給優(yōu)化帶來麻煩，所以一般不直接使用三元式。 CompilerPrinciples21 4.間接三元式間接三元式 在三元式的基礎(chǔ)上附加一張指示器表在三元式的基礎(chǔ)上附加一張指示器表間接碼表，按間接碼表，按運(yùn)算的先后順序列出有關(guān)三元式在三元式表中的位置。這運(yùn)算的先后順序列出有關(guān)三元式在三元式表中的位置。這種表示方法稱為間接三元式。種表示方法稱為間接三元式。 例：例： 語句語句X:=(A+B)X:=(A+B)* *C; Y:=D(A+B)C; Y:=D(A+B)的間接三元式的間接三元式間接碼表（1）（2）（3）（1）（4）（5）CompilerPrinciples22

13、v 有了間接碼表后，一方面相同的三元式就無須重復(fù)填進(jìn)表中，節(jié)約了空間；另一方面，當(dāng)在代碼優(yōu)化過程中需要調(diào)整運(yùn)算順序時(shí)，只需重新安排間接碼表，無須改動(dòng)三元式。v 當(dāng)然這樣一來，語義規(guī)則中應(yīng)添加產(chǎn)生間接碼表的動(dòng)作，并且向三元式表中每填入一個(gè)三元式前，必須先查看一下此式是否已經(jīng)在表中出現(xiàn)過。CompilerPrinciples23 四、四元式四、四元式 一個(gè)四元式是一個(gè)帶有四個(gè)域的記錄結(jié)構(gòu)：op,arg1,arg2及result。它實(shí)際上就是一條三地址的指令。 例：A+B*(C-D)-E/FG的四元式為： OP ARG1 ARG2 RESULT - C D T1 * B T1 T2 + A T2 T

14、3 F G T4 / E T4 T5 - T3 T5 T6 CompilerPrinciples24v規(guī)定凡只有一個(gè)運(yùn)算量時(shí)只用ARG1。v以上的Ti都是臨時(shí)變量，其處理方法可以像用戶自定義變量一樣進(jìn)符號(hào)表，也可以直接用某種整數(shù)碼表示。賦值語句賦值語句A:=-BA:=-B* *(C+D)(C+D)填倒順序也可填倒順序也可式之間的聯(lián)系與三元式不同（通過指示器），它是通過臨式之間的聯(lián)系與三元式不同（通過指示器），它是通過臨時(shí)變量，所以更動(dòng)四元式很容易，這就為優(yōu)化提供了方便，時(shí)變量，所以更動(dòng)四元式很容易，這就為優(yōu)化提供了方便，因?yàn)椴粻砍兜礁淖冎甘酒鞯膯栴}。因?yàn)椴粻砍兜礁淖冎甘酒鞯膯栴}。從以上例子可以

15、看出，四元式出現(xiàn)的從以上例子可以看出，四元式出現(xiàn)的順序和表達(dá)式計(jì)值順序一樣，但四元順序和表達(dá)式計(jì)值順序一樣，但四元CompilerPrinciples25例：將語句:if AVBD then i:=i+1 else i:=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:=BD(2) T2:=AV T1(3) if

16、T2 goto (7)(4) T3:=i-1(5) i:= T3(6) goto (9)(7) T4:=i+1(8) i:= T4(9)有時(shí)將四元式表示成更直觀的形式三地址代碼三地址代碼形式：x:=a op b (賦值形式)與賦值語句的區(qū)別：其右邊最多只能有一個(gè)運(yùn)算符。CompilerPrinciples26參考書中推薦的三地址指令形式：參考書中推薦的三地址指令形式：v賦值語句賦值語句x := y op z， x := op y， x := yv無條件轉(zhuǎn)移無條件轉(zhuǎn)移goto Lv條件轉(zhuǎn)移條件轉(zhuǎn)移if x relop y goto Lv過程調(diào)用過程調(diào)用param x 和和call p , nv過

17、程返回過程返回 return yv索引賦值索引賦值x := yi和和 xi := yv地址和指針賦值地址和指針賦值x := &y，x := y和和 x := yCompilerPrinciples273.3.某些語句的四元式及翻譯某些語句的四元式及翻譯 一、說明語句的翻譯一、說明語句的翻譯 程序語言中的說明語句都是給編譯程序提供信息的，諸如類型、維數(shù)、每維的界種類等，因此一般不生成目標(biāo)，只是在編譯時(shí)把有關(guān)信息填入相應(yīng)表格即可。為局部名字建立符號(hào)表?xiàng)l目為它分配存儲(chǔ)單元符號(hào)表中包含名字的類型和分配給它的存儲(chǔ)單元的相對(duì)地址等信息 CompilerPrinciples28 1.簡單說明句：用一

18、個(gè)基本字來定義一串名字，其語法描述一般為： Dinteger namelistreal namelist namelistnamelist,ii 直接用這種文法來制導(dǎo)翻譯有點(diǎn)麻煩，就是只能在把所有名字規(guī)約成namelist之后才能把性質(zhì)登記到符號(hào)表中。這就意味著在掃描名字時(shí)，應(yīng)把名字用一個(gè)隊(duì)列（或棧）保存起來，然后再處理。實(shí)際上，我們可以對(duì)文法稍做改動(dòng)，就可以免去建立隊(duì)列或棧的過程。修改文法如下： DD,iinteger ireal i CompilerPrinciples29v 例： integer i1,i2,i3詞法分析后：詞法分析后： int iint i1 1 , i , i2 2

19、, i , i3 3(07,-)(07,-)(06,i1)(06,i1) (12,-)(12,-)語法分析：語法分析：s s5 5i i2 2s s0 0s s1 1s s2 2# #intinti i1 1s s0 0s s3 3# #D Ds s4 4, ,D DD DLRLR分析器分析器語義動(dòng)作：語義動(dòng)作：FILL(ENTRY(iFILL(ENTRY(i2 2),D),D1 1ATT);ATT); D DATT:=DATT:=D11ATTATT DD DD1 1 ,i ,i2 2語義動(dòng)作：語義動(dòng)作：FILL(ENTRY(iFILL(ENTRY(i1 1),int);),int); D D

20、ATT:=intATT:=int Dinteger i Dinteger i1 1.CompilerPrinciples30 2.數(shù)組說明：遇到數(shù)組說明，應(yīng)把有關(guān)信息收集到一個(gè)“內(nèi)情向量”表格之中，每個(gè)數(shù)組對(duì)應(yīng)一個(gè)“內(nèi)情向量”。例如，arrayl1:u1,l2:u2,ln:un的內(nèi)情向量為： di=ui-li+1所求地址: D=CONSPART+VARPART CONSPART=a-C C=(l1d2+l2)d3+l3)d4+)+ln-1)dn+ln維數(shù)維數(shù)類型類型數(shù)組首址CompilerPrinciples31v 顯然，內(nèi)情向量的大小完全由維數(shù)決定。一般來說，像FORTRAN,ALGOL,P

21、ASCAL等語言的程序，其內(nèi)情向量在編譯時(shí)完全可以確定了。關(guān)于內(nèi)情向量的填寫，編譯時(shí)完全可以做了，而且是只在編譯時(shí)使用，故可以把它安排成符號(hào)表的一部分，無須帶到目標(biāo)程序運(yùn)行階段。但有時(shí)為了處理方便，也一起帶到目標(biāo)程序中。v 對(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ù)組首址。CompilerPrinciples32v BEGIN BEGIN i:=1; N:=1; C:=0; i:=1; N:=1; C:=0; WHILE i=n DO WHIL

22、E i=n DO BEGIN BEGIN d di i:=u:=ui i-l-li i+1; N:=N+1; N:=N* *d di i; C:=C; C:=C* *d di i+l+li i; ; 把把l li i,u,ui i,d,di i填入內(nèi)情向量中填入內(nèi)情向量中; i:=i+1; i:=i+1 END; END; 申請(qǐng)申請(qǐng)N N個(gè)單元的數(shù)組空間，令其首址為個(gè)單元的數(shù)組空間，令其首址為a;a; 把把n,C,typen,C,type和和a a填入內(nèi)情向量中填入內(nèi)情向量中 ENDEND； 其他記錄說明、過程說明的翻譯也大同小異，此處不再贅述。CompilerPrinciples33 二、賦

23、值語句的翻譯二、賦值語句的翻譯 1.簡單算術(shù)表達(dá)式的賦值語句： 所謂簡單指不考慮數(shù)組元素、記錄、函數(shù)的引用等情況。對(duì)這種算術(shù)表達(dá)式和賦值語句的四元式我們已經(jīng)介紹過，現(xiàn)在就來看看如何翻譯。我們先來討論所有分量都是相同類型的情況，如都是整型。于是，我們可用如下的二義文法來進(jìn)行描述： Sid:=E EESid:=E EE1 1+E+E2 2EE1 1* *E E2 2(E(E1 1)-E)-E1 1idid CompilerPrinciples34v語義動(dòng)作： Sid:=E p:=lookup();Sid:=E p:=lookup(); if (p!=nil) then

24、emit(p:=E.place) if (p!=nil) then emit(p:=E.place) else error else error EE EE1 1 op E op E2 2 E.place:= newtemp; E.place:= newtemp; emit(E.place:= E emit(E.place:= E1 1.place op E.place op E2 2.place) .place) E-E E-E1 1 E.place:=newtemp; E.place:=newtemp; emit(E.place:=uminus E emit(E.place:=uminus

25、 E1 1.place).place) E(E E(E1 1) E.place:= E) E.place:= E1 1.place.place Eid p:=lookup(); Eid p:=lookup(); if (p if (p!=!=nil) then E.place:=pnil) then E.place:=p else error else errorCompilerPrinciples35 2.類型轉(zhuǎn)換 實(shí)際上我們可以把類型信息反映到運(yùn)算符中，例如用+i,*i表示定點(diǎn)+、*，用+r,*r表示浮點(diǎn)+、*。有的程序設(shè)計(jì)語言允許混合運(yùn)算，有的不允許。如果不允

26、許，則發(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)于EEEE1 1 op E op E2 2 的語義子程序也應(yīng)作相應(yīng)改動(dòng)，使其在必要時(shí)能產(chǎn)生對(duì)運(yùn)算分量進(jìn)行類型轉(zhuǎn)換的四元式。CompilerPrinciples36v例：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ì)Ei來說， E.pla

27、ce:= ENTRY(i)現(xiàn)在應(yīng)加上E.MODE:=MODE(i); 而對(duì)EE1 op E2 ，其語義子程序可以用如下流程圖來表示：CompilerPrinciples37T1:=newtempT1:=newtempstartE1.MODE=intE1.MODE=int&E2.MODE=int&E2.MODE=intE1.MODE=rE1.MODE=r&E2.MODE=r&E2.MODE=rE1.MODE=intE1.MODE=intE.MODE:=rE.MODE:=rT T2 2:=newtemp:=newtempemit(itr,emit(itr,E E2

28、2.place,-,T.place,-,T2 2) )emit(opemit(opr r, ,E E1 1.place,T.place,T2 2,T,T1 1) )E.MODE:=rE.MODE:=rT T2 2:=newtemp:=newtempemit(itr,emit(itr,E E1 1.place,-,T.place,-,T2 2) )emit(opemit(opr r,T,T2 2, ,E E2 2.place,T.place,T1 1) )E.MODE:=intE.MODE:=intemit(opemit(opi i,E,E1 1.place,.place,E E2 2.plac

29、e,T.place,T1 1) )E.MODE:=rE.MODE:=remit(opemit(opr r,E,E1 1.place,.place,E E2 2.place,T.place,T1 1) )endyyynnnCompilerPrinciples38 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)

30、dn+ln 靜態(tài)數(shù)組的信息向量在編譯過程中就可填寫，動(dòng)態(tài)數(shù)組的信息向量要在運(yùn)行時(shí)填。總而言之，待到引用數(shù)組元素時(shí)，實(shí)際上信息向量已經(jīng)完全填好，因此，我們要計(jì)算D是毫無問題的。CompilerPrinciples39v 于是，我們可以把VARPART=(i1d2+i2)d3+i3)d4+)+in-1)dn+in 計(jì)算出來，放入臨時(shí)變量T中，并用T作“變址器”，把CONSPART=a-C計(jì)算出來，放入臨時(shí)變量T1中，并用T1作“基址”。v 這樣一來，對(duì)數(shù)組元素的引用可用變址方式進(jìn)行：D=T1T；進(jìn)而X:=T1T的四元式可寫為(=,T1T,-,X)，這兒=是“變址取數(shù)”操作。其實(shí)還可寫成：(=,T1

31、,T,X)。類似地，“變址存數(shù)”操作可寫成 (=,X,-,T1T)，即XT1T。CompilerPrinciples40 (2)數(shù)組元素引用的翻譯 首先對(duì)包含數(shù)組元素的賦值語句給出如下模式的文法： AV:=E Videlist|id elistelist,E|E EE+E|(E)|V 使用該文法計(jì)算VARPART不太方便，因?yàn)樵谡麄€(gè)elist的翻譯過程中隨時(shí)都需要知道數(shù)組名id的符號(hào)表入口，以獲得關(guān)于id的全部信息。為此我們把變量V的產(chǎn)生式改寫： Velist|id elistelist,E|idE(1)elist:(1)elist:下標(biāo)表達(dá)式串下標(biāo)表達(dá)式串; ;(2)E(2)E中只給出中只給

32、出+ +，可認(rèn)為代表，可認(rèn)為代表op;op;(3)(3)該數(shù)組元素的定義是嵌套的該數(shù)組元素的定義是嵌套的這樣一來，每當(dāng)用elistidE規(guī)約時(shí)，elist就獲得了有關(guān)id的信息CompilerPrinciples41v 于是我們可以把含有數(shù)組元素的賦值語句的翻譯規(guī)則對(duì)應(yīng)每個(gè)產(chǎn)生式的語義動(dòng)作構(gòu)造出來了，下面還是看個(gè)例子先：v 設(shè)有說明array A1:10,1:20，給定賦值語句： (1)X:=AI,J; (2)AI+2,J+1:=M+N; 則(1)的四元式序列為： (*,I,20,T) i1d2 (+,J,T,T) i1d2+i2=VARPART=T (-,A,21,T1) a-C=CONSP

33、ART=T1 (=,T1T,-,T2) T2:=T1T (:=,T2,-,X) X:=T2CompilerPrinciples42v (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,-,T1T) M+NAI+2,J+1 參考書中參考書中給出了具體的翻譯模式，此處不再啰嗦給出了具體的翻譯模式，此處不再啰嗦。CompilerPrinciples43 三、控制三、控制流流語句的翻譯語句的

34、翻譯 布爾表達(dá)式在高級(jí)程序語言中只出現(xiàn)在兩個(gè)方面：求邏輯值和作為各種控制語句的條件表達(dá)式。顯然對(duì)布爾表達(dá)式求值的四元式的翻譯，我們完全可以仿照算術(shù)表達(dá)式的翻譯來進(jìn)行。 例如 ABC=D可翻譯成如下四元式序列： (=,C,D,T1) (,B,T1,T2) (,A,T2,T3) 但是對(duì)于控制語句中的條件表達(dá)式，我們還必須結(jié)合控制語句作進(jìn)一步的分析。CompilerPrinciples44 1. 條件語句中布爾表達(dá)式的翻譯 出現(xiàn)在條件語句if E then S1 else S2 中的布爾表達(dá)式E，它的作用僅在于控制對(duì)S1或S2的選擇,亦即提供“真”“假”出口，所以其值無需一直保留。E.codeS1.

35、codegoto S.nextS2.codeto E.trueto E.falseE.true:E.false:S.next:CompilerPrinciples45 于是我們可以采用一種優(yōu)化措施來處理，用一種遞推的方式來確定真假出口（短路）。 如：AB 可理解為 if A then true else B AB 可理解為 if A then B else false A 可理解為 if A then false else true ABC=D呢？ 根據(jù)這樣的思考，我們可以把作為控制條件的任何布爾表達(dá)式表示成僅含下列三種形式的四元式的序列： (jnz,a,-,p) (jnz,a,-,p) 表示

36、表示 if a goto p if a goto p (jrop,x,y,p) (jrop,x,y,p) 表示表示 if x rop y goto p if x rop y goto p (j,-,-,p) (j,-,-,p) 表示表示 goto p goto pCompilerPrinciples46v例： if ABC=D then S1 else S2 的四元式： 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.(S

37、2的四元式序列 ) q. CompilerPrinciples47 到此為止看起來翻譯四元式序列似乎問題不大了，只要把有關(guān)描述文法寫出，再配上相應(yīng)的語義動(dòng)作就可以了。例如：EEE|EE|E|(E)|i|i rop i配上語義動(dòng)作。 但是還有一個(gè)相當(dāng)麻煩的問題需要解決，就是有關(guān)轉(zhuǎn)移的四元式的第四部分（result）的轉(zhuǎn)移地址無法填寫（如上例中7，5，p+1等），因?yàn)樵谏稍撍脑降臅r(shí)候這個(gè)地址往往還是未知數(shù)。那么，該如何處理呢？CompilerPrinciples48 想一下我們編寫程序的時(shí)候，對(duì)于goto L ，在L還不知道的情況下是如何處理的呢？我們并沒有因?yàn)長還不知道就停滯不前，而是先記住

38、該語句的位置而把L處空出來，一直到編寫到L時(shí)，再回過頭來找到goto把L的值填上，那么該如何用算法實(shí)現(xiàn)這樣一個(gè)智能過程呢？ 那就是“回填(backpatching)”！和棧的使用一樣，這也是一種非常巧妙的技巧。它把一個(gè)由跳轉(zhuǎn)指令組成的列表以綜合屬性的形式進(jìn)行傳遞。下面結(jié)合著“標(biāo)號(hào)”來具體說明一下：CompilerPrinciples49 2.標(biāo)號(hào)和無條件轉(zhuǎn)移的翻譯標(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)用的無

39、條件轉(zhuǎn)移(向后轉(zhuǎn)移的goto L )，也很容易處理。對(duì)L查表得到它的定義地址p，就可生成goto L的四元式(j,-,-,p)。CompilerPrinciples50 (3)對(duì)于先應(yīng)用后定義的情況(前向轉(zhuǎn)移goto L )： 拉鏈返填:把所有以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)該欄作新鏈頭，

40、然后產(chǎn)生四元式(j,-,-,q)。 一旦標(biāo)號(hào)L定義時(shí)，我們將根據(jù)這條鏈回填那些待填轉(zhuǎn)移目標(biāo)的四元式，直到某個(gè)四元式的地址部分為0（鏈尾）。如下圖： CompilerPrinciples51(r) (j,-,-,q)(q) (j,-,-,p)(p) (j,-,-,y)(x) (j,-,-,0)未定義標(biāo)號(hào)的引用鏈符號(hào)表四元式CompilerPrinciples52 一般而言，假定用下面的產(chǎn)生式來定義帶標(biāo)號(hào)語句 Slabel S labeli: 那么，當(dāng)用labeli:進(jìn)行歸納時(shí)，應(yīng)作如下的語義動(dòng)作： .若若i i所指的標(biāo)示符所指的標(biāo)示符( (假定為假定為L)L)不在符號(hào)表中時(shí)，則把它填不在符號(hào)表中

41、時(shí)，則把它填入，置入，置“類型類型”為為“標(biāo)號(hào)標(biāo)號(hào)”，“定義否定義否”為為“已已”，“地址地址”為為nextquadnextquad； . .若若L L已在符號(hào)表中但已在符號(hào)表中但“類型類型”不為不為“標(biāo)號(hào)標(biāo)號(hào)”或或“定義否定義否”為為“已已”，則報(bào)錯(cuò)；，則報(bào)錯(cuò)； . .若若L L已在符號(hào)表中，則把標(biāo)志已在符號(hào)表中，則把標(biāo)志“未未”改為改為“已已”，然后把，然后把地址欄中的鏈頭（記為地址欄中的鏈頭（記為q q）取出，同時(shí)把）取出，同時(shí)把nextquadnextquad填在其中，填在其中，最后執(zhí)行最后執(zhí)行backpatch(q,nextquad)backpatch(q,nextquad)。Com

42、pilerPrinciples53 當(dāng)然，這兒“拉鏈”和“返填”都要用一個(gè)子程序（函數(shù)過程）來處理。 現(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ì) if E then S1 else s2 ，當(dāng)掃描了then 之后就可以返填E的“真”出口，因?yàn)檫@時(shí)已經(jīng)知道了S1的第一個(gè)四元式的編號(hào)了。但E的“假”出口還必須等到開始處理S2時(shí)才能返填。CompilerPrinciple

43、s54 3.循環(huán)與分情況語句的翻譯循環(huán)與分情況語句的翻譯 (1)循環(huán)語句 大多數(shù)程序語言中都有如下形式的循環(huán)句： Sfor i:=E1 step E2 until E3 do S1 其語義各語言可能有所不同，主要區(qū)別在先判斷、后執(zhí)行還是先執(zhí)行、后判斷。按Algol語言的解釋： i:=E1； goto over; again: i:=i+E2; over: if i=E3 then begin S1; goto again end;CompilerPrinciples55v 于是為了產(chǎn)生四元式，描述文法改寫如下： F1for i:=E1 F2F1 step E2 F3F2 until E3 SF

44、3 do S1 根據(jù)前面的解釋，i在幾處都用到，故ENTRY(i)必須保留下來，而該文法正是基于這樣的考慮而寫出來的。 于是語義動(dòng)作也就容易寫了：CompilerPrinciples56v 例如F1for i:=E1 對(duì)應(yīng)的語義動(dòng)作: (1)產(chǎn)生四元式：emit(:=,E1.place,-,ENTRY(i); (2)保留ENTRY(i)：F1.place:=ENTRY(i); (3)因?yàn)間oto over 的轉(zhuǎn)移地址暫時(shí)填不上，必須 建鏈：F1.chain:=nextquad; (4)產(chǎn)生無條件轉(zhuǎn)移指令：emit(j,-,-,0); (5)保留again的地址：F1.quad:=nextqua

45、d; 注意：在源程序的語句中，并沒有again，over這樣的標(biāo)號(hào)，因此也就沒有進(jìn)符號(hào)表的問題。CompilerPrinciples57 F2F1 step E2 : (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);CompilerPrinciples58 F3F2 until E3 ：這是一

46、個(gè)簡單的條件句，需要注意兩個(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);CompilerPrinciples59 SF3 do S1 ： (1)產(chǎn)生四元式： emit(j,-,-,F3.quad); (2)若S1建鏈，則也有返填問題：Backpatch(S1.chain,F3.q

47、uad) (3)轉(zhuǎn)離循環(huán)的轉(zhuǎn)移目標(biāo)留待處理外層S時(shí)再返填，故要保留：S.chain:=F3.chain 用于改變程序控制流的語句還有：goto, break, continue, return等。思考：這些語句應(yīng)如何處理？CompilerPrinciples60 (2)分情況語句 各種語言的分支語句不盡相同（case,switch等），這里我們假定其形式為左下所示： case E of C1 : S1; C2 : S2; Cn-1 : Sn-1; otherwise : Sn end;T:=E;T:=E;L L1 1: if TC: if TC1 1 goto L goto L2 2; ; S S1 1; goto next; g