1、S.P,O.P,第5章語法制導翻譯技術和中間代碼生成,要求明確語義分析的任務 明確屬性文法和語法制導翻譯的含義 明確自底向上和自頂向下語法制導翻譯的區(qū)別和特點 明確生成中間代碼的目的，中間代碼的幾種形式,教學目標,屬性文法 語法制導翻譯法的基本思想 常見的中間代碼 各種不同語法結構的語法制導翻譯技術,教學內容,詞法分析，語法分析：解決單詞和語言成分的識別及詞法和語法結構的檢查。語法結構可形式化地用一組產生式來描述。給定一組產生式，我們能夠很容易地將其分析器構造出來。 本章要介紹的是語義分析和中間代碼生成技術。 程序語言中間代碼目標代碼,翻譯,翻譯,根據(jù)語義規(guī)則對識別出的各種語法成分析其含義，進

2、行初步翻譯，生成相應的中間代碼或直接生成目標代碼。,第一，審查每個語法結構的靜態(tài)語義，即檢查語法結構合法的程序是否真正有意義。也稱靜態(tài)語義檢查。（類型檢查、控制流的檢查、一致性檢查、相關名字的檢查） 第二，如果靜態(tài)語義正確，語義處理則要執(zhí)行真正的翻譯，要么生成中間代碼，要么生成實際的目標代碼。（說明性語句：填符號表；可執(zhí)行性語句：生成中間代碼）,語義分析的任務,類型檢查。 控制流檢查，確保控制語句有合法的轉向點。例如，C語言中的break語句使控制跳離包括該語句的最小的switch，while或for語句。如果不存在包括它的這樣的語句，則應報錯。,靜態(tài)語義檢查,靜態(tài)語義檢查,一致性檢查。很多情

3、況下要求對象只能被定義一次。例如，語言中規(guī)定一個標識符在同一作用域中只能被說明一次，同一case語句的標號不能相同，枚舉類型的元素不能重復出現(xiàn)等。 相關名字檢查。有的語言中有時規(guī)定，同一名字必須出現(xiàn)兩次或多次。例如，Ada語言中，循環(huán)或程序塊可以有一個名字，它出現(xiàn)在這些結構的開頭和結尾，如同語句括號一般，編譯程序必須檢查它們的配對情況。,附加了一組屬性和運算（語義）規(guī)則的文法,5.2 屬性文法,文法符號X的屬性t常用X.t來表示,語義規(guī)則是根據(jù)產生式所蘊涵的語義操作建立起來的，并與語義分析的目標有關 不同的產生式對應不同的語義規(guī)則 不同的分析目標也對應不同的語義規(guī)則,靜態(tài)語義檢查、符號表操作、

4、代碼生成及打印各種錯誤信息,屬性文法,屬性文法的形式定義： AG： AG=（G，V，E） G:上下文無關文法; V:屬性的有窮集合;每一個屬性與某一個文法符號相關聯(lián)；用文法符號屬性表示 E:表示屬性的斷言或謂詞的有窮集合(語義規(guī)則);每一個斷言與文法的某個產生式相關聯(lián)) 屬性:綜合屬性(自下而上傳遞信息)、繼承屬性（自上而下傳遞信息),非終結符E、T及F都有一個綜合屬性val,符號i有一個綜合屬性。 某些非終結符加下標是為了區(qū)分一個產生式中同一非終結符多次出現(xiàn),語 義 規(guī) 則,E E1+T,E T,T T1 * F,T F,F (E),F i,E.val=E1.val+T.val,E.val=

5、T.val,T.val=T1.val F.val,T.val=F.val,F.val=E.val,F.val=i.lexval,產生式,例5.1,語法制導翻譯的過程,語法制導翻譯：將語義規(guī)則與語法規(guī)則相結合，在語法分析的過程中通過執(zhí)行語義動作，計算語義屬性值，從而完成預定的翻譯工作。,自底向上語法制導翻譯,自頂向下語法制導翻譯,語法制導翻譯的實現(xiàn),語法制導翻譯分為兩種處理方法： （1）語法制導定義（自底向上）： 對每個產生式編制一個語義子程序，在進行語法分析的過程中，當一個產生式獲得匹配時，就調用相應的語義子程序實現(xiàn)語義檢查與翻譯。這種實現(xiàn)方案隱藏了其中語義規(guī)則的計算次序等實現(xiàn)細節(jié)，不必規(guī)定翻

6、譯順序。 （2）翻譯方案（自頂向下）： 在產生式右部的適當位置，插入相應的語義動作，按照分析的進程，執(zhí)行遇到的語義動作。這是一種動作與分析交錯的實現(xiàn)方案。,輸入符號串 分析樹 執(zhí)行語義規(guī)則 翻譯結果,翻譯步驟,（）從分析樹得到描述結點屬性間依賴關系的依賴圖，由依賴圖得到語義規(guī)則的計算次序,（1）分析輸入符號串，建立分析語法樹,（）進行語義規(guī)則的計算，得到翻譯結果,語法制導定義,對每個產生式編制一個語義子程序 在進行語法分析的過程中，當一個產生式獲得匹配時，就調用相應的語義子程序實現(xiàn)語義檢查與翻譯,自底向上傳遞信息,自頂向下（自左向右）傳遞信息,print(E.val)打印由E產生的算術表達式的

7、值，可認為這條規(guī)則定義了L的一個虛屬性。,L E,E E1+T,E T,T T1 * F,T F,F (E),F i,print(E.val),E.val=E1.val+T.val,E.val=T.val,T.val=T1.val F.val,T.val=F.val,F.val=E.val,F.val=i.lexval,例5.綜合屬性,語 義 規(guī) 則,產生式,一個結點的綜合屬性值是其子結點的某些屬性來決定的,+3*4的注釋分析樹,通常使用自底向上的分析方法 在每個結點處使用語義規(guī)則來計算綜合屬性值 當一個產生式獲得匹配時，就調用相應的語義子程序 從葉結點到根結點進行計算,只含有綜合屬性的語法制

8、導定義稱為S屬性定義,S屬性定義與自底向上翻譯,LR分析器可以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算 LR分析器增加屬性值（語義）棧,首先，為文法的每條規(guī)則設計相應的語義子程序； 增加一個語義信息棧； 在語法分析的同時做語義處理：即在用某一個產生式進行規(guī)約的同時，調用相應的語義子程序完成所用規(guī)則的語義動作，并將每次動作后的值保存在語義棧中,翻譯步驟,計算表達式2+3*5,GE： 1 EE+T 2 ET 3 TT*F 4 TF 5 F(E) 6 Fi,i+i*i,表達式2+3*5的歸約過程,注意,句柄歸約在先，語義動作調用在后 歸約時，棧內句柄各符號的語義信息與句柄及同時出

9、棧，整個句柄所表示的語義信息則賦給相應產生式左部非終結符號的語義變量，并讓該非終結符號及語義信息同時入棧,生成中間代碼的目的 (1)便于優(yōu)化 (2)便于移植 (3)邏輯結構清晰,常見的中間代碼形式： 后綴式 三地址代碼（四元式、三元式和間接三元式 ）圖形（抽象語法樹、有向無環(huán)圖）,中間代碼：一種介于源語言和目標語言之間的中間語言形式,5.中間代碼,中綴表示后綴表示 a+b ab+ a+b*c abc*+ (a+b)*c ab+c* a:=b*c+b*d abc*bd*+:=,特點,1、運算對象出現(xiàn)的順序和原有順序（從左到右）相同 2、運算符按實際計算順序（從左到右）出現(xiàn) 3、運算符緊跟在運算對

10、象的后面出現(xiàn)，且沒有括號,優(yōu)點：簡明、便于計值,后綴式,分別給出下列表達式的后綴表示,1. -a+b*(-c+d) 2. X:=-(a+b)/(c-d)-(a+b*c) 3. a=c b=d 4. ab+c ada+be,逆波蘭表示法（后綴式）,特點：運算符直接寫在其運算對象之后。 不再有括號 運算對象出現(xiàn)的次序未變 求值過程簡單，宜于用棧實現(xiàn),后綴式的計算 用一個棧實現(xiàn)。 一般的計算過程是：自左至右掃描后綴式，每碰到運算量就把它推進棧。每碰到k目運算符就把它作用于棧頂?shù)膋個項，并用運算結果代替這k個項。,三地址代碼,種類,（1）x = y op z形式的賦值語句，其中op是二元運算符。 （2

11、）x = op y形式的賦值語句，其中op是一元運算符。 （3）x = y形式的賦值語句。 （4）無條件轉移語句goto L，表示下一個要執(zhí)行的語句是標號為L的語句。 （5）條件轉移語句if x rop y goto L中，rop為關系運算符，如果x和y滿足關系rop，就轉而執(zhí)行標號為L的語句，否則順序執(zhí)行下一個語句。,（6）過程調用語句param x 和call p , n。源程序中的過程調用語句p(x1，x2，xn)可以產生如下的三地址代碼： param x1 param x2 param xn call p, n 其中n為實參個數(shù)。過程返回語句形如return y，其中y為過程返回的一個

12、值。,（7）變址賦值： x= yi，把從y開始的第i個存儲單元的值賦給x。 xi= y，把y的值賦給x開始的第i個存儲單元。 其中，x，y和i都代表數(shù)據(jù)對象。 （8）地址和指針賦值： x=單目運算，運算對象2為空 (2) (*,(1),c) (3) (+,a,(2),三元式,X=a+b*c Y=d-b*c,三元式表 (1)(*,b,c) (2)(+,a,(1) (3)(=,x,(2) (4)(_,d,(1) (5)(=,y,(4),四元式 (三地址代碼）,X=a*b+c*d的四元式序列 三地址代碼 (1)(* ,a,b,T1) (1)T1=a*b (2)(*, c,d,T2) (2)T2=c*

13、d (3)(+,T1,T2,T3) (3)T3=T1+T2 (4)(=,T3,_,X) (4)X=T3,2020年8月22日,編 譯 原 理,a:=b*(-c)+b*(-c)的圖表示法,2020年8月22日,編 譯 原 理,抽象語法樹對應的代碼： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,2020年8月22日,編 譯 原 理,DAG對應的代碼： T1:=-c T2:=b*T1 T5:=T2+T2 a:=T5,抽象語法樹對應的代碼： T1:=-c T2:=b*T1 T3:=-c T4:=b*T3 T5:=T2+T4 a:=T5,屬性翻譯文法的

14、應用,綜合屬性與自下而上定值 每個非終結符的屬性值都是根據(jù)位于其下面那些符號的屬性值來確定的，即按一種自下而上的方式來確定的。 繼承屬性和自上而下定值 非終結符的屬性值或者根據(jù)其上層非終結符的屬性來確定或者根據(jù)產生式右部其它符號的屬性來確定。這種屬性值是根據(jù)自上而下方式確定的。,自底向上的語法制導翻譯,自底向上的語法制導翻譯方法是在自底向上的語法分析過程中逐步實現(xiàn)語義規(guī)則的翻譯方法。在實現(xiàn)時注意以下幾點： （1）自底向上的翻譯的特點，棧的操作，對產生式的要求等 （2）各種程序語句的目標結構 （3）從源結構到目標結構的變換方法（包括對產生式的改造等）,算術表達式和賦值語句的翻譯,翻譯步驟： （1

15、）分析文法的特點； （2）設計一系列的語義變量、定義語義過程、語義函數(shù)； （3）設計每一條規(guī)則的語義子程序； （4）增加一個語義信息棧，構造LR分析表; (5)語法分析同時語義處理.,例： 有文法GA： 1.Ai:=E 2.E E+TT 3.T T*FF 4.F P 5.P i (E) 簡單算術表達式的計值順序與四元式出現(xiàn)的順序相同,因此目標代碼的順序(結構)為: (1)先生成E的代碼(一系列順序執(zhí)行的四元式) (2)把E的值賦給變量i(表達式的結果賦給賦值語句的左變量),引入語義變量,語義過程和語義函數(shù) (1)語義變量E.place:表示存放E值的變量名在符號表中的入口地址或臨時變量的整數(shù)碼

16、. (2)語義函數(shù)newtemp():申請一個臨時單元,存放中間結果; (3)語義過程emit(T=arg1 op arg2):產生一條四元式,并添入四元式表中; (4)語義過程lookup():審查是否出現(xiàn)在符號表中,在:返回地址,不在:返回NULL; (5)語義函數(shù)entry(i):回送標識符i在符號表中的入口地址.,表達式的語義動作設計,1. Ai:=Eemit(entry(i)=E.place 2. E E1+TE.place=newtemp(), emit(E.place)=E1.place+T.place 3.E T E.place=newtemp(), e

17、mit(E.place=T.place) 4. T T1*FT.place=newtemp(), emit(T.place)=T1.place*F.place 5. T F T.place=newtemp(), emit(T.place=F.place),6.F _P F.place=newtemp(), emit(F.place)=P.place 7.P (E) P.place=newtemp(), emit(P.place=E.place) 8.P iP.place=newtemp(), emit(P.place=Entry(i),例如:表達式X:=a+b*(c-d)的翻譯,K+1: T1

18、:=c-d K+2: T2=b*T1 K+3: T3:=a+T2 K+4: X:=T3,(-,c,d,T1) (*,b,T1,T2) (+,a,T2,T3) (:=,T3,_,X),布爾表達式的翻譯,布爾表達式 是由布爾運算符(and,or,not)作用于布爾變量(或常數(shù))或關系表達式而形成的。 布爾表達式的作用： 用作控制語句中的條件：if-then、 while、repeat等 邏輯賦值句中的邏輯運算,布爾表達式到四元式的翻譯,文法：EEEEEE(E)idE rop E 其中，(and)、(or)、(not)為布爾（邏輯）運算符；rop為關系運算符（，=，）；id為布爾（邏輯）變量或布爾（

19、邏輯）常數(shù)；E rop E為關系表達式。 布爾表達式的求值方法： 通過逐步計算出各部分的值來計算整個表達式。 利用布爾運算符的性質計算其值,布爾表達式作為控制語句中的條件式,作用是用于選擇下一個執(zhí)行點 while E do S1 E的作用是選擇S1執(zhí)行,還是跳過S1語句,執(zhí)行S1后面的語句 E有兩個出口: 真:S1語句 假:S1后面的語句,While語句的目標結構,布爾初等量(布爾變量和關系表達式)的目標結構,由兩個轉移四元式構成,一個表示真出口Li,另一個表示假出口Lj,設E是一布爾變量, 它的目標結構為: (1) if E goto Li (jumpt , E,_, Li ) (jnz,A

20、,_, Li) (2) if E1 rop E2 goto Li (jump ,E1 ,E2 ,Li) (jrop,E1,E2, Li) 例:(j,a,b,p) (3) goto Lj (jump Lj ) (j,_,_, Lj ),舉例:if ab then A:=x+y的四元式序列,if ab goto Li (真出口) goto Lj (假出口) Li:S的第一個四元式 S的最后一個四元式 Lj:S 后面的語句,(1) if ab goto (3) (2) goto (5) (3)T1:=x+y (4)A:=T1 (5),多因子組成的布爾表達式的翻譯,例: if ab c then S1

21、 else S2 分析結果如下: 當ab為真,執(zhí)行S1,不需要計算c的值 當ab為假,計算c的值,c為真:執(zhí)行S1,為假:執(zhí)行S2 當ab與c分別為真時,程序轉向一致,真出口相同(S1) 當ab與c分別為假時,程序轉向一致,假出口相同(S2),if ab c then S1 elseS2的四元式序列,(1) if ab goto S1的第一條語句 (5) (2) goto (3) (3) if c goto S1的第一條語句 (5) (4) goto S2的第一條語句 ( p+1 (5) 關于S1的四元式序列 (p) Goto q (p+1)關于S2的四元式序列 (q)后繼四元式,目標結構,E

22、的代碼 T F,S1的代碼,JUMP S,S2的代碼,S（后繼語句）,2020年8月22日,編 譯 原 理,if E then S1 else S2的四元式序列,(1) if E goto (3) (2) goto (S2的第一個四元式) (p+1) (3)關于S1的四元式序列 (p) goto r (執(zhí)行完S1后轉出) (p+1)關于S2的四元式序列 (r) 后繼四元式,2020年8月22日,編 譯 原 理,while E do S1的四元式序列,(1) if E goto (3) (2)goto ( S1后面的語句) (p+1) (3)關于S1的四元式序列 (p) goto (1) (p+

23、1) 后繼四元式,2020年8月22日,編 譯 原 理,真出口鏈、假出口鏈、回填（Backparch),在多個因子組成的布爾表達式中，可能有多個因子的真出口或假出口的轉移去向相同，但又不能立刻知道具體轉向位置。 把轉移方向相同的四元式鏈在一起，一旦發(fā)現(xiàn)具體轉移目標，就回填。 真出口用Etrue來表示。 假出口用Efalse來表示。 回填Backparch（g,t)將t填入由g所指向的四元式的結果部分,2020年8月22日,編 譯 原 理,if ab c then S1 elseS2的真假出口回填描述,(1) if ab goto 0 /E的真出口Etrue有待回填 (2) goto (3) /

24、*回填E的第一個假出口 (3) if c goto (1)/* （3）是E的真出口鏈 (4) goto 0 /*E的假出口Efalse有待回填 (5) 關于S1的四元式序列/*此時回填真出口Etrue (p) goto 0 /*有待回填q的位置 (p+1)關于S2的四元式序列/*此時回填假出口Efalse (q)后繼四元式/*此時回填q,2020年8月22日,編 譯 原 理,語法制導翻譯中使用的公共變量、過程和函數(shù),guad:四元式指針 (表示四元式的編號或地址) GEN(X):生成一條四元式,把它放到四元式表的尾部,(和前面介紹的emit功能相同) Nextguad:指向下一個即將形成的四元

25、式的編號,其初值為1,執(zhí)行一次GEN(X),Nextguad自動加1; merg（p1,p2)函數(shù)將以 p1,p2為鏈首的兩個四元式合并為一,返回合并后的鏈首,條件語句的翻譯,基本思路： 先對定義它的文法進行改造，以便能在相應處添加上語義子程序； 根據(jù)它的語義，設計出相應語義子程序的動作。,2020年8月22日,編 譯 原 理,if語句的文法,S if E then S1 S if E then S1 else S2 (E是轉移條件) 對if E then S1 else S2,其Etrue直到掃描到then,產生S1的第一個四元式序號時,才能將該標號作為E的真鏈填入到Etrue,而Efals

26、e 直到掃描到else,產生S2的第一個四元式序號時,才得到Efalse的值。,2020年8月22日,編 譯 原 理,if語句文法的改造,(1) C if E then (2) T C S1 else (3) S T S2 (4) S C S1 目標結構如右圖,2020年8月22日,編 譯 原 理,(1) C if E then backpatch(Etrue, Nextguad),C.chain=Efalse 當用產生式if E then 進行歸約時,生成了條件E的代碼,E的假出口不能回填,通過非終結符C向后傳遞,所以引入C.chain鏈.,if語句的語義動作,2020年8月22日,編 譯

27、原 理,(2) T C S1 else q:= Nextguad,emit(goto 0) Backpatch(C.chain,Nextguad), T.chain=merg(S1.chain,q) 當用產生式T C S1 else 歸約時,S1的代碼已經形成,回填E的 假出口即C.chain。此時S2 的代碼尚未形成,S1的轉出鏈和JMP轉向相同,合并為一,通過T向后傳遞.,if語句的語義動作,2020年8月22日,編 譯 原 理,if語句的語義動作,(3)S T S2 S.chain:=merg(T.chain,S2.chain) (4) S C S1 S.chain:=merg(C.ch

28、ain,S1.chain),2020年8月22日,編 譯 原 理,If AB CD then if AB then F:=1 else F:=0 else G:=G+1,采用then 與else的最近匹配原則(三地址指令) (1)if A goto (3) (2)goto 0 (13) (3)if B goto (5) (4)goto (2) (13) (5) if CD goto (7) (6)goto (4) (13) (7)if AB goto (9) (8)goto 0 (11),(9)F:=1 (10) goto 0 (15) (11) F:=0 (12) goto (10) (15

29、) (13) T:=G+1 (14) G:=T (15),2020年8月22日,編 譯 原 理,If AB CD then if AB then F:=1 else F:=0 else G:=G+1,四元式形式代碼 (1)(jnz,A,_,(3) (2)(j,_,_,0) (13) (3)(jnz,B,_,(5) (4)(j,_,_,(2) (13) (5)(j,C,D,(7) (6)(j,_,_,(4) (13) (7)(j,A,B,(9) (8)(j,_,_,0) (11),(9)(:=,1,_,F) (10)(j,_,_,0) (15) (11)(:=,0,_,F) (12)(j,_,_

30、,(10) (15) (13)(+,G,1,T) (14)(:=,T,_,G) (15),2020年8月22日,編 譯 原 理,While 語句的翻譯,文法:GS S while E do S 文法改造為: S CS1 C W E do W while,2020年8月22日,編 譯 原 理,（1）W while W.head:= Nextguad; 當用W while 歸約時, Nextguad記下E的第一個四元式的位置,保留在Wguad中。 （2）C W E do backpatch(Etrue, Nextguad, C.chain=Efalse,C.head= W.head 當使用C W

31、E do 進行歸約時,E的代碼已經生成有兩個出口Etrue和Efalse,掃描完do后,可以回填Etrue,而Efalse要到S1語句全部生成后才能回填,因此為待填信息,由C向后傳遞。,While 語句的語義動作,2020年8月22日,編 譯 原 理,While 語句的語義動作,（3）SC S1 Backpatch(S1chain,C.head);S.chain:= C.chain;GEN(goto,W.head); 當用上式進行歸約時，S1語句全部產生，while 語句結束應返回，因此產生四元式（goto w.head),同時回填Efalse,2020年8月22日,編 譯 原 理,while

32、 a0b0 do if xy then b:=b-1 else a:=a-1,假設四元式序列從100開始編號 100（j,a,0,102) 101 (j,_,_,0) (112) 102 (j,b,0,104) 103 (j,_,_,101) (112) 104 (j,x,y,106) 105 (j,_,_,0) (109) 106 (-,b,1,T1),107 (:=,T1,_,b) 108 (j,_,_,100) 109 (j,a,1,T2) 110 (:=,T2,_.a) 111 (j,_,_,100) 112,2020年8月22日,編 譯 原 理,文法GS: SSaAA AAbBB B

33、cSde (1)證明AacAbcBaAdbed是文法的一個句型. (2)請寫出該句型的所有短語、素短語及句柄。 （3）為文法GS 的產生式構造相應的翻譯子程序，使句型AacAbcBaAdbed經該翻譯方案翻譯后，輸出為131042521430。,2020年8月22日,編 譯 原 理,文法及相應的翻譯方案如下:,SbTc print”1” Sa print”2” TR print”3” RR/S print”4” RS print”5” 對于輸入符號串 bR/bTc/bSc/ac,該符號串的輸出是什么? 輸出為1453142431,歸約的次序為: (1) SbTc (1) (2) RR/S (4) (3) RS (5) (4) TR (3) (5) SbTc (1) (6) RR/S (