第6章 語法制導翻譯和中間代碼生成

1、第六章 語法制導翻譯和中間代碼生成學習目標：掌握：常見語法成分的中間代碼形式；常見語法成分的屬性文法或翻譯方法理解：屬性文法、語法制導翻譯方法天津財經(jīng)大學信息科學與技術系主要內(nèi)容屬性文法和語法制導翻譯：屬性文法語法制導翻譯基本思想中間代碼的表示形式（逆波蘭式、四元式、三元式、間接三元式、樹結構等等）簡單算術表達式和賦值語句的翻譯布爾表達式到四元式的翻譯控制結構翻譯成四元式天津財經(jīng)大學信息科學與技術系目標程序源程序詞法分析語法分析語義分析中間代碼生成代碼優(yōu)化目標代碼生成表格管理出錯處理天津財經(jīng)大學信息科學與技術系語義分析基礎語義分析的內(nèi)容主要是類型相容檢查，有以下幾種：各種條件表達式的類型是不是

2、boolean型？運算符的分量類型是否相容？賦值語句的左右部的類型是否相容？形參和實參的類型是否相容?下標表達式的類型是否為所允許的類型？函數(shù)說明中的函數(shù)類型和返回值的類型是否一致？天津財經(jīng)大學信息科學與技術系語義分析基礎-語義分析的內(nèi)容（續(xù)）其它語義檢查：VE中的V是不是變量，而且是數(shù)組類型？V.i中的V是不是變量，而且是記錄類型？i是不是該記錄的域名？x+f()中的f是不是函數(shù)名？形參個數(shù)和實參個數(shù)是否一致？每個使用性標識符是否都有聲明？有無標識符的重復聲明？天津財經(jīng)大學信息科學與技術系語義分析基礎在語義分析同時產(chǎn)生中間代碼，在這種模式下，語義分析的主要功能如下：語義審查在掃描聲明部分時構

3、造標識符的符號表在掃描語句部分時產(chǎn)生中間代碼中間代碼：獨立于機器，復雜性介于源語言和機器語言之間，十分接近目標機器指令的一種表示形式。對于中間代碼的產(chǎn)生，是很困難的，因為語義形式化比語法形式化難得多。目前普遍采用的語義分析方法語法制導翻譯方法使用屬性文法為工具來說明程序設計語言的語義。天津財經(jīng)大學信息科學與技術系6.1屬性文法(Attribute Grammar)屬性對文法的每一個符號，引進一些屬性，這些屬性代表與文法符號相關的信息，如類型、值、存儲位置等。語義規(guī)則為文法的每一個產(chǎn)生式配備的計算屬性的計算規(guī)則，稱為語義規(guī)則。屬性文法是帶屬性的一種文法它的主要思想：首先對于每個文法符號引進相關的

4、屬性符號；其次對于每個產(chǎn)生式寫出計算屬性值的語義規(guī)則天津財經(jīng)大學信息科學與技術系6.1 屬性文法(續(xù))屬性文法的形式定義一個屬性文法是一個三元組,A(G, V, F)G是一個上下文無關文法；V是屬性的有窮集；F是關于屬性的斷言的有窮集。說明：每個屬性與文法符號相聯(lián)，N.t表示文法符號N的屬性t。屬性值又稱語義值。存儲屬性值的變量又稱語義變量。每個斷言與文法的某個產(chǎn)生式相聯(lián)，寫在 內(nèi)。屬性的斷言又稱語義規(guī)則，它所描述的工作可以包括屬性計算、靜態(tài)語義檢查、符號表的操作、代碼生成等，有時寫成函數(shù)或過程段。天津財經(jīng)大學信息科學與技術系6.1 屬性文法(續(xù))例 完成類型檢查的屬性文法ET1+T2T1.t

5、int AND T2.tintET1 or T2T1.tbool AND T2.tboolTnumT.t :intTtrueT.t :boolTfalseT.t :bool天津財經(jīng)大學信息科學與技術系6.1 屬性文法(續(xù))屬性的分類：綜合屬性：從語法樹的角度來看，如果一個結點的某一屬性值是由該結點的子結點的屬性值計算來的，則稱該屬性為綜合屬性。內(nèi)在屬性是綜合屬性。用于“自下而上”傳遞信息天津財經(jīng)大學信息科學與技術系6.1 屬性文法(續(xù))繼承屬性從語法樹的角度來看，若一個結點的某一屬性值是由該結點的兄弟結點和（或）父結點的屬性值計算來的，則稱該屬性為繼承屬性。用于“自上而下”傳遞信息特別說明：終

6、結符只有綜合屬性，它們由詞法分析器提供非終結符既有綜合屬性也有繼承屬性，但文法開始符沒有繼承屬性天津財經(jīng)大學信息科學與技術系6.1 屬性文法(續(xù))例 簡單算術表達式求值的屬性文法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 E.val、T.val、F.val都是綜合屬性終結符digit只有綜合屬性lexval ，它的值由詞法分析器提供天津財經(jīng)大學信

7、息科學與技術系6.2 語法制導翻譯概論語法制導翻譯基本思想：在語法分析過程中，隨著分析的步步進展，每當使用一條產(chǎn)生式進行推導（對于自上而下分析）或歸約（對于自下而上分析），就執(zhí)行該產(chǎn)生式所對應的語義動作（語義子程序），完成相應的翻譯工作（產(chǎn)生中間代碼）。語法制導翻譯法不論對自上而下分析或自下而上分析都適用。天津財經(jīng)大學信息科學與技術系例 簡單算術表達式求值的屬性文法EE1+T E.val :E1.val +T.val ET E.val :T.val TT1*digit T.val :T1.val * digit.lexval Tdigit T.val :digit.lexval 2+3*5的語

8、法樹：EE1+TT1*5T23T.val=2T.val=3T.val=15E.val=2E.val=17自下而上語法制導翻譯過程：一旦語法分析確認輸入符號串是一個句子，它的值也同時由語義規(guī)則計算出來天津財經(jīng)大學信息科學與技術系6.3 中間代碼的形式定義：中間代碼是獨立于機器，復雜性介于源語言和機器語言之間，十分接近目標機器指令的一種表示形式。使用中間代碼的好處：中間代碼與具體機器無關，便于編譯程序改變目標機便于對中間代碼進行與機器無關的優(yōu)化表示形式：逆波蘭式、四元式、三元式、間接三元式和樹形表示天津財經(jīng)大學信息科學與技術系6.3.1 逆波蘭表示法（后綴式） 逆波蘭表示法將運算對象寫在前面，把運

9、算符寫在后面，因而也稱后綴式。例如：程序設計語言中的表示逆波蘭表示a+bab+a+b*c abc * +(a+b)*cab+c *天津財經(jīng)大學信息科學與技術系bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例：表達式bc*d的后綴式 bcd*+的計值過程后綴式的計算機處理后綴式的最大優(yōu)點是易于計算機處理處理過程：從左到右掃描后綴式，每碰到運算對象就推進棧；碰到運算符就從棧頂彈出相應目數(shù)的運算對象施加運算，并把結果推進棧。最后的結果留在棧頂。天津財經(jīng)大學信息科學與技術系逆波蘭表示法的擴充逆波蘭表示法很容易擴充到表達式以外的范圍 例如：語句逆波蘭表示備注a:=b+cabc+

10、:=:=看作二目運算符GOTO LL jumpjump看成一目運算符，表示GOTOIf E then S1 else S2ES1S2￥把￥ 看成三目運算符，表示if then else天津財經(jīng)大學信息科學與技術系6.3.2 三元式三元式(算符op，第一個運算對象ARG1,第二個運算對象ARG2)說明：三元式的某些運算對象是另一個三元式的編號（代表其結果）一目算符只需選用一個運算對象（ARG1）多目算符可用連續(xù)幾個三元式表示例： a :b*c+b*d表示為 (1) (* ,b,c)(2) (* ,b,d)(3) (+ ,(1),(2)(4) (:,(3),a)天津財經(jīng)大學信息科學與技術系6.3.

11、3 樹形表示樹形表示二目運算對應二叉子樹，多目運算對應多叉子樹，但通常通過引入新結點表示成二叉子樹。例如：a:b*c+b*d 表示成:=a+*bcbd葉子結點代表運算量，非葉子結點代表運算符天津財經(jīng)大學信息科學與技術系6.3.4 四元式四元式四元式是一種比較普遍采用的中間代碼形式(算符op，ARG1，ARG2，運算結果RESULT）例如：a:b*c+b*d的四元式表示如下： (*,b,c,t1 )(*,b,d,t2 )(+,t1,t2,t3 )(:,t3 ,a ) 其中t i（i1,2,3）是編譯程序引入的臨時變量天津財經(jīng)大學信息科學與技術系6.3.4 四元式（續(xù)）四元式的優(yōu)點：四元式比三元式

12、更便于優(yōu)化優(yōu)化要求改變運算順序或刪除某些運算，引起編號的變化。三元式通過編號引用中間結果，編號的變化引起麻煩；四元式通過臨時變量引用中間結果，編號變化無影響。四元式對生成目標代碼有利四元式表示很類似于三地址指令，很容易轉換成機器代碼。天津財經(jīng)大學信息科學與技術系6.3.4 四元式（續(xù)）四元式的另一種表示有時為了更直觀，把四元式寫成簡單賦值形式或更易理解的形式(三地址碼)四元式直觀形式（1）（ * , b , c , t1）（1） t1:b*c（2）（ * , b , d , t2）（2） t2:b*d（3）（ +, t1 , t2 , t3）（3） t3:t1+t2（4）（:, t3 , a）

13、（4） a:t3天津財經(jīng)大學信息科學與技術系6.3.5 間接三元式為了便于優(yōu)化處理，不直接使用三元式，而是另設一張指示器表（稱為間接碼表），它按照運算的先后順序列出有關三元式在三元式表中的位置。即：用一張間接碼表輔以三元式表的方法來表示中間代碼。四元式、間接三元式的優(yōu)化同樣方便，三元式的優(yōu)化十分困難。天津財經(jīng)大學信息科學與技術系舉例：給出A+B*(C-D)+E/(C-D)N的逆波蘭式、四元式、三元式、間接三元式的表示1、逆波蘭式：ABCD-*+ECD-N/+2、四元式：(-,C,D,T1)(*,B,T1,T2)(+,A, T2, T3)(-,C,D, T4)(, T4,N, T5)(/,E,

14、T5, T6)(+, T3, T6, T7)天津財經(jīng)大學信息科學與技術系舉例：給出A+B*(C-D)+E/(C-D)N的逆波蘭式、四元式、三元式、間接三元式的表示3、三元式：(-,C,D)(*,B,1)(+,A, 2)(-,C,D)(, 4),N)(/,E,5)(+, 3),6)4、間接三元式：(-,C,D)(*,B,1)(+,A, 2)(, 1),N)(/,E,4)(+, 3),5)間接碼表1)2)3)1)4)5)6)天津財經(jīng)大學信息科學與技術系6.4 語法制導翻譯主要討論自下而上的語法制導翻譯在一個產(chǎn)生式進行歸約時，執(zhí)行相應的語義動作進行翻譯（產(chǎn)生中間代碼）天津財經(jīng)大學信息科學與技術系6.

15、4.1簡單賦值語句到四元式的翻譯簡單賦值語句是指不含復雜數(shù)據(jù)類型（如數(shù)組，記錄等）的賦值語句。賦值語句的語義檢查包括：每個使用性標識符是否都有聲明？運算符的分量類型是否相容？賦值語句的左右部的類型是否相容？賦值語句的翻譯目標：在賦值語句右部表達式產(chǎn)生的四元式序列后加一條賦值四元式天津財經(jīng)大學信息科學與技術系6.4.1簡單賦值語句到四元式的翻譯考慮如下文法描述的簡單賦值句的翻譯：Ai:=E EE+E|E*E|-E|(E)|i (6.1)A代表賦值語句，設只含整型變量的運算1、需要定義一系列的語義變量和語義過程：NEWTEMP：函數(shù)，生成臨時變量，每次調(diào)用生成一個新的臨時變量，如t1, t2 ,

16、返回一個整數(shù)碼作為函數(shù)值。ENTRY(i)：函數(shù)過程，查找并取得與i相對應的標識符在符號表中的位置（入口），簡稱i值。E.PLACE：與E相聯(lián)系的語義變量，表示存放E值的變量名在符號表的入口。GEN(OP,ARG1,ARG1,RESULT)：語義過程，將四元式(OP,ARG1,ARG1,RESULT)填進四元式表中。 天津財經(jīng)大學信息科學與技術系使用上述變量和過程，對文法6.1所定義的賦值語句的翻譯算法可由下述語義動作予以描述6.4.1簡單賦值語句到四元式的翻譯產(chǎn)生式語義動作Ai:=E GEN(:=,E.PLACE,-,ENTRY(i) EE(1)+E (2) E.PLACE:=NEWTEMP

17、; GEN(+,E(1).PLACE,E(2).PLACE,E.PLACE) EE(1)*E (2) E.PLACE:=NEWTEMP; GEN(*,E(1).PLACE,E(2).PLACE,E.PLACE) E-E(1) E.PLACE:=NEWTEMP; GEN(,E(1).PLACE,-,E.PLACE) E(E(1) E.PLACE:=E(1).PLACE Ei E.PLACE:=ENTRY(i) 天津財經(jīng)大學信息科學與技術系輸入串棧PLACE四元式A:=-B*(C+D):=-B*(C+D)iA-B*(C+D)i:=A_B*(C+D)i:= -A_ _*(C+D)i:= -iA_ _

18、B*(C+D)i:= -EA_ _B(,B,-,T1)*(C+D)i:= EA_T1(C+D)i:= E*A_T1 _C+D)i:= E*(A_T1 _ _+D)i:= E*( iA_T1 _ _C+D)i:= E*( EA_T1 _ _CD)i:= E*( E+A_T1 _ _C_)i:= E*( E+iA_T1 _ _C_D)i:= E*( E+EA_T1 _ _C_D(+,C,D,T2)i:= E*( EA_T1 _ _T2i:= E*( E)A_T1 _ _T2 _i:= E* EA_T1 _T2(*, T1 ,T2,T3)i:=EA_ T3(:=, T3, - ,A)A2例：寫出下面

19、賦值語句A:=-B*(C+D)的自下而上語法制導翻譯的過程，及生成的四元式。Ai:=E EE+E|E*E|-E|(E)|i 四元式為:(1)(,B,-,T1) (2) (+,C,D,T2) (3)(*, T1 ,T2,T3) (4) (:=, T3, - ,A)天津財經(jīng)大學信息科學與技術系3、類型轉換表達式中可能出現(xiàn)不同類型的變量和常量若不接受不同類型的運算對象混合運算，則應指出錯誤；若接受混合運算則要進行類型轉換處理。例：假定表達式可以有混合運算，變量可以是整型和實型，且當兩個不同類型的變量進行運算時先把整型變量轉換成實型，再進行運算。用 +i , *i , i 表示整型運算，用 +r ,

20、*r, r表示實型運算，用一目算符 itr 表示將整型量轉換成實型量的運算令文法6.1中的 i 既可以是整型也可以是實型用E.MODE表示E的類型信息，其值為int或r，則產(chǎn)生式EE(1) op E(2)的語義動作中，關于E.MODE的語義規(guī)則可定義為： if E1. MODE int AND E2. MODE int then E. MODE :=int else E. MODE :=r 天津財經(jīng)大學信息科學與技術系3、類型轉換（續(xù)）EE(1) op E(2) 的語義程序應該修改，必要時產(chǎn)生對運算量進行類型轉換的四元式：(itr,A,-,T)，表示把整型A轉換成實型量，結果存于T中。例：假定

21、輸入串為X:=Y+I*J，其中X,Y為實型，I,J為整型，則其產(chǎn)生的四元式為：(1) (*i ,I,J,T1) (2)(itr,T1,-,T2) (3) (+r ,Y,T2,T3) (4) (:=,T3,-,X)例：關于產(chǎn)生式EE(1) op E(2) 的語義子程序更為具體的描述為：天津財經(jīng)大學信息科學與技術系T:=NEWTEMP;IF E1.MODE=int AND E2.MODE=int THEN BEGIN GEN(opi , E1.PLACE, E2.PLACE,T); E.MODE:=int ENDELSE IF E1.MODE=r AND E2.MODE=r THEN BEGIN

22、GEN(opr , E1.PLACE, E2.PLACE,T); E.MODE:=r ENDELSE IF E1.MODE=int /*AND E2.MODE=r */ THEN BEGIN U:=NEWTEMP; GEN(itr, E1.PLACE,-,U);GEN(opr , U,E2.PLACE,T); E.MODE:=r ENDELSE /* E1.MODE=r AND E2.MODE=int */ BEGINU:=NEWTEMP; GEN(itr, E2.PLACE,-,U);GEN(opr , E2.PLACE, U, T); E.MODE:=r ENDE.PLACE:=TEE(1

23、) op E(2)天津財經(jīng)大學信息科學與技術系布爾表達式的兩個作用：用于邏輯運算，計算邏輯值作為控制語句(如if-then,while)的條件表達式布爾表達式由布爾算符（not,and,or）作用于布爾變量（或常數(shù)）或關系表達式而形成的。關系表達式的形式：E1 rop E2，rop是關系算符(如, , =)6.4.2布爾表達式到四元式的翻譯天津財經(jīng)大學信息科學與技術系為簡單起見，只考慮如下形式的布爾表達式的翻譯，文法(6.2)EE or E | E and E | not E | (E ) | id rop id |id布爾算符的優(yōu)先順序（從高到低）為：not,and,or，且and和or都服

24、從左結合，not服從右結合關系算符的優(yōu)先級都相同，而且高于任何布爾算符，低于任何算術算符6.4.2布爾表達式到四元式的翻譯-續(xù)天津財經(jīng)大學信息科學與技術系1.布爾表達式的計算方法： 采用兩種方法：數(shù)值表示的直接計算與邏輯表示的短路計算直接計算與算術表達式計算方法基本相同如：1 or 0 and 1=1 or 0 的結果為：1短路計算即布爾表達式計算到某一部分就可以得到結果，而無需對布爾表達式進行完全計算?？梢杂胕f-then-else來解釋A or B if A then true else BA and Bif A then B else falsenot Aif A then false

25、else true天津財經(jīng)大學信息科學與技術系2、直接計算的語法制導翻譯布爾表達式有兩種翻譯方法。（視計算機硬件條件來確定，如果執(zhí)行條件轉移效率較低，就用第一種方法）直接計算的語法制導翻譯 如同翻譯算術表達式一樣來翻譯布爾表達式如：A or B and not C被翻譯成：(1) (not,C,- ,T1)(2) (and,B,T1,T2)(3) (or,A,T2,T3)天津財經(jīng)大學信息科學與技術系3.作為條件控制的布爾式翻譯基本翻譯方法當布爾表達式用于控制條件時，并不需要計算表達式的值，而是一旦確定了表達式為真或為假，就將控制轉向相應的代碼序列。S2 的代碼S1 的代碼E的代碼E.false

26、 E.true if E then S1 else S2為布爾表達式E引入兩個新的屬性：E.true：表達式的真出口，它指向表達式為真時的轉向E.false：表達式的假出口，它指向表達式為假時的轉向天津財經(jīng)大學信息科學與技術系把布爾表達式E翻譯成下述形式的條件轉移和無條件轉移的四元式序列：( jnz , A , - , p )若A為真，則轉向四元式p( jrop , A , B , p )若A rop B為真，則轉向四元式p( j , - , - , p )無條件轉向四元式p3.作為條件控制的布爾式翻譯-續(xù)天津財經(jīng)大學信息科學與技術系(1) ( jnz , A , - , 5 )A的真出口為5

27、(2) ( j , - , - , 3 )A的假出口為3(3) ( j , B , D , 5 )BD的真出口為5(4) ( j , - , - , p+1 ) BD的假出口為(p+1)(5) (關于S1的四元式序列)(p)( j , - , - , q )跳過S2的代碼段(p+1)(關于S2的四元式序列)(q)(1) - (4)是布爾式A or BD 翻譯產(chǎn)生的代碼，全部是條件轉移和無條件轉移四元式，沒有布爾運算。例：if A or BD then S1 else S2翻譯成如下四元式序列天津財經(jīng)大學信息科學與技術系具體說明如下：用E.true和E.false 分別表示E的“真”和“假”出口

28、轉移目標，在翻譯E時并未能確定。對于E為 a rop b 形式，生成代碼如下：( jrop , a , b , E.true )( j , E.false )以結構圖表示：E的代碼E.falseE.true天津財經(jīng)大學信息科學與技術系對于E為 E1 or E2的形式，生成代碼結構如下：E1.的代碼E2.的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true若E1為真，則可知E為真，即E1的真出口和E的真出口一樣；若E1為假，則必須計算E2，因此E1的假出口應是E2代碼的第一個四元式序號；E2的真出口和假出口分別與E的真出口和假出口一樣天津財經(jīng)大學信息科學與

29、技術系E1.的代碼E2.的代碼E1.falseE2.falseE.falseE1.trueE2.trueE.true對于E為 E1 and E2的形式，生成代碼結構如下：對于E為 not E1形式，只需調(diào)換E1的真假出口，即可得到E的真假出口。天津財經(jīng)大學信息科學與技術系例：E 為 ab or cf ，翻譯為四元式序列：（1） (j, a,b,E.true)（2） (j, - ,- ,(3)（3） (j, e ,f ,E.true)（6） (j, - ,- ,E.false)舉例真假出口的拉鏈與回填在把布爾式翻譯成一串條件轉和無條件轉四元式時，真假出口未能在生成四元式時確定；而且多個四元式可能

30、有相同的出口天津財經(jīng)大學信息科學與技術系說明：E.true和E.false不能在產(chǎn)生四元式的同時確定，要等將來目標明確時再回填，為此要記錄這些要回填的四元式。通常采用“拉鏈”的辦法，把需要回填E.true的四元式拉成一條“真”鏈，把需要回填E.false的四元式拉成一條“假”鏈。if ab or cf then S1 else S2翻譯為四元式序列：（1） (j , a ,b ,(7)（2） (jump, - ,- ,(3)（3） (j , e ,f ,(7)（6） (jump, - ,- ,(p+1) （7）(關于S1的四元式)（p）(jump, - ,- ,q)(p+1)(關于S2的四元式

31、) (q)天津財經(jīng)大學信息科學與技術系練習：把下面的語句翻譯成四元式序列：If AB or CD then X:=Y else X:=Y=1100 (j,A,B,104)101 (j,-,-,102)102 (j,C,D,104)103 (j,-,-,106)104 (:=,Y,-,X)105 (j,-,-,108)106 (+,Y,1,T)107 (:=,T,-,X)108說明：產(chǎn)生是100103是對應布爾式AB or C=,C,D,106)。但這些是下一階段代碼優(yōu)化要討論的問題，暫不討論。天津財經(jīng)大學信息科學與技術系6.4.3 控制語句的翻譯以if 語句，while語句為例說明控制語句的翻譯方法S if E then S1 if語句| if E then S1 else S2if語句| while E do Swhile語句其中：E:布爾表達式， S，S1 , S2 為語句天津財經(jīng)大學信息科學與技術系E1=1E2=1S1S2S3endstartYesNoYesNo條件轉移語句的共同特點是：根據(jù)布爾表達式取值，分別執(zhí)行不同的語句序列。問題：不同的語句序列結束后，如何使控制轉向語句的結束。例如：if E1