1、第七講第七講 語義分析和語義分析和中間代碼產(chǎn)生中間代碼產(chǎn)生u語義分析概述語義分析概述u中間語言中間語言u幾種常用語句的翻譯幾種常用語句的翻譯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ù)1.審查每一個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法正確的結(jié)構(gòu)是否有意義。如：賦值語句：x:=x+y,左邊變量類型與右邊變量類型是否一致。2.在語義正確的基礎(chǔ)上生成一種中間代碼或目標(biāo)代碼。CompilerPrinciples5 二、語義分析的范圍二、語義分析的范圍1.確定類型：確定標(biāo)識符所關(guān)聯(lián)的數(shù)據(jù)類型。2.類型檢查：按語言的類型規(guī)則，檢查運(yùn)算的合法性與運(yùn)算分量類型的一致性，必要時(shí)作類型轉(zhuǎn)換。3.識別含義：根據(jù)語言的語義定義（形式或非形式），識別程序中各構(gòu)造成分組合到一起的含義，并作

3、相應(yīng)的語義處理（生成中間代碼或目標(biāo)代碼）。CompilerPrinciples64.控制流檢查：控制流語句必須轉(zhuǎn)移到合法的地方。 如C中，break語句規(guī)定跳出最內(nèi)層的循環(huán)或switch語句。5.一致性檢查：在很多場合要求對象只能被說明一次。如：pascal語言規(guī)定同一個(gè)標(biāo)識符在一個(gè)分程序中只能被說明一次等。6.相關(guān)名字檢查：如：Ada，循環(huán)或塊可以有一個(gè)名字，它出現(xiàn)在這些結(jié)構(gòu)的開頭或結(jié)尾。編譯程序必須檢查這兩個(gè)地方用的名字是否相同。其它：如名字的作用域分析等也是語義分析的工作。CompilerPrinciples7三、語義描述工具和語義分析方法三、語義描述工具和語義分析方法1.語義描述工具

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

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

6、 a+b ab+ a*(b+c) abc+* -a+b*c abc*+CompilerPrinciples11 二、圖表示法二、圖表示法 這里要介紹的圖表示圖表示包括DAG與我們前面介紹過的抽象語法樹。 1. 無循環(huán)有向圖（DAG） DAG與抽象語法樹基本上一樣，對表達(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+*buminusbuminusccassigna+*b

7、uminusca:=ba:=b* *-c+b-c+b* *-c-c的圖表示法的圖表示法抽象語法樹DAGCompilerPrinciples13 2.再來看A*B+C*D的樹、后綴式后綴式：AB*CD*+ 不難看出，后綴式實(shí)際上是抽象語法樹的線性表示形式（后序表示）； +*ABCDCompilerPrinciples14 3.樹表示的翻譯法： 例： 產(chǎn)生式 語義動作 (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 E.val:=LEAF(i)建

8、立一棵新樹，以建立一棵新樹，以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+y*z (1) * y z (2

9、) + x (1) 這兒實(shí)際實(shí)現(xiàn)時(shí)x,y,z也都是指示器，指向這些變量在符號表中的位置。算符OP一般用整數(shù)編碼，而且可以加進(jìn)一些諸如類型之類的信息。 指示器-指向（1）在表格中的位置CompilerPrinciples16 對于一目運(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)CompilerPrinciples1

10、7樹、后綴式與三元式OPARG1ARG2(1)*AB(2)*CD(3)+(1)(2) 后綴式：AB*CD*+ 后綴式實(shí)際上是抽象語法樹的線性表示形式（后序表示）；樹是三元式的翻版，每個(gè)三元式對應(yīng)一棵（二叉）子樹，最后的三元式對應(yīng)樹根。+*ABCDCompilerPrinciples18 3.語法制導(dǎo)產(chǎn)生三元式 (1) EE1 op E2 我們用E.val表示一個(gè)指示器，它或指向有關(guān)符號表的某項(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在符號表中的位置。若用LOOKUP(NAME)函數(shù)表示對NAME查找符號表，找到則返回表項(xiàng)位置，找不到則返回NULL。 于是可如下實(shí)現(xiàn)： 詞法分析器掃描到標(biāo)識符i時(shí)送回（種別碼，i值），語法分析器把i放入語義變量i.LEXCAL中，這時(shí)就可以調(diào)用ENTRY過程： CompilerPrinciples20 FUNCTION ENTRY(NAME) BEGIN ENTRY:=LOOKUP(NAME); IF ENTRY=NULL THEN

12、ERROR; END 由于三元式的計(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)的間接三元式的間接三元式OPARG1ARG2(1)+AB(2)*(1)C(3

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

14、*(C-D)-E/FG的四元式為： OP ARG1 ARG2 RESULT - C D T1 * B T1 T2 + A T2 T3 F G T4 / E T4 T5 - T3 T5 T6 CompilerPrinciples24v規(guī)定凡只有一個(gè)運(yùn)算量時(shí)只用ARG1。v以上的Ti都是臨時(shí)變量，其處理方法可以像用戶自定義變量一樣進(jìn)符號表，也可以直接用某種整數(shù)碼表示。OPARG1ARG2RESULT(1)B-T1(2)+CDT2(3)*T1T2T3(4):=T3-A賦值語句賦值語句A:=-BA:=-B* *(C+D)(C+D)填倒順序也可填倒順序也可式之間的聯(lián)系與三元式不同（通過指示器），它是通過

15、臨式之間的聯(lián)系與三元式不同（通過指示器），它是通過臨時(shí)變量，所以更動四元式很容易，這就為優(yōu)化提供了方便，時(shí)變量，所以更動四元式很容易，這就為優(yōu)化提供了方便，因?yàn)椴粻砍兜礁淖冎甘酒鞯膯栴}。因?yàn)椴粻砍兜礁淖冎甘酒鞯膯栴}。從以上例子可以看出，四元式出現(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,

16、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 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參考書中推薦的三地址指令形式：參考書中推薦的三地址指令形式：

17、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過程返回過程返回 return yv索引賦值索引賦值x := yi和和 xi := yv地址和指針賦值地址和指針賦值x := &y，x := y和和 x := yCompilerPrinciples273.3.某些語句的四元式及翻譯某些語句的四元式及翻譯 一、說明語句的翻譯一、說明語句的翻譯 程序語言中的說明語句都是給編譯程序提供信息的，諸如類型、維數(shù)、每維的界

18、種類等，因此一般不生成目標(biāo)，只是在編譯時(shí)把有關(guān)信息填入相應(yīng)表格即可。為局部名字建立符號表?xiàng)l目為它分配存儲單元符號表中包含名字的類型和分配給它的存儲單元的相對地址等信息 CompilerPrinciples28 1.簡單說明句：用一個(gè)基本字來定義一串名字，其語法描述一般為： Dinteger namelistreal namelist namelistnamelist,ii 直接用這種文法來制導(dǎo)翻譯有點(diǎn)麻煩，就是只能在把所有名字規(guī)約成namelist之后才能把性質(zhì)登記到符號表中。這就意味著在掃描名字時(shí)，應(yīng)把名字用一個(gè)隊(duì)列（或棧）保存起來，然后再處理。實(shí)際上，我們可以對文法稍做改動，就可以免去建立

19、隊(duì)列或棧的過程。修改文法如下： DD,iinteger ireal i CompilerPrinciples29v 例： integer i1,i2,i3詞法分析后：詞法分析后： int iint i1 1 , i , i2 2 , 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分析器分析器語義動作：語義動作：FILL(ENTRY(iFILL(ENTRY(i2 2)

20、,D),D1 1ATT);ATT); D DATT:=DATT:=D11ATTATT DD DD1 1 ,i ,i2 2語義動作：語義動作：FILL(ENTRY(iFILL(ENTRY(i1 1),int);),int); D DATT:=intATT:=int Dinteger i Dinteger i1 1.CompilerPrinciples30 2.數(shù)組說明：遇到數(shù)組說明，應(yīng)把有關(guān)信息收集到一個(gè)“內(nèi)情向量”表格之中，每個(gè)數(shù)組對應(yīng)一個(gè)“內(nèi)情向量”。例如，arrayl1:u1,l2:u2,ln:un的內(nèi)情向量為： di=ui-li+1所求地址: D=CONSPART+VARPART CON

21、SPART=a-C C=(l1d2+l2)d3+l3)d4+)+ln-1)dn+lnl1u1d1l2u2d2lnundnnCtypea維數(shù)維數(shù)類型類型數(shù)組首址CompilerPrinciples31v 顯然，內(nèi)情向量的大小完全由維數(shù)決定。一般來說，像FORTRAN,ALGOL,PASCAL等語言的程序，其內(nèi)情向量在編譯時(shí)完全可以確定了。關(guān)于內(nèi)情向量的填寫，編譯時(shí)完全可以做了，而且是只在編譯時(shí)使用，故可以把它安排成符號表的一部分，無須帶到目標(biāo)程序運(yùn)行階段。但有時(shí)為了處理方便，也一起帶到目標(biāo)程序中。v 對動態(tài)數(shù)組，則編譯時(shí)開辟出信息向量表區(qū)，同時(shí)應(yīng)有填寫信息向量的目標(biāo)指令，我們可以用如下一個(gè)子程序

22、來處理。該程序的入口參數(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 WHILE 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; EN

23、D; 申請申請N N個(gè)單元的數(shù)組空間，令其首址為個(gè)單元的數(shù)組空間，令其首址為a;a; 把把n,C,typen,C,type和和a a填入內(nèi)情向量中填入內(nèi)情向量中 ENDEND； 其他記錄說明、過程說明的翻譯也大同小異，此處不再贅述。CompilerPrinciples33 二、賦值語句的翻譯二、賦值語句的翻譯 1.簡單算術(shù)表達(dá)式的賦值語句： 所謂簡單指不考慮數(shù)組元素、記錄、函數(shù)的引用等情況。對這種算術(shù)表達(dá)式和賦值語句的四元式我們已經(jīng)介紹過，現(xiàn)在就來看看如何翻譯。我們先來討論所有分量都是相同類型的情況，如都是整型。于是，我們可用如下的二義文法來進(jìn)行描述： Sid:=E EESid:=E EE1

24、1+E+E2 2EE1 1* *E E2 2(E(E1 1)-E)-E1 1idid CompilerPrinciples34v語義動作： Sid:=E p:=lookup();Sid:=E p:=lookup(); if (p!=nil) then 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.pla

25、ce:= 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 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)

26、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)算，有的不允許。如果不允許，則發(fā)現(xiàn)有類型不相同的運(yùn)算分量就應(yīng)該報(bào)錯。如果允許，就要進(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)改動，使其在必要時(shí)能產(chǎn)生對運(yùn)算分量

27、進(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) 語義動作： 對Ei來說， E.place:= ENTRY(i)現(xiàn)在應(yīng)加上E.MODE:=MODE(i); 而對EE1 op E2 ，其語義子程序可以用如下流程圖來表示：CompilerPrinciples37T1:=newtempT1:=newtempstartE1.MODE=intE1.MODE=int&E2.MODE=int&E2.M

28、ODE=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 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.p

29、lace,-,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.place,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ù)組元素的引用主要存

30、在一個(gè)下標(biāo)地址的計(jì)算問題，這取決于數(shù)組在存儲器中的存放方式，故不同的存放方式會產(chǎn)生不同的中間代碼。以下我們以按行存放方式加以說明。 前面說過，數(shù)組元素的地址D=CONSPART+VARPART而CONSPART=a-C,其中 C=(l1d2+l2)d3+l3)d4+)+ln-1)dn+ln 靜態(tài)數(shù)組的信息向量在編譯過程中就可填寫，動態(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ì)算出來

31、，放入臨時(shí)變量T中，并用T作“變址器”，把CONSPART=a-C計(jì)算出來，放入臨時(shí)變量T1中，并用T1作“基址”。v 這樣一來，對數(shù)組元素的引用可用變址方式進(jìn)行：D=T1T；進(jìn)而X:=T1T的四元式可寫為(=,T1T,-,X)，這兒=是“變址取數(shù)”操作。其實(shí)還可寫成：(=,T1,T,X)。類似地，“變址存數(shù)”操作可寫成 (=,X,-,T1T)，即XT1T。CompilerPrinciples40 (2)數(shù)組元素引用的翻譯 首先對包含數(shù)組元素的賦值語句給出如下模式的文法： AV:=E Videlist|id elistelist,E|E EE+E|(E)|V 使用該文法計(jì)算VARPART不太方

32、便，因?yàn)樵谡麄€(gè)elist的翻譯過程中隨時(shí)都需要知道數(shù)組名id的符號表入口，以獲得關(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中只給出中只給出+ +，可認(rèn)為代表，可認(rèn)為代表op;op;(3)(3)該數(shù)組元素的定義是嵌套的該數(shù)組元素的定義是嵌套的這樣一來，每當(dāng)用elistidE規(guī)約時(shí)，elist就獲得了有關(guān)id的信息CompilerPrinciples41v 于是我們可以把含有數(shù)組元素的賦值語句的翻譯規(guī)則對應(yīng)每個(gè)產(chǎn)生式的語義動作構(gòu)造出來了，下面還是看個(gè)例子先

33、：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=CONSPART=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

34、,T1) a-C=CONSPART (+,M,N,T4) M+N (=,T4,-,T1T) M+NAI+2,J+1 參考書中給出了具體的翻譯模式，此處不再啰嗦。參考書中給出了具體的翻譯模式，此處不再啰嗦。CompilerPrinciples43 三、控制流語句的翻譯三、控制流語句的翻譯 布爾表達(dá)式在高級程序語言中只出現(xiàn)在兩個(gè)方面：求邏輯值和作為各種控制語句的條件表達(dá)式。顯然對布爾表達(dá)式求值的四元式的翻譯，我們完全可以仿照算術(shù)表達(dá)式的翻譯來進(jìn)行。 例如 ABC=D可翻譯成如下四元式序列： (=,C,D,T1) (,B,T1,T2) (,A,T2,T3) 但是對于控制語句中的條件表達(dá)式，我們還必須

35、結(jié)合控制語句作進(jìn)一步的分析。CompilerPrinciples44 1. 條件語句中布爾表達(dá)式的翻譯 出現(xiàn)在條件語句if E then S1 else S2 中的布爾表達(dá)式E，它的作用僅在于控制對S1或S2的選擇,亦即提供“真”“假”出口，所以其值無需一直保留。E.codeS1.codegoto S.nextS2.codeto E.trueto E.falseE.true:E.false:S.next:CompilerPrinciples45 于是我們可以采用一種優(yōu)化措施來處理，用一種遞推的方式來確定真假出口（短路）。 如：AB 可理解為 if A then true else B AB 可

36、理解為 if A then B else false A 可理解為 if A then false else true ABC=D呢？ 根據(jù)這樣的思考，我們可以把作為控制條件的任何布爾表達(dá)式表示成僅含下列三種形式的四元式的序列： (jnz,a,-,p) (jnz,a,-,p) 表示表示 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

37、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.(S2的四元式序列 ) q. CompilerPrinciples47 到此為止看起來翻譯四元式序列似乎問題不大了，只要把有關(guān)描述文法寫出，再配上相應(yīng)的語義動作就可以了。例如：EEE|EE|E|(E)|i|i rop i配上語義動作。 但是還有一個(gè)相當(dāng)麻煩的問題需要解決，就是有關(guān)轉(zhuǎn)移的四元式的第四部分（result）的轉(zhuǎn)

38、移地址無法填寫（如上例中7，5，p+1等），因?yàn)樵谏稍撍脑降臅r(shí)候這個(gè)地址往往還是未知數(shù)。那么，該如何處理呢？CompilerPrinciples48 想一下我們編寫程序的時(shí)候，對于goto L ，在L還不知道的情況下是如何處理的呢？我們并沒有因?yàn)長還不知道就停滯不前，而是先記住該語句的位置而把L處空出來，一直到編寫到L時(shí)，再回過頭來找到goto把L的值填上，那么該如何用算法實(shí)現(xiàn)這樣一個(gè)智能過程呢？ 那就是“回填(backpatching)”！和棧的使用一樣，這也是一種非常巧妙的技巧。它把一個(gè)由跳轉(zhuǎn)指令組成的列表以綜合屬性的形式進(jìn)行傳遞。下面結(jié)合著“標(biāo)號”來具體說明一下：CompilerPr

39、inciples49 2.標(biāo)號和無條件轉(zhuǎn)移的翻譯標(biāo)號和無條件轉(zhuǎn)移的翻譯 (1)對于說明性出現(xiàn)的標(biāo)號，很容易處理： L: S 當(dāng)這種語句被處理之后，標(biāo)號L被稱為“定義了”的。也就是，在符號表中，標(biāo)號L的“地址”欄將登記上語句S的第一個(gè)四元式的地址（編號）。 (2)對于先定義后應(yīng)用的無條件轉(zhuǎn)移(向后轉(zhuǎn)移的goto L )，也很容易處理。對L查表得到它的定義地址p，就可生成goto L的四元式(j,-,-,p)。CompilerPrinciples50 (3)對于先應(yīng)用后定義的情況(前向轉(zhuǎn)移goto L )： 拉鏈返填:把所有以L為轉(zhuǎn)移目標(biāo)的四元式串在一起。鏈的首地址放在符號表中L的“地址”欄中。

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

41、)未定義標(biāo)號的引用鏈符號表四元式CompilerPrinciples52 一般而言，假定用下面的產(chǎn)生式來定義帶標(biāo)號語句 Slabel S labeli: 那么，當(dāng)用labeli:進(jìn)行歸納時(shí)，應(yīng)作如下的語義動作： .若若i i所指的標(biāo)示符所指的標(biāo)示符( (假定為假定為L)L)不在符號表中時(shí)，則把它填不在符號表中時(shí)，則把它填入，置入，置“類型類型”為為“標(biāo)號標(biāo)號”，“定義否定義否”為為“已已”，“地址地址”為為nextquadnextquad； . .若若L L已在符號表中但已在符號表中但“類型類型”不為不為“標(biāo)號標(biāo)號”或或“定義否定義否”為為“已已”，則報(bào)錯；，則報(bào)錯； . .若若L L已在符號

42、表中，則把標(biāo)志已在符號表中，則把標(biāo)志“未未”改為改為“已已”，然后把，然后把地址欄中的鏈頭（記為地址欄中的鏈頭（記為q q）取出，同時(shí)把）取出，同時(shí)把nextquadnextquad填在其中，填在其中，最后執(zhí)行最后執(zhí)行backpatch(q,nextquad)backpatch(q,nextquad)。CompilerPrinciples53 當(dāng)然，這兒“拉鏈”和“返填”都要用一個(gè)子程序（函數(shù)過程）來處理。 現(xiàn)在返回到那些無法填寫轉(zhuǎn)移地址的四元式的處理上，它完全是按照如上講的方法進(jìn)行的。這就要記住每條四元式的編號。因?yàn)橛小罢?、假”出口的問題 ，所以對文法中的非終結(jié)符還要引進(jìn)兩個(gè)語義值，如E.T

43、C,E.FC。建鏈在產(chǎn)生四元式的時(shí)候就可以做了，而返填必須在標(biāo)號定義后才能進(jìn)行。 如對 if E then S1 else s2 ，當(dāng)掃描了then 之后就可以返填E的“真”出口，因?yàn)檫@時(shí)已經(jīng)知道了S1的第一個(gè)四元式的編號了。但E的“假”出口還必須等到開始處理S2時(shí)才能返填。CompilerPrinciples54 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；

44、 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 SF3 do S1 根據(jù)前面的解釋，i在幾處都用到，故ENTRY(i)必須保留下來，而該文法正是基于這樣的考慮而寫出來的。 于是語義動作也就容易寫了：CompilerPrinciples56v 例如F1for i:=E1 對應(yīng)的語義動作: (1)產(chǎn)生四元式：emit(:=,E1.place,-

45、,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:=nextquad; 注意：在源程序的語句中，并沒有again，over這樣的標(biāo)號，因此也就沒有進(jìn)符號表的問題。CompilerPrinciples57 F2F1 step E2 : (1)again的地址應(yīng)繼續(xù)保留： F2.quad:=F1.quad; (2)i的符號表入口也要保留： F2.place:

46、=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 ：這是一個(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)假出口還不

47、知道，則建鏈：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.quad) (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; goto next;L L2 2: if T