第五章語法制導翻譯(2)

1、1第五章第五章 語法制導翻譯語法制導翻譯5.4 5.5編譯原理25.4 語法制導的翻譯模式語法制導的翻譯模式(Translation Scheme)q語法制導翻譯（SDT）是SDD的實現(xiàn)。q語法制導翻譯模式（SDT）是拓廣的CFG， 在文法中嵌入語義動作，語義動作寫在花括號“”里，可以出現(xiàn)在產(chǎn)生式右部適當位置。q當歸約出產(chǎn)生式右部的某個非終結(jié)符號后，就執(zhí)行緊接在該非終結(jié)符號右邊的語義動作。編譯原理3q任何SDT可以通過先建立語法分析樹，然后前序遍歷執(zhí)行語義動作。q但是，我們希望SDT能夠在語法分析的同時進行，無需構(gòu)造好分析樹。這里討論兩類：基礎文法是LR，SDD是S-attributed；基礎

2、文法是LL，SDD是L-attributed。編譯原理4SDD vs. SDTq語義規(guī)則q語義動作產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 E E1 + T E.val := E1 .val + T.val E E1 + T E.val := E1 .val + T.val 編譯原理5SDD vs. SDTq語義規(guī)則q語義動作產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 E E1 + T E.code := E1 . code | T. code | + E E1 + T print(+); 編譯原理65.4.1 后綴后綴SDTq自底向上分析S屬性文法。A X Y Z語義動作編譯原理7 L E n

3、 print (E.val); E E1 + T E.val := E1 .val + T.val; E T E.val := T.val; T T1 * F T.val := T1.val F.val ; T F T.val := F.val; F (E) F.val := E.val; F digit F.val := digit.lexval; 編譯原理85.4.2后綴后綴SDT的語法分析實現(xiàn)的語法分析實現(xiàn)qA X Y ZX Y Z X.x Y.y Z.ztop文法符號綜合屬性編譯原理9 例例5.15 顯式操作語法分析棧顯式操作語法分析棧 L E n print (stacktop-1.

4、val); top = top -1; E E1 + T stacktop-2.val = stacktop-2 .val + stacktop.val; top = top -2; E T T T1 * F stacktop-2.val = stacktop-2 .val stacktop.val; top = top -2; T F F (E) stacktop-2.val = stacktop-1 .val ； top = top -2; F digit 編譯原理103*5 n的分析計算過程的分析計算過程digit3top編譯原理113*5 n的分析計算過程的分析計算過程F3top編譯原

5、理123*5 n的分析計算過程的分析計算過程T3* digit5top編譯原理133*5 n的分析計算過程的分析計算過程T3* F5top編譯原理143*5 n的分析計算過程的分析計算過程T15 top編譯原理153*5 n的分析計算過程的分析計算過程E15 top編譯原理163*5 n的分析計算過程的分析計算過程E15n top編譯原理173*5 n的分析計算過程的分析計算過程L15 top編譯原理185.4.3 產(chǎn)生式內(nèi)部帶語義動作的產(chǎn)生式內(nèi)部帶語義動作的SDTqB X a Y LR：歸約出X之后立即執(zhí)行動作aLL：試圖展開Y之前執(zhí)行動作a編譯原理19例，中綴到后綴轉(zhuǎn)換的例，中綴到后綴轉(zhuǎn)換

6、的SDD Production Semantic Ruleexpr expr1 + term expr.t := expr1.t | term.t | +expr expr1 term expr.t := expr1.t | term.t | -expr term expr.t := term.tterm 0 term.t := 0term 1 term.t := 1. .term 9 term.t := 9編譯原理20 例，中綴到后綴轉(zhuǎn)換的例，中綴到后綴轉(zhuǎn)換的SDTL E nE E1+ T print(+) E TT T1* F print(*) T FF (E)F digit print(

7、digit.lexval)編譯原理21 例例5.16 翻譯為翻譯為前綴前綴表達式表達式L E nE print(+) E1+ TE TT print(*) T1* FT FF (E)F digit print(digit.lexval)Not all SDTs can be implemented during parsing:Not a LR Grammar?編譯原理22嵌入動作的分析樹：嵌入動作的分析樹：3*5+4編譯原理235.4.4 從從SDT中刪除左遞歸中刪除左遞歸q例5.17 帶左遞歸的文法的翻譯模式。E E1 + T print(+); E T轉(zhuǎn)換為：E TRR + print(

8、+); RR 編譯原理24 A A1Y A.a := g (A1.a, Y.y) A X A.a := f (X.x) 消除左遞歸后：A X R.i := f (X.x) R A.a := R.s R Y R1.i := g (R.i, Y.y) R1 R.s := R1.s R R.s := R.i 例：一個一般化的例子例：一個一般化的例子編譯原理25 A A1Y A.a := g (A1.a, Y.y) A X A.a := f (X.x) Y1XY2AAA.a = g ( g ( f (X.x), Y1.y), Y2.y).a = g ( f (X.x), Y1.y).a = f (X.

9、x).y.y.x編譯原理26A X R.i := f (X.x) R A.a := R.s R Y R1.i := g (R.i, Y.y) R1 R.s := R1.s R R.s := R.i AXRY1RY2R.i=g ( g ( f (X.x), Y1.y), Y2.y).i = g ( f (X.x), Y1.y) .y.i = f (X.x).y.xa sss編譯原理275.4.5 L屬性定義的屬性定義的SDTq確定語義動作的執(zhí)行時機q如何將語義動作嵌入產(chǎn)生式右部的適當位置？編譯原理281. 只有綜合屬性綜合屬性的情況：將計算綜合屬性的語義規(guī)則作為產(chǎn)生式右邊末尾的動作。例如：原則：

10、原則： 產(chǎn)生式 語義規(guī)則 T T1 * F T.val := T1.val * F.val 產(chǎn)生式 語義動作 T T1 * F T.val := T1.val * F.val編譯原理292. 同時存在綜合屬性和繼承屬性，建立翻譯模式的必要條件：產(chǎn)生式右部符號的繼承屬性必須在這個符號以前的動作中計算出來；一個動作不能引用該動作右邊符號的綜合屬性；產(chǎn)生式左邊非終結(jié)符號的綜合屬性只有在它所引用的所有屬性都計算出來以后才能計算。計算這種屬性的動作通?？梢苑旁诋a(chǎn)生式右端的末尾。編譯原理30例：例：翻譯模式 S A1A2 A1.in := 1; A2.in := 2 A a print(A.in)不符合條

11、件(1)。 若改寫成 S A1.in := 1; A2.in := 2 A1A2 A a print(A.in)則就符合條件(1)。編譯原理31E1.val上圖可以用命令：E sub 1.val 描述。例5.18數(shù)學排版語言的翻譯模式片斷。數(shù)學排版語言的翻譯模式片斷。ai上圖可以用命令：a sub i sub j 描述。j編譯原理32例5.18數(shù)學排版語言的翻譯模式。數(shù)學排版語言的翻譯模式。q綜合屬性：ht ：描述heightdp ：描述depthq 繼承屬性ps：point size，設定字體大小。 Assume ps = 10。 下標的大小按比例縮小，位置下降。編譯原理33圖圖5-25 盒

12、子的大小和高度的語法制導定義盒子的大小和高度的語法制導定義編譯原理34S B BB B sub B B sub 1 E sub 1E1B1.htmax(B1.ht, B2.ht 0.25 * B.ps )E sub 1的推導過程的推導過程(忽略二義性問題)max(B1.dp, B2.dp + 0.25 * B.ps) 非終結(jié)符號 B (表示Box)代表一個公式。 產(chǎn)生式 B B1B2 代表兩個方框的并置。 B B1 sub B2 代表一個布局，其中 B2 是比 B1 小一號的方框， B2 是 B1 的下標。編譯原理35翻譯模式翻譯模式編譯原理36如何消除二義性如何消除二義性?S BB B1B2

13、B B1 sub B2B (B) | text結(jié)合性：右結(jié)合優(yōu)先級：sub高于并置S BB T B1 | TT F sub T1 | FF (B) | text編譯原理37例例5.19 qS while (C) S1C.codeS1.codegoto L1.C.true:C.false:to C.trueto C.falsewhile語句L1:L2:編譯原理38 產(chǎn)生式 語義規(guī)則S while (C) S1 L1 = newlabel();L2 = newlabel();S1.next = L1;C.false = S.next;C.true = L2; S.code = label | L1

14、 | C.code | label | L2 | S1.code S while ( L1 = newlabel(); L2 = newlabel(); C.false = S.next;C.true = L2;C) S1.next = L1;S1 S.code = label | L1 | C.code | label | L2 | S1.code 編譯原理395.5 實現(xiàn)實現(xiàn)L屬性定義的翻譯屬性定義的翻譯q建立注釋語法分析樹q構(gòu)造語法分析樹，加入動作，按照前序順序執(zhí)行q使用遞歸下降的語法分析器，在預測分析的過程中實現(xiàn)L屬性定義。編譯原理40例例5.20編譯原理41例例5.22編譯原理42編

15、譯原理435.5.1 從翻譯模式中消除左遞歸從翻譯模式中消除左遞歸例5.14 帶左遞歸的文法的翻譯模式。S-屬性定義E E1 + T E.val := E1.val + T.valE E1 - T E.val := E1.val - T.valE T E.val := T.valT (E) T.val := E.valT num T.val := num.val編譯原理44經(jīng)過轉(zhuǎn)換的帶有右遞歸文法的翻譯模式經(jīng)過轉(zhuǎn)換的帶有右遞歸文法的翻譯模式E T R.i := T.val R E.val := R.sR + T R1.i := R.i + T.val R1 R.s := R1.s R R.s

16、:= R.iT ( E ) T.val := E.valT num T.val := num.val編譯原理45表達式表達式9-5+2的計算的計算E valT.val=9num.val=9i = 9 R s-T.val=5num.val=5i = 4 R s+ +T.val=2i = 6 R snum.val=2編譯原理46例5.15 轉(zhuǎn)換后的構(gòu)造語法樹的翻譯模式E T R.i := T.nptr R E.nptr := R.s R + T R1.i := mknode(+, R.i, T.nptr) R1 R.s := R1.s R - T R1.i := mknode(-, R.i, T.

17、nptr) R1 R.s := R1.s R R.s := R.i T ( E ) T.nptr := E.nptr T id T.nptr :=mkleaf(id, id.entry) T num T.nptr :=mkleaf(num, num.val) 編譯原理47+-idto entry for anum 4idto entry for c圖圖5.29 使用繼承屬性構(gòu)造使用繼承屬性構(gòu)造 a - 4 + c 的語法樹的語法樹 idi R sT nptr+i R snumT nptr-i R sE.nptrT nptrid編譯原理485.5.2 預測翻譯器的設計預測翻譯器的設計算法算法5.

18、1 預測語法制導翻譯器的構(gòu)造預測語法制導翻譯器的構(gòu)造輸入輸入: 語法制導翻譯模式語法制導翻譯模式, 其基礎文法適于預測分析其基礎文法適于預測分析輸出輸出: 語法制導翻譯器語法制導翻譯器方法方法: 修改預測分析器的結(jié)構(gòu)。修改預測分析器的結(jié)構(gòu)。1. 為每個非終結(jié)符號A構(gòu)造一個函數(shù)， A的每個繼承屬性對應函數(shù)的一個參數(shù)， A的綜合屬性對應函數(shù)的返回值(假定A只有一個綜合屬性)，并為出現(xiàn)在A的產(chǎn)生式中的文法符號的每個屬性定義一個局部變量；2. A函數(shù)的代碼根據(jù)當前的輸入決定使用哪一個產(chǎn)生式；編譯原理493. 與每個產(chǎn)生式有關的代碼如下：1) 對于帶有綜合屬性x的單詞符號X，把x的值保存在為X.x聲明的

19、變量中，產(chǎn)生匹配X的調(diào)用，并繼續(xù)輸入；2) 對于非終結(jié)符號B，產(chǎn)生一個賦值語句c:=B(b1,b2,bk), b1,b2,bk 是代表B的繼承屬性的變量，c是代表B的綜合屬性的變量；3) 對于每個動作，將其代碼拷貝到分析器，把對屬性的引用改為對相應的局部變量的引用。算法算法5.1 預測語法制導翻譯器的構(gòu)造預測語法制導翻譯器的構(gòu)造編譯原理50例例5.16 q圖5.28中的文法是LL(1)文法，適于自頂向下的分析。q從文法中非終結(jié)符號的屬性，可以得到函數(shù)E，R和T的參數(shù)和返回值的類型。由于E和T沒有繼承屬性，所以它們不含有參數(shù)。 編譯原理51把兩個R產(chǎn)生式結(jié)合起來, 新的產(chǎn)生式用符號addop代表

20、+和-：R addopT R1.i = mknode(addop.lexeme, R.i, T.nptr) R1 R.s = R1.sR R.s = R.i編譯原理52R的翻譯器代碼基于的翻譯器代碼基于產(chǎn)生式產(chǎn)生式 R addop T R | 的語法分析過程：的語法分析過程：編譯原理53編譯原理545.5.4 L屬性的自底向上屬性的自底向上qS-屬性的自底向上計算綜合屬性在歸約時執(zhí)行計算動作qL-屬性的自底向上計算語義動作不在最右內(nèi)嵌的語義動作繼承屬性的計算關鍵問題解決方法引入標記標記編譯原理55刪除嵌入在翻譯模式中的動作刪除嵌入在翻譯模式中的動作q語義動作如何執(zhí)行希望在歸約時執(zhí)行所有的動作都

21、出現(xiàn)在產(chǎn)生式的末尾q可以采用在翻譯模式中插入標記非終結(jié)符號的方法。A B.i = f(A.i) B C改寫為：A M B CM M.i = A.i; M.s = f(M.i) 編譯原理56例：引入標記非終結(jié)符號例：引入標記非終結(jié)符號M,N，改寫翻譯模式：，改寫翻譯模式：E T RR + T M R | - T N R | T numprint(num.val) M print(+) N print(-) E T RR + T print(+) R1 | - T print(-) R1 | T num print(num.val)編譯原理57分析棧中的繼承屬性分析棧中的繼承屬性q繼承屬性的值無非

22、有兩種來源一開始就存在來自綜合屬性，經(jīng)過復制來自綜合屬性，經(jīng)過計算編譯原理58 DT type in Lint in L , x in L , q p 圖5.32 在每一個L結(jié)點L.in = T.type繼承屬性來自綜合屬性，其值由復寫規(guī)則決定，繼承屬性來自綜合屬性，其值由復寫規(guī)則決定，且繼承屬性的位置固定的情形。且繼承屬性的位置固定的情形。編譯原理59翻譯模式翻譯模式D T L.in := T.type L T int T.type = integerT realT.type = realL L1 .in := L.in L1 , id addtype(id.entry, L.in) L i

23、d addtype(id.entry, L.in) 復寫規(guī)則編譯原理60圖圖5.33 當當L的右邊符號被歸約時，的右邊符號被歸約時，T正好在其右邊的符號的正好在其右邊的符號的下面下面輸入 state 使用的產(chǎn)生式 real p, q, r p,q,r p,q,r ,q,r ,q,r q,r ,r ,r r - real T Tp TL TL, TL,q TL TL, TL,r TL D Treal Lid LL,id LL,id DTL 編譯原理61圖圖5.34 T.type的值在的值在L.in處被使用處被使用產(chǎn)生式 代碼段 D TL; T int T real L L,id L id Val

24、ntop := integer Valntop := real Addtype(valtop, valtop-3 Addtype(valtop, valtop-1 屬性T.type在棧中的位置相對于棧頂是事先知道的。因此，可以用棧中的屬性值T.type代替L.in。編譯原理62模擬繼承屬性的計算模擬繼承屬性的計算q這兩種情況如何處理？繼承屬性的存放位置不能事先預知繼承屬性需要通過計算得到編譯原理63一個不能預知屬性值在棧中所放位置的例子一個不能預知屬性值在棧中所放位置的例子考慮下面SDD： 產(chǎn)生式 語義規(guī)則 S aAC C.i := A.s S bABC C.i := A.s C c C.s

25、:= g(C.i)屬性C.i通過一個復寫規(guī)則來繼承屬性A.s 的值。 Sa A C s i Sb A B C s i編譯原理64一個不能預知屬性值在棧中所放位置的例子一個不能預知屬性值在棧中所放位置的例子考慮下面翻譯模式：S aA C.i := A.s C S bAB C.i := A.s C C c C.s := g(C.i)屬性C.i通過一個復寫規(guī)則來繼承屬性A.s 的值。 Sa A C s i Sb A B C s i編譯原理65通過標記非終結(jié)符通過標記非終結(jié)符M復寫屬性的值復寫屬性的值 產(chǎn)生式 語義規(guī)則 S aAC C.i := A.s S bABMC M.i :=A.s; C.i :

26、= M.s C c C.s := g(C.i) M M.s := M.i Sb A B C s i (a)原產(chǎn)生式 Sb A B M C s i s i (b) 依賴關系編譯原理66cAb_A.s.topcMBAa_M.sB.sA.s.top通過標記非終結(jié)符M復寫屬性的值，預知屬性值在棧中所放位置編譯原理67標記非終結(jié)符也可以用來模擬不是復寫規(guī)則的語標記非終結(jié)符也可以用來模擬不是復寫規(guī)則的語義規(guī)則義規(guī)則例如，例如，產(chǎn)生式語義規(guī)則 S a A C C.i := f(A.s)此時，決定C.i的規(guī)則不是復寫規(guī)則， C.i值尚未在val棧中形成。這個問題仍然可以使用標記非終結(jié)符號來解決：產(chǎn)生式語義規(guī)則

27、 S a A N C N.i := A.s; C.i := N.s N N.s := f(N.i)編譯原理68cSiCiNsAsacAaC.sA.s.topcNAaC.sN.sA.s.top編譯原理69例例5.19 使用三個標記非終結(jié)符使用三個標記非終結(jié)符所有繼承屬性都由復寫規(guī)則賦值。編譯原理70編譯原理71圖圖5.37 語法制導定義的實現(xiàn)語法制導定義的實現(xiàn)產(chǎn)生式 代碼段SKBK stackntop.ps = 10;BB1 L B2 stackntop.ht = max(stacktop-2.ht, stacktop.ht);stackntop.dp = max(stacktop-2.dp,

28、stacktop.dp);L stackntop.ps = stacktop-1.psBB1 sub M B2 stackntop.ht = max(stacktop-3.ht, stacktop.ht stacktop-4.ps * 0.25); stackntop.dp = max(stacktop-3.dp, stacktop.dp stacktop-4.dp * 0.25); M stackntop.ps = stacktop-2.ps * 0.70B ( N B1 ) stackntop.ht = stacktop-1.ht;stackntop.dp = stacktop-1.dp;

29、N stackntop.ps = stacktop-1.psBtext stackntop.ht = getHeight(stacktop-1.ps, stacktop.lexval);stackntop.dp = getDepth(stacktop-1.ps, stacktop.編譯原理72Esub1.val的分析樹的分析樹SKtext.val BMsubBtextE text1BBBL 編譯原理73Esub1.val的注釋分析樹的注釋分析樹SKtext.val BMsubBtextE text1BBBL s=10pspsipshth=E.hsps hth=1.hi編譯原理74Esub1.v

30、al的注釋分析樹的注釋分析樹SKtext.val BMsubBtextE text1BBBL s=10h=E.hhtishthtishththtpspspspspsh=1.hh=.val.h編譯原理75引進標記非終結(jié)符號對基礎文法的影響引進標記非終結(jié)符號對基礎文法的影響q基礎文法是LL(1)文法沒有影響，修改后的文法仍將保持LL(1)文法。因為每個標記非終結(jié)符號是唯一的，而且只有唯一一個的產(chǎn)生式q基礎文法是LR(1)文法q引入標記非終結(jié)符號可能使修改后的文法變成非LR(1)文法編譯原理76 例例5.16 翻譯為前綴表達式翻譯為前綴表達式L E nE print(+) E1+ TE TT print(*) T1