編譯原理與技術10/31/20221《編譯原理與技術》講義編譯原理與技術10/23/20221《編譯原理與技術》講義語法制導翻譯屬性文法S-屬性定義L-屬性定義語法制導定義與翻譯方案自底向上翻譯S-屬性定義自底向上計算自底向上計算繼承屬性自頂向下翻譯10/31/20222《編譯原理與技術》講義語法制導翻譯屬性文法10/23/20222《編譯原理與技術》屬性文法屬性文法（AttributedGrammar）

上下文無關文法+屬性+屬性計算規則屬性－用來描述文法符號的語義特征，如常量的“值”、變量的類型和存儲位置等。e.g.二義性表達式文法G，非終結符E有屬性E.val（表達式的值）EE‘+’E|

E‘*’E|‘(‘E‘)’|number屬性計算規則（語義規則）與產生式相關聯的反映文法符號屬性之間關系的“規則”10/31/20223《編譯原理與技術》講義屬性文法屬性文法（AttributedGrammar）10屬性文法語法制導定義（文法＋屬性＋語義規則）

語義規則僅表明屬性間“抽象”關系，不涉及具體翻譯實現細節，如計算次序等。翻譯方案（文法＋屬性＋語義動作）語義規則－即語義動作，可體現若干實現的細節。10/31/20224《編譯原理與技術》講義屬性文法10/23/20224《編譯原理與技術》講義e.g.1算術表達式的計算器 產生式 語法制導定義EE1‘+’E2E.val:=E1.val+E2.valEE1‘*’E2E.val:=E1.val*E2.valE’(‘E1‘)’E.val:=E1.valEnumberE.val:=number.lex_val10/31/20225《編譯原理與技術》講義e.g.1算術表達式的計算器 產生式 語法制導定義e.g.1算術表達式的計算器 產生式 翻譯方案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}10/31/20226《編譯原理與技術》講義e.g.1算術表達式的計算器 產生式 翻譯方案10屬性文法屬性的分類若產生式AX1X2…Xn，與之相關的屬性計算規則

b:=f(c1,c2,…)－如果屬性b是產生式左部符號A的屬性則稱其為A的綜合屬性；－如果屬性b是產生式右部符號Xi的屬性則稱其為Xi的繼承屬性；－c1,c2,…一般是產生式右部其它符號的(綜合)屬性或A的繼承屬性；－固有屬性：終結符僅有的屬性。如number.lex_val。通常由詞法程序提供。10/31/20227《編譯原理與技術》講義屬性文法屬性的分類10/23/20227《編譯原理與技術》講A.bX1.c1X2.c2X…綜合屬性A.b的計算A的繼承屬性AX1.c1X2.c2…繼承屬性Xk.b的計算A的繼承屬性Xk.bX屬性依賴圖10/31/20228《編譯原理與技術》講義A.bX1.c1X2.c2X…綜合屬性A.b的計算Ae.g.2屬性依賴圖: 3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=510/31/20229《編譯原理與技術》講義e.g.2屬性依賴圖: 3＋4×5E.val=語義規則的計算方法分析樹方法 －為輸入串建立分析樹 －由語義規則建立屬性依賴圖（沒有屬性循環依賴的） －對依賴圖進行拓撲排序，得到屬性計算次序 －依次計算屬性，得到“翻譯”結果基于規則的方法 －構造編譯器時，事先對產生式的語義規則進行分析，得到屬性計算次序忽略規則的方法 －屬性計算次序僅由分析方法限定。如S-屬性定義可以在自下而上分析時，在歸約前計算。如YACC中的語義動作。10/31/202210《編譯原理與技術》講義語義規則的計算方法分析樹方法10/23/202210《編譯原e.g.3屬性計算次序: 3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=51234567810/31/202211《編譯原理與技術》講義e.g.3屬性計算次序: 3＋4×5E.val=S-屬性定義－語義規則僅包含綜合屬性計算（可以有固有屬性出現）。－適合自底向上計算e.g.語法樹－語法樹與分析樹 語法樹可看作分析樹的濃縮。也稱抽象語法樹。而分析樹可看成具體語法樹。10/31/202212《編譯原理與技術》講義S-屬性定義－語義規則僅包含綜合屬性計算（可以有固有屬性出現SifB-exprthenS1elseS2 語法樹 分析樹語法樹vs.分析樹if-then-elseB-exprS1S2SifB-exprthenS1elseS210/31/202213《編譯原理與技術》講義SifB-exprthen a:=b*-c+b*-c 語法樹分析樹

語法樹vs.分析樹assigna+*b@c*b@cassignEEE+E*EbE@Ea賦值語句cE*EbE@c算符10/31/202214《編譯原理與技術》講義 a:=b*-c+b*-c語法樹DAG（去除了公共子表達式的無環有向圖） a:=b*-c+b*-c

語法樹vs.DAGassigna+*b@c*b@cassigna+*b@c語法樹DAG10/31/202215《編譯原理與技術》講義DAG（去除了公共子表達式的無環有向圖）語法樹vs.DAe.g.4構造表達式的語法樹（DAG） 產生式 語義規則EE1+E2E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)EE1-E2E.nptr:=mknode(‘-’,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)EE1/E2E.nptr:=mknode(‘/’,E1.nptr,E2.nptr)E(E1)E.nptr:=E1.nptrE-E1E.nptr:=mknode(‘@’,E1.nptr,－)EnumberE.nptr:=mkleaf(‘NUM’,number.lex_val)EidE.nptr:=mkleaf(‘ID’,id.entry)10/31/202216《編譯原理與技術》講義e.g.4構造表達式的語法樹（DAG） 產生式 e.g.4構造表達式的語法樹（DAG）

E.nptr－E的語法樹（根結點指針）

mknode(op,left,right)－建立一個表達式語法樹結點，它的運算符為op，左、右運算對象是left和right所指的語法樹。如果建成DAG，則需要檢查是否已存在相應內部結點op，其左右運算對象分別是left和right。若沒有則新建一個。

mkleaf(‘NUM’,number.lex_val)－

mkleaf(‘ID’,id.entry)－ 建立表達式語法樹的葉結點。建DAG也需檢查是否已有相應結點。10/31/202217《編譯原理與技術》講義e.g.4構造表達式的語法樹（DAG） E.nptr－e.g.4構造表達式a+b*-4的屬性結構樹

E.nptrE.nptrE.nptr+E.nptrE.nptr*ab@E.nptr4IDaIDbNUM4@

-*

+

10/31/202218《編譯原理與技術》講義e.g.4構造表達式a+b*-4的屬性結構樹E.nptre.g.4構造表達式a+b*-4的語法樹（DAG）

+

IDa*

IDb@

-NUM410/31/202219《編譯原理與技術》講義e.g.4構造表達式a+b*-4的語法樹（DAG）+L-屬性定義－如果產生式AX1X2…Xn的語義規則只計算 1）A的綜合屬性，或者 2）Xi的繼承屬性，且該屬性僅依賴于產生式右部Xi的左邊符號Xj（j<i）的（綜合）屬性或A的繼承屬性；－S-屬性定義均為L-屬性定義－可按深度優先次序計算 －一種自然的屬性計算次序 －在分析期間完成翻譯。屬性計算與結點建立有聯系；適合于自頂向下和自底向上分析方法。10/31/202220《編譯原理與技術》講義L-屬性定義－如果產生式AX1X2…Xn的語義規則只計算深度優先次序

proceduredfvisit(n:node) begin foreachchildmofn,fromlefttorightdo begin evaluateinheritedattributesofm;

dfvisit(m); end; evaluatesynthesizedattributesofn; end10/31/202221《編譯原理與技術》講義深度優先次序 proceduredfvisit(n:e.g.5非L-屬性定義的語法制導定義 產生式 語義規則 ALM L.i:=l(A.i) M.i:=m(L.s) A.s:=f(M.s) AQR R.i:=r(A.i)

Q.i:=q(R.s) A.s:=f(Q.s)10/31/202222《編譯原理與技術》講義e.g.5非L-屬性定義的語法制導定義 產生式 語義翻譯方案中的動作－語義動作可放在產生式右端任何位置；這也就顯式地給出了動作的執行時刻。（可認為是在深度優先遍歷中的執行時刻）e.g.6將含有+和-運算的中綴表達式翻譯為后綴形式： ETR RaddopT{print(addop.lex_val)}R|

Tnumber{print(number.lex_val)}10/31/202223《編譯原理與技術》講義翻譯方案中的動作－語義動作可放在產生式右端任何位置；這也就顯e.g.6中綴翻譯為后綴：9-4+5ETR9print(9)-Tprint(‘-’)R4print(4)+Tprint(‘+’)5print(5)R1234510/31/202224《編譯原理與技術》講義e.g.6中綴翻譯為后綴：9-4+5ETR9print翻譯方案中的動作－設計翻譯方案時，必須保證動作所引用的屬性值是可用的。 －只有綜合綜合屬性時（S-屬性定義），動作放在產生式末尾； －若有繼承屬性時，動作的放置須保證： －（產生式右部）符號的繼承屬性必須在 此符號前計算； －動作不要引用其右邊符號的綜合屬性； －左部非終結符的綜合屬性一般放在產生式末 尾（確保它引用的屬性均已計算完且可用）10/31/202225《編譯原理與技術》講義翻譯方案中的動作－設計翻譯方案時，必須保證動作所引用的屬性值e.g.7翻譯方案的書寫 SA1A2{A1.in:=1;A2.in:=2} Aa{print(A.in)}改寫為： S

{A1.in:=1}A1{A2.in:=2}A2

Aa{print(A.in)}10/31/202226《編譯原理與技術》講義e.g.7翻譯方案的書寫 SA1A2{A1e.g.8類型說明的語法制導定義（0）產生式 語義規則DTL L.in:=T.typeTint T.type:=integerTreal T.type:=realLL1,id L1.in:=L.in

addtype(id.entry,L.in) Lid addtype(id.entry,L.in)10/31/202227《編譯原理與技術》講義e.g.8類型說明的語法制導定義（0）產生式e.g.8類型說明的語法制導定義（0）－

屬性傳遞DTLL，kL，jiint10/31/202228《編譯原理與技術》講義e.g.8類型說明的語法制導定義（0）－

屬性傳遞DTLLe.g.8類型說明的語法制導定義（1）改寫上述類型聲明文法，使得其中的T成為L的子結點（即產生式右部），可以避免繼承屬性的使用。修改后文法如下： DLTintTrealLL1,idLTid10/31/202229《編譯原理與技術》講義e.g.8類型說明的語法制導定義（1）改寫上述類型聲明文法，e.g.8類型說明的語法制導定義（2）產生式 語義規則

DL

Tint T.type:=integerTreal T.type:=realLL1,id L.in:=L1.in

addtype(id.entry,L1.in)

LTid

addtype(id.entry,T.type); L.in:=T.type10/31/202230《編譯原理與技術》講義e.g.8類型說明的語法制導定義（2）產生式 e.g.8類型說明的語法制導定義（2）

屬性傳遞DTLL，kL，jiint10/31/202231《編譯原理與技術》講義e.g.8類型說明的語法制導定義（2）

屬性傳遞DTLL，ke.g.8類型說明的語法制導定義（3）Pascal語言類型聲明文法如下：DL:TTintTrealLL1,idLid該聲明文法的“問題”在于，L中聲明的變量的類型T處于產生式中L的右邊！若用繼承屬性L.in來傳遞類型信息T.type形成非L－屬性定義。從而無法在完成L分析同時將有關類型信息填入符號表！可以考慮將T作為L的子結點（通過修改文法）來改變這種情況10/31/202232《編譯原理與技術》講義e.g.8類型說明的語法制導定義（3）Pascal語言類型e.g.8類型說明的語法制導定義（4）產生式 語義規則DidL addtype(id.entry,L.in) Tint T.type:=integerTreal T.type:=realL,idL1 L.in:=L1.in

addtype(id.entry,L1.in) L:T L.in:=T.type10/31/202233《編譯原理與技術》講義e.g.8類型說明的語法制導定義（4）產生式 e.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)時，該翻譯方案輸出什么？10/31/202234《編譯原理與技術》講義e.g.9翻譯方案的計算次序 EE+T{priS-屬性定義的自底向上計算拓廣分析棧，即添加屬性棧，包含文法符號的綜合屬性。在歸約實施前，右部各符號的綜合屬性（若有的話）已放在與符號位置對應的屬性棧上，因此，可以先計算獲得左部非終結符的綜合屬性。然后再歸約，這時從分析棧中彈出句柄，（注意，此時改變棧頂top即可）最后，將左部符號連同其屬性放入由top指示的分析棧及屬性棧的位置中。這種屬性棧只能存放綜合屬性。回想YACC中如何做的？10/31/202235《編譯原理與技術》講義S-屬性定義的自底向上計算拓廣分析棧，即添加屬性棧，包含文法如果AXYZ，相關語義規則如下：A.a:=f(X.x,Y.y,Z.z)顯然，X.x在Val[top-2]Y.y在Val[top-1]Z.z在Val[top]A.a在Val[ntop]，ntop=top–|句柄長度|+1Val[ntop]:=f(val[top-2],Val[top-1],Val[top])屬性棧與分析棧ZZ.zYY.yXX.x…………分析棧屬性棧Valtopbottom10/31/202236《編譯原理與技術》講義如果AXYZ，相關屬性棧與分析棧ZZ.zYY.yXX.x…如果AB，相關語義規則如下：A.a:=B.b顯然，B.b在Val[top]A.a在Val[ntop]，ntop=top–1+1=top,即歸約前后棧頂top不變，也即Val[ntop]和Val[top]對應屬性棧同一個單元，所以，可以省略原語義規則對應的屬性棧操作： Val[ntop]:=Val[top]屬性棧與分析棧BB.b…………分析棧屬性棧Valtopbottom10/31/202237《編譯原理與技術》講義如果AB，相關屬性棧與分析棧BB.b…………分析棧屬性棧e.g.10計算表達式的（棧）代碼產生式語義規則代碼段LE‘\n’Print(E.val)Print(Val[top-1])EE1+TE.val:=E1.val+T.valVal[ntop]:=Val[top-2]+Val[top]ETE.val:=T.valTT1*FT.val:=T1.val*F.valVal[ntop]:=Val[top-2]*Val[top]TFT.val:=F.valF(E)F.val:=E.valVal[ntop]:=Val[top-1]FdigitF.val:=digit.lex_val10/31/202238《編譯原理與技術》講義e.g.10計算表達式的（棧）代碼產生式語義規則代碼段L如何在自底向上分析中計算繼承屬性？ －屬性棧上僅能存放綜合屬性 －能否將繼承屬性的引用轉換成綜合屬性？分析棧中符號的繼承屬性 －屬性copy規則 如果，AXY，有語義規則Y.i:=X.s， 翻譯方案可寫為： AX{Y.i:=X.s}Y

自底向上計算繼承屬性10/31/202239《編譯原理與技術》講義如何在自底向上分析中計算繼承屬性？自底向上計算繼承屬性10/自底向上計算繼承屬性－由屬性copy規則可知，Y的繼承屬性Y.i和X.s在屬性棧上同一位置。這樣對屬性Y.i的引用可以轉化為對X.s的引用。若計算Y的綜合屬性Y.s時需要引用Y.i，則此時Y.i（即X.s）就緊鄰在句柄下面；如果Y的句柄形成前，它的某個右部符號需使用Y.i，這時，也可以直接使用Y.i。（Howtouse?）bottom………………XX.s（Y.i）……分析棧屬性棧Valtop句柄（歸約為Y）top－句柄長10/31/202240《編譯原理與技術》講義自底向上計算繼承屬性－由屬性copy規則可知，Y的繼承屬性e.g.11C聲明的翻譯方案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)}對于輸入串：intp,q,r分析過程如下：10/31/202241《編譯原理與技術》講義e.g.11C聲明的翻譯方案DT{L.in 輸入串 分析棧 產生式

intp,q,r p,q,r int p,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

TLLL,id

D

DTL注意：每次歸約成L時，T與L的位置關系－－T就在句柄的下面！10/31/202242《編譯原理與技術》講義 輸入串 分析棧 產生式注意：每次歸約成L時e.g.11C聲明的“代碼段” 產生式 代碼段（只含綜合屬性）

DTL Tint val[ntop]:=integer

Treal val[ntop]:=real LL1,id addtype(val[top],val[top-3]) Lid addtype(val[top],val[top-1])L的繼承屬性L.in10/31/202243《編譯原理與技術》講義e.g.11C聲明的“代碼段” 產生式 代碼段（問題1：繼承屬性的位置在構造編譯器時不可預知（或不固定），如e.g.12產生式 語義規則SaAC

C.i:=A.sSbA

B

C

C.i:=A.sCc C.s:=g(C.i) … 用Cc歸約時，C.i的值可能在val[top-1]或者在val[top-2]的位置上。解決辦法是考慮將其統一。 引入標記非終結符M和產生式M。模擬繼承屬性的計算bottomccABaAb……分析棧1分析棧2top10/31/202244《編譯原理與技術》講義問題1：繼承屬性的位置在構造編譯器時不可預知（或不固定），如產生式 語義規則SaAC

C.i:=A.sSbA

B

M

C

C.i:=M.s M.i:=A.sCc C.s:=g(C.i)M M.s:=M.i

…引入M后，C.i可從句柄c的下面(val[top-1])取得！屬性傳遞： A.s

M.iM.sC.iC.se.g.12引入標記非終結符bottomAMaB…A…b……分析棧1分析棧2topcc10/31/202245《編譯原理與技術》講義產生式 語義規則e.g.12引入標記非終結符bo產生式 代碼段SaAC

SbA

B

M

C

Cc val[ntop]:=g(val[top-1])Mval[ntop]:=val[top-1]…可否將M放在SaAC產生式中？M.i10/31/202246《編譯原理與技術》講義產生式 代碼段M.i10/23/202246《編譯原模擬繼承屬性的計算問題2：語義規則不是簡單的屬性復寫拷貝。e.g.13:將例12中的SaAC語義規則換為： 產生式 語義規則 SaAC C.i:=f(A.s)雖然在例12中引入了M使得“A.s”可在val[top-1]處找到，但在S的兩個產生式中C.i的取值方式不同，導致C.s的計算嘛…這次可以考慮引入標記非終結符N和N10/31/202247《編譯原理與技術》講義模擬繼承屬性的計算問題2：語義規則不是簡單的屬性復寫拷貝。1e.g.13引入標記非終結符N產生式 語義規則 SaA

N

C C.i:=N.s

N.i:=A.s

N

N.s:=f(N.i)

(其他產生式和語義規則不變） (代碼段略）

10/31/202248《編譯原理與技術》講義e.g.13引入標記非終結符N產生式 產生式 語義規則 SB B.ps:=10 S.ht:=B.ht BB1B2 B1.ps:=B.ps B2.ps:=B.ps B.ht:=max(B1.ht,B2.ht) BB1subB2 B1.ps:=B.ps B2.ps:=shrink(B.ps) B.ht:=disp(B1.ht,B2.ht) Btext B.ht:=text.h×B.pse.g.14文字排版的語法制導定義10/31/202249《編譯原理與技術》講義 產生式 語義規則e.g.14文字排版的語法制導S：S.ht，綜合屬性；待排公式的整體高度B：B.ps，繼承屬性；公式（文本）中字體“點”的大小B.ht，綜合屬性；公式排版高度text：text.h，文本高度max：求兩個排版公式的最大高度shrink(B)：將點大小縮小為B的30％disp(B1.ht，B2.ht)：向下調整B2的位置文字排版中的符號屬性E1Val10/31/202250《編譯原理與技術》講義S：S.ht，綜合屬性；待排公式的整體高度文字排版中的符文字排版的翻譯方案（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)} Btext {B.ht:=text.h×B.ps}10/31/202251《編譯原理與技術》講義文字排版的翻譯方案（0） S {B.文字排版中引入標記符號為了自底向上計算：Btext {B.ht:=text.h×B.ps}必須確定繼承屬性B.ps的（“屬性棧”）位置。為此引入標記非終結符L、M和N及其屬性，包括相應的空產生式和有關屬性規則。這樣B.ps即可在緊靠“句柄”text下方的位置上找到。(L的綜合屬性置為B.ps的初值)SL

BBB1MB2BB1subNB2texttext.hLL.s=10分析棧屬性棧topbottom10/31/202252《編譯原理與技術》講義文字排版中引入標記符號為了自底向上計算：texttext.hSL {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)}Btext {B.ht:=text.h×B.ps}文字排版的翻譯方案（1）10/31/202253《編譯原理與技術》講義SL {B.ps:=L.s} 產生式 代碼段SL

B val[ntop]:=val[top]BB1M

B2val[ntop]:=max(val[top-2],val[top])BB1subNB2val[ntop]:=disp(val[top-3],val[top])Btext val[ntop]:=val[top]×val[top-1]L val[ntop]:=10M val[ntop]:=val[top-1]N val[ntop]:=shrink(val[top-2])10/31/202254《編譯原理與技術》講義產生式 代碼段10/23/202254《編譯原理與技（L-屬性定義）自頂向下翻譯刪除翻譯方案中的左遞歸

AA1Y{A.a:=g(A1.a,Y.y)} AX{A.a:=f(X.x)}消除左遞歸： AX {R.i:=f(X.x)}//傳遞“左”運算量 R{A.a:=R.s} RY {R1.i:=g(R.i,Y.y)} R1 {R.s:=R1.s} R

{R.s:=R.i}//返回結果10/31/202255《編譯原理與技術》講義（L-屬性定義）自頂向下翻譯刪除翻譯方案中的左遞歸10/23輸入串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.s10/31/202256《編譯原理與技術》講義輸入串XY1Y2的翻譯XA.a:=f(X.x)A.ae.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:=mkleaf(‘ID’,id.entry)}10/31/202257《編譯原理與技術》講義e.g.15刪除翻譯方案中左遞歸EE1+T{刪除左遞歸后：引入非終結符RET{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}//返回最終語法樹（其余略）10/31/202258《編譯原理與技術》講義刪除左遞歸后：引入非終結符R10/23/202258《編譯原（遞歸下降）預測翻譯器的設計為每個非終結符A構造用于分析和屬性計算的函數（注意，在遞歸下降的語法分析中構造的僅是過程），這樣的函數構成如下： －參數：符號A的繼承屬性 －返回值：符號A的綜合屬性（記錄） －局部變量：A的產生式中每個符號的屬性均有對應的局部量（A的繼承屬性除外） －函數體形式為：（類似遞歸分析過程） －根據輸入符號決定產生式的選擇； －對每個可能選擇的產生式從左自右分析并計算屬性（執行語義動作） 10/31/202259《編譯原理與技術》講義（遞歸下降）預測翻譯器的設計為每個非終結符A構造用于分析和屬 －對每個可能選擇的產生式從左自右分析并計算屬性（執行語義動作）： （1）終結符X，將X.x保存在相應的局部量中（如果有的話），調用match(X); （2）非終結符B，產生賦值c:=B(b1,b2,…bn)，c和bi分別是B的綜合屬性和繼承屬性對應的局部變量； （3）語義動作，將代碼直接拷貝到函數體中，而其中屬性出現改為局部量的引用； （4）函數結尾：returnA的綜合屬性。10/31/202260《編譯原理與技術》講義 －對每個可能選擇的產生式從左自右分析并計算屬性（執行語e.g.16遞歸翻譯函數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}10/31/202261《編譯原理與技術》講義e.g.16遞歸翻譯函數R+10/23/202261編譯原理與技術10/31/202262《編譯原理與技術》講義編譯原理與技術10/23/20221《編譯原理與技術》講義語法制導翻譯屬性文法S-屬性定義L-屬性定義語法制導定義與翻譯方案自底向上翻譯S-屬性定義自底向上計算自底向上計算繼承屬性自頂向下翻譯10/31/202263《編譯原理與技術》講義語法制導翻譯屬性文法10/23/20222《編譯原理與技術》屬性文法屬性文法（AttributedGrammar）

上下文無關文法+屬性+屬性計算規則屬性－用來描述文法符號的語義特征，如常量的“值”、變量的類型和存儲位置等。e.g.二義性表達式文法G，非終結符E有屬性E.val（表達式的值）EE‘+’E|

E‘*’E|‘(‘E‘)’|number屬性計算規則（語義規則）與產生式相關聯的反映文法符號屬性之間關系的“規則”10/31/202264《編譯原理與技術》講義屬性文法屬性文法（AttributedGrammar）10屬性文法語法制導定義（文法＋屬性＋語義規則）

語義規則僅表明屬性間“抽象”關系，不涉及具體翻譯實現細節，如計算次序等。翻譯方案（文法＋屬性＋語義動作）語義規則－即語義動作，可體現若干實現的細節。10/31/202265《編譯原理與技術》講義屬性文法10/23/20224《編譯原理與技術》講義e.g.1算術表達式的計算器 產生式 語法制導定義EE1‘+’E2E.val:=E1.val+E2.valEE1‘*’E2E.val:=E1.val*E2.valE’(‘E1‘)’E.val:=E1.valEnumberE.val:=number.lex_val10/31/202266《編譯原理與技術》講義e.g.1算術表達式的計算器 產生式 語法制導定義e.g.1算術表達式的計算器 產生式 翻譯方案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}10/31/202267《編譯原理與技術》講義e.g.1算術表達式的計算器 產生式 翻譯方案10屬性文法屬性的分類若產生式AX1X2…Xn，與之相關的屬性計算規則

b:=f(c1,c2,…)－如果屬性b是產生式左部符號A的屬性則稱其為A的綜合屬性；－如果屬性b是產生式右部符號Xi的屬性則稱其為Xi的繼承屬性；－c1,c2,…一般是產生式右部其它符號的(綜合)屬性或A的繼承屬性；－固有屬性：終結符僅有的屬性。如number.lex_val。通常由詞法程序提供。10/31/202268《編譯原理與技術》講義屬性文法屬性的分類10/23/20227《編譯原理與技術》講A.bX1.c1X2.c2X…綜合屬性A.b的計算A的繼承屬性AX1.c1X2.c2…繼承屬性Xk.b的計算A的繼承屬性Xk.bX屬性依賴圖10/31/202269《編譯原理與技術》講義A.bX1.c1X2.c2X…綜合屬性A.b的計算Ae.g.2屬性依賴圖: 3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=510/31/202270《編譯原理與技術》講義e.g.2屬性依賴圖: 3＋4×5E.val=語義規則的計算方法分析樹方法 －為輸入串建立分析樹 －由語義規則建立屬性依賴圖（沒有屬性循環依賴的） －對依賴圖進行拓撲排序，得到屬性計算次序 －依次計算屬性，得到“翻譯”結果基于規則的方法 －構造編譯器時，事先對產生式的語義規則進行分析，得到屬性計算次序忽略規則的方法 －屬性計算次序僅由分析方法限定。如S-屬性定義可以在自下而上分析時，在歸約前計算。如YACC中的語義動作。10/31/202271《編譯原理與技術》講義語義規則的計算方法分析樹方法10/23/202210《編譯原e.g.3屬性計算次序: 3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=51234567810/31/202272《編譯原理與技術》講義e.g.3屬性計算次序: 3＋4×5E.val=S-屬性定義－語義規則僅包含綜合屬性計算（可以有固有屬性出現）。－適合自底向上計算e.g.語法樹－語法樹與分析樹 語法樹可看作分析樹的濃縮。也稱抽象語法樹。而分析樹可看成具體語法樹。10/31/202273《編譯原理與技術》講義S-屬性定義－語義規則僅包含綜合屬性計算（可以有固有屬性出現SifB-exprthenS1elseS2 語法樹 分析樹語法樹vs.分析樹if-then-elseB-exprS1S2SifB-exprthenS1elseS210/31/202274《編譯原理與技術》講義SifB-exprthen a:=b*-c+b*-c 語法樹分析樹

語法樹vs.分析樹assigna+*b@c*b@cassignEEE+E*EbE@Ea賦值語句cE*EbE@c算符10/31/202275《編譯原理與技術》講義 a:=b*-c+b*-c語法樹DAG（去除了公共子表達式的無環有向圖） a:=b*-c+b*-c

語法樹vs.DAGassigna+*b@c*b@cassigna+*b@c語法樹DAG10/31/202276《編譯原理與技術》講義DAG（去除了公共子表達式的無環有向圖）語法樹vs.DAe.g.4構造表達式的語法樹（DAG） 產生式 語義規則EE1+E2E.nptr:=mknode(‘+’,E1.nptr,E2.nptr)EE1-E2E.nptr:=mknode(‘-’,E1.nptr,E2.nptr)EE1*E2E.nptr:=mknode(‘*’,E1.nptr,E2.nptr)EE1/E2E.nptr:=mknode(‘/’,E1.nptr,E2.nptr)E(E1)E.nptr:=E1.nptrE-E1E.nptr:=mknode(‘@’,E1.nptr,－)EnumberE.nptr:=mkleaf(‘NUM’,number.lex_val)EidE.nptr:=mkleaf(‘ID’,id.entry)10/31/202277《編譯原理與技術》講義e.g.4構造表達式的語法樹（DAG） 產生式 e.g.4構造表達式的語法樹（DAG）

E.nptr－E的語法樹（根結點指針）

mknode(op,left,right)－建立一個表達式語法樹結點，它的運算符為op，左、右運算對象是left和right所指的語法樹。如果建成DAG，則需要檢查是否已存在相應內部結點op，其左右運算對象分別是left和right。若沒有則新建一個。

mkleaf(‘NUM’,number.lex_val)－

mkleaf(‘ID’,id.entry)－ 建立表達式語法樹的葉結點。建DAG也需檢查是否已有相應結點。10/31/202278《編譯原理與技術》講義e.g.4構造表達式的語法樹（DAG） E.nptr－e.g.4構造表達式a+b*-4的屬性結構樹

E.nptrE.nptrE.nptr+E.nptrE.nptr*ab@E.nptr4IDaIDbNUM4@

-*

+

10/31/202279《編譯原理與技術》講義e.g.4構造表達式a+b*-4的屬性結構樹E.nptre.g.4構造表達式a+b*-4的語法樹（DAG）

+

IDa*

IDb@

-NUM410/31/202280《編譯原理與技術》講義e.g.4構造表達式a+b*-4的語法樹（DAG）+L-屬性定義－如果產生式AX1X2…Xn的語義規則只計算 1）A的綜合屬性，或者 2）Xi的繼承屬性，且該屬性僅依賴于產生式右部Xi的左邊符號Xj（j<i）的（綜合）屬性或A的繼承屬性；－S-屬性定義均為L-屬性定義－可按深度優先次序計算 －一種自然的屬性計算次序 －在分析期間完成翻譯。屬性計算與結點建立有聯系；適合于自頂向下和自底向上分析方法。10/31/202281《編譯原理與技術》講義L-屬性定義－如果產生式AX1X2…Xn的語義規則只計算深度優先次序

proceduredfvisit(n:node) begin foreachchildmofn,fromlefttorightdo begin evaluateinheritedattributesofm;

dfvisit(m); end; evaluatesynthesizedattributesofn; end10/31/202282《編譯原理與技術》講義深度優先次序 proceduredfvisit(n:e.g.5非L-屬性定義的語法制導定義 產生式 語義規則 ALM L.i:=l(A.i) M.i:=m(L.s) A.s:=f(M.s) AQR R.i:=r(A.i)

Q.i:=q(R.s) A.s:=f(Q.s)10/31/202283《編譯原理與技術》講義e.g.5非L-屬性定義的語法制導定義 產生式 語義翻譯方案中的動作－語義動作可放在產生式右端任何位置；這也就顯式地給出了動作的執行時刻。（可認為是在深度優先遍歷中的執行時刻）e.g.6將含有+和-運算的中綴表達式翻譯為后綴形式： ETR RaddopT{print(addop.lex_val)}R|

Tnumber{print(number.lex_val)}10/31/202284《編譯原理與技術》講義翻譯方案中的動作－語義動作可放在產生式右端任何位置；這也就顯e.g.6中綴翻譯為后綴：9-4+5ETR9print(9)-Tprint(‘-’)R4print(4)+Tprint(‘+’)5print(5)R1234510/31/202285《編譯原理與技術》講義e.g.6中綴翻譯為后綴：9-4+5ETR9print翻譯方案中的動作－設計翻譯方案時，必須保證動作所引用的屬性值是可用的。 －只有綜合綜合屬性時（S-屬性定義），動作放在產生式末尾； －若有繼承屬性時，動作的放置須保證： －（產生式右部）符號的繼承屬性必須在 此符號前計算； －動作不要引用其右邊符號的綜合屬性； －左部非終結符的綜合屬性一般放在產生式末 尾（確保它引用的屬性均已計算完且可用）10/31/202286《編譯原理與技術》講義翻譯方案中的動作－設計翻譯方案時，必須保證動作所引用的屬性值e.g.7翻譯方案的書寫 SA1A2{A1.in:=1;A2.in:=2} Aa{print(A.in)}改寫為： S

{A1.in:=1}A1{A2.in:=2}A2

Aa{print(A.in)}10/31/202287《編譯原理與技術》講義e.g.7翻譯方案的書寫 SA1A2{A1e.g.8類型說明的語法制導定義（0）產生式 語義規則DTL L.in:=T.typeTint T.type:=integerTreal T.type:=realLL1,id L1.in:=L.in

addtype(id.entry,L.in) Lid addtype(id.entry,L.in)10/31/202288《編譯原理與技術》講義e.g.8類型說明的語法制導定義（0）產生式e.g.8類型說明的語法制導定義（0）－

屬性傳遞DTLL，kL，jiint10/31/202289《編譯原理與技術》講義e.g.8類型說明的語法制導定義（0）－

屬性傳遞DTLLe.g.8類型說明的語法制導定義（1）改寫上述類型聲明文法，使得其中的T成為L的子結點（即產生式右部），可以避免繼承屬性的使用。修改后文法如下： DLTintTrealLL1,idLTid10/31/202290《編譯原理與技術》講義e.g.8類型說明的語法制導定義（1）改寫上述類型聲明文法，e.g.8類型說明的語法制導定義（2）產生式 語義規則

DL

Tint T.type:=integerTreal T.type:=realLL1,id L.in:=L1.in

addtype(id.entry,L1.in)

LTid

addtype(id.entry,T.type); L.in:=T.type10/31/202291《編譯原理與技術》講義e.g.8類型說明的語法制導定義（2）產生式 e.g.8類型說明的語法制導定義（2）

屬性傳遞DTLL，kL，jiint10/31/202292《編譯原理與技術》講義e.g.8類型說明的語法制導定義（2）

屬性傳遞DTLL，ke.g.8類型說明的語法制導定義（3）Pascal語言類型聲明文法如下：DL:TTintTrealLL1,idLid該聲明文法的“問題”在于，L中聲明的變量的類型T處于產生式中L的右邊！若用繼承屬性L.in來傳遞類型信息T.type形成非L－屬性定義。從而無法在完成L分析同時將有關類型信息填入符號表！可以考慮將T作為L的子結點（通過修改文法）來改變這種情況10/31/202293《編譯原理與技術》講義e.g.8類型說明的語法制導定義（3）Pascal語言類型e.g.8類型說明的語法制導定義（4）產生式 語義規則DidL addtype(id.entry,L.in) Tint T.type:=integerTreal T.type:=realL,idL1 L.in:=L1.in

addtype(id.entry,L1.in) L:T L.in:=T.type10/31/202294《編譯原理與技術》講義e.g.8類型說明的語法制導定義（4）產生式 e.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)時，該翻譯方案輸出什么？10/31/202295《編譯原理與技術》講義e.g.9翻譯方案的計算次序 EE+T{priS-屬性定義的自底向上計算拓廣分析棧，即添加屬性棧，包含文法符號的綜合屬性。在歸約實施前，右部各符號的綜合屬性（若有的話）已放在與符號位置對應的屬性棧上，因此，可以先計算獲得左部非終結符的綜合屬性。然后再歸約，這時從分析棧中彈出句柄，（注意，此時改變棧頂top即可）最后，將左部符號連同其屬性放入由top指示的分析棧及屬性棧的位置中。這種屬性棧只能存放綜合屬性。回想YACC中如何做的？10/31/202296《編譯原理與技術》講義S-屬性定義的自底向上計算拓廣分析棧，即添加屬性棧，包含文法如果AXYZ，相關語義規則如下：A.a:=f(X.x,Y.y,Z.z)顯然，X.x在Val[top-2]Y.y在Val[top-1]Z.z在Val[top]A.a在Val[ntop]，ntop=top–|句柄長度|+1Val[ntop]:=f(val[top-2],Val[top-1],Val[top])屬性棧與分析棧ZZ.zYY.yXX.x…………分析棧屬性棧Valtopbottom10/31/202297《編譯原理與技術》講義如果AXYZ，相關屬性棧與分析棧ZZ.zYY.yXX.x…如果AB，相關語義規則如下：A.a:=B.b顯然，B.b在Val[top]A.a在Val[ntop]，ntop=top–1+1=top,即歸約前后棧頂top不變，也即Val[ntop]和Val[top]對應屬性棧同一個單元，所以，可以省略原語義規則對應的屬性棧操作： Val[ntop]:=Val[top]屬性棧與分析棧BB.b…………分析棧屬性棧Valtopbottom10/31/202298《編譯原理與技術》講義如果AB，相關屬性棧與分析棧BB.b…………分析棧屬性棧e.g.10計算表達式的（棧）代碼產生式語義規則代碼段LE‘\n’Print(E.val)Print(Val[top-1])EE1+TE.val:=E1.val+T.valVal[ntop]:=Val[top-2]+Val[top]ETE.val:=T.valTT1*FT.val:=T1.val*F.valVal[ntop]:=Val[top-2]*Val[top]TFT.val:=F.valF(E)F.val:=E.valVal[ntop]:=Val[top-1]FdigitF.val:=digit.lex_val10/31/202299《編譯原理與技術》講義e.g.10計算表達式的（棧）代碼產生式語義規則代碼段L如何在自底向上分析中計算繼承屬性？ －屬性棧上僅能存放綜合屬性 －能否將繼承屬性的引用轉換成綜合屬性？分析棧中符號的繼承屬性 －屬性copy規則 如果，AXY，有語義規則Y.i:=X.s， 翻譯方案可寫為： AX{Y.i:=X.s}Y

自底向上計算繼承屬性10/31/2022100《編譯原理與技術》講義如何在自底向上分析中計算繼承屬性？自底向上計算繼承屬性10/自底向上計算繼承屬性－由屬性copy規則可知，Y的繼承屬性Y.i和X.s在屬性棧上同一位置。這樣對屬性Y.i的引用可以轉化為對X.s的引用。若計算Y的綜合屬性Y.s時需要引用Y.i，則此時Y.i（即X.s）就緊鄰在句柄下面；如果Y的句柄形成前，它的某個右部符號需使用Y.i，這時，也可以直接使用Y.i。（Howtouse?）bottom………………XX.s（Y.i）……分析棧屬性棧Valtop句柄（歸約為Y）top－句柄長10/31/2022101《編譯原理與技術》講義自底向上計算繼承屬性－由屬性copy規則可知，Y的繼承屬性e.g.11C聲明的翻譯方案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)}對于輸入串：intp,q,r分析過程如下：10/31/2022102《編譯原理與技術》講義e.g.11C聲明的翻譯方案DT{L.in 輸入串 分析棧 產生式

intp,q,r p,q,r int p,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

TLLL,id

D

DTL注意：每次歸約成L時，T與L的位置關系－－T就在句柄的下面！10/31/2022103《編譯原理與技術》講義 輸入串 分析棧 產生式注意：每次歸約成L時e.g.11C聲明的“代碼段” 產生式 代碼段（只含綜合屬性）

DTL Tint val[ntop]:=integer