編譯原理與技術(shù)

1、2022-3-9編譯原理與技術(shù)講義1編譯原理與技術(shù)語法制導(dǎo)翻譯2022-3-9編譯原理與技術(shù)講義2語法制導(dǎo)翻譯屬性文法lS-屬性定義lL-屬性定義l語法制導(dǎo)定義與翻譯方案自底向上翻譯lS-屬性定義自底向上計(jì)算l自底向上計(jì)算繼承屬性自頂向下翻譯2022-3-9編譯原理與技術(shù)講義3屬性文法屬性文法（Attributed Grammar）上下文無關(guān)文法上下文無關(guān)文法+屬性屬性+屬性計(jì)算規(guī)則屬性計(jì)算規(guī)則 屬性用來描述文法符號(hào)的語義特征，如常量的“值”、變量的類型和存儲(chǔ)位置等。e.g. 二義性表達(dá)式文法G，非終結(jié)符E有屬性E.val（表達(dá)式的值）EE + E | E * E | ( E ) | numb

2、er 屬性計(jì)算規(guī)則（語義規(guī)則）與產(chǎn)生式相關(guān)聯(lián)的反映文法符號(hào)屬性之間關(guān)系的“規(guī)則”2022-3-9編譯原理與技術(shù)講義4屬性文法語法制導(dǎo)定義（文法屬性語義規(guī)則）語義規(guī)則僅表明屬性間“抽象”關(guān)系，不涉及具體翻譯實(shí)現(xiàn)細(xì)節(jié)，如計(jì)算次序等。翻譯方案（文法屬性語義動(dòng)作）語義規(guī)則即語義動(dòng)作，可體現(xiàn)若干實(shí)現(xiàn)的細(xì)節(jié)。2022-3-9編譯原理與技術(shù)講義5e.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 := nu

3、mber.lex_val2022-3-9編譯原理與技術(shù)講義6e.g.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 2022-3-9編譯原理與技術(shù)講義7屬性文法屬性的分類若產(chǎn)生式AX1X2Xn，與之相關(guān)的屬性計(jì)算規(guī)則b := f ( c1, c2, )如果屬性b是產(chǎn)生式左部符號(hào)左部符號(hào)A的屬性的屬性則稱其為A的的綜合屬性；綜合屬性；如果屬性b是產(chǎn)生式右部符號(hào)

4、右部符號(hào)Xi的屬性的屬性則稱其為Xi的繼承屬性；的繼承屬性；c1, c2, 一般是產(chǎn)生式右部其它符號(hào)的(綜合)屬性或A的繼承屬性； 固有屬性：終結(jié)符僅有的屬性。如number.lex_val。通常由詞法程序提供。2022-3-9編譯原理與技術(shù)講義8A.bX1.c1X2.c2X綜合屬性A.b的計(jì)算A的繼承屬性AX1.c1X2.c2繼承屬性Xk.b的計(jì)算A的繼承屬性Xk.bX屬性依賴圖2022-3-9編譯原理與技術(shù)講義9e.g. 2 屬性依賴圖:345E. val = 23E. val = 3+E. val = 20number. lex_val = 3E. val = 4E. val = 5nu

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

6、val = 20number. lex_val = 3E. val = 4E. val = 5number. lex_val = 4number. lex_val = 5123456782022-3-9編譯原理與技術(shù)講義12S-屬性定義語義規(guī)則僅包含綜合屬性計(jì)算（可以有固有屬性出現(xiàn)）。適合自底向上計(jì)算e.g. 語法樹語法樹與分析樹 語法樹可看作分析樹的濃縮。也稱抽象語法樹。而分析樹可看成具體語法樹。2022-3-9編譯原理與技術(shù)講義13 S if B-expr then S1 else S2語法樹 分析樹語法樹 vs. 分析樹if-then-elseB-exprS1S2Sif B-expr t

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

8、2.nptr)EE1 - E2 E.nptr := mknode(-,E1.nptr, E2.nptr)EE1 * 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)2022-3-9編譯原理與技術(shù)講義17e.

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

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

11、9編譯原理與技術(shù)講義21深度優(yōu)先次序procedure dfvisit( n : node )beginfor each child m of n, from left to right do begin evaluate inherited attributes of m; dfvisit( m ) ; end; evaluate synthesized attributes of n;end2022-3-9編譯原理與技術(shù)講義22e.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

12、.i)Q.i := q(R.s)A.s := f(Q.s)2022-3-9編譯原理與技術(shù)講義23翻譯方案中的動(dòng)作語義動(dòng)作可放在產(chǎn)生式右端任何位置；這也就顯式地給出了動(dòng)作的執(zhí)行時(shí)刻。（可認(rèn)為是在深度優(yōu)先遍歷中的執(zhí)行時(shí)刻）e.g. 6將含有+和-運(yùn)算的中綴表達(dá)式翻譯為后綴形式：ET RR addop T print( addop.lex_val) R | T number print( number.lex_val) 2022-3-9編譯原理與技術(shù)講義24e.g. 6 中綴翻譯為后綴 ：9-4+5ETR9print(9)-Tprint(-)R4print(4)+Tprint(+)5print(5)

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

14、 A2 A a print( A.in ) 2022-3-9編譯原理與技術(shù)講義27e.g.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)2022-3-9編譯原理與技術(shù)講義28e.g.8 類型說明的語法制導(dǎo)定義（0）屬性傳遞DTLL，kL，jiint2022-3-9編譯原理與技術(shù)講義29e.g.8類型說明的語法制導(dǎo)定義（

15、1）改寫上述類型聲明文法，使得其中的T成為L(zhǎng)的子結(jié)點(diǎn)（即產(chǎn)生式右部），可以避免繼承屬性的使用。修改后文法如下：DL Tint Treal LL1 , id LT id2022-3-9編譯原理與技術(shù)講義30e.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.type2022-3-9編譯原理與技術(shù)講義31e.g.8類型說明

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

17、產(chǎn)生式語義規(guī)則 D id L addtype(id.entry,L.in)Tint T.type := integer Treal T.type := real L, id L1 L.in := L1.in addtype(id.entry, L1.in)L : T L.in := T.type2022-3-9編譯原理與技術(shù)講義34e.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)時(shí)

18、，該翻譯方案輸出什么？2022-3-9編譯原理與技術(shù)講義35S-屬性定義的自底向上計(jì)算拓廣分析棧，即添加屬性棧，包含文法符號(hào)的綜合屬性。在歸約實(shí)施前，右部各符號(hào)的綜合屬性（若有的話）已放在與符號(hào)位置對(duì)應(yīng)的屬性棧上，因此，可以先計(jì)算獲得左部非終結(jié)符的綜合屬性。然后再歸約，這時(shí)從分析棧中彈出句柄，（注意，此時(shí)改變棧頂注意，此時(shí)改變棧頂top即可即可）最后，將左部符號(hào)連同其屬性放入由top指示的分析棧及屬性棧的位置中。這種屬性棧只能存放綜合屬性?；叵隮ACC中如何做的？2022-3-9編譯原理與技術(shù)講義36如果AXYZ，相關(guān)語義規(guī)則如下：A.a := f(X.x,Y.y,Z.z)顯然，X.x在Val

19、top-2Y.y在Valtop-1Z.z在ValtopA.a在Valntop ，ntop = top |句柄長(zhǎng)度|+1Val ntop := f( valtop-2, Valtop-1, Valtop )屬性棧與分析棧ZZ.zYY.yXX.x分析棧屬性棧Valtopbottom2022-3-9編譯原理與技術(shù)講義37如果AB ，相關(guān)語義規(guī)則如下：A.a := B.b 顯然，B.b在ValtopA.a在Valntop ，ntop = top 1+1 = top ,即歸約前后棧頂top不變，也即Val ntop 和 Valtop對(duì)應(yīng)屬性棧同一個(gè)單元，所以，可以省略原語義規(guī)則對(duì)應(yīng)的屬性棧操作：所以，可

20、以省略原語義規(guī)則對(duì)應(yīng)的屬性棧操作：Valntop := Valtop屬性棧與分析棧BB.b分析棧屬性棧Valtopbottom2022-3-9編譯原理與技術(shù)講義38e.g.10 計(jì)算表達(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.valV

21、alntop:=Valtop-1FdigitF.val := digit.lex_val2022-3-9編譯原理與技術(shù)講義39如何在自底向上分析中計(jì)算繼承屬性？ 屬性棧上僅能存放綜合屬性 能否將繼承屬性的引用轉(zhuǎn)換成綜合屬性？分析棧中符號(hào)的繼承屬性 屬性copy規(guī)則如果，AXY，有語義規(guī)則Y.i := X.s，翻譯方案可寫為： A X Y.i := X.s Y自底向上計(jì)算繼承屬性2022-3-9編譯原理與技術(shù)講義40自底向上計(jì)算繼承屬性 由屬性copy規(guī)則可知，Y的繼承屬性Y.i和X.s在屬性棧上同一位置。這樣對(duì)屬性Y.i的引用可以轉(zhuǎn)化為對(duì)X.s的引用。若計(jì)算若計(jì)算Y的綜合屬性的綜合屬性Y.s時(shí)

22、需要引用時(shí)需要引用Y.i，則此時(shí)，則此時(shí)Y.i（即（即X.s）就緊鄰在句柄下面；）就緊鄰在句柄下面；如果如果Y的句柄形成前，的句柄形成前，它的某個(gè)右部符號(hào)它的某個(gè)右部符號(hào)需使用需使用Y.i，這時(shí)，這時(shí)，也可以直接使用也可以直接使用Y.i。（How to use?）bottomXX.s（Y.i）分析棧屬性棧Valtop句柄（歸約為Y）top句柄長(zhǎng)句柄長(zhǎng)2022-3-9編譯原理與技術(shù)講義41e.g.11 C聲明的翻譯方案 DT L.in := T.type L Tint T.type := integer Treal T.type := real L L1.in := L.in L1 , id a

23、ddtype(id.entry, L.in) Lid addtype(id.entry, L.in) 對(duì)于輸入串：int p,q,r 分析過程如下：2022-3-9編譯原理與技術(shù)講義42輸入串 分析棧 產(chǎn)生式 int p,q,r p,q,r intp,q,r T Tint ,q,r Tp ,q,r TL Lid q,r TL, ,r TL,q ,r TL LL , id r TL, TL,r TL LL , id D DTL注意：每次歸約成L時(shí)，T與L的位置關(guān)系T就在句柄的下面！2022-3-9編譯原理與技術(shù)講義43e.g.11 C聲明的“代碼段”產(chǎn)生式 代碼段（只含綜合屬性）DT L Tin

24、tvalntop:=integer Trealvalntop:=real L L1 , id addtype(valtop,valtop-3)Lid addtype(valtop,valtop-1)L的繼承屬性L.in2022-3-9編譯原理與技術(shù)講義44問題1：繼承屬性的位置在構(gòu)造編譯器時(shí)不可預(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歸約時(shí)，C.i的值可能在valtop-1或者在valtop-2的位置上。解決辦法是考慮將其統(tǒng)一。引入標(biāo)記非終結(jié)符 M和產(chǎn)生式M 。模擬繼承屬性

25、的計(jì)算bottomccABaAb分析棧1分析棧2top2022-3-9編譯原理與技術(shù)講義45產(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的下面(valtop-1)取得！屬性傳遞： A.s M.i M.s C.i C.se.g.12 引入標(biāo)記非終結(jié)符bottomAMaBAb分析棧1分析棧2topcc2022-3-9編譯原理與技術(shù)講義46產(chǎn)生式代碼段S a A CS b A B M CC c valntop:= g(valtop-1)M valnt

26、op := valtop-1可否將M放在S a A C產(chǎn)生式中？M.i2022-3-9編譯原理與技術(shù)講義47模擬繼承屬性的計(jì)算問題2：語義規(guī)則不是簡(jiǎn)單的屬性復(fù)寫拷貝。e.g.13 : 將例12中的S a A C語義規(guī)則換為：產(chǎn)生式語義規(guī)則 S a A CC.i := f( A.s )雖然在例12中引入了M使得“A.s”可在valtop-1處找到，但在S的兩個(gè)產(chǎn)生式中C.i的取值方式不同，導(dǎo)致C.s的計(jì)算嘛這次可以考慮引入標(biāo)記非終結(jié)符N和N2022-3-9編譯原理與技術(shù)講義48e.g.13 引入標(biāo)記非終結(jié)符N 產(chǎn)生式 語義規(guī)則 S a A N C C.i := N.s N.i := A.s NN

27、.s := f(N.i)(其他產(chǎn)生式和語義規(guī)則不變）(代碼段略）2022-3-9編譯原理與技術(shù)講義49產(chǎn)生式語義規(guī)則SB B.ps := 10S.ht := B.htBB1B2B1.ps := B.psB2.ps := B.ps B.ht := max(B1.ht,B2.ht)BB1 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)定義2022-3-9編譯原理與技術(shù)講義50S ： S.ht，綜合屬性；待排公式的整體高度B ：

28、B.ps，繼承屬性； 公式（文本）中字體“點(diǎn)”的大小 B.ht，綜合屬性；公式排版高度text ：text.h，文本高度max ：求兩個(gè)排版公式的最大高度shrink(B) ：將點(diǎn)大小縮小為B的30disp(B1.ht，B2.ht)：向下調(diào)整B2的位置文字排版中的符號(hào)屬性E1Val2022-3-9編譯原理與技術(shù)講義51文字排版的翻譯方案（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(

29、B.ps) B2 B.ht := disp(B1.ht,B2.ht) B text B.ht := text.h B.ps 2022-3-9編譯原理與技術(shù)講義52文字排版中引入標(biāo)記符號(hào)為了自底向上計(jì)算：B text B.ht := text.h B.ps 必須確定繼承屬性B.ps的（“屬性棧”）位置。為此引入標(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分析棧屬性棧topbottom2022-3-9編譯原理

30、與技術(shù)講義53S 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 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）2022-3-9編譯原理與技術(shù)講義54 產(chǎn)生式代碼

31、段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 := valtopvaltop-1L valntop := 10M valntop := valtop-1N valntop := shrink( valtop-2 )2022-3-9編譯原理與技術(shù)講義55（L-屬性定義）自頂向下翻譯刪除翻譯方案中的左遞歸A A1Y A.a := g(A1.a, Y.y) A X A.a := f( X.x) 消除

32、左遞歸：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é)果2022-3-9編譯原理與技術(shù)講義56輸入串XY1Y2的翻譯XA.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.s2022-3-9編譯原理與技術(shù)講義57e.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 := mkl