1、 編譯程序的任務是把源程序翻譯成目標程序，這個目標程序必須和源程序的語義等同，也就是說，盡管它們的語法結構完全不同，但它們所表達的結果應完全相同。通常，在詞法分析程序和語法分析程序對源程序的語法結構進行分析之后，要么由語法分析程序直接調用相應的語義子程序進行語義處理，要么首先生成語法樹或該結構的某種表示，再進行語義處理 。第七章語法制導翻譯和中間代碼生成第七章語法制導翻譯和中間代碼生成語義處理語義處理編譯中的語義處理是指兩個功能：一、審查每個語法結構的靜態語義，即驗證語 法結構合法的程序是否真正有意義二、如果靜態語義正確，語義處理則要執行真正的翻譯，即，要么生成程序的一種中間表示形式（中間代碼

2、），要么生成實際的目標代碼 。 為什么有的編譯程序直接生成目標代碼，有的編譯程序采用中間代碼，所謂中間代碼，也稱中間語言，是復雜性介于源程序語言和機器語言的一種表示形式。一般，快速編譯程序直接生成目標代碼，沒有將中間代碼翻譯成目標代碼的額外開銷。但是為了使編譯程序結構在邏輯上更為簡單明確，常采用中間代碼，這樣可以將與機器相關的某些實現細節置于代碼生成階段仔細處理，并且可以在中間代碼一級進行優化工作使得代碼優化比較容易實現 。屬性文法語法制導翻譯思想中間代碼一些語句的翻譯 現在很多編譯程序采用語法制導翻譯方法。這仍不是一種形式系統，但它是比較接近形式化的。這種方法使用屬性文法為工具來說明程序設計

3、語言的語義。一個屬性文法包含一個上下文無關文法和一系列語義規則，這些語義規則附在文法的每個產生式上，在語法分析過程中，完成附加在所使用的產生式上的語義規則描述的動作，從而實現語義處理。 屬性文法屬性文法屬性，常用以描述事物或人的特征、性質、品質等等。比如，談到一個物體，可以用“顏色”描述它，談起某人，可以使用“有幽默感”來形容他。對編譯程序使用的語法樹的結點，可以用“類型”、“值”或“存儲位置”來描述它。屬性文法屬性文法屬性文法是一個三元組：A=(G,V,F),其中 G：是一個上下文無關文法V：有窮的屬性集,每個屬性與文法的一個終結符或非終結符相連 F：關于屬性的屬性斷言或謂詞集.每個斷言與一

4、個產生式相聯.而此斷言只引用該產生式左端或右端的終結符或非終結符相聯的屬性 如，有文法G為：ET1+T2|T1orT2Tnum|true|false因為T在同一個產生式里出現了兩次，使用上角標將它們區分開。 屬性文法記號中常使用N.t的形式表示與非終結符N相聯的屬性t。比如可把完成對上面表達式的類型檢查的屬性文法寫成形式：類型檢查的屬性文法類型檢查的屬性文法ET1+T2 T1.t=int AND T2.t=int ET1orT2 T1.t=bool AND T2.t=bool TfalseT.t：=boolTnumT.t：=int TtrueT.t：=bool與每個非終結符與每個非終結符T相聯

5、的有屬性相聯的有屬性t，t要么是要么是int，要么是，要么是bool。與非終結符。與非終結符E的產生式相的產生式相聯的斷言指明：兩個聯的斷言指明：兩個T的屬性必須相同。的屬性必須相同。ET+T43(a)T1.t=intT2.t=intE T 1 . t + T2.t T+T43 靜態語義審查靜態語義審查輸入串3+4的語法樹 語法樹結點帶有語語法樹結點帶有語義信息的表示。義信息的表示。可以用如下的方式定義的“值”的語義：1）EE1+E2 E.val：=E1.val+E2.val2）E1 E.val：=13）E0 E.val：=0屬性文法最早出自克努特筆下。他把屬性分成兩類：繼承屬性和綜合屬性，我

6、們不對屬性文法進行理論上的研究而僅僅將它做為工具描述語義分析。在編譯的許多實際應用中，屬性和斷言以多種形式出現，也就是說，與每個文法符號相聯的可以是各種屬性、斷言、以及語義規則，或者某種程序設計語言的程序段等等 。 簡單算術表達式求值的語義描述：產生式語義規則（0）LEprint(E.val)（1）EE1+T E.val：=E1.val+T.val（2）ETE.val：=T.val（3）TT1*FT.val：=T1.valF.val（4）TFT.val：=F.val（5）F(E)F.val：=E.val（6）FdigitF.val：=digit.lexval在該描述中，每個非終結符都有一個屬性

7、：一個整數值的稱作val的屬性。按照語義規則對每個產生式來說，它的左部E，T，F的屬性值的計算來自它右部的非終結符，這種屬性稱作綜合屬性。單詞digit僅有綜合屬性，它的值是由詞法分析程序提供的。和產生式LE相聯的語義規則是一個過程，打印由E產生的表達式的值。我們可以理解為L的屬性是空的或是虛的。在語法分析過程中，隨著分析的步步進展，根據每個產生式所對應的語義子程序（或語義規則描述的語義動作）進行翻譯的辦法稱作語法制導翻譯 。語法制導翻譯語法制導翻譯 假定我們現在要分析的語法成分是簡單算術表達式，所完成的語義的處理不是將它翻譯成中間代碼或目標代碼，而是計算表達式的值。采用的描述系統是上節的例1

8、。假如語法分析方法是自下而上的。在用某一產生式進行歸約的同時就執行相應的語義動作，在分析出一個句子時，這個句子的“值”也就同時產生了，例如輸入串是3*5+4。 LE.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語法分析器，現在把它的分析棧擴充，使得每個文法符號都跟有語義值同時把LR分析器的能力擴大，使它不僅執行語法分析任務，且能在用某個產生式進行歸

9、約的同時調用相應的語義子程序，完成在屬性文法中描述的語義動作。每步工作后的語義值保存在擴充的分析棧里“語義值”欄中。采用LR分析，其中使用d代替digit。分析和計值2+3*5的過程如下：狀狀態態ACTION（動作）（動作）GOTO（轉換）（轉換）d+*()#ETF0s5s41231s6 Acc2r2s7r2r23r4r4r4r44s5s48235r6r6r6r66s5s4937s5s4108s6s119r1s7r1r110r3r3r3r311r5r5r5r5步驟步驟歸約動作歸約動作狀態棧狀態棧語義棧語義棧符號棧符號棧余輸入串余輸入串1）0#2+3*5#2）05 #2+3*5#3）r6032#

10、F+3*5#4）r4022#T+3*5#5）r2012#E+3*5#6）0162#E+3*5#7）01652 #E+3*5#8）r6016323#E+F*5#9）r4016923#E+T*5#10）0169723#E+T*5#11）01697523 #E+T*5#12）r601697(10)235#E+T*F#13）r31692(15)#E+T#14）r101-17#E#15）接受接受 2+3*5的分析和計值過程 所謂“中間代碼”是一種結構簡單、含義明確的記號系統，這種記號系統可以設計為多種多樣的形式，重要的設計原則為兩點：一是容易生成；二是容易將它翻譯成目標代碼。編譯程序所使用的中間代碼有多

11、種形式。常見的有逆波蘭記號、三元式、四元式和樹形表示。 中間代碼形式中間代碼形式 逆波蘭記號是最簡單的一種中間代碼表示形式，早在編譯程序出現之前，它就用于表示算術表達式，是波蘭邏輯學家盧卡西維奇發明的。這種表示法將運算對象寫在前面，把運算符號寫在后面，比如把a+b寫成ab+，把a*b寫成ab*，用這種表示法表示的表達式也稱做后綴式。 逆波蘭記號逆波蘭記號程序設計語言中的逆波蘭表示：a+b ab+a+b*c abc*+(a+b)*c ab+c*a：=b*c+b*d abc*bd*+：= 后綴表示法表示表達式，其最大的優點是最易于計算機處理表達式。利用一個棧，自左至右掃描算術表達式（后綴表示）。每

12、碰到運算對象，就把它推進棧；碰到運算符，若該運算符是二目的，則對棧頂部的兩個運算對象實施運算，并將運算結果代替這兩個運算對象而進棧。若是一目運算符，則對棧頂元素執行該運算，并以運算結果代替該元素進棧。最后的結果留在棧頂。 BCD*+（它的中綴表示為-B+C*D，使用表示一目減）的計值過程為：1、B進棧；2、對棧頂元素施行一目減運算，并將結果代 替棧頂， 即-B置于棧頂；3、C進棧；4、D進棧；5、棧頂兩元素相乘，兩元素退棧，相乘結果置 棧頂；6、棧頂兩元素相加，兩元素退棧，相加結果進棧，現在棧頂存放的是整個表達式的值。由于后綴式表示上的簡潔和計值的方便，特別適用于解釋執行的程序設計語言的中間表

13、示，也方便具有堆棧體系的計算機的目標代碼生成。 三元式表示三元式表示把表達式及各種語句表示成一組三元式。每個三把表達式及各種語句表示成一組三元式。每個三元式三個組成部分是：算符元式三個組成部分是：算符op，第一運算對象，第一運算對象ARG1，和第二運算對象，和第二運算對象ARG2。 三元式表示三元式表示a：=b*c+b*d的三元式表示為：的三元式表示為：（1）（）（*b，c）（2）（）（*b，d）（3）（）（+ （1），）， （2）（4）（：）（：= （3），）， a）：=a + * * b c b d樹形表示是三元式表示翻版。上述三元式可表示成下面的樹表示 ：*T1T2e1* e2 + T1

14、T2e1+ e2T1-e1表達式的樹形表示很容易實現：簡單變量或常數的樹就是該變量或常數自身，如果表達式e1和e2的樹分別為T1和T2，那么e1+ e2，e1* e2，-e1的樹分別為： 三元式三元式: (1) ( - C D ) (2) ( * B (1) ) (3) ( + A (2) ) (4) ( - C D ) (5) ( (4) N ) (6) ( / E (5) ) (7) ( + (3) (6) )例例 : A + B * ( C - D ) + E / ( C - D ) N間接三元式間接三元式 : 間接三元式序列間接三元式序列 間接碼表間接碼表 (1) ( - C D )

15、（1） (2) ( * B (1) ) （2） (3) ( + A (2) ) （3） (4) ( (1) N ) （1） (5) ( / E (4) ) （4） (6) ( + (3) (5) ) （5） （6） A + B * ( C - D ) + E / ( C - D ) N 四元式是一種比較普遍采用的中間代碼形式。四元式的四個組成成分是：算符op，第一和第二運算對象ARG1和ARG2及運算結果RESULT。運算對象和運算結果有時指用戶自己定義的變量，有時指編譯程序引進的臨時變量 。四元式四元式a:=b*c+b*d的四元式表示如下：（1）（*, b, c, t1）（2）（*, b,

16、d, t2）（3）（+ t1, t2, t3）（4）（:=, t3, , a） A + B * ( C - D ) + E / ( C - D ) N 逆波蘭逆波蘭 : A B C D - * + E C D N / + 四元式四元式 : (1) ( - C D T1 ) (2) ( * B T1 T2) (3) ( + A T2 T3) (4) ( - C D T4) (5) ( T4 N T5) (6) ( / E T5 T6) (7) ( + T3 T6 T7) 四元式和三元式的主要不同在于，四元式對中間結果的引用必須通過給定的名字，而三元式是通過產生中間結果的三元式編號。也就是說，四元

17、式之間的聯系是通過臨時變量實現的。 四元式表示很類似于三地址指令，有時把這類中間表示稱為“三地址代碼”因為這種表示可看作一種虛擬三地址機的通用匯編碼，即這種虛擬機的每條“指令”包含操作符和三個地址，兩個是為運算對象的，一個是為結果的。這種表示對于代碼優化和目標代碼生成都較有利。為了更直觀，把四元式的形式寫成簡單賦值形式。比如把上述四元式序列寫成：（1）t1：=b*c（2）t2：=b*d（3）t3：= t1+ t2（4）a：= t3把（jump，L）寫成goto L把（jrop，B，C，L）寫成if B rop C goto L為了敘述的方便，兩種形式我們將同時使用。 簡單賦值語句的四元式翻譯簡

18、單賦值語句的四元式翻譯 首先對id表示的單詞定義一屬性，用做語義變量，用Lookup()表示審查是否出現在符號表中，如在，則返回一指向該登錄項的指針，否則返回nil。語義過程emit表示輸出四元式到輸出文件上。語義過程newtemp表示生成一臨時變量，每調用一次，生成一新的臨時變量。語義變量E.place，表示存放E值的變量名在符號表的登錄項或一整數碼 產生式和語義描述：（1）Sid：=E p：=look up()； if pnil then emit(p：=E.place) else error（2）EE1+E2 E.place：=ne

19、w temp； emit(E.place：=E1.place+E2.place)（3）EE1*E2 E.place：=new temp； emit(E.place：=E1.place*E2.place （4）E-E1 E.place：=newtemp； emit(E.place：= uminusE1.place)() E( E1) E.place：= E1.place() Eid P：=lookup()； if Pnil then E.place：=P else error() E( E1) E.place：= E1.place() Eid P：=lookup()；

20、 if Pnil then E.place：=P else error程序設計語言中的布爾表達式有兩個作用。一是計算邏輯值，二是用做改變控制流語句中的條件表達式，如if-then, if-then-else，或是while-do語句中那樣。布爾表達式是由布爾算符（and, or和not）施于布爾變量或關系表達式而成。即布爾表達式的形式為E1 rop E2，其中E1和E2都是算術表達式，rop是關系符，如= ，=，=，等等 。布爾表達式的翻譯布爾表達式的翻譯計算布爾表達式的值有兩種辦法，第一種辦法，如同計算算術表達式一樣，步步計算出各部分的真假值，最后計算出整個表達式的值。例如，用數1表示tru

21、e，用0表示false。那么布爾表達式1 or(not 0 and 0)or 0的計算過程是：1 or(not 0 and 0)or 0=1 or(1 and 0)or 0=1 or 0 or 0=1 or 0=1布爾表達式的翻譯方法布爾表達式的翻譯方法另一種計算方法是采取某種優化措施，只計算部分表達式，例如要計算A or B，若計算出A的值為1，那么B的值就無需再計算了，因為不管B的值為何結果，A or B的值都為1。上述兩種方法對于不包含布爾函數調用的表達式是沒有什么差別的。但是，假若一個布爾式中會有布爾函數調用，并且這種函數調用引起副作用（如有對全局量的賦值）時，這兩種方法未必等價。采用

22、哪種方法取決于程序設計語言的語義 。 若按第一種辦法計算布爾表達式。布爾表達式a or b and not c翻譯成四元式序列為：（1）t1：=not c（2）t2：= b and t1（3）t3：=a or t2對于像ab這樣的關系表達式，可看成等價的條件語句if ab then 1 else 0，它翻譯成的四元式序列為：（1）if ab goto (4)（2）t ：=0（3）goto(5)（4）t：=1（5） 下面給出了按第一種辦法計算布爾表達式的值，將布爾表達式翻譯成四元式的描述，其中nextstat給出的輸出序列中下一四元式序號。emit過程每被調用一次，nextstat增加1。EE1

23、orE2 E.place：=new temp； emit(E.place：=E1.place orE2.place)EE1 and E2 E.place：=new temp emit(E.place：=E1.place andE2.place)Enot E1 E.place：=newtemp：； emit(E.place：= notE1.place)E（E1） E.place：= E1.place Eid1 rop id2E.place：=newtemp； emit(if id1.place rop id2.place goto nextstat+3)； emit(E.place：= 0) e

24、mit( goto nextstat+2) emit(E.place：= 1)Eture E.place：=newtemp； emit(E.place：= 1)Efalse (E.place：=newtemp； emit(E.place：= 0)Eid1 relop id2 E.place：=newtemp； emit(if id1.place relop.opid2.place goto nextstat+3)； emit(E.place：= 0) emit( goto nextstat+2) emit(E.place：= 1)Eture E.place：=newtemp； emit(E.p

25、lace：= 1)Efalse (E.place：=newtemp； emit(E.place：= 0) 現在討論出現在現在討論出現在if-then；if-then-else和和while-do等語句中的布爾表達式等語句中的布爾表達式E的翻譯。的翻譯。這三種語句的語法為：這三種語句的語法為：Sif E then S1|if E then S1 else S2 | while E do S1控制語句中布爾表達式的翻譯控制語句中布爾表達式的翻譯 E.false 控制語句中布爾表達式的翻譯控制語句中布爾表達式的翻譯控制語句控制語句 Sif E then S1 else S2 E 的代碼的代碼 E.t

26、rue E.true: S1的代碼的代碼 goto outE.false: S2的代碼的代碼out: 作為條件轉移的E，僅把E翻譯成代碼是一串條件轉和無條件轉四元式。翻譯的基本思路是，對于E為a rop b的形式生成代碼為：if a rop b goto E. true 和goto E.false 對于E為E1 or E2的形式，若E1是真，則可知道E為真即E1的真出口和E的真出口一樣。如果E1是假，那么必須計算E2，E1的假出口就是E2代碼的第一個四元式標號，這時E2的真出口和假出口分別與E的真出口和假出口一樣。類似的考慮適于E1 and E2的情形。E1的翻譯理解容易，只需調換E1的真假出

27、口即可得到E的真假出口。1 . 把條件轉移的布爾表達式把條件轉移的布爾表達式E 翻譯成僅含翻譯成僅含 條件真條件真 轉轉 和和 無條件無條件 轉轉 的四元式的四元式 E ： a rop b ? if a rop b goto E.true goto E.false如如 ： ab or cd and ef 可可 翻譯成如下四元式：翻譯成如下四元式：(1 ) if ab goto E.true(2) goto (3)(3) if cd goto (5)(4) goto E.false(5) if ef goto E.true(6) goto E.false (翻譯翻譯不是最優不是最優) 上述四元式

28、（1）和（5），（4）和（6）的轉移地址并不能產生這些四元式的同時得知。例如（1）和（5）的轉移地址是在整個布爾表達式的四元式產生完畢之后才得知。因此要回填這個地址。為了記錄需回填地址的四元式，常采用一種“拉鏈”的辦法。把需回填E.true的四元式拉成一鏈，把需回填E.false的四元式拉成一鏈，分別稱做“真”鏈和“假”鏈 。2拉鏈返填拉鏈返填 （10） goto L （10）goto 0 鏈尾鏈尾 （10）（20） goto L （20）goto 10 （30） goto L (30) goto 20 鏈頭鏈頭（30）（40）L： （40）L: . 一、一、 開關語句開關語句開關語句（開關語

29、句（case語句或語句或swith語句）是很多程序設計語言中都有的，方式不語句）是很多程序設計語言中都有的，方式不盡相同。我們假定要討論的開關語句的形式為：盡相同。我們假定要討論的開關語句的形式為：switch E ofcase V1: S1case V2: S2case Vn-1: Sn-1default: Snend控制結構的翻譯控制結構的翻譯直觀上看，case語句可翻譯成如下的一連串條件轉移語句。t :=E;L1: ifV1 goto L2;S1;goto next;L2: if tV2 goto L3;S2goto next;Ln-1:if tVn-1 goto Ln;Sn-1;got

30、o next;Ln: Sn;next:下面）給出開關語句的一種翻譯結果（中間代碼），其中把所有的測試都放在最后，以便目標代碼生成階段產生高質量的目標指令。goto testL1:S1的中間代碼goto nextL2:S2的中間代碼goto next Ln-1:Sn-1的中間代碼goto nextLn:Sn的中間代碼goto nexttest:if t=V1 goto L1if t=V2 goto L2 if t=Vn-1 goto Ln-1goto Lnnext:二、二、 for循環語句循環語句除了除了while-do語句外，很多程序設計語言具有下面形式的語句外，很多程序設計語言具有下面形式的

31、循環語句：循環語句：for i :=E1 step E2 until E3 do S1我們按我們按ALGOL的意義來翻譯這種循環句。為了簡單起見，的意義來翻譯這種循環句。為了簡單起見，假定假定E2總是正的。在這種假定下，上述循環句的總是正的。在這種假定下，上述循環句的ALGOL意義等價于：意義等價于：i :=E1goto OVER;AGAIN: i :=i+E2;OVER: if iE3 thenbegin S1; goto AGAIN end;例如，循環語句for :=1 step 1 until N do M :=M+將翻譯成如下的四元式序列：100 :=1101 goto 103102

32、:=+1103 if N goto 105104 goto 108105 T :=M+106 M :=T107 goto 102108三、三、 goto語句語句 多數程序語言中的轉移是通過標號和多數程序語言中的轉移是通過標號和goto語句語句實現的。帶標號語句的形式是實現的。帶標號語句的形式是L：S；goto語句的語句的形式是形式是goto L。 當當L ： S；語句處理之后，標號；語句處理之后，標號L是是“定義了定義了”的。即在符號表中，將登記的。即在符號表中，將登記L的項的的項的“地址地址”欄欄中登上語句中登上語句S的第一個四元式的地址。的第一個四元式的地址。 如果gotoL是一個向上轉移

33、的語句，那么，當編譯程序碰到這個語句時，L必是已定義了的。通過對L查找符號表獲得它的定義地址p，編譯程序可立即產生出相應于這個goto L的四元式如 ( j, , , p)。 如果goto L是一個向下轉移的語句，也就是說，標號L尚未定義，那么，若L是第一次出現，則把它填進符號表中并標志上“未定義”。由于L尚未定義，對goto L只能產生一個不完全的四元式（goto ），它的轉移目標須待L定義時再回填進去。在這種情況下，必須把所有那些以L為轉移目標的四元式的地址全都記錄下來，以便一旦L定義時就可對這些四元式進行回填。 我們將采用所示的拉鏈辦法，把所有以L為轉移目標的四元式串在一起。鏈的首地址放在符號表中L的“地址”欄中。建鏈的方法是：若goto L中的標號L尚未在符號表中出現，則把L填入表中，置L“定義否”標志為“未”，把nextstat填進L的地址欄中作為新鏈首，然后，產生四元式(goto 0)，其中0為鏈尾標志。若L已在符號表中現出（但“定義否”標志為“未”），則把它的地址欄中的編號（記為q）取出，把nextstat填進該欄作新鏈首，然后產生四元式（goto q） 符號表符號表名字名字類型類型定義定義否否地址地址M ML標號標號未未r 四元式四元式(p) (goto 0)(q)