編譯原理與技術

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

2、er 屬性計算規(guī)則（語義規(guī)則）與產(chǎn)生式相關聯(lián)的反映文法符號屬性之間關系的“規(guī)則”2022-3-9編譯原理與技術講義4屬性文法語法制導定義（文法屬性語義規(guī)則）語義規(guī)則僅表明屬性間“抽象”關系，不涉及具體翻譯實現(xiàn)細節(jié)，如計算次序等。翻譯方案（文法屬性語義動作）語義規(guī)則即語義動作，可體現(xiàn)若干實現(xiàn)的細節(jié)。2022-3-9編譯原理與技術講義5e.g.1算術表達式的計算器 產(chǎn)生式 語法制導定義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編譯原理與技術講義6e.g.1算術表達式的計算器 產(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編譯原理與技術講義7屬性文法屬性的分類若產(chǎn)生式AX1X2Xn，與之相關的屬性計算規(guī)則b := f ( c1, c2, )如果屬性b是產(chǎn)生式左部符號左部符號A的屬性的屬性則稱其為A的的綜合屬性；綜合屬性；如果屬性b是產(chǎn)生式右部符號

4、右部符號Xi的屬性的屬性則稱其為Xi的繼承屬性；的繼承屬性；c1, c2, 一般是產(chǎn)生式右部其它符號的(綜合)屬性或A的繼承屬性； 固有屬性：終結符僅有的屬性。如number.lex_val。通常由詞法程序提供。2022-3-9編譯原理與技術講義8A.bX1.c1X2.c2X綜合屬性A.b的計算A的繼承屬性AX1.c1X2.c2繼承屬性Xk.b的計算A的繼承屬性Xk.bX屬性依賴圖2022-3-9編譯原理與技術講義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編譯原理與技術講義10語義規(guī)則的計算方法分析樹方法 為輸入串建立分析樹 由語義規(guī)則建立屬性依賴圖（沒有屬性循環(huán)依賴的） 對依賴圖進行拓撲排序，得到屬性計算次序 依次計算屬性，得到“翻譯”結果基于規(guī)則的方法 構造編譯器時，事先對產(chǎn)生式的語義規(guī)則進行分析，得到屬性計算次序忽略規(guī)則的方法 屬性計算次序僅由分析方法限定。如S-屬性定義可以在自下而上分析時，在歸約前計算。如YACC中的語義動作。2022-3-9編譯原理與技術講義11e.g. 3 屬性計算次序: 345E. val = 23E. val = 3+E.

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

7、hen S1else S22022-3-9編譯原理與技術講義14 a := b* -c + b * -c 語法樹 分析樹語法樹 vs. 分析樹assigna+*bc*bcassignEEE+E*EbEEa賦值語句cE*EbEc算符2022-3-9編譯原理與技術講義15DAG（去除了公共子表達式的無環(huán)有向圖）a := b* -c + b * -c語法樹 vs. DAGassigna+*bc*bcassigna+*bc語法樹DAG2022-3-9編譯原理與技術講義16e.g.4 構造表達式的語法樹（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編譯原理與技術講義17e.

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

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

11、9編譯原理與技術講義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編譯原理與技術講義22e.g.5 非L-屬性定義的語法制導定義產(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編譯原理與技術講義23翻譯方案中的動作語義動作可放在產(chǎn)生式右端任何位置；這也就顯式地給出了動作的執(zhí)行時刻。（可認為是在深度優(yōu)先遍歷中的執(zhí)行時刻）e.g. 6將含有+和-運算的中綴表達式翻譯為后綴形式：ET RR addop T print( addop.lex_val) R | T number print( number.lex_val) 2022-3-9編譯原理與技術講義24e.g. 6 中綴翻譯為后綴 ：9-4+5ETR9print(9)-Tprint(-)R4print(4)+Tprint(+)5print(5)

13、R123452022-3-9編譯原理與技術講義25翻譯方案中的動作設計翻譯方案時，必須保證動作所引用的屬性值是可用的。只有綜合綜合屬性時（S-屬性定義），動作放在產(chǎn)生式末尾； 若有繼承屬性時，動作的放置須保證： （產(chǎn)生式右部）符號的繼承屬性必須在此符號前計算； 動作不要引用其右邊符號的綜合屬性； 左部非終結符的綜合屬性一般放在產(chǎn)生式末 尾（確保它引用的屬性均已計算完且可用）2022-3-9編譯原理與技術講義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編譯原理與技術講義27e.g.8 類型說明的語法制導定義（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編譯原理與技術講義28e.g.8 類型說明的語法制導定義（0）屬性傳遞DTLL，kL，jiint2022-3-9編譯原理與技術講義29e.g.8類型說明的語法制導定義（

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

16、的語法制導定義（2）屬性傳遞DTLL，kL，jiint2022-3-9編譯原理與技術講義32e.g.8 類型說明的語法制導定義（3）Pascal語言類型聲明文法如下： DL : T Tint Treal LL1 , id Lid該聲明文法的“問題”在于，L中聲明的變量的類型T處于產(chǎn)生式中L的右邊！若用繼承屬性L.in來傳遞類型信息T.type形成非L屬性定義。從而無法在完成L分析同時將有關類型信息填入符號表！可以可以考慮將考慮將T作為作為L的子結點（通過修的子結點（通過修改文法）來改變這種情況改文法）來改變這種情況2022-3-9編譯原理與技術講義33e.g.8 類型說明的語法制導定義（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編譯原理與技術講義34e.g.9 翻譯方案的計算次序EE+T print( “1” ) ET print( “2” ) TT*F print( “3” ) TF print( “4” ) F(E) print( “5” ) Fid print( “6” ) 輸入串是id*(id+id)時

18、，該翻譯方案輸出什么？2022-3-9編譯原理與技術講義35S-屬性定義的自底向上計算拓廣分析棧，即添加屬性棧，包含文法符號的綜合屬性。在歸約實施前，右部各符號的綜合屬性（若有的話）已放在與符號位置對應的屬性棧上，因此，可以先計算獲得左部非終結符的綜合屬性。然后再歸約，這時從分析棧中彈出句柄，（注意，此時改變棧頂注意，此時改變棧頂top即可即可）最后，將左部符號連同其屬性放入由top指示的分析棧及屬性棧的位置中。這種屬性棧只能存放綜合屬性?；叵隮ACC中如何做的？2022-3-9編譯原理與技術講義36如果AXYZ，相關語義規(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 |句柄長度|+1Val ntop := f( valtop-2, Valtop-1, Valtop )屬性棧與分析棧ZZ.zYY.yXX.x分析棧屬性棧Valtopbottom2022-3-9編譯原理與技術講義37如果AB ，相關語義規(guī)則如下：A.a := B.b 顯然，B.b在ValtopA.a在Valntop ，ntop = top 1+1 = top ,即歸約前后棧頂top不變，也即Val ntop 和 Valtop對應屬性棧同一個單元，所以，可以省略原語義規(guī)則對應的屬性棧操作：所以，可

20、以省略原語義規(guī)則對應的屬性棧操作：Valntop := Valtop屬性棧與分析棧BB.b分析棧屬性棧Valtopbottom2022-3-9編譯原理與技術講義38e.g.10 計算表達式的（棧）代碼產(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編譯原理與技術講義39如何在自底向上分析中計算繼承屬性？ 屬性棧上僅能存放綜合屬性 能否將繼承屬性的引用轉換成綜合屬性？分析棧中符號的繼承屬性 屬性copy規(guī)則如果，AXY，有語義規(guī)則Y.i := X.s，翻譯方案可寫為： A X Y.i := X.s Y自底向上計算繼承屬性2022-3-9編譯原理與技術講義40自底向上計算繼承屬性 由屬性copy規(guī)則可知，Y的繼承屬性Y.i和X.s在屬性棧上同一位置。這樣對屬性Y.i的引用可以轉化為對X.s的引用。若計算若計算Y的綜合屬性的綜合屬性Y.s時

22、需要引用時需要引用Y.i，則此時，則此時Y.i（即（即X.s）就緊鄰在句柄下面；）就緊鄰在句柄下面；如果如果Y的句柄形成前，的句柄形成前，它的某個右部符號它的某個右部符號需使用需使用Y.i，這時，這時，也可以直接使用也可以直接使用Y.i。（How to use?）bottomXX.s（Y.i）分析棧屬性棧Valtop句柄（歸約為Y）top句柄長句柄長2022-3-9編譯原理與技術講義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) 對于輸入串：int p,q,r 分析過程如下：2022-3-9編譯原理與技術講義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時，T與L的位置關系T就在句柄的下面！2022-3-9編譯原理與技術講義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編譯原理與技術講義44問題1：繼承屬性的位置在構造編譯器時不可預知（或不固定），如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)一。引入標記非終結符 M和產(chǎn)生式M 。模擬繼承屬性

25、的計算bottomccABaAb分析棧1分析棧2top2022-3-9編譯原理與技術講義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 引入標記非終結符bottomAMaBAb分析棧1分析棧2topcc2022-3-9編譯原理與技術講義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編譯原理與技術講義47模擬繼承屬性的計算問題2：語義規(guī)則不是簡單的屬性復寫拷貝。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的兩個產(chǎn)生式中C.i的取值方式不同，導致C.s的計算嘛這次可以考慮引入標記非終結符N和N2022-3-9編譯原理與技術講義48e.g.13 引入標記非終結符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編譯原理與技術講義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 文字排版的語法制導定義2022-3-9編譯原理與技術講義50S ： S.ht，綜合屬性；待排公式的整體高度B ：

28、B.ps，繼承屬性； 公式（文本）中字體“點”的大小 B.ht，綜合屬性；公式排版高度text ：text.h，文本高度max ：求兩個排版公式的最大高度shrink(B) ：將點大小縮小為B的30disp(B1.ht，B2.ht)：向下調(diào)整B2的位置文字排版中的符號屬性E1Val2022-3-9編譯原理與技術講義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編譯原理與技術講義52文字排版中引入標記符號為了自底向上計算：B text B.ht := text.h B.ps 必須確定繼承屬性B.ps的（“屬性?！保┪恢?。為此引入標記非終結符L、M和N及其屬性，包括相應的空產(chǎn)生式和有關屬性規(guī)則。這樣B.ps即可在緊靠“句柄”text下方的位置上找到。(L的綜合屬性置為B.ps的初值)SL BBB1M B2BB1 sub N B2texttext.hLL.s=10分析棧屬性棧topbottom2022-3-9編譯原理

30、與技術講義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編譯原理與技術講義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編譯原理與技術講義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) /傳遞“左”運算量 R A.a := R.s R Y R1.i := g(R.i, Y.y) R1 R.s := R1.s R R.s := R.i /返回結果2022-3-9編譯原理與技術講義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編譯原理與技術講義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