中科大2021－2022學(xué)年秋季第一學(xué)期《編譯原理與技術(shù)》第七講 語法制導(dǎo)翻譯

1、編譯原理與技術(shù)語法制導(dǎo)翻譯7/25/20221編譯原理與技術(shù)講義語法制導(dǎo)翻譯屬性文法S-屬性定義L-屬性定義語法制導(dǎo)定義與翻譯方案自底向上翻譯S-屬性定義自底向上計(jì)算自底向上計(jì)算繼承屬性自頂向下翻譯7/25/20222編譯原理與技術(shù)講義屬性文法屬性文法（Attributed Grammar）上下文無關(guān)文法+屬性+屬性計(jì)算規(guī)則 屬性用來描述文法符號的語義特征，如常量的“值”、變量的類型和存儲位置等。e.g. 二義性表達(dá)式文法G，非終結(jié)符E有屬性E.val（表達(dá)式的值）EE + E | E * E | ( E ) | number 屬性計(jì)算規(guī)則（語義規(guī)則）與產(chǎn)生式相關(guān)聯(lián)的反映文法符號屬性之間關(guān)系的

2、“規(guī)則”7/25/20223編譯原理與技術(shù)講義屬性文法語法制導(dǎo)定義（文法屬性語義規(guī)則）語義規(guī)則僅表明屬性間“抽象”關(guān)系，不涉及具體翻譯實(shí)現(xiàn)細(xì)節(jié)，如計(jì)算次序等。翻譯方案（文法屬性語義動作）語義規(guī)則即語義動作，可體現(xiàn)若干實(shí)現(xiàn)的細(xì)節(jié)。7/25/20224編譯原理與技術(shù)講義e.g.1算術(shù)表達(dá)式的計(jì)算器 產(chǎn)生式 語法制導(dǎo)定義EE1 + E2 E.val := E1.val + E2.valEE1 * E2 E.val := E1.val * E2.valE( E1 ) E.val := E1.valEnumber E.val := number.lex_val7/25/20225編譯原理與技術(shù)講義e.g

3、.1算術(shù)表達(dá)式的計(jì)算器 產(chǎn)生式 翻譯方案EE1 + E2 E.val := E1 .val + E2.val EE1 * E2 E.val := E1.val * E2.val E( E1 ) E.val := E1.val Enumber E.val := number.lex_val 7/25/20226編譯原理與技術(shù)講義屬性文法屬性的分類若產(chǎn)生式AX1X2Xn，與之相關(guān)的屬性計(jì)算規(guī)則b := f ( c1, c2, )如果屬性b是產(chǎn)生式左部符號A的屬性則稱其為A的綜合屬性；如果屬性b是產(chǎn)生式右部符號Xi的屬性則稱其為Xi的繼承屬性；c1, c2, 一般是產(chǎn)生式右部其它符號的(綜合)屬性或

4、A的繼承屬性； 固有屬性：終結(jié)符僅有的屬性。如number.lex_val。通常由詞法程序提供。7/25/20227編譯原理與技術(shù)講義A.bX1.c1X2.c2X綜合屬性A.b的計(jì)算A的繼承屬性AX1.c1X2.c2繼承屬性Xk.b的計(jì)算A的繼承屬性Xk.bX屬性依賴圖7/25/20228編譯原理與技術(shù)講義e.g. 2 屬性依賴圖:345E. val = 23E. val = 3+E. val = 20number. lex_val = 3E. val = 4E. val = 5number. lex_val = 4number. lex_val = 57/25/20229編譯原理與技術(shù)講義語

5、義規(guī)則的計(jì)算方法分析樹方法 為輸入串建立分析樹 由語義規(guī)則建立屬性依賴圖（沒有屬性循環(huán)依賴的） 對依賴圖進(jìn)行拓?fù)渑判颍玫綄傩杂?jì)算次序 依次計(jì)算屬性，得到“翻譯”結(jié)果基于規(guī)則的方法 構(gòu)造編譯器時，事先對產(chǎn)生式的語義規(guī)則進(jìn)行分析，得到屬性計(jì)算次序忽略規(guī)則的方法 屬性計(jì)算次序僅由分析方法限定。如S-屬性定義可以在自下而上分析時，在歸約前計(jì)算。如YACC中的語義動作。7/25/202210編譯原理與技術(shù)講義e.g. 3 屬性計(jì)算次序:345E. val = 23E. val = 3+E. val = 20number. lex_val = 3E. val = 4E. val = 5number. l

6、ex_val = 4number. lex_val = 5123456787/25/202211編譯原理與技術(shù)講義S-屬性定義語義規(guī)則僅包含綜合屬性計(jì)算（可以有固有屬性出現(xiàn)）。適合自底向上計(jì)算e.g. 語法樹語法樹與分析樹 語法樹可看作分析樹的濃縮。也稱抽象語法樹。而分析樹可看成具體語法樹。7/25/202212編譯原理與技術(shù)講義 S if B-expr then S1 else S2語法樹 分析樹語法樹 vs. 分析樹if-then-elseB-exprS1S2SifB-exprthenS1elseS27/25/202213編譯原理與技術(shù)講義 a := b* -c + b * -c 語法樹

7、分析樹語法樹 vs. 分析樹assigna+*bc*bcassignEEE+E*EbEEa賦值語句cE*EbEc算符7/25/202214編譯原理與技術(shù)講義DAG（去除了公共子表達(dá)式的無環(huán)有向圖）a := b* -c + b * -c語法樹 vs. DAGassigna+*bc*bcassigna+*bc語法樹DAG7/25/202215編譯原理與技術(shù)講義e.g.4 構(gòu)造表達(dá)式的語法樹（DAG）產(chǎn)生式 語義規(guī)則EE1 + E2 E.nptr := mknode(+,E1.nptr, E2.nptr)EE1 - E2 E.nptr := mknode(-,E1.nptr, E2.nptr)EE1

8、 * E2 E.nptr := mknode(*,E1.nptr, E2.nptr)EE1 / E2 E.nptr := mknode(/,E1.nptr, E2.nptr)E( E1 ) E.nptr := E1.nptrE - E1 E.nptr := mknode(,E1.nptr, )Enumber E.nptr := mkleaf(NUM,number.lex_val)Eid E.nptr := mkleaf(ID,id.entry)7/25/202216編譯原理與技術(shù)講義e.g.4 構(gòu)造表達(dá)式的語法樹（DAG）E.nptr E的語法樹（根結(jié)點(diǎn)指針） mknode(op, left,

9、 right)建立一個表達(dá)式語法樹結(jié)點(diǎn)，它的運(yùn)算符為op，左、右運(yùn)算對象是left和right所指的語法樹。如果建成DAG，則需要檢查是否已存在相應(yīng)內(nèi)部結(jié)點(diǎn)op，其左右運(yùn)算對象分別是left和right。若沒有則新建一個。 mkleaf(NUM,number.lex_val) mkleaf(ID,id.entry)建立表達(dá)式語法樹的葉結(jié)點(diǎn)。建DAG也需檢查是否已有相應(yīng)結(jié)點(diǎn)。7/25/202217編譯原理與技術(shù)講義e.g.4 構(gòu)造表達(dá)式a+b*-4的屬性結(jié)構(gòu)樹 E.nptrE.nptrE.nptr+E.nptrE.nptr*abE.nptr4ID aID bNUM4 -* + 7/25/2022

10、18編譯原理與技術(shù)講義e.g.4 構(gòu)造表達(dá)式a+b*-4的語法樹（DAG） + ID a* ID b -NUM47/25/202219編譯原理與技術(shù)講義L-屬性定義如果產(chǎn)生式AX1X2Xn 的語義規(guī)則只計(jì)算1）A的綜合屬性，或者2）Xi的繼承屬性，且該屬性僅依賴于產(chǎn)生式右部Xi的左邊符號Xj（ji）的（綜合）屬性或A的繼承屬性；S-屬性定義均為L-屬性定義可按深度優(yōu)先次序計(jì)算 一種自然的屬性計(jì)算次序 在分析期間完成翻譯。屬性計(jì)算與結(jié)點(diǎn)建立有聯(lián)系；適合于自頂向下和自底向上分析方法。7/25/202220編譯原理與技術(shù)講義深度優(yōu)先次序procedure dfvisit( n : node )beg

11、infor each child m of n, from left to right do begin evaluate inherited attributes of m; dfvisit( m ) ; end; evaluate synthesized attributes of n;end7/25/202221編譯原理與技術(shù)講義e.g.5 非L-屬性定義的語法制導(dǎo)定義產(chǎn)生式語義規(guī)則ALML.i := l(A.i)M.i := m(L.s)A.s := f(M.s)AQRR.i := r(A.i)Q.i := q(R.s)A.s := f(Q.s)7/25/202222編譯原理與技術(shù)講義

12、翻譯方案中的動作語義動作可放在產(chǎn)生式右端任何位置；這也就顯式地給出了動作的執(zhí)行時刻。（可認(rèn)為是在深度優(yōu)先遍歷中的執(zhí)行時刻）e.g. 6將含有+和-運(yùn)算的中綴表達(dá)式翻譯為后綴形式：ET RR addop T print( addop.lex_val) R | T number print( number.lex_val) 7/25/202223編譯原理與技術(shù)講義e.g. 6 中綴翻譯為后綴 ：9-4+5ETR9print(9)-Tprint(-)R4print(4)+Tprint(+)5print(5)R123457/25/202224編譯原理與技術(shù)講義翻譯方案中的動作設(shè)計(jì)翻譯方案時，必須保證動

13、作所引用的屬性值是可用的。只有綜合綜合屬性時（S-屬性定義），動作放在產(chǎn)生式末尾； 若有繼承屬性時，動作的放置須保證： （產(chǎn)生式右部）符號的繼承屬性必須在此符號前計(jì)算； 動作不要引用其右邊符號的綜合屬性； 左部非終結(jié)符的綜合屬性一般放在產(chǎn)生式末 尾（確保它引用的屬性均已計(jì)算完且可用）7/25/202225編譯原理與技術(shù)講義e.g.7 翻譯方案的書寫S A1 A2 A1.in := 1 ; A2.in := 2 A a print( A.in ) 改寫為：S A1.in := 1 A1 A2.in := 2 A2 A a print( A.in ) 7/25/202226編譯原理與技術(shù)講義e.g

14、.8 類型說明的語法制導(dǎo)定義（0） 產(chǎn)生式語義規(guī)則 DT L L.in := T.type Tint T.type := integer Treal T.type := real LL1 , id L1.in := L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in)7/25/202227編譯原理與技術(shù)講義e.g.8 類型說明的語法制導(dǎo)定義（0）屬性傳遞DTLL，kL，jiint7/25/202228編譯原理與技術(shù)講義e.g.8類型說明的語法制導(dǎo)定義（1）改寫上述類型聲明文法，使得其中的T成為L的子結(jié)點(diǎn)（即產(chǎn)生式右部），可以避免繼承屬

15、性的使用。修改后文法如下：DL Tint Treal LL1 , id LT id7/25/202229編譯原理與技術(shù)講義e.g.8類型說明的語法制導(dǎo)定義（2） 產(chǎn)生式語義規(guī)則 D L Tint T.type := integer Treal T.type := real LL1 , id L.in := L1.in addtype(id.entry, L1.in)LT id addtype(id.entry, T.type); L.in := T.type7/25/202230編譯原理與技術(shù)講義e.g.8類型說明的語法制導(dǎo)定義（2）屬性傳遞DTLL，kL，jiint7/25/202231編譯

16、原理與技術(shù)講義e.g.8 類型說明的語法制導(dǎo)定義（3）Pascal語言類型聲明文法如下： DL : T Tint Treal LL1 , id Lid該聲明文法的“問題”在于，L中聲明的變量的類型T處于產(chǎn)生式中L的右邊！若用繼承屬性L.in來傳遞類型信息T.type形成非L屬性定義。從而無法在完成L分析同時將有關(guān)類型信息填入符號表！可以考慮將T作為L的子結(jié)點(diǎn)（通過修改文法）來改變這種情況7/25/202232編譯原理與技術(shù)講義e.g.8 類型說明的語法制導(dǎo)定義（4） 產(chǎn)生式語義規(guī)則 D id L addtype(id.entry,L.in)Tint T.type := integer Trea

17、l T.type := real L, id L1 L.in := L1.in addtype(id.entry, L1.in)L : T L.in := T.type7/25/202233編譯原理與技術(shù)講義e.g.9 翻譯方案的計(jì)算次序EE+T print( “1” ) ET print( “2” ) TT*F print( “3” ) TF print( “4” ) F(E) print( “5” ) Fid print( “6” ) 輸入串是id*(id+id)時，該翻譯方案輸出什么？7/25/202234編譯原理與技術(shù)講義S-屬性定義的自底向上計(jì)算拓廣分析棧，即添加屬性棧，包含文法符號

18、的綜合屬性。在歸約實(shí)施前，右部各符號的綜合屬性（若有的話）已放在與符號位置對應(yīng)的屬性棧上，因此，可以先計(jì)算獲得左部非終結(jié)符的綜合屬性。然后再歸約，這時從分析棧中彈出句柄，（注意，此時改變棧頂top即可）最后，將左部符號連同其屬性放入由top指示的分析棧及屬性棧的位置中。這種屬性棧只能存放綜合屬性?；叵隮ACC中如何做的？7/25/202235編譯原理與技術(shù)講義如果AXYZ，相關(guān)語義規(guī)則如下：A.a := f(X.x,Y.y,Z.z)顯然，X.x在Valtop-2Y.y在Valtop-1Z.z在ValtopA.a在Valntop ，ntop = top |句柄長度|+1Val ntop := f

19、( valtop-2, Valtop-1, Valtop )屬性棧與分析棧ZZ.zYY.yXX.x分析棧屬性棧Valtopbottom7/25/202236編譯原理與技術(shù)講義如果AB ，相關(guān)語義規(guī)則如下：A.a := B.b 顯然，B.b在ValtopA.a在Valntop ，ntop = top 1+1 = top ,即歸約前后棧頂top不變，也即Val ntop 和 Valtop對應(yīng)屬性棧同一個單元，所以，可以省略原語義規(guī)則對應(yīng)的屬性棧操作：Valntop := Valtop屬性棧與分析棧BB.b分析棧屬性棧Valtopbottom7/25/202237編譯原理與技術(shù)講義e.g.10 計(jì)算

20、表達(dá)式的（棧）代碼產(chǎn)生式語義規(guī)則代碼段LE nPrint( E.val )Print( Valtop-1 )EE1+TE.val := E1.val + T.valValntop:=Valtop-2+ValtopETE.val := T.valTT1*FT.val := T1.val * F.valValntop:=Valtop-2*ValtopTFT.val := F.valF(E)F.val := E.valValntop:=Valtop-1FdigitF.val := digit.lex_val7/25/202238編譯原理與技術(shù)講義如何在自底向上分析中計(jì)算繼承屬性？ 屬性棧上僅能存放綜

21、合屬性 能否將繼承屬性的引用轉(zhuǎn)換成綜合屬性？分析棧中符號的繼承屬性 屬性copy規(guī)則如果，AXY，有語義規(guī)則Y.i := X.s，翻譯方案可寫為： A X Y.i := X.s Y自底向上計(jì)算繼承屬性7/25/202239編譯原理與技術(shù)講義自底向上計(jì)算繼承屬性 由屬性copy規(guī)則可知，Y的繼承屬性Y.i和X.s在屬性棧上同一位置。這樣對屬性Y.i的引用可以轉(zhuǎn)化為對X.s的引用。若計(jì)算Y的綜合屬性Y.s時需要引用Y.i，則此時Y.i（即X.s）就緊鄰在句柄下面；如果Y的句柄形成前，它的某個右部符號需使用Y.i，這時，也可以直接使用Y.i。（How to use?）bottomXX.s（Y.i）分

22、析棧屬性棧Valtop句柄（歸約為Y）top句柄長7/25/202240編譯原理與技術(shù)講義e.g.11 C聲明的翻譯方案 DT L.in := T.type L Tint T.type := integer Treal T.type := real L L1.in := L.in L1 , id addtype(id.entry, L.in) Lid addtype(id.entry, L.in) 對于輸入串：int p,q,r 分析過程如下：7/25/202241編譯原理與技術(shù)講義輸入串 分析棧 產(chǎn)生式 int p,q,r p,q,r intp,q,r T Tint ,q,r Tp ,q,r

23、 TL Lid q,r TL, ,r TL,q ,r TL LL , id r TL, TL,r TL LL , id D DTL注意：每次歸約成L時，T與L的位置關(guān)系T就在句柄的下面！7/25/202242編譯原理與技術(shù)講義e.g.11 C聲明的“代碼段”產(chǎn)生式 代碼段（只含綜合屬性）DT L Tintvalntop:=integer Trealvalntop:=real L L1 , id addtype(valtop,valtop-3)Lid addtype(valtop,valtop-1)L的繼承屬性L.in7/25/202243編譯原理與技術(shù)講義問題1：繼承屬性的位置在構(gòu)造編譯器時不

24、可預(yù)知（或不固定），如e.g.12 產(chǎn)生式語義規(guī)則S a A C C.i := A.sS b A B CC.i := A.sC cC.s := g(C.i)用C c歸約時，C.i的值可能在valtop-1或者在valtop-2的位置上。解決辦法是考慮將其統(tǒng)一。引入標(biāo)記非終結(jié)符 M和產(chǎn)生式M 。模擬繼承屬性的計(jì)算bottomccABaAb分析棧1分析棧2top7/25/202244編譯原理與技術(shù)講義產(chǎn)生式語義規(guī)則S a A CC.i := A.sS b A B M CC.i := M.sM.i := A.sC cC.s := g(C.i)M M.s := M.i 引入M后，C.i 可從句柄c的下

25、面(valtop-1)取得！屬性傳遞： A.s M.i M.s C.i C.se.g.12 引入標(biāo)記非終結(jié)符bottomAMaBAb分析棧1分析棧2topcc7/25/202245編譯原理與技術(shù)講義產(chǎn)生式代碼段S a A CS b A B M CC c valntop:= g(valtop-1)M valntop := valtop-1可否將M放在S a A C產(chǎn)生式中？M.i7/25/202246編譯原理與技術(shù)講義模擬繼承屬性的計(jì)算問題2：語義規(guī)則不是簡單的屬性復(fù)寫拷貝。e.g.13 : 將例12中的S a A C語義規(guī)則換為：產(chǎn)生式語義規(guī)則 S a A CC.i := f( A.s )雖然

26、在例12中引入了M使得“A.s”可在valtop-1處找到，但在S的兩個產(chǎn)生式中C.i的取值方式不同，導(dǎo)致C.s的計(jì)算嘛這次可以考慮引入標(biāo)記非終結(jié)符N和N7/25/202247編譯原理與技術(shù)講義e.g.13 引入標(biāo)記非終結(jié)符N 產(chǎn)生式 語義規(guī)則 S a A N C C.i := N.s N.i := A.s NN.s := f(N.i)(其他產(chǎn)生式和語義規(guī)則不變）(代碼段略）7/25/202248編譯原理與技術(shù)講義產(chǎn)生式語義規(guī)則SB B.ps := 10S.ht := B.htBB1B2B1.ps := B.psB2.ps := B.ps B.ht := max(B1.ht,B2.ht)BB1

27、 sub B2 B1.ps := B.psB2.ps := shrink(B.ps) B.ht := disp(B1.ht,B2.ht)B text B.ht := text.h B.pse.g.14 文字排版的語法制導(dǎo)定義7/25/202249編譯原理與技術(shù)講義S ： S.ht，綜合屬性；待排公式的整體高度B ： B.ps，繼承屬性； 公式（文本）中字體“點(diǎn)”的大小 B.ht，綜合屬性；公式排版高度text ：text.h，文本高度max ：求兩個排版公式的最大高度shrink(B) ：將點(diǎn)大小縮小為B的30disp(B1.ht，B2.ht)：向下調(diào)整B2的位置文字排版中的符號屬性E1Val

28、7/25/202250編譯原理與技術(shù)講義文字排版的翻譯方案（0）S B.ps := 10 B S.ht := B.ht B B1.ps := B.ps B1 B2.ps := B.ps B2 B.ht := max(B1.ht,B2.ht) B B1.ps := B.ps B1 sub B2.ps := shrink(B.ps) B2 B.ht := disp(B1.ht,B2.ht) B text B.ht := text.h B.ps 7/25/202251編譯原理與技術(shù)講義文字排版中引入標(biāo)記符號為了自底向上計(jì)算：B text B.ht := text.h B.ps 必須確定繼承屬性B.p

29、s的（“屬性棧”）位置。為此引入標(biāo)記非終結(jié)符L、M和N及其屬性，包括相應(yīng)的空產(chǎn)生式和有關(guān)屬性規(guī)則。這樣B.ps即可在緊靠“句柄”text下方的位置上找到。(L的綜合屬性置為B.ps的初值)SL BBB1M B2BB1 sub N B2texttext.hLL.s=10分析棧屬性棧topbottom7/25/202252編譯原理與技術(shù)講義S L B.ps := L.s L L.s := 10 B S.ht := B.ht B B1.ps := B.ps M M.s := M.i B1 M.i := B.ps M B2.ps := M.s B2 B.ht := max(B1.ht,B2.ht) B

30、 B1.ps := B.ps B1 sub N.i := B.ps N N.s :=shrink(N.i) N B2.ps := N.s B2 B.ht := disp(B1.ht,B2.ht) B text B.ht := text.h B.ps 文字排版的翻譯方案（1）7/25/202253編譯原理與技術(shù)講義 產(chǎn)生式代碼段S L B valntop := valtop BB1 M B2 valntop := max(valtop-2,valtop)BB1 sub N B2 valntop := disp(valtop-3,valtop)B text valntop := valtopval

31、top-1L valntop := 10M valntop := valtop-1N valntop := shrink( valtop-2 )7/25/202254編譯原理與技術(shù)講義（L-屬性定義）自頂向下翻譯刪除翻譯方案中的左遞歸A A1Y A.a := g(A1.a, Y.y) A X A.a := f( X.x) 消除左遞歸：A X R.i := f( X.x) /傳遞“左”運(yùn)算量 R A.a := R.s R Y R1.i := g(R.i, Y.y) R1 R.s := R1.s R R.s := R.i /返回結(jié)果7/25/202255編譯原理與技術(shù)講義輸入串XY1Y2的翻譯XA

32、.a := f( X.x)A.a := g(f( X.x), y1.y)y1A.a := g(g(f( X.x), y1.y), y2.y)y2A.aXR.i := f(X.x)Y1R.i := g(f(X.x),Y1.y)Y2R.i := g(g(f(X.x),Y1.y), Y2.y)R.sR.sR.s7/25/202256編譯原理與技術(shù)講義e.g.15 刪除翻譯方案中左遞歸EE1 + T E.nptr := mknode(+,E1.nptr, T.nptr)EE1 - T E.nptr := mknode(-,E1.nptr, T.nptr)ET E.nptr := T.nptr T( E ) T.nptr := E.nptr Tnum T.nptr := mkleaf(NUM,num.val) Tid T.nptr := mkl