第8章語法制導(dǎo)翻譯和中間代碼生成

第8章語法制導(dǎo)翻譯

和中間代碼生成語法分析的作用是判斷一個(gè)輸入是否為一個(gè)句子，并且同時(shí)獲得該句子的語法結(jié)構(gòu)，即語法樹。例如在算術(shù)表達(dá)式的翻譯中，不僅要知道表達(dá)式中各個(gè)運(yùn)算的先后次序，即語法結(jié)構(gòu)，而且還要知道該表達(dá)式中的各個(gè)變量和常量的內(nèi)存地址或值，要知道計(jì)算過程的中間結(jié)果所存放的內(nèi)存地址或值，甚至還要知道其數(shù)據(jù)類型。這些信息都被稱為語義信息，而對(duì)語義信息進(jìn)行相應(yīng)的分析處理就叫做語義分析。因此，翻譯是一個(gè)語法分析和語義分析綜合在一起進(jìn)行的過程。在編譯程序中使用了這樣的一種技術(shù)，就是在語法分析的同時(shí)進(jìn)行語義分析的工作，并同步地完成相應(yīng)語句的翻譯。這種技術(shù)就稱為語法制導(dǎo)翻譯。第5章教學(xué)內(nèi)容屬性文法的概念；語法制導(dǎo)翻譯的概念；常用的中間代碼形式；程序設(shè)計(jì)語言的語法結(jié)構(gòu)的自底向上的語法制導(dǎo)翻譯方法。一、屬性文法屬性文法是在上下文無關(guān)文法的基礎(chǔ)上為每個(gè)文法符號(hào)（終結(jié)符或非終結(jié)符）配備若干個(gè)相關(guān)的“值”（稱為屬性）。這些屬性代表與文法符號(hào)相關(guān)的信息，例如它的類型、值、代碼序列、符號(hào)表內(nèi)容等等。屬性和變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性一般分為兩類：綜合屬性和繼承屬性。簡(jiǎn)單的說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。屬性加工的過程即是語義處理的過程，對(duì)于文法的每一個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，則稱為語義規(guī)則。在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條語義規(guī)則的形式為：b:=f(c1,c2,…,ck)

這里f是一個(gè)函數(shù)，而且或者（1）b是A的一個(gè)綜合屬性并且c1,c2,…ck是產(chǎn)生式右邊文法符號(hào)的屬性；或者（2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1,c2,…ck是A或產(chǎn)生式右邊任何文法符號(hào)的屬性。在這兩種情況下，屬性b依賴于屬性c1,c2…,ck。要特別強(qiáng)掉的是：終結(jié)符只有綜合屬性，它由詞法分析器提供；非終結(jié)符既可以有綜合屬性也可以有繼承屬性，文法開始符號(hào)的所有繼承屬性作為屬性計(jì)算前的初始值。一般來講，對(duì)出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個(gè)計(jì)算規(guī)則，屬性計(jì)算規(guī)則中只能使用相應(yīng)產(chǎn)生式的文法符號(hào)的屬性，這有利于產(chǎn)生式范圍內(nèi)“封裝”屬性的依賴性。然而，出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算,由屬性計(jì)算器的參數(shù)提供。語義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語義檢查、符號(hào)表操作、代碼生成等。語義規(guī)則可能產(chǎn)生副作用（如產(chǎn)生代碼），也可能不是變?cè)膰?yán)格函數(shù)（如某個(gè)規(guī)則給出可用的下一個(gè)數(shù)據(jù)單元的地址）。這樣的語義規(guī)則通常寫成過程調(diào)用，或過程段。綜合屬性在語法樹中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。因此，通常使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語義規(guī)則計(jì)算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S—屬性文法。繼承屬性在語法樹中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定。用繼承屬性來表示程序語言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。屬性文法的定義【定義】一個(gè)屬性文法AG是一個(gè)四元組，即AG=(G,A,R,B)，其中⑴G=(N,T,S,P)是一個(gè)前后文無關(guān)文法；⑵A=∪XN∪TA(X)是一個(gè)屬性的有限集合；⑶R=∪pPR(p)是一個(gè)語義規(guī)則式的有限集合；⑷B=∪pPB(p)是一個(gè)條件的有限集合；屬性文法的定義并且滿足以下兩個(gè)條件：1．對(duì)任意兩個(gè)符號(hào)的X和Y，若X≠Y，則A(X)∩A(Y)=；2．對(duì)于任何在L(G)的句子所對(duì)應(yīng)的語法樹上出現(xiàn)的符號(hào)X，X的任意一個(gè)屬性X.a的計(jì)算，至多只有一條語義規(guī)則式可以應(yīng)用。

屬性文法示例【例5．1】簡(jiǎn)單臺(tái)式計(jì)算器的算術(shù)表達(dá)式的屬性文法：產(chǎn)生式集G:語義規(guī)則式集R:LE{print(E.val)}EE1+T{E.val=E1.val+T.val}ET{E.val=T.val}TT1

*F{T.val=T1.val×F.val}TF{T.val=F.val}F(E){F.val=E.val}Fdigit{F.val=digit.lexval}

示例

在該描述中，每個(gè)非終結(jié)符都有一個(gè)屬性：一個(gè)整數(shù)值的稱作val的屬性。按照語義規(guī)則對(duì)每個(gè)產(chǎn)生式來說，它的左部E，T，F(xiàn)的屬性值的計(jì)算來自它右部的非終結(jié)符，這種屬性稱作綜合屬性。單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。和產(chǎn)生式LE相聯(lián)的語義規(guī)則是一個(gè)過程，打印由E產(chǎn)生的表達(dá)式的值。我們可以理解為L的屬性是空的或是虛的。設(shè)表達(dá)式為3*5+4，則語義動(dòng)作打印數(shù)值19LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。LR分析器增加語義棧。#X1…XmI0I1…Im

語義棧

-X1.VAL…Xm

.VALSLR(1)分析表digit+*()＃ETF0s5s41231s6acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5狀態(tài)ACTIONGOTO步驟分析棧棧頂狀態(tài),輸入符剩余輸入串10#-Action[0,2]=S5移進(jìn)22+3*5#205#2--Action[5,+]=r6用F→digit歸約，執(zhí)行語義動(dòng)作F.val=2+3*5#303#F-2Action[3,+]=r4用T→F歸約，執(zhí)行語義動(dòng)作T.val=F.val+3*5#LR分析：增加語義棧歸約時(shí)進(jìn)行語義動(dòng)作。給出２＋３*５的分析和計(jì)值過程。步驟分析棧棧頂狀態(tài),輸入符剩余輸入串402#T-2Action[2,+]=r2用E→T歸約，執(zhí)行語義動(dòng)作E.val=T.val+3*5#501#E-2Action[1,+]=S6移進(jìn)++3*5#6016#E+-2-Action[6,3]=S5移進(jìn)33*5#70165#E+3-2--Action[5,*]=r6用F→digit歸約，執(zhí)行語義動(dòng)作F.val=3

*5#80163

#E+F-2-3Action[3,*]=r4用T→F歸約，執(zhí)行語義動(dòng)作T.val=F.val

*5#90169#E+T-2-3Action[9,*]=S7移進(jìn)*

*5#1001697#E+T*-2-3-Action[7,5]=S5移進(jìn)5

5#11016975#E+T*5-2-3--Action[5,#]=r6用F→digit歸約,執(zhí)行語義動(dòng)作F.val=5#120169710#E+T*F-2-3-5Action[10,#]=r3用T→T*F歸約,執(zhí)行語義動(dòng)作T.val=T.val×F.val＝3×5＝15

#130169#E+T-2-15Action[9,#]=r1用E→E+T歸約,執(zhí)行語義動(dòng)作E.val=E.val＋T.val＝2＋15＝17

#1401#E-17Action[1,#]=acc成功接收輸入串#二.語義分析的任務(wù)

編譯程序的任務(wù)是把源程序翻譯成目標(biāo)程序，這個(gè)目標(biāo)程序必須和源程序的語義等同，也就是說，盡管它們的語法結(jié)構(gòu)完全不同，但它們所表達(dá)的結(jié)果應(yīng)完全相同。通常，在詞法分析程序和語法分析程序?qū)υ闯绦虻恼Z法結(jié)構(gòu)進(jìn)行分析之后，要么由語法分析程序直接調(diào)用相應(yīng)的語義子程序進(jìn)行語義處理，要么首先生成語法樹或該結(jié)構(gòu)的某種表示，再進(jìn)行語義處理。編譯中的語義處理是指兩個(gè)功能：審查每個(gè)語法結(jié)構(gòu)的靜態(tài)語義，即驗(yàn)證語法結(jié)構(gòu)合法的程序是否真正有意義。有時(shí)把這個(gè)工作稱為靜態(tài)語義分析或靜態(tài)審查。如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，即，要么生成程序的一種中間表示形式（中間代碼），要么生成實(shí)際的目標(biāo)代碼。

通常包括：類型檢查?？刂屏鳈z查?？刂屏髡Z句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語言中break語句使控制跳離包括該語句的最小while、for或switch語句。如果不存在包括它的語句，則報(bào)錯(cuò)。一致性檢查。在很多場(chǎng)合要求對(duì)象只能被定義一次。例如Pascal語言規(guī)定同一標(biāo)識(shí)符在一個(gè)分程序中只能被說明一次，同一case語句的標(biāo)號(hào)不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。相關(guān)名字檢查。有時(shí)，同一名字必須出現(xiàn)兩次或多次。例如，Ada語言程序中，循環(huán)或程序塊可以有一個(gè)名字，出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，編譯程序必須檢查這兩個(gè)地方用的名字是相同的。名字的作用域分析。三、中間代碼翻譯為中間語言的好處：（1）便于進(jìn)行與機(jī)器無關(guān)的代碼優(yōu)化；（2）使編譯程序改變目標(biāo)機(jī)更容易；（3）使編譯程序的結(jié)構(gòu)在邏輯上更為簡(jiǎn)單明確，以中間語言為界面，編譯前端和后端的接口更清晰。編譯程序所使用的中間代碼有多種形式。常見的有逆波蘭式、三元式和樹形、四元式表示。1.逆波蘭式逆波蘭式是最簡(jiǎn)單的一種中間代碼表示形式，早在編譯程序出現(xiàn)之前，它就用于表示算術(shù)表達(dá)式，是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的。這種表示法將運(yùn)算對(duì)象寫在前面，把運(yùn)算符號(hào)寫在后面，比如把a(bǔ)+b寫成ab+，把a(bǔ)*b寫成ab*，用這種表示法表示的表達(dá)式也稱做后綴式。示例中綴算術(shù)表達(dá)式逆波蘭式a+bab+a+b*cabc*+(a+b)*cab+c*a=b*c+d*eabc*de*+=a=b*(c+b)*d/eabcb+*d*e/=后綴表示法表示表達(dá)式，其最大的優(yōu)點(diǎn)是易于計(jì)算機(jī)處理表達(dá)式。常用的算法是使用一個(gè)棧，自左至右掃描算術(shù)表達(dá)式（后綴表示），每掃描到運(yùn)算對(duì)象，就把它推進(jìn)棧；掃描到運(yùn)算符，若該運(yùn)算符是二目的，則對(duì)棧頂部的兩個(gè)運(yùn)算對(duì)象實(shí)施該運(yùn)算，并將運(yùn)算結(jié)果代替這兩個(gè)運(yùn)算對(duì)象而進(jìn)棧；若是一目運(yùn)算符，則對(duì)棧頂元素執(zhí)行該運(yùn)算，并以運(yùn)算結(jié)果代替該元素進(jìn)棧，最后的結(jié)果留在棧頂。由于后綴式表示上的簡(jiǎn)潔和計(jì)值的方便，特別適用于解釋執(zhí)行的程序設(shè)計(jì)語言的中間表示，也方便具有堆棧體系的計(jì)算機(jī)的目標(biāo)代碼生成。2.三元式和樹形表示另一類中間代碼形式是三元式。把表達(dá)式及各種語句表示成一組三元式。每個(gè)三元式由三個(gè)部分組成，分別是：(算符op，第一運(yùn)算對(duì)象ARG1，第二運(yùn)算對(duì)象ARG2)運(yùn)算對(duì)象可能是源程序中的變量，也可能是某個(gè)三元式的結(jié)果，用三元式的編號(hào)表示。對(duì)于一目算符op，只需選用一個(gè)運(yùn)算對(duì)象，不妨規(guī)定只用ARG1。至于多目算符，可用若干個(gè)相繼的三元式表示。

示例【例如】a=b*c+d*e的三元式表示為：

（1）（*，b，c）

（2）（*，d，e）

（3）（+，（1），（2））

（4）（＝，（3），a）樹形表示樹形表示是三元式表示的翻版。bc**+ade=3.四元式四元式是一種比較普遍采用的中間代碼形式。四元式的四個(gè)組成成分是：算符op第一運(yùn)算對(duì)象ARG1第二運(yùn)算對(duì)象ARG2運(yùn)算結(jié)果RESULT運(yùn)算對(duì)象和運(yùn)算結(jié)果有時(shí)指用戶自己定義的變量，有時(shí)指編譯程序引進(jìn)的臨時(shí)變量。示例四元式形式：

(op,arg1,arg2,result)【例如】a=b*c+d*e的四元式為：

（1）（*，b，c，T1）

（2）（*，d，e，T2）

（3）（+，

T1，T2，

T3）

（4）（=，T3，－，

a）四元式表示很類似于三地址指令，確實(shí)，有時(shí)把這類中間表示稱為“三地址代碼”，因?yàn)檫@種表示可看作一種虛擬三地址機(jī)的通用匯編碼，即這種虛擬機(jī)的每條“指令”包含操作符和三個(gè)地址，兩個(gè)是為運(yùn)算對(duì)象的，一個(gè)是為結(jié)果的。這種表示對(duì)于代碼優(yōu)化和目標(biāo)代碼生成都較有利。示例為了更直觀，也把四元式的形式寫成簡(jiǎn)單賦值形式或更易理解的形式：result＝arg1oparg2【例如】把上述四元式序列寫成：（1）t1=b*c（2）t2=b*d

（3）t3=t1+t2

（4）a=t3（jump，－，－，L）寫成gotoL（jrop，B，C，L）寫成ifBropCgotoL例如:A+B*(C-D)+E/(C-D)^N四、簡(jiǎn)單賦值語句的翻譯語義過程GEN表示產(chǎn)生一個(gè)四元式，并且填入四元式表中。語義過程N(yùn)ewtemp表示生成一個(gè)臨時(shí)變量，每調(diào)用一次，生成一新的臨時(shí)變量。語義變量E．place，表示存放E值的變量名在符號(hào)表的登錄項(xiàng)或一整數(shù)碼（若此變量是一個(gè)臨時(shí)變量）。語義變量Entry(id)回送標(biāo)識(shí)符id在符號(hào)表中的入口地址。簡(jiǎn)單賦值語句的屬性文法產(chǎn)生式語義規(guī)則

S→id=E{GEN（=，E.Place，_，Entry(id)）}E→E1+E2{E.place=Newtemp；GEN(+,E1.place,E2.place,E.place)}E→E1*E2{E．place=Newtemp；GEN(*,E1.place,E2.place,E.Place)}E→－E1{E.place=Newtemp；GEN(@,E1.place,_,E.place)}E→（E1）{E.place=E1.place}E→id{E.place=Entry(id)}a=b*c+d*e的翻譯過程a=b*c+d*e

E(c)EE(b)E(d)E(e)T11.(*,b,c,T1)ET22.(*,d,e,T2)ET33.(+,T1,T2,T3)S4.(=,T3,_,a)（1）（*，b，c，T1）

（2）（*，d，e，T2）

（3）（+，T1，T2，T3）

（4）（=，T3，_，a）a=b*c+d*e的翻譯結(jié)果a=-b*(c+d)的翻譯過程略。類型轉(zhuǎn)換的語義處理實(shí)際上，在一個(gè)表達(dá)式中可能會(huì)出現(xiàn)各種不同類型的變量或常數(shù)。即編譯程序還應(yīng)執(zhí)行這樣的語義動(dòng)作：對(duì)表達(dá)式中的運(yùn)算對(duì)象應(yīng)進(jìn)行類型檢查，如不能接受不同類型的運(yùn)算對(duì)象的混合運(yùn)算，則應(yīng)指出錯(cuò)誤；如能接受混合運(yùn)算，則應(yīng)進(jìn)行類型轉(zhuǎn)換的語義處理。例如，算術(shù)表達(dá)式可以進(jìn)行實(shí)型量與整型量的混合運(yùn)算，并且約定，當(dāng)兩個(gè)不同類型的量進(jìn)行運(yùn)算時(shí)，必須首先將整型量轉(zhuǎn)換為實(shí)型量。語義變量語義變量E．type表示E的類型信息；為區(qū)別整型加（乘）和實(shí)型加（乘），把+（*）分別寫作+i（*

i）和+r（*

r）。用一目算符itr表示將整型運(yùn)算對(duì)象轉(zhuǎn)換成實(shí)型。示例產(chǎn)生式：E→E1*E2語義動(dòng)作：｛E．place=Newtemp；

ifE1.type=intANDE2.type＝int{

GEN（*i，E1.place，E2.place，E.place,）；

E．type=int}

elseifE1.type=realANDE2.type=real{

GEN(*r,E1．place,E2．place,E.place);

E.type=real}示例elseifE1.type＝int/*andE2.type=real*/{t=Newtemp；

GEN（itr，E1.place，_，t）；

GEN（*r，t，E2.place，E.place,）

E.type=real}

else/*E1·type＝realandE2．type＝int*/

{t=Newtemp；

GEN（itr，E2.place，_，t）；

GEN（*r，E1.place，t，E.place,） E．type=real｝}五、布爾表達(dá)式的翻譯程序設(shè)計(jì)語言中的布爾表達(dá)式有兩個(gè)作用。一是計(jì)算邏輯值，二是用做改變控制流語句中的條件表達(dá)式，如在if-then，if-then-else，或是while-do語句中那樣。布爾表達(dá)式是由布爾算符and，or和not施于布爾變量或關(guān)系表達(dá)式而成。即布爾表達(dá)式的形式為E1ropE2，其中E1和E2都是算術(shù)表達(dá)式，rop是關(guān)系符，如＜＝，＜，＝，〉＝，≠等等。只考慮簡(jiǎn)單的布爾表達(dá)式文法：

E→EandE|EorE|notE|idropid|id并且按通常習(xí)慣，約定布爾算符的優(yōu)先順序（從高到低）為not、and、or，并且and和or服從左結(jié)合。布爾表達(dá)式的翻譯方法通常，計(jì)算布爾表達(dá)式的值有兩種辦法，第一種辦法，如同計(jì)算算術(shù)表達(dá)式一樣，計(jì)算出各部分的真假值，最后計(jì)算出整個(gè)表達(dá)式的值。例如，用數(shù)值1表示true，用0表示false。那么布爾表達(dá)式1or（not0and0）or0的計(jì)算過程是：

1or（not0and0）or0

＝1or（1and0）or0

＝1or0or0

＝1or0

＝1布爾值的翻譯方案E→E1orE2｛E.place=Newtemp；GEN（or，E1.place，E2.place，E.place）｝E→E1andE2｛E.place=Newtemp；

GEN（and，E1.place，E2.place，E.place）｝E→notE1｛E.place=Newtemp；

GEN（not，E1.place，_，E.place）｝E→（E1）｛E.place=E1.place｝E→id1ropid2{E.place=Newtemp；GEN(jrop,Entry(id1),Entry(id2),E.place)}E→id{E.place=Entry(id)}另一種計(jì)算方法是采取某種優(yōu)化措施，只計(jì)算部分表達(dá)式:AorB，若A的值為1，則無需計(jì)算B的值，因?yàn)椴还蹷的值為何結(jié)果，AorB的值都為1。AandB，若A的值為0，則無需計(jì)算B的值，因?yàn)椴还蹷的值為何結(jié)果，AandB的值都為0。控制語句中布爾表達(dá)式的翻譯條件控制語句ifEthenS1elseS2的目標(biāo)代碼結(jié)構(gòu)如下：E的代碼S1的代碼S2的代碼真假“真”出口與“假”出口布爾表達(dá)式E的作用僅在于控制對(duì)S1和S2的選擇，而無須最終保留E值，故作為轉(zhuǎn)移條件的布爾表達(dá)式E，可賦予它兩種出口：“真”出口E.TC→S1“假”出口E.FC→S2作為轉(zhuǎn)移條件的布爾表達(dá)式E，可翻譯為如下的四元式序列：（jnz,A,_,p)表示ifAgotop(jrop,A1,A2,p)表示ifA1ropA2gotop(j,_,_,p)表示gotop示例【例如】條件語句ifAorB＜CthenS1elseS2

可翻譯為：(1)(jnz,A,_,(5))(2)(j,_,_,(3))(3)(j＜,B,C,(5))(4)(j,_,_,(p+1))(5)關(guān)于S1的四元式序列……(p)(j,_,_,(q))(p+1)關(guān)于S2的四元式序列……(q)如何確定一個(gè)表達(dá)式的真假出口考慮E為E1orE2的形式：若E1為真，則E為真，所以E1的真出口就是整個(gè)E的真出口。若E1為假，則必須計(jì)算E2，E2代碼的第一個(gè)四元式標(biāo)號(hào)就是E1的假出口，而E2的真出口和假出口就是整個(gè)E的真出口和假出口。如何確定一個(gè)表達(dá)式的真假出口考慮E為E1andE2的形式：若E1為假，則E為假，所以E1的假出口就是整個(gè)E的假出口。若E1為真，則必須計(jì)算E2，E2代碼的第一個(gè)四元式標(biāo)號(hào)就是E1的真出口，而E2的真出口和假出口就是整個(gè)E的真出口和假出口?？紤]E為notE1的形式：只需調(diào)換E1的真假出口即可得到E的真假出口。拉鏈為了記錄需回填地址的四元式，常采用一種“拉鏈”的辦法。把需回填E．TC的四元式拉成一條鏈子，把需回填E．FC的四元式拉成一條鏈子，分別稱做"真"鏈和"假"鏈。示例若有四元式序列：（10）…gotoE．TC…（20）…gotoE．TC…（30）…gotoE．TC則把需回填E.TC的四元式(10)，(20)和(30)鏈成:（10）…goto（0）…（20）…goto（10）…（30）…goto（20）把地址（30）稱作鏈?zhǔn)祝?為鏈尾標(biāo)志，即地址（10）為鏈尾。自底向上分析中的一種翻譯方案E→E1orE2(1)EA→E1or{Backpatch(E1.

FC,NXQ);EA.TC

=E1.TC}(1’)E→EAE2{E

.FC

=E2.FC;

E

.

TC=Merg(EA.

TC,E1.TC)}【說明】Backpatch(p,t):將p鏈接的四元式的第四元都回填t；Merg(p1,p2):將以p1和p2為鏈?zhǔn)椎膬蓷l鏈合并為一條鏈，返回時(shí)的函數(shù)值作為合并后的鏈?zhǔn)?。E→E1andE2(2)EB→E1and{Backpatch(E1

.

TC,NXQ);EB.

FC

=E1.FC}(2’)E→EBE2{E

.

TC

=E2.TC;

E

.

FC=Merg(EB.FC,E1.FC)}(3)E→notE1{E.TC=E1.FC;E.FC=E1.TC}(4)E→(E1){E.TC=E1.TC; E.FC=E1.FC}(5)E→id1ropid2{E.TC=NXQ; E.FC=NXQ+1; GEN(jrop，Entry(id1)，Entry(id2)，0); GEN(j，_，_，0)}(6)E→id{E.TC=NXQ；E.FC=NXQ＋1; GEN(jnz，Entry(id)，_，0); GEN(j，_，_，0)}六、控制語句的翻譯考慮ifthen，ifthenelse和whiledo語句的翻譯。G[S]：S→ifEthenS

|ifEthenSelseS

|whileEdoS

|beginLend

|A

L→L；S

|S其中各非終結(jié)符號(hào)的意義是：S--語句

L--語句串A--賦值句E--布爾表達(dá)式1.條件語句if的翻譯考慮if語句的翻譯。產(chǎn)生式S→ifEthenS

|ifEthenSelseS

兩個(gè)問題布爾式E的"真、"假"出口尚待回填E.TC,E.FC。ifEthenS1elseS2elseS3在翻譯完S2之后，S1后的無條件轉(zhuǎn)移目標(biāo)仍無法確定，因?yàn)樗粌H要跨越S2還應(yīng)跨越S3。即轉(zhuǎn)移目標(biāo)的確定和語句所處的環(huán)境密切相關(guān)。故也可象處理布爾表達(dá)式一樣，讓非終結(jié)符S（和L）含有一項(xiàng)語義值S．CHAIN（和L．CHAIN）。也是一條鏈，它把所有那些四元式串在一起，這些四元式期待在翻譯完S（L）之后回填轉(zhuǎn)移目標(biāo)。真正的回填工作將在處理S的外層環(huán)境的某一適當(dāng)時(shí)候完成。單分支條件語句的目標(biāo)結(jié)構(gòu)ifEthenS1的目標(biāo)代碼結(jié)構(gòu)如下：E的代碼S1的代碼E.TCE.FCS1.CHAINS.CHAIN多分支條件語句的目標(biāo)結(jié)構(gòu)ifEthenS1elseS2的目標(biāo)代碼結(jié)構(gòu)如下：E的代碼S1的代碼S2的代碼E.TCE.FCjmp0S1.CHAINS2.CHAINS.CHAIN翻譯方案ifEthenS1

C→ifEthen{Backpatch(E

.

TC,NXQ);C.CHAIN=E.FC}S→CS1{S

.

CHAIN=Merg(C.CHAIN,S1.CHAIN)}ifEthenS1elseS2C→ifEthen{Backpatch(E

.

TC,NXQ);C.CHAIN=E.FC}TP→CS1else{q=NXQ;GEN(j,_,_,0);Backpatch(C.CHAIN,NXQ);TP

.

CHAIN=Merg(S1.CHAIN,q)}S→TPS2{S

.

CHAIN=Merg(TP.CHAIN,S2.CHAIN)}2.循環(huán)語句的翻譯whileEdoS1的目標(biāo)代碼結(jié)構(gòu)如下：E的代碼S1的代碼E.TCE.FCS1.CHAINS.CHAINjmphead翻譯方案W→while{W

.quad=NXQ}Wd→WEdo{Backpatch(E

.

TC,NXQ); Wd.CHAIN=E.FC; Wd.quad=W.quad}S→WdS1{Backpatch(S1.CHAIN,

Wd.quad);GEN(j,_,_,Wd.quad);S

.

CHAIN=Wd.quad}第一個(gè)四元式的地址示例while（A＜B）doif（C＜D）thenX=Y+Z將被翻譯成如下的一串四元式：

100(j＜,A,B,102)

101(j,_,_,107)

102(j＜,C,D,104)

103(j,_,_,100)

104(+,Y,Z,T1)

105(=,T1,_,X)

106(j,_,_,100)1073.for循環(huán)語句fori=E1stepE2untilE3doS1為了簡(jiǎn)單起見，假定E2總是正的。在這種假定下，上述循環(huán)句的意義等價(jià)于：

i=E1；

gotoOVER；

AGAIN：i=i+E2；

OVER：ifi≤E3then

beginS1；gotoAGAINend；七、簡(jiǎn)單說明語句的翻譯程序設(shè)計(jì)語言中的說明語句旨在定義各種形式的有名實(shí)體，如常量、變量、數(shù)組、記錄(結(jié)構(gòu))、過程、子程序等等，說明語句的種類也多，對(duì)象說明、變量說明、類型說明、過程說明等等。編譯程序把說明語句中定義的名字和性質(zhì)登記在符號(hào)表中，用以檢查名字的引用和說明是否一致。許多說明語句的翻譯并不生成相應(yīng)的目標(biāo)代碼。過程說明和動(dòng)態(tài)數(shù)組的說明有相應(yīng)的代碼。簡(jiǎn)單說明句的文法程序設(shè)計(jì)語言中最簡(jiǎn)單的說明句的語法描述為：D→integer〈namelist〉|real〈namelist〉〈namelise〉→〈namelist〉，id|id即使用關(guān)鍵字integer和real定義一串名字的性質(zhì)。對(duì)這種說明句的翻譯是指在符號(hào)表中登錄該名和性質(zhì)。翻譯方案語義變量D.type：用以記錄說明句所引入的名字的性質(zhì)(int還是real)；語義過程enter(id,A)：把名字id和類型A登錄在符號(hào)表中。(1)D→integerid{enter(id,int);

D.type=int}

(2)D→realid{enter(id,real);

D.type=real}

(3)D→D1,id{enter(id,D1.type);

D.type=D1.type}八、數(shù)組元素訪問的翻譯討論包括數(shù)組元素的表達(dá)式和賦值語句的翻譯問題。一個(gè)數(shù)組是由同一類型數(shù)據(jù)所組成的某種n維矩形結(jié)構(gòu)。沿著每一維的距離稱為一個(gè)下標(biāo)。每維的下標(biāo)只能在該維的上、下限之內(nèi)變動(dòng)。數(shù)組的每個(gè)元素是矩形結(jié)構(gòu)中的一個(gè)點(diǎn)，它的位置可通過給出每維的下標(biāo)來確定。數(shù)組的存儲(chǔ)數(shù)組的存儲(chǔ)表示有多種形式，最簡(jiǎn)單的一種是把整個(gè)數(shù)組按行（或按列）存放在一片連續(xù)存儲(chǔ)區(qū)中。例如，若A是一個(gè)2×3的二維數(shù)組，每個(gè)元素占一個(gè)單元，那么，所謂按行和按列的存儲(chǔ)方式分別如圖所示。有些程序語言，如FORTRAN，要求以列為序存放數(shù)組；另一些，如PL／l，要求以行為序；還有一些則取決于編譯程序設(shè)計(jì)者的意愿。數(shù)組按列存放A[1,1]A[1,2]A[1,3]A[2,1]A[2,2]A[2,3]數(shù)組按行存放A[1,1]A[2,1]A[1,2]A[2,2]A[1,3]A[2,3]計(jì)算數(shù)組元素的地址數(shù)組元素的地址計(jì)算和數(shù)組的存儲(chǔ)方式密切相關(guān)。在以行為序的情形下，如何計(jì)算數(shù)組元素的地址。例如，假定A是一個(gè)10×20的二維數(shù)組，各維的下限為1，每個(gè)元素占用一個(gè)機(jī)器字（令存儲(chǔ)器是以字編址的），數(shù)組的首地址，即A［l，1］的地址為a，那么，數(shù)組元素A［i，j］的地址為a十（i—1）×20十（j—l）或等價(jià)地表示成（a－21）＋（20×i＋j）以行為序計(jì)算數(shù)組元素的地址設(shè)A是一個(gè)ALGOLn維數(shù)組arrayA[l1：u1，l2：u2，…，ln：un]令di＝ui一1i十1，i＝1，2，…，n，a為數(shù)組的首地址，即A[l1，l2，…，ln]的地址。元素A[i1，i2，…，in]的地址D為：D＝a+(i1-l1)d2d3…dn+(i2-l2)d3d4…dn+…+(in-1-ln-1)dn+(in-ln)經(jīng)因子分解后得D＝CONSPART＋VARPART其中CONSPART＝a－CC＝(…((l1d2+l2)d3+13)d4+…+ln－1)dn+lnVARPART＝(…((i1d2+i2)d3+i3)d4+…+in－1)dn+in數(shù)組元素引用的中間代碼1.將產(chǎn)生兩組計(jì)算數(shù)組元素地址的四元式。一組計(jì)算VARPART，并將它放在某個(gè)臨時(shí)單元T中；另一組計(jì)算CONSPART，并把它放在另一個(gè)臨時(shí)單元T1中。同時(shí)用Ti[T]表示數(shù)組元素的地址。數(shù)組元素引用的中間代碼2.對(duì)應(yīng)“數(shù)組元素引用”（引用其值）和“對(duì)數(shù)組元素賦值”有兩個(gè)相應(yīng)的四元式：“變址取數(shù)”和“變址存數(shù)”。“變址取數(shù)”的四元式是：（＝［］，T1［T］，_，X）即X＝T1［T］“變址存數(shù)”的四元式是：（［］＝，X1，_，T1［T］）即T1［T］＝X賦值語句中數(shù)組元素的翻譯含數(shù)組元素的賦值語句的文法為：A→V＝EV→i［<elist>］|i<elist＞→<elist>，E|EE→E＋E|（E）|V為了產(chǎn)生計(jì)算VARPART的四元式序列，需要如下的語義變量和過程：elist．ARRAY：表示數(shù)組名在符號(hào)表中的位置，即數(shù)組名的符號(hào)表入口。elist．DIM：下標(biāo)的個(gè)數(shù)（數(shù)組維數(shù)）計(jì)數(shù)器。elist．PLACE：記存業(yè)已形成的VARPART的中間結(jié)果單元名字在符號(hào)表中的位置，或是一個(gè)臨時(shí)變量的整數(shù)碼。LIMIT（ARRAY，k）：這是一個(gè)函數(shù)過程，它給出數(shù)組ARRAY的第k維長度dk。其中，ARRAY是數(shù)組名在符號(hào)表中的位置。

說明每個(gè)變量V有兩項(xiàng)語義值（屬性），V．PLACE和V．OFFSET。若V是一個(gè)簡(jiǎn)單變量名i，則V．PLACE就是指此名的符號(hào)表入口，而V．OFFSET將為null。若V是一個(gè)下標(biāo)變量名i，則V．PLACE就是指保存CONSPART的臨時(shí)變量名的整數(shù)碼，而V．OFFSET則指保存VARPART的臨時(shí)變量名的整數(shù)碼。注意，null是一個(gè)特殊值，它是區(qū)分簡(jiǎn)單變量名和下標(biāo)變量名的標(biāo)志。翻譯方案（1）A→V＝E｛IF（V.OFFSET=null）THEN／*V是一個(gè)簡(jiǎn)單變量名*／GEN(=,E.PLACE,_,V.PLACE)ELSEGEN([]=,E.PLACE,_,V.PLACE[V.OFFSET])｝此處，若V是一個(gè)下標(biāo)變量，那么，我們產(chǎn)生“變址存數(shù)”的四元式。（2）E→E1＋E2｛T＝Newtemp；GEN(+,