大三下編譯最終作業(yè)lect5-attribute

1、2011年春季學(xué)期編譯技術(shù)第5章語導(dǎo)翻翻譯譯Syntax-Directed Translation.語導(dǎo)翻譯概述5.1 屬性文法5.2 翻譯模式5.3 自頂向下翻譯5.4 自底向上翻譯2.語導(dǎo)翻譯概述在語法分析完成之后，一般還需要把輸入的源代碼翻譯為一種目標(biāo)表示形式。n語導(dǎo)翻譯（syntax-directed translation）指的是編譯器在分析過程中執(zhí)行的工作n 首先是語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標(biāo)代碼n 文法符號的屬性可以描述文法符號的語義例如，一個變量文法符號的屬性可以有變量的類型，層次，地址等。表達(dá)式的屬性有類型，值等。n 通過對屬性值的計(jì)算完成翻譯任務(wù)3語

2、義動作（semantic action）分析器中添加一些代碼分析器的語法動作一起配合執(zhí)行。n 語法動作：指的是分析過程中的移進(jìn)和歸約n 語義動作：每個產(chǎn)生式都關(guān)聯(lián)一些代碼序列， 當(dāng)該產(chǎn)生式被應(yīng)用的時候會執(zhí)行相應(yīng)的代碼。n 對于代碼序列中可以做什么并沒有強(qiáng)加的限制這里的代碼通常是和分析器一起進(jìn)行編譯的可以用于打印消息，停止分析活動，或者是處理編譯器的數(shù)據(jù)結(jié)構(gòu)4語義值（Semantic Value）1. . .n每個符號都對應(yīng)一個（或多個）語義值。n 在自底向上分析中，X1. . .Xn的語義值是已知的，這樣語義動作會為A計(jì)算一個語義值。n 在自頂向下分析中，A的值是已知的，而在該產(chǎn)生式被應(yīng)用之后

3、才能夠知道X1. . .Xn的值。n 終結(jié)符號的語義值通過詞法得到。n 非終結(jié)符號的語義值通過產(chǎn)生式對應(yīng)的語義動作來計(jì)算。ttribute)5n 繼承屬性(InheritedAttribute)n 在分析樹中，一個結(jié)點(diǎn)的綜合屬性值是從其子結(jié)點(diǎn)的屬性值計(jì)算出來的；而一個結(jié)點(diǎn)的繼承屬性值是由該結(jié)點(diǎn)兄弟結(jié)點(diǎn)和父結(jié)點(diǎn)的屬性值計(jì)算出來的。語義翻譯的實(shí)現(xiàn)緊跟著語法分析的進(jìn)展n 每識別出一個語法結(jié)構(gòu)，就會對它的語義進(jìn)行分析和翻譯。6綜合屬性示例 （表達(dá)式文法）語法繼承屬性示例A xA | x語法語義值計(jì)算符號串中每個 x 的位置8."AX1X2Xn ÎP都有與之相關(guān)聯(lián)的若干個屬性定義規(guī)則

4、，屬性定義規(guī)則一般形式為= f(c1, c2f是一個函數(shù)，而且k)1c是A的一個屬性并且c1, c2, , ck是A的繼承屬性或是某個Xi的屬性，稱c為A的綜合屬性?；?c是某個符號Xi的屬性并且c1, c2, , ck是A或Xj的屬性，稱c為Xi的一個繼承屬性。在兩種情況下，都說屬性 c 依賴于屬性 c1, , ck。Ø屬性定義規(guī)則也可以是過程（void型函數(shù)）調(diào)用，此時稱為A的虛綜合屬性。9臺式計(jì)算器屬性文法定義10產(chǎn)生式屬性定義規(guī)則L®Enprint (E.val)E ®E1+TE.val := E1.val + T.valE ®TE.val :=

5、 T.valF ®(E)F.val := E.valF ®integerF.val := integer.lexval 3*5+4n的計(jì)算過程T×val:=15T×val:=3*分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成11digit×lexval:=5F×val:=3LE×val:=19digit×lexval:=3F×val:=5F×val:=4i i ×l xl =4T×val:=4E×val:=15+n帶有繼承屬性 .的屬性文法定義12產(chǎn)生式屬性定義規(guī)則D&#

6、174;TLL.in:=T ®intT.type :=integerT ®realT.type :=realL ®L1, idL1.in :=L.in EnterID(, L.in)L ®idEnterID (, L.in)real id1, id2, id3的計(jì)算過程DTLin 564 typereal,in 7id3 3 nameL8in 9L10,id22 name 屬性編號代表計(jì)算順序。(編號6/8/10對應(yīng)動作EnterID) 順序并不唯一。id1131 name屬性求值n 有向邊：若結(jié)點(diǎn)m表示的屬性值依賴于結(jié)點(diǎn)n的

7、屬性值，則有從n到m的有向邊。n 若依賴圖中無環(huán)，則存在一個拓?fù)渑判?，它就是屬性值的?jì)算順序。14抽象語法樹 （Abstract Syntax Tree) 產(chǎn)生式 S if B then S1 else S2 的語法樹if-then-else |BS1S2 賦值語句的語法樹assignmentvariableexpression在語法樹中，運(yùn)算符號和關(guān)鍵字都不在葉結(jié)點(diǎn)，而是在內(nèi)部結(jié)點(diǎn)中出現(xiàn)。15具體語法樹 vs. 抽象語法樹具體語法樹 （分析樹）16.v抽象語法樹具體語法樹抽象語法樹（AST）建立表達(dá)式的語法樹的屬性文法建立表達(dá)式的語法樹使用的函數(shù):1. mknode (op, left, r

8、ight) 建立一個運(yùn)算符號結(jié)點(diǎn), 標(biāo)號是op, 兩個域left和right指向運(yùn)算分量結(jié)點(diǎn)的指針。2. mkleaf (id, name) 建立一個標(biāo)識符結(jié)點(diǎn), 由標(biāo)號id標(biāo)識, 一個域entry指向標(biāo)識符符號表中相應(yīng)的項(xiàng)。3. mkleaf (num, val) 建立一個常數(shù)結(jié)點(diǎn), 標(biāo)號為num, 域val用于存放常數(shù)的值。上述函數(shù)都會返回新建立結(jié)點(diǎn)的指針。18例：a-4+c的語法樹idto entrycidto entry a19num4+建立語法樹的屬性文法定義產(chǎn)生式語義規(guī)則E ® E1+T E ® E1-TE ® T T ® (E)T 

9、4; idT ® numE.nptr:=mknode('+',E1.nptr,T.nptr) E.nptr:=mknode('-',E1.nptr,T.nptr) E.nptr:=T.nptrT.nptr:=E.nptrT.nptr:=mkleaf(id,) T.nptr:=mkleaf(num,num.val)20例：a-4+c的語法樹的構(gòu)造過程idto entrycidto entry a21+num4例：+*dabc22表達(dá)式 a *-c)+(b-c)*d 的DAGS-屬性文法中使用一個附加的域來存放 合屬性析棧statevalto

10、p23.ZZ.z.YY.y綜合屬性的計(jì)算"A®ab := f(c1,c2,ck)b是A的綜合屬性, ci(1£ i£k)是a中符號的屬性。綜合屬性的值在自底向上的分析過程中，每步歸約時，計(jì)算相應(yīng)的屬性值。A®XYZA.a:=f(X.x, Y.y, Z.z)A.aX.xZ.z24stateval定義式 A.a:=f(X.x, Y.y, Z.z)（抽象）變成valnewtop:=f(valtop-2,valtop-1,valtop)（具體可執(zhí)行代碼）。在執(zhí)行代碼段之前執(zhí)行： newtop:=top-r+1top:=newtop;執(zhí)行代碼段后執(zhí)行：r

11、是句柄的長度.25top.statevaltopYY.yZZ.z.AA.a例：用26產(chǎn)生式代碼段L®EnE ®E+TE ®TT ®T*F T ®FF ®(E)F ®digitprintf (valnewtop) valnewtop:=valtop-2+valtopval newto:=val to -2 *val tovalnewtop:=valtop-127輸入stackval使用的產(chǎn)生式* +4n-*5+4n33*5+4nF3F®digit*5+4nT3T®F 5+4nT*3-+4nT*53-5+4n

12、T*F3-5F ®digit翻譯輸入 *所做的移動 翻譯輸入3*5+4n所做的移動（續(xù)）T® T*FE® T+4n+4n4nnn nT E E+E+4E+F E+T151515-15-415-415-4F ® digitT® F®+En19 -L® EnL1928L-屬性文法一個屬性文法是L-屬性文法, 如果"AX1X2XnÎP, 其每一個屬性定義規(guī)則中的每一個屬性或是一個綜合屬性，或是Xj (1£j £ n)的一個繼承屬性， 并且這個繼承屬性僅依賴于1. 產(chǎn)生式中Xj的左邊符號X1，

13、X2，Xj-1的屬性; 和2. A的繼承屬性。29 每一個S-屬性文法都是L-屬性文法。 L-屬性定義可用于按深度優(yōu)先順序來計(jì)算。非L-屬性文法的例子上表的屬性文法定義不是L-屬性文法。文法符號Q的繼承屬性依賴于它右邊文法符號R的屬性。30產(chǎn)生式屬性定義規(guī)則A®LML.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s).i:=r(A.i)A ®.i:=q(R.s)A.s:=f(Q.s).對屬性文法的擴(kuò)充一種便于譯模式翻譯的形式。n 把其中的屬性定義規(guī)則改為計(jì)算屬性值的規(guī)則（或稱語義動作）用花括號 括起來，它們可入到產(chǎn)生式右部的任何合適的位置上。n 這是一種語法分

14、析和語義動作交錯的表示法，它表達(dá)在按深度優(yōu)先遍歷分析樹的過程中何時執(zhí)行語義動作。n 翻譯模式給出了使用語義規(guī)則進(jìn)行計(jì)算的順序。可看成是分析過程中翻譯的注釋。n 原來的不含語義動作的文法稱作是基礎(chǔ)文法。31例：一個簡單的翻譯模式(只包含+/-操作的表達(dá)式)ETRRaddop T print(addop.lexeme) R1|Tnum print(num.val)把語義動作看成終結(jié)符號，輸入9-5+2, 其分析樹見下頁，當(dāng)按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問的語義動作，將輸出9 5 - 2 +它是輸入表達(dá)式9-5+2的后綴式。32 9-5+2的帶語義動作的分析樹 ERT-R9RT+Te5233Pt(&

15、#180;2´)Pt(´5´)Pt(´+´)Pt(´-´)Pt(´9´)翻譯模式的設(shè)計(jì)需要保證語義動作性值。分情況考慮：還沒有計(jì)算的屬1. 只需要綜合屬性的情況：n 為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應(yīng)的產(chǎn)生式右邊的末尾。例如：T®T1*F 所需動作: T.val:=T1.val * F.valT®T1*F T.val:=T1.val * F.val 34翻譯模式的設(shè)計(jì)2.既有綜合屬性又有繼承屬性：n 產(chǎn)生式右邊的符號的繼承屬性必須在這個符號以前的動作中計(jì)算出來

16、。n 一個動作不能性。這個動作右邊符號的綜合屬n 產(chǎn)生式左邊非終結(jié)符號的綜合屬性只有在它所的所有屬性都計(jì)算出來以后才能計(jì)算。計(jì)算這種屬性的動作通?？煞旁诋a(chǎn)生式右端的末尾。35不正確的翻譯模式36可以改成如下的形式：S ® A1.in:=1 A1 A2.in:=2 A2A ®a print(A.in) 下面的翻譯模式不滿足要求：S ®A1A2 A1.in:=1;A2.in:=2A ®a print(A.in) 如何構(gòu)造語義動作集合？造合適的語義動作集合要深入理解在給定分析技術(shù)（自頂向下或自底向上）中推導(dǎo)的過程。要想書寫清晰而簡潔的語義動作，通常需要對文法進(jìn)

17、行重新構(gòu)造，以幫助在合適的地方來計(jì)算語義值。在最初獲得了適合自頂向下或自底向上分析的文法之后，往往在編譯器構(gòu)造的這個階段還是會對文法進(jìn)行修改以提供對語義動作的支持。37.自頂向下的翻譯n 首先要從翻譯模式中消除左遞歸n 對于一個翻譯模式，若采用自頂向下分析， 必須消除左遞歸和提取左公因子，在改寫基礎(chǔ)文法時考慮屬性值的計(jì)算38左遞歸文法翻譯模式的轉(zhuǎn)換例把帶左遞歸的文法的翻譯模式轉(zhuǎn)換成不帶左遞歸的文法的翻譯模式。39E ® E1+T E.val := E1.val + T.val E ® E1-T E.val := E1.val - T.val E ® T E.val

18、 := T.val T ® (E) T.val := E.val T ® num T.val := num.val帶左遞歸的文法的翻譯模式 經(jīng)過轉(zhuǎn)換的不帶有左遞歸文法的翻譯模式40ET R.i := T.val R E.val := R.s R+T R1.i := R.i +T.val R1= R1.s R-T1.i := R.i - T.val R1 R.s := R1.s R R.s := R.i T (E) T.val := E.val Tnum T.val := num.val E ×val=6R ×i=9 ; R ×s= 6T

19、5;val=9R ×i=4;R ×s= 6T ×val=59T ×val=2R × i=6;+5R ×s= 6 表達(dá)式9-5+2的計(jì)算 2e41左遞歸翻譯模式的一般化及消除左遞歸的翻譯模式左遞歸翻譯模式AXRRY R.i := f (X.x) A.a := R.s AA1Y A.a := g (A1.a, Y.y) R1.i :=R.i, Y.yAX A.a := f (X.x) R1 R.s := R1.s R R.s := R.i n 假設(shè)每一個文法符號都有一個綜合屬性， 用相應(yīng)的小寫字母表示，g 和 f 是任意函數(shù)n 經(jīng)過轉(zhuǎn)換的

20、翻譯模式中使用了R的繼承屬性 i和綜合屬性 s。42Y2Y1X43含左遞歸的文法A.a = f X.xA.a = g ( f (X.x), Y1.y)A.a = g ( g ( f (X.x),Y1 .y),Y2 .y)輸入：XY1Y2XY1 R2.s := R3.s Y2 不含左遞歸的文法44R3.s := R3.iR3.i = g ( g ( f(X ×x),Y1×y),Y2 ×y)R2.i = g ( f(X.x),Y1.y)R1.s := R2.sR1.i = f (X.x)A.a := R1.sA例：45建立表達(dá)式語法樹的翻譯模式：E®E1+T

21、E.nptr := mknode(´+´, E1.nptr, T.nptr) E®E1-TE.nptr := mknode(´-´, E1.nptr, T.nptr)E®TE.nptr :=T.nptr從翻譯模式中消除左遞歸，變成下面的翻譯模式。消除左遞歸之后的翻譯模式：46E TR.i := T.nptrRE.nptr := R.s R +TR1.= mknode ' ',. , T.nptr) R1 R.s := R1 .sR -TR1 .i := mknode ('-', R.i, T.nptr)

22、 R1 R .s := R1 .sR R .s := R .iT (E)T.nptr := E.nptrT idT.nptr := mkleaf id, T num T.nptr := mkleaf (num, num.val)使用繼承屬性構(gòu)造語法樹EnptrTidRTiRnptr-nptr+TiRsnumididto entry for cidto entry for a47num4-+a- 4+c翻譯器的設(shè)計(jì)算法:語導(dǎo)翻譯器的建立輸入：一個基礎(chǔ)文法是 LL(1) 文法的翻譯模式。輸出：一個語導(dǎo)翻譯器的代碼。方法：在分析器中加入語義動作代碼。（1）"AÎVN

23、, 建立一個可遞歸調(diào)用的函數(shù)A。為A的每一個繼承屬性都設(shè)置一個形式參數(shù)，函數(shù)的返回值是A的綜合屬性值。為A產(chǎn)生式涉及的每個屬性值設(shè)一個局部變量。（2）函數(shù)A的代碼要根據(jù)當(dāng)前的輸入符號來決定使用哪一個產(chǎn)生式。48（3） 與每一個產(chǎn)生式有關(guān)的代碼，從左到右根椐產(chǎn)生式右部是單詞符號、非終結(jié)符號還是語義動作， 分別是：（a）對于帶有綜合屬性x的單詞符號X，x存放在相應(yīng)的局部變量中。編寫一個match(X)。（b）對于BÎVN，編寫一個賦值語句c := B (b1, b2, ，bk)其中， b1, b2, ，bk是B的繼承屬性，c是存放B的綜合屬性值的局部變量。（c）對于每個動作，把動作的代碼

24、抄進(jìn)翻譯器中，用存放屬性值的變量來代替對屬性值的每一次。（d）編寫返回A綜合屬性值的語句。9自頂向下的翻譯器代碼示例例：構(gòu)造簡單表達(dá)式語法樹的翻譯模式RaddopTR1.i := mknode (addop.lexeme,R.irR1RR.s := R1.sR.s := R.i50翻譯程序:相應(yīng)的syntax-tree-node* Rsntax-tree-node* Ri )syntax-tree-node*Tnptr, *R1i, *R1s, *Rs;char addoplexeme;if(lookahead = addop)/*產(chǎn)生式Raddop T R*/addoplexeme = le

25、xval; match (addop);Tnptr = T();/* T 是一個函數(shù) */R1i = mknode addo R1s = R (R1i);Rs = R1s ;lexemeRirelse Rs = Ri; /*產(chǎn)生式R®e*/ return (Rs);51RaddopT R1.i := mknode (addop.lexeme, R.i, T.nptr) R1 R.s := R1.sR R.s := R.i例：表達(dá)式文法的翻譯器(生成AST)52含左遞歸的翻譯模式：EE1+T E.nptr := mknode (+, E1.nptr, T.nptr)ETE.nptr :

26、= T.nptr TT1*F T.nptr := mknode (*, T1.nptr, F.nptr)TF T.nptr := F.nptr F(E) F.nptr := E.nptr Fid F.nptr := mkleaf (ID, ) Fnum F.nptr := mkleaf (NUM, num.val)轉(zhuǎn)換：不含左遞歸的翻譯模式53ET R.i := T. nptr R E.nptr := R.sR +T R1.i := mknode (+, R.i, T.nptr) R1 R.s := R1.s R R.s := R.i T F P.i := F. nptr P T

27、. nptr :=P.sP *F1.i := mknode * P.i, F.nptr) P1 P.s := P1.s P P.s := P.i F(E) F. nptr := E.nptr Fid F.nptr := mkleaf (ID, ) Fnum F.nptr := mkleaf (NUM, num.val) 54typedef node structchar d;struct node *left,*right; BType;typedef BType* Pointer;Pointer FE( )Pointer R_i, T_nptr, E_nptr, R_s; T_

28、nptr = FT( );R_i = T_nptr;R_s = FR(R_i); E_nptr = R_s;return E_nptr;翻譯程序ETR.i := T. n trR E.nptr := R.sRTR1 R1.i := mknode (, R.i, T.nptr) = R1.s R R.s := R.i 55Pointer FR(Pointer R_i)Pointer R1_i,T_nptr,R_s,R1_s; if(lookahead = )match();T_nptr = FT( );R1_i = mknode(R_i, T_nptr);R1_s = FR(R1_i);R_s

29、= R1_s; return R_s;elseR_s = R_i; return R_s;56F(E) F. nptr := E.nptr Fid F.nptr := mkleaf (ID, ) Pointer FF( )Fnum F.nptr := mkleaf (NUM, num.val)Pointer F_nptr,E_nptr; int num_val,id_name; if(lookahead=()match(); E_nptr = FE( ); match(); F_nptr = E_nptr;return F_nptr;else if(lookahead=id)id

30、_name = lex_val; match(id); F_nptr = mkleaf (ID,id_name); return F_n trelse if(lookahead=num)num_val = lex_val; match(num); F_nptr = mkleaf (NUM,num_val); return F_nptr;else error(“(, id or num expected !”);.自底向上翻譯了便于翻譯程序的設(shè)計(jì)底向上翻譯通常要求動作都放在產(chǎn)生式之后，以便在用該產(chǎn)生式歸約時執(zhí)行這些動作。對于翻譯模式中嵌入在產(chǎn)生式中間的動作，應(yīng)當(dāng)通過等價變換把它們移到產(chǎn)生式之后。

31、符和產(chǎn)生式這樣簡單的方法來實(shí)現(xiàn)。57例1：算術(shù)表達(dá)式58算術(shù)表達(dá)式后綴式翻譯模式的等價變換LEnETRRTMR1|M print(+) TFPP*FNP1|Nprint(*) F(E)Fnum print( num.val) LEnETRRT print(+) R1 | TFPP*F print(*) P1 | F(E)Fnum print( num.val) 例 2： SFOR i :=E1 TO E2 DO S1 FOR語句的中間代碼形式：59E1.code （表達(dá)式E1的中間代碼）i. place := E1.place;E2.code （表達(dá)式E2的中間代碼）loop:if i.pla

32、ce > E2.place goto out;S1.code （語句S1的中間代碼）i. place := Succ(i.place); （計(jì)算i的后繼）goto loop;例2：語句的翻譯模式SFOR i :=E1 TO E2 DO S1SFOR i :=E1 Gen(i.place, := , E1.place) TOE2 loop :=nextstmt;Gen(if, i.place, >, E2.place, goto) DO S1 backpatch(S1.nextlist, nextstmt);Gen (i.place, :=, Succ(i.place); S.nextlist:=loop;Gen (goto, loop)60 nextstmt的值是將要產(chǎn)生的中間代碼語句的地址； 函數(shù)Gen的功能是產(chǎn)生相應(yīng)的中間代碼語句，如調(diào)用Gen(i.place,:=, E1.place)能夠產(chǎn)生語句i.place:= E