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

2、是L-attributed。,編譯原理,4,SDD vs. SDT,語義規(guī)則 語義動作,E E1 + T E.val := E1 .val + T.val ,編譯原理,5,SDD vs. SDT,語義規(guī)則 語義動作,E E1 + T print(+); ,編譯原理,6,5.4.1 后綴SDT,自底向上分析S屬性文法。 A X Y Z語義動作,編譯原理,7,編譯原理,8,5.4.2后綴SDT的語法分析實現(xiàn),A X Y Z,X Y Z,X.x Y.y Z.z,top,文法符號,綜合屬性,編譯原理,9,例5.15 顯式操作語法分析棧,編譯原理,10,3*5 n的分析計算過程,digit,3,top,

3、編譯原理,11,3*5 n的分析計算過程,F,3,top,編譯原理,12,3*5 n的分析計算過程,T,3,*,digit,5,top,編譯原理,13,3*5 n的分析計算過程,T,3,*,F,5,top,編譯原理,14,3*5 n的分析計算過程,T,15,top,編譯原理,15,3*5 n的分析計算過程,E,15,top,編譯原理,16,3*5 n的分析計算過程,E,15,n,top,編譯原理,17,3*5 n的分析計算過程,L,15,top,編譯原理,18,5.4.3 產(chǎn)生式內(nèi)部帶語義動作的SDT,B X a Y LR：歸約出X之后立即執(zhí)行動作a LL：試圖展開Y之前執(zhí)行動作a,編譯原理,

4、19,例，中綴到后綴轉(zhuǎn)換的SDD,編譯原理,20,例，中綴到后綴轉(zhuǎn)換的SDT,L E n E E1+ T print(+) E T T T1* F print(*) T F F (E) F digit print(digit.lexval),編譯原理,21,例5.16 翻譯為前綴表達式,L E n E print(+) E1+ T E T T print(*) T1* F T F F (E) F digit print(digit.lexval),Not all SDTs can be implemented during parsing: Not a LR Grammar ?,編譯原理,22

5、,嵌入動作的分析樹：3*5+4,編譯原理,23,5.4.4 從SDT中刪除左遞歸,例5.17 帶左遞歸的文法的翻譯模式。 E E1 + T print(+); E T 轉(zhuǎn)換為： E TR R + print(+); R R ,編譯原理,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.

6、a, Y.y) A X A.a := f (X.x) ,編譯原理,26,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 ,編譯原理,27,5.4.5 L屬性定義的SDT,確定語義動作的執(zhí)行時機 如何將語義動作嵌入產(chǎn)生式右部的適當位置？,編譯原理,28,1. 只有綜合屬性的情況：將計算綜合屬性的語義規(guī)則作為產(chǎn)生式右邊末尾的動作。例如：,原則：,產(chǎn)生式 語義規(guī)則 T T1 * F T.val := T1.val * F.val,產(chǎn)生式 語義動作 T T1 * F T.val :

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

8、)。,編譯原理,31,E,1,.val,上圖可以用命令：E sub 1.val 描述。,例5.18數(shù)學排版語言的翻譯模式片斷。,a,i,上圖可以用命令：a sub i sub j 描述。,j,編譯原理,32,例5.18數(shù)學排版語言的翻譯模式。,綜合屬性： ht ：描述height dp ：描述depth 繼承屬性ps：point size，設定字體大小。 Assume ps = 10。 下標的大小按比例縮小，位置下降。,編譯原理,33,圖5-25 盒子的大小和高度的語法制導定義,編譯原理,34,S B BB B sub B B sub 1 E sub 1,E,1,B1.ht,max(B1.ht

9、, 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 B B B1B2 B B1 sub B2 B (B) | text,結(jié)合性：右結(jié)合 優(yōu)先級：sub高于并置,S B B T B1 | T T F sub T1 | F F (B) | tex

10、t,編譯原理,37,例5.19,S while (C) S1,C.code S1.code goto L1 .,C.true:,C.false:,to C.true,to C.false,while語句,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 | C.code | label | L2 | S1.code,S while ( L1 = newlabel();

11、L2 = newlabel(); C.false = S.next;C.true = L2; C) S1.next = L1; S1 S.code = label | L1 | C.code | label | L2 | S1.code ,編譯原理,39,5.5 實現(xiàn)L屬性定義的翻譯,建立注釋語法分析樹 構(gòu)造語法分析樹，加入動作，按照前序順序執(zhí)行 使用遞歸下降的語法分析器，在預測分析的過程中實現(xiàn)L屬性定義。,編譯原理,40,例5.20,編譯原理,41,例5.22,編譯原理,42,編譯原理,43,5.5.1 從翻譯模式中消除左遞歸,例5.14 帶左遞歸的文法的翻譯模式。 S-屬性定義 E E1

12、+ T E.val := E1.val + T.val E E1 - T E.val := E1.val - T.val E T E.val := T.val T (E) T.val := E.val T num T.val := num.val,編譯原理,44,經(jīng)過轉(zhuǎn)換的帶有右遞歸文法的翻譯模式,E T R.i := T.val R E.val := R.s R + T R1.i := R.i + T.val R1 R.s := R1.s R R.s := R.i T ( E ) T.val := E.val T num T.val := num.val,編譯原理,45,表達式9-5+2的計

13、算,編譯原理,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.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,+,-,id to ent

14、ry for a,num 4,id to entry for c,圖5.29 使用繼承屬性構(gòu)造 a - 4 + c 的語法樹,id,i R s,T nptr,+,i R s,num,T nptr,-,i R s,E.nptr,T nptr,id,編譯原理,48,5.5.2 預測翻譯器的設計算法5.1 預測語法制導翻譯器的構(gòu)造,輸入: 語法制導翻譯模式, 其基礎文法適于預測分析 輸出: 語法制導翻譯器 方法: 修改預測分析器的結(jié)構(gòu)。 1. 為每個非終結(jié)符號A構(gòu)造一個函數(shù)， A的每個繼承屬性對應函數(shù)的一個參數(shù)， A的綜合屬性對應函數(shù)的返回值(假定A只有一個綜合屬性)，并為出現(xiàn)在A的產(chǎn)生式中的文法符

15、號的每個屬性定義一個局部變量； 2. A函數(shù)的代碼根據(jù)當前的輸入決定使用哪一個產(chǎn)生式；,編譯原理,49,3. 與每個產(chǎn)生式有關的代碼如下： 1) 對于帶有綜合屬性x的單詞符號X，把x的值保存在為X.x聲明的變量中，產(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)造,編譯原理,50,例5.16,圖5.28中的文法是LL(1)文法，適于自頂向下的分析。

16、 從文法中非終結(jié)符號的屬性，可以得到函數(shù)E，R和T的參數(shù)和返回值的類型。由于E和T沒有繼承屬性，所以它們不含有參數(shù)。,編譯原理,51,把兩個R產(chǎn)生式結(jié)合起來, 新的產(chǎn)生式用符號addop 代表+和-： R addop T R1.i = mknode(addop.lexeme, R.i, T.nptr) R1 R.s = R1.s R R.s = R.i,編譯原理,52,R的翻譯器代碼基于產(chǎn)生式 R addop T R |的語法分析過程：,編譯原理,53,編譯原理,54,5.5.4 L屬性的自底向上,S-屬性的自底向上計算 綜合屬性在歸約時執(zhí)行計算動作 L-屬性的自底向上計算 語義動作不在最右內(nèi)

17、嵌的語義動作 繼承屬性的計算關鍵問題 解決方法引入標記,編譯原理,55,刪除嵌入在翻譯模式中的動作,語義動作如何執(zhí)行 希望在歸約時執(zhí)行 所有的動作都出現(xiàn)在產(chǎn)生式的末尾 可以采用在翻譯模式中插入標記非終結(jié)符號的方法。,A B.i = f(A.i) B C 改寫為： A M B C M M.i = A.i; M.s = f(M.i),編譯原理,56,例：引入標記非終結(jié)符號M,N，改寫翻譯模式：,E T RR + T M R | - T N R | T numprint(num.val) M print(+) N print(-) ,E T R R + T print(+) R1 | - T print(-) R1 | T num print(num.val),編譯原理,57,分析棧中的繼承屬性,繼承屬性的值無非有兩種來源 一開始就存在 來自綜合屬性，經(jīng)過復制 來自綜合屬性，經(jīng)過計算,編譯原理,58,D T type in L int in L , x in L , q p 圖5.32 在每一個L結(jié)點L.in = T.type,繼承屬性來自綜合屬性，其值由復寫規(guī)則決定，且繼承屬性的位置固定的情形。,編譯原理,59,翻譯模式,D T L.in := T.type L T int T.t