第六章語法制導翻譯和中間代碼生成8.0編譯程序的任務是把源程序翻譯成目標程序，這個目標程序必須和源程序的語義等同，盡

管它們的結(jié)構(gòu)完全不同，但它們表達的結(jié)果

應完全相同。編譯的階段分為：源程序fi詞法分析fi語法分析fi

語義分析fi

中間代碼生成fi

代碼優(yōu)化

fi

目標代碼生成fi

目標程序語法分析以后，將進入語義分析階段。語義分析主要有兩個功能：第一，審查每個語法結(jié)構(gòu)的靜態(tài)語義，即驗證語法結(jié)構(gòu)合法的程序是否真正有意義。第二，如果靜態(tài)語義正確，語義處理要執(zhí)行真正的翻譯，即要么生成程序的一種中間代碼，要么生成實際的目標代碼。中間代碼，是復雜性介于源程序語言和機器語言的一種表現(xiàn)形式。直接生成目標代碼，可以減少中間環(huán)節(jié)，加快處理速度，節(jié)省額外開銷。通過中間代碼生成目標代碼，使得編譯程序結(jié)構(gòu)在邏輯上更為簡單明確，同時細化處理過程，有利于代碼優(yōu)化。語義分析與中間代碼生成詞法分析與語法分析以后進入語義分析和中間代碼生成階段希望語義分析和中間代碼生成自動實現(xiàn)但語義分析過程中語義形式化的方法很困難,沒有類似詞法或語法那樣形式化的方法實現(xiàn)語義的分析,至少沒有公認的實用方法目前,普遍采用屬性文法和語法制導的翻譯方法對語義處理工作進行比較規(guī)范和抽象的描述.8.1屬性文法屬性文法是語法制導翻譯的重要工具，通過它來說明程序設計語言的語義。也就是說，屬性文法來實現(xiàn)制導作用。一個屬性文法包含一個上下文無關(guān)文法和一系列語義規(guī)則，這些語義規(guī)則附在文法的每個產(chǎn)生式上，在語法分析過程中，既要分析語法正確性，又要描述語義規(guī)則的動作，從而實現(xiàn)語義處理。（可見，與以前文法增加了語義規(guī)則的描述。實際上，在語法分析過程中，除了考慮移進和規(guī)約，又要解釋語義描述。）8.1屬性文法屬性概念解釋。屬性常用以描述事物或人物的特征、性質(zhì)、品質(zhì)等等。定義：一個屬性文法是一個三元組，A=（G，V，F(xiàn)）。其中，G是上下文無關(guān)文法；V是屬性集；F是斷言或

謂詞集。屬性與文法的非終結(jié)符或終結(jié)符相聯(lián)；屬性像變量一樣，可以計算和傳遞，屬性計算的過程就是語義處理的過程；斷言或謂詞與文法的產(chǎn)生式相聯(lián)。斷言或謂詞就是一組屬性的計算規(guī)則，即語義規(guī)則。屬性文法記號：N.t

；表示與非終結(jié)符N相聯(lián)的屬性t。例如：Efi

T1+T2

|

T1orT2Tfi

num

|

true

|false屬性文法可以描述為：Efi

T1+T2{T1.t=int

AND

T2.t=int}Efi

T1orT2{T1.t=bool

AND

T2.t=bool}Tfi

num{T.t

:

=int}Tfi

true{T.t

:

=bool}Tfi

false

{T.t

:

=bool}與非終結(jié)符相關(guān)的屬性t。與產(chǎn)生式相關(guān)的斷言為：兩個T的屬性相同。在屬性文法中，描述屬性、斷言和語義規(guī)則的形式多種多樣。例如：簡單算術(shù)表達式求值的語義描述：語義規(guī)則print(E.val)E.val

:

=E1.val+T.valE.val

:

=T.valT.val

:

=T1.val*F.valT.val

:

=F.valF.val

:

=E.valF.val=digit.lexval產(chǎn)生式(0)Lfi

E(1)Efi

E1+T(2)Efi

T(3)Tfi

T1*F(4)Tfi

F(5)Ffi

(E)(6)Ffi

digit在上述屬性文法中的每個非終結(jié)符都有一個屬性.val。屬性屬性分為兩種：繼承屬性：用于“自上而下”傳遞和計算綜合屬性：用于“自下而上”傳遞和計算屬性信息的傳遞對每個產(chǎn)生式，左部的非終結(jié)符屬性來自

右部非終結(jié)符的計算。也就是說這種屬性

的獲得受到右部屬性的影響，是綜合屬性。對于終結(jié)符，只有綜合屬性。產(chǎn)生式左部屬性可能來自右部某個非終結(jié)符屬性的傳遞，即存在著繼承屬性。8.2

語法制導翻譯概論在語法分析過程中，每一步的進展，都根據(jù)每個產(chǎn)生式所對應的語義規(guī)則描述的語義動作進行翻譯的方法稱做語法制導翻譯。采用自上而下的分析，在用某一個產(chǎn)生式進行推導的同時就進行相應的語義動作。即執(zhí)行對應的一組語義規(guī)則。采用自下而上的分析，在用某一個產(chǎn)生式進行規(guī)約的同時就執(zhí)行相應的語義動作。即執(zhí)行對應的一組語義規(guī)則。這些語義規(guī)則就是程序設計語言中的語義子程序。8.2

語法制導翻譯概論語義子程序可以完成任何語義動作，在語法分析的同時調(diào)用這些語義子程序完成相應的語義分析工作。這樣在分析語句符合語法的同時也就求出表達式的“值”。如果仍然采用自下向上分析方法，在分析過程中，也要有分析棧、分析表和輸入串。因為，增加了

語義分析，所以增加了一個語義棧。即棧包括三

個部分：狀態(tài)棧、符號棧和語義棧。舉例：產(chǎn)生式Lfi

EEfi

E1+TEfi

TTfi

T1*FTfi

FFfi

(E)Ffi

digit語義規(guī)則print(E.val)E.val

:

=E1.val+T.valE.val

:

=T.valT.val

:

=T1.val*F.valT.val

:

=F.valF.val

:

=E.valF.val=digit.lexval對輸入符號串：2+3*5進行分析擴充的分析棧：狀態(tài)棧、語義棧和文法符號棧；使得每個文法符號都與語義有關(guān)。形式如下表：SMy。ValYSM-1x。Valx………………………S0-#狀態(tài)棧語義棧符號棧狀態(tài)ACTION（動作）GOTO（轉(zhuǎn)換）d+*()#ETF0s5s41231s62r2s7r23r4r4r44s5s48235r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5分析與計算過程步驟規(guī)約動作狀態(tài)棧語義棧符號棧留余輸入串10-#2+3*5#205-

-#2+3*5#3r603-2#F+3*5#4r402-2#T+3*5#5r201-2#E+3*5#6016-2-#E+3*5#70165-2-

-#E+3*5#8r60163-2-3#E+F*5#9r40169-2-3#E+T*5#1001697-2-3-#E+T*5#11016975-2-3-

-#E+T*5#12r601697（10）-2-3-5#E+T*F#13r30169-2-（15）#E+T#14r101-（17）#E#15接受本例是直接生成計算值，如果把語義子程序改為生成中間代碼，那么就可以在語法制導下逐步產(chǎn)生中間代碼。8.3

中間代碼的形式中間代碼是編譯程序使用的一種獨立于目標機的、易于翻譯成目標程序的中間表示形式中間代碼的復雜性介于用高級語言書寫的源程序和用機器語言表示的目標程序之間常用的中間代碼：逆波蘭式、樹形表示、三元式、四元式等。其中以四元式最為普遍。8.3

中間代碼的形式逆波蘭記號將運算對象寫在前面，運算符號寫在后面。如：a+b(ab+)、a*b（ab*）。也稱為后綴式。逆波蘭表示最大的優(yōu)點是易于計算機處理表達式。表現(xiàn)為利用棧的操作。自左向右掃描算術(shù)表達式。如果遇到算術(shù)運算對象，則將其壓入棧頂；如果

遇到運算符，若為兩目運算，則對棧頂兩元素計

算，將結(jié)果替換棧頂兩元素；若為一目運算，則

結(jié)果替換棧頂一個元素。這種方式特別適合解釋執(zhí)行的程序設計語言的中間表示。逆波蘭表示不僅適用于算術(shù)表達式，也可以用于結(jié)構(gòu)的控制語句、轉(zhuǎn)移語句等。但是，處理起來要復雜的多。逆波蘭表示程序設計語言中的表示逆波蘭表示a+bab+a+b*cabc*+(a+b)

*

cab+c*a:=b*c+b*dabc*bd*+:=遇到運算對象后，就把它壓入堆棧；分別將a、b、c壓入棧底（a在最底）；遇到運算符號，若為兩目運算，計算棧頂?shù)膬蓚€運算對象（b*c）再做+運算。8.3

中間代碼的形式三元式和樹形表示把表達式或語句用一組三個元素的式子表示。三個元素為：算符（OP）、第一運算對象、第二運算對象。例如：a:=b*c+b*d可以表示為：（1）（*b,c

）（2）（*b,d

）（3）（+（1）（2））（4）（：=（3）a）三元式中含有對中間結(jié)果的引用，即具有繼承性。這種繼承性可以表述多目計算。三元式的樹形表示:=a+**bcbd簡單變量或常數(shù)的樹就是該變量或常數(shù)自身二目運算對應二叉樹，多目運算對應多叉樹為了便于安排存貯空間，多叉樹往往要轉(zhuǎn)換為二叉樹8.3

中間代碼的形式四元式四元式是一種比較常見的中間代碼形式。四元式的四個元素為：運算符、第一運算對象、第二運算對象、運算結(jié)果。四元式簡單表示：t1:=b*c。b，c為運算對象，*為運算符，t1為運算結(jié)果。例如：a:=b*c+b*d的四元式表示為：1.（*，b，c，t1）2.（

*，b，d，t2）3.（+，t1，t2，t3）4.（：=，t3，-，a)例如：賦值語句：A：=-B*（C+D）四元式為：（@，B，-，T1）（+，C，D，T2）（*，T1，

T2，T3）（：=，

T3，-，A）–與三元式的區(qū)別在于對中間結(jié)果的引用必須通

過給定的名字。而三元式通過中間結(jié)果的編號。–所謂三地址：就是計算機指令除了操作碼外，包含三個地址，兩個為運算對象，一個結(jié)果。8.3

中間代碼的形式例題：分別給出表達式-(a*(b-c))+d的逆波蘭式和四元式表示。逆波蘭式：–

@(a*(b-c))+d@(a*(bc-))+d@(abc-*)+d

(abc-*@)+d

abc-*@d+–注意：@為求負的運算符--(a*(b-c))+d四元式：–

（-，b，c，T1）–

（*，a，

T1

，T2）–

（

@

，T2，-，T3）–

（+，T3，d，

T4）8.3

中間代碼的形式無論是逆波蘭表示，還是三元式或四元式都是編譯過程中的中間代碼表現(xiàn)形式。將程序設計語言中的各種語句按照語義規(guī)則進行翻譯的過程中形成的中間代碼可以是四元式、三元式或逆波蘭式等。8.4

簡單賦值語句的翻譯符號表：在編譯過程中，為了完成源程序到目標代碼的翻譯，需要不斷收集、記錄和使用源程序中一些語法符號、特征和屬性等相關(guān)信息。將這些信息建立一個表格，稱為符號表。賦值語句由文法Afi

id：=E描述，其中，A為非終結(jié)符代表賦值語句，id為賦值語句的左部（可以為簡單變量或邏輯變量），E為右部的算術(shù)表達式、邏輯表達式或者其他類型的表達式。首先對id表示的單詞定義一個屬性，用做語義變量；用Lookup()表示審查是否出現(xiàn)在符號表中，如果在,則指向該項的登錄指針，否則，返回nil。語義過程emit表示輸出四元式到輸出文件上。語義過程newtemp表示生成一個臨時變量，每調(diào)用一次，生成一新的臨時變量。語義變量E.place表示存放E值的變量在符號表的登錄項；如果E是一個臨時變量，則E.place表示一個整數(shù)碼。賦值語句直觀的語義是將賦值號右邊表達式的值賦予左部量。具體語義處理時要注意賦值號兩邊類型一致的要求，若類型一致可直接賦值，若不一致或拒絕賦值或以左部量類型為準對右部表達式E的值產(chǎn)生類型轉(zhuǎn)換指令。賦值語句的四元式翻譯S

fi

id：=E

{p:=lookup();???E

fi

E1*E2if

p<>nil

thenemit(p’:=‘E.place)else

error}{E.place:=newtemp;emit(E.place’:=‘E1.place’*’E2.place)上述假設變量類型是一致的，但是，實際上，一個表達式中有各種類型的變量。所以語義規(guī)則上要有相應的處理。這時需要注意的是：除了值的屬性以外，還要有類型的屬性。根據(jù)數(shù)據(jù)結(jié)構(gòu)類型的不同，語義處理的復雜程度也不同。8.5

布爾表達式的翻譯布爾表達式的作用：一是計算邏輯值；二是控制流程。布爾表達式的組成由布爾運算符（與、或、非）和布爾變量或關(guān)系表達式（關(guān)系表達

式結(jié)果為布爾量）。關(guān)系表達式的形式為：E1

rop

E2。其中，E1

和E2都是算術(shù)表達式，rop

為關(guān)系運算符。布爾表達式的翻譯方法計算布爾表達式的第一種方法：計算每部分的真假值（步步計算），最后計算整個表達式的值。計算布爾表達式的第二種方法：采用某種優(yōu)化算法，即只計算部分表達式，就能得出整個表達式結(jié)果。根據(jù)不同計算方法，翻譯的過程不同。布爾表達式a

or

b

and

not

c翻譯成四元式序列t1

:

=

not

ct2

:

=b

and

t1t3

:

=a

or

t2關(guān)系表達式a>b，可以看成等價的條件語句ifa>bthen

1else

0，翻譯成四元式序列為：if

a>b

goto

(4)t

:

=

0goto

(5)t

:

=

15.……其中用臨時變量t存放關(guān)系表達式a>b的值?？刂普Z句中布爾表達式的翻譯方法控制語句通常有三種：if–then；if–then–

else

和while–do

；語法形式為：Sfi

if

E

then

S1

|

if

E

thenS1else

S2

|

while

Edo

S1實際上作為條件控制的語句E，它的的四元式翻譯思路是：E為a

rop

b

生成代碼為：if

arop

bgotoE.true和E.false。表達式有兩個出口：真出口和假出口。a<b

or

c<d

and

e>f表達式翻譯成四元式序列if

a<b

goto

E.truegoto

3if

c<d

goto

5goto

E.falseif

e>f

goto

E.truegoto

E.false上述四元式序列引出兩個問題：1是優(yōu)化代碼；2是“真出口”和“假出口”在四元式生成時并不能具體確定，必須要生成完后，返回來重新確認，即“回填”。為了記錄將來需要“回填”的地址，采用一種叫“拉鏈”的辦法。回填E.true地址叫

“真”拉鏈；回填E.false

地址叫“假”拉鏈；關(guān)于拉鏈回填方法的另外一角度的分析程序設計語言中的語句標號是標識一個語句的。它在程序中出現(xiàn)有兩種意義：一是定義性出現(xiàn)，如：L：S；另一是使用性出現(xiàn)，如：goto

L。編譯程序處理過程中，對標號的處理是，程序中某個標號的第一次出現(xiàn)（無論是定義性還是使用性）都要填寫標號表：標號名（L）定義與否標志（D）地址（add）標號名即標號本身或相應的內(nèi)碼表示；定義與否標志為：定義性出現(xiàn)D=1；使用性出現(xiàn)D=0。地址：當D=1時，add為標號L所標識的語句翻譯成四元式序列的第一個四元式地址；當D=0時，標號L還未定義，需要將來回填，但這時要把所有以L為轉(zhuǎn)移目標的四元式地址記錄下來，以便一旦L確定可以回填。關(guān)于拉鏈回填方法的另外一角度的分析例如：……??10goto

L1…….?20goto

L1?…….?30goto

L1?…….?40L1:………注意上述10、20、30、40不是語句標號，而是語句的地址。前3次出現(xiàn)L1標號，為使用性；第四次出現(xiàn)為定義性出現(xiàn)。每出現(xiàn)L1標號對應的四元式10（j，--，--，0）20（j，--，--，10）30（j，--，--，20）40（j，--，--，30）按照逆序反填回去。標號名（L）定義與否標志（D）地址（add）L1010L1020L1030L11408.6

控制結(jié)構(gòu)的翻譯在程序設計語言中,控制結(jié)構(gòu)語句通常有:if-thenif-then-elsewhile-do在控制語句中的布爾表達式翻譯過程中,對”真出口”和”假出口”通常采用”拉鏈”,”回填”方法進行翻譯確認;事實上,在對于整個控制結(jié)構(gòu)語句也存在著一個出口不確定的問題;那就是當執(zhí)行完整個控制語句后,將執(zhí)行一個無條件轉(zhuǎn)移語句指令,將控制離開這個語句;但是,