編譯原理與技術(shù)課件

2023/8/2《編譯原理與技術(shù)》講義1語(yǔ)法制導(dǎo)翻譯屬性文法S-屬性定義L-屬性定義語(yǔ)法制導(dǎo)定義與翻譯方案自底向上翻譯S-屬性定義自底向上計(jì)算自底向上計(jì)算繼承屬性自頂向下翻譯2023/8/2《編譯原理與技術(shù)》講義1語(yǔ)法制導(dǎo)翻譯屬性文法2023/8/2《編譯原理與技術(shù)》講義2屬性文法屬性文法（AttributedGrammar）

上下文無(wú)關(guān)文法+屬性+屬性計(jì)算規(guī)則屬性－用來(lái)描述文法符號(hào)的語(yǔ)義特征，如常量的“值”、變量的類型和存儲(chǔ)位置等。e.g.二義性表達(dá)式文法G，非終結(jié)符E有屬性E.val（表達(dá)式的值）EE‘+’E|

E‘*’E|‘(‘E‘)’|number

屬性計(jì)算規(guī)則（語(yǔ)義規(guī)則）與產(chǎn)生式相關(guān)聯(lián)的反映文法符號(hào)屬性之間關(guān)系的“規(guī)則”2023/8/2《編譯原理與技術(shù)》講義2屬性文法屬性文法（A2023/8/2《編譯原理與技術(shù)》講義3屬性文法語(yǔ)法制導(dǎo)定義（文法＋屬性＋語(yǔ)義規(guī)則）

語(yǔ)義規(guī)則僅表明屬性間“抽象”關(guān)系，不涉及具體翻譯實(shí)現(xiàn)細(xì)節(jié)，如計(jì)算次序等。翻譯方案（文法＋屬性＋語(yǔ)義動(dòng)作）語(yǔ)義規(guī)則－即語(yǔ)義動(dòng)作，可體現(xiàn)若干實(shí)現(xiàn)的細(xì)節(jié)。2023/8/2《編譯原理與技術(shù)》講義3屬性文法2023/8/2《編譯原理與技術(shù)》講義4e.g.1算術(shù)表達(dá)式的計(jì)算器

產(chǎn)生式 語(yǔ)法制導(dǎo)定義EE1‘+’E2E.val:=E1.val+E2.valEE1‘*’E2E.val:=E1.val*E2.valE’(‘E1‘)’E.val:=E1.valEnumberE.val:=number.lex_val2023/8/2《編譯原理與技術(shù)》講義4e.g.1算術(shù)表達(dá)式2023/8/2《編譯原理與技術(shù)》講義5e.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}2023/8/2《編譯原理與技術(shù)》講義5e.g.1算術(shù)表達(dá)式2023/8/2《編譯原理與技術(shù)》講義6屬性文法屬性的分類若產(chǎn)生式AX1X2…Xn，與之相關(guān)的屬性計(jì)算規(guī)則

b:=f(c1,c2,…)－如果屬性b是產(chǎn)生式左部符號(hào)A的屬性則稱其為A的綜合屬性；－如果屬性b是產(chǎn)生式右部符號(hào)Xi的屬性則稱其為Xi的繼承屬性；－c1,c2,…一般是產(chǎn)生式右部其它符號(hào)的(綜合)屬性或A的繼承屬性；－固有屬性：終結(jié)符僅有的屬性。如number.lex_val。通常由詞法程序提供。2023/8/2《編譯原理與技術(shù)》講義6屬性文法屬性的分類2023/8/2《編譯原理與技術(shù)》講義7A.bX1.c1X2.c2Xn.cn…綜合屬性A.b的計(jì)算A的繼承屬性AX1.c1X2.c2…繼承屬性Xk.b的計(jì)算A的繼承屬性Xk.bXn.cn屬性依賴圖2023/8/2《編譯原理與技術(shù)》講義7A.bX1.c1X22023/8/2《編譯原理與技術(shù)》講義8e.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=52023/8/2《編譯原理與技術(shù)》講義8e.g.2屬性依2023/8/2《編譯原理與技術(shù)》講義9語(yǔ)義規(guī)則的計(jì)算方法分析樹方法 －為輸入串建立分析樹 －由語(yǔ)義規(guī)則建立屬性依賴圖（沒有屬性循環(huán)依賴的） －對(duì)依賴圖進(jìn)行拓?fù)渑判?，得到屬性?jì)算次序 －依次計(jì)算屬性，得到“翻譯”結(jié)果基于規(guī)則的方法 －構(gòu)造編譯器時(shí)，事先對(duì)產(chǎn)生式的語(yǔ)義規(guī)則進(jìn)行分析，得到屬性計(jì)算次序忽略規(guī)則的方法 －屬性計(jì)算次序僅由分析方法限定。如S-屬性定義可以在自下而上分析時(shí)，在歸約前計(jì)算。如YACC中的語(yǔ)義動(dòng)作。2023/8/2《編譯原理與技術(shù)》講義9語(yǔ)義規(guī)則的計(jì)算方法分2023/8/2《編譯原理與技術(shù)》講義10e.g.3屬性計(jì)算次序: 3＋4×5E.val=23E.val=3+E.val=20number.lex_val=3E.val=4×E.val=5number.lex_val=4number.lex_val=5123456782023/8/2《編譯原理與技術(shù)》講義10e.g.3屬性2023/8/2《編譯原理與技術(shù)》講義11S-屬性定義－語(yǔ)義規(guī)則僅包含綜合屬性計(jì)算（可以有固有屬性出現(xiàn)）。－適合自底向上計(jì)算e.g.語(yǔ)法樹－語(yǔ)法樹與分析樹 語(yǔ)法樹可看作分析樹的濃縮。也稱抽象語(yǔ)法樹。而分析樹可看成具體語(yǔ)法樹。2023/8/2《編譯原理與技術(shù)》講義11S-屬性定義－語(yǔ)義2023/8/2《編譯原理與技術(shù)》講義12SifB-exprthenS1elseS2

語(yǔ)法樹 分析樹語(yǔ)法樹vs.分析樹if-then-elseB-exprS1S2SifB-exprthenS1elseS22023/8/2《編譯原理與技術(shù)》講義122023/8/2《編譯原理與技術(shù)》講義13 a:=b*-c+b*-c

語(yǔ)法樹分析樹

語(yǔ)法樹vs.分析樹assigna+*b@c*b@cassignEEE+E*EbE@Ea賦值語(yǔ)句cE*EbE@c算符2023/8/2《編譯原理與技術(shù)》講義13 a2023/8/2《編譯原理與技術(shù)》講義14DAG（去除了公共子表達(dá)式的無(wú)環(huán)有向圖）

a:=b*-c+b*-c

語(yǔ)法樹vs.DAGassigna+*b@c*b@cassigna+*b@c語(yǔ)法樹DAG2023/8/2《編譯原理與技術(shù)》講義14DAG（去除了公共2023/8/2《編譯原理與技術(shù)》講義15e.g.4構(gòu)造表達(dá)式的語(yǔ)法樹（DAG）

產(chǎn)生式 語(yǔ)義規(guī)則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)2023/8/2《編譯原理與技術(shù)》講義15e.g.4構(gòu)造表2023/8/2《編譯原理與技術(shù)》講義16e.g.4構(gòu)造表達(dá)式的語(yǔ)法樹（DAG）

E.nptr

－E的語(yǔ)法樹（根結(jié)點(diǎn)指針）

mknode(op,left,right)－建立一個(gè)表達(dá)式語(yǔ)法樹結(jié)點(diǎn)，它的運(yùn)算符為op，左、右運(yùn)算對(duì)象是left和right所指的語(yǔ)法樹。如果建成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á)式語(yǔ)法樹的葉結(jié)點(diǎn)。建DAG也需檢查是否已有相應(yīng)結(jié)點(diǎn)。2023/8/2《編譯原理與技術(shù)》講義16e.g.4構(gòu)造表2023/8/2《編譯原理與技術(shù)》講義17e.g.4構(gòu)造表達(dá)式a+b*-4的屬性結(jié)構(gòu)樹

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

-*

+

2023/8/2《編譯原理與技術(shù)》講義17e.g.4構(gòu)造表2023/8/2《編譯原理與技術(shù)》講義18e.g.4構(gòu)造表達(dá)式a+b*-4的語(yǔ)法樹（DAG）

+

IDa*

IDb@

-NUM42023/8/2《編譯原理與技術(shù)》講義18e.g.4構(gòu)造表2023/8/2《編譯原理與技術(shù)》講義19L-屬性定義－如果產(chǎn)生式AX1X2…Xn的語(yǔ)義規(guī)則只計(jì)算

1）A的綜合屬性，或者

2）Xi的繼承屬性，且該屬性僅依賴于產(chǎn)生式右部Xi的左邊符號(hào)Xj（j<i）的（綜合）屬性或A的繼承屬性；－S-屬性定義均為L(zhǎng)-屬性定義－可按深度優(yōu)先次序計(jì)算 －一種自然的屬性計(jì)算次序 －在分析期間完成翻譯。屬性計(jì)算與結(jié)點(diǎn)建立有聯(lián)系；適合于自頂向下和自底向上分析方法。2023/8/2《編譯原理與技術(shù)》講義19L-屬性定義－如果2023/8/2《編譯原理與技術(shù)》講義20深度優(yōu)先次序

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

dfvisit(m); end; evaluatesynthesizedattributesofn; end2023/8/2《編譯原理與技術(shù)》講義20深度優(yōu)先次序 pr2023/8/2《編譯原理與技術(shù)》講義21e.g.5非L-屬性定義的語(yǔ)法制導(dǎo)定義

產(chǎn)生式 語(yǔ)義規(guī)則

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)2023/8/2《編譯原理與技術(shù)》講義21e.g.5非L-2023/8/2《編譯原理與技術(shù)》講義22翻譯方案中的動(dòng)作－語(yǔ)義動(dòng)作可放在產(chǎn)生式右端任何位置；這也就顯式地給出了動(dòng)作的執(zhí)行時(shí)刻。（可認(rèn)為是在深度優(yōu)先遍歷中的執(zhí)行時(shí)刻）e.g.6將含有+和-運(yùn)算的中綴表達(dá)式翻譯為后綴形式：

ETR RaddopT{print(addop.lex_val)}R|

Tnumber{print(number.lex_val)}2023/8/2《編譯原理與技術(shù)》講義22翻譯方案中的動(dòng)作－2023/8/2《編譯原理與技術(shù)》講義23e.g.6中綴翻譯為后綴：9-4+5ETR9print(9)-Tprint(‘-’)R4print(4)+Tprint(‘+’)5print(5)R123452023/8/2《編譯原理與技術(shù)》講義23e.g.6中綴2023/8/2《編譯原理與技術(shù)》講義24翻譯方案中的動(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ì)算完且可用）2023/8/2《編譯原理與技術(shù)》講義24翻譯方案中的動(dòng)作－2023/8/2《編譯原理與技術(shù)》講義25e.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)}2023/8/2《編譯原理與技術(shù)》講義25e.g.7翻譯方2023/8/2《編譯原理與技術(shù)》講義26e.g.8類型說(shuō)明的語(yǔ)法制導(dǎo)定義（0）

產(chǎn)生式 語(yǔ)義規(guī)則

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)2023/8/2《編譯原理與技術(shù)》講義26e.g.8類型說(shuō)2023/8/2《編譯原理與技術(shù)》講義27e.g.8類型說(shuō)明的語(yǔ)法制導(dǎo)定義（0）－

屬性傳遞DTLL，kL，jiint2023/8/2《編譯原理與技術(shù)》講義27e.g.8類型說(shuō)2023/8/2《編譯原理與技術(shù)》講義28e.g.8類型說(shuō)明的語(yǔ)法制導(dǎo)定義（1）改寫上述類型聲明文法，使得其中的T成為L(zhǎng)的子結(jié)點(diǎn)（即產(chǎn)生式右部），可以避免繼承屬性的使用。修改后文法如下：

DLTintTrealLL1,idLTid2023/8/2《編譯原理與技術(shù)》講義28e.g.8類型說(shuō)明2023/8/2《編譯原理與技術(shù)》講義29e.g.8類型說(shuō)明的語(yǔ)法制導(dǎo)定義（2）

產(chǎn)生式 語(yǔ)義規(guī)則

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.type2023/8/2《編譯原理與技術(shù)》講義29e.g.8類型說(shuō)明2023/8/2《編譯原理與技術(shù)》講義30e.g.8類型說(shuō)明的語(yǔ)法制導(dǎo)定義（2）

屬性傳遞DTLL，kL，jiint2023/8/2《編譯原理與技術(shù)》講義30e.g.8類型說(shuō)明2023/8/2《編譯原理與技術(shù)》講義31e.g.8類型說(shuō)明的語(yǔ)法制導(dǎo)定義（3）Pascal語(yǔ)言類型聲明文法如下：

DL:TTintTrealLL1,idLid該聲明文法的“問(wèn)題”在于，L中聲明的變量的類型T處于產(chǎn)生式中L的右邊！若用繼承屬性L.in來(lái)傳遞類型信息T.type形成非L－屬性定義。從而無(wú)法在完成L分析同時(shí)將有關(guān)類型信息填入符號(hào)表！可以考慮將T作為L(zhǎng)的子結(jié)點(diǎn)（通過(guò)修改文法）來(lái)改變這種情況2023/8/2《編譯原理與技術(shù)》講義31e.g.8類型說(shuō)2023/8/2《編譯原理與技術(shù)》講義32e.g.8類型說(shuō)明的語(yǔ)法制導(dǎo)定義（4）

產(chǎn)生式 語(yǔ)義規(guī)則

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.type2023/8/2《編譯原理與技術(shù)》講義32e.g.8類型說(shuō)2023/8/2《編譯原理與技術(shù)》講義33e.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í)，該翻譯方案輸出什么？2023/8/2《編譯原理與技術(shù)》講義33e.g.9翻譯方2023/8/2《編譯原理與技術(shù)》講義34S-屬性定義的自底向上計(jì)算拓廣分析棧，即添加屬性棧，包含文法符號(hào)的綜合屬性。在歸約實(shí)施前，右部各符號(hào)的綜合屬性（若有的話）已放在與符號(hào)位置對(duì)應(yīng)的屬性棧上，因此，可以先計(jì)算獲得左部非終結(jié)符的綜合屬性。然后再歸約，這時(shí)從分析棧中彈出句柄，（注意，此時(shí)改變棧頂top即可）最后，將左部符號(hào)連同其屬性放入由top指示的分析棧及屬性棧的位置中。這種屬性棧只能存放綜合屬性。回想YACC中如何做的？2023/8/2《編譯原理與技術(shù)》講義34S-屬性定義的自底2023/8/2《編譯原理與技術(shù)》講義35如果AXYZ，相關(guān)語(yǔ)義規(guī)則如下：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–|句柄長(zhǎng)度|+1Val[ntop]:=f(val[top-2],Val[top-1],Val[top])屬性棧與分析棧ZZ.zYY.yXX.x…………分析棧屬性棧Valtopbottom2023/8/2《編譯原理與技術(shù)》講義35如果AXYZ，相2023/8/2《編譯原理與技術(shù)》講義36如果AB，相關(guān)語(yǔ)義規(guī)則如下：A.a:=B.b顯然，B.b在Val[top]A.a在Val[ntop]，ntop=top–1+1=top,即歸約前后棧頂top不變，也即Val[ntop]和Val[top]對(duì)應(yīng)屬性棧同一個(gè)單元，所以，可以省略原語(yǔ)義規(guī)則對(duì)應(yīng)的屬性棧操作：

Val[ntop]:=Val[top]屬性棧與分析棧BB.b…………分析棧屬性棧Valtopbottom2023/8/2《編譯原理與技術(shù)》講義36如果AB，相關(guān)2023/8/2《編譯原理與技術(shù)》講義37e.g.10計(jì)算表達(dá)式的（棧）代碼產(chǎn)生式語(yǔ)義規(guī)則代碼段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_val2023/8/2《編譯原理與技術(shù)》講義37e.g.10計(jì)算2023/8/2《編譯原理與技術(shù)》講義38如何在自底向上分析中計(jì)算繼承屬性？ －屬性棧上僅能存放綜合屬性 －能否將繼承屬性的引用轉(zhuǎn)換成綜合屬性？分析棧中符號(hào)的繼承屬性 －屬性copy規(guī)則 如果，AXY，有語(yǔ)義規(guī)則Y.i:=X.s， 翻譯方案可寫為：

AX{Y.i:=X.s}Y

自底向上計(jì)算繼承屬性2023/8/2《編譯原理與技術(shù)》講義38如何在自底向上分析2023/8/2《編譯原理與技術(shù)》講義39自底向上計(jì)算繼承屬性－由屬性copy規(guī)則可知，Y的繼承屬性Y.i和X.s在屬性棧上同一位置。這樣對(duì)屬性Y.i的引用可以轉(zhuǎn)化為對(duì)X.s的引用。若計(jì)算Y的綜合屬性Y.s時(shí)需要引用Y.i，則此時(shí)Y.i（即X.s）就緊鄰在句柄下面；如果Y的句柄形成前，它的某個(gè)右部符號(hào)需使用Y.i，這時(shí)，也可以直接使用Y.i。（Howtouse?）bottom………………XX.s（Y.i）……分析棧屬性棧Valtop句柄（歸約為Y）top－句柄長(zhǎng)2023/8/2《編譯原理與技術(shù)》講義39自底向上計(jì)算繼承屬2023/8/2《編譯原理與技術(shù)》講義40e.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)}對(duì)于輸入串：intp,q,r分析過(guò)程如下：2023/8/2《編譯原理與技術(shù)》講義40e.g.11C2023/8/2《編譯原理與技術(shù)》講義41

輸入串 分析棧 產(chǎn)生式

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時(shí)，T與L的位置關(guān)系－－T就在句柄的下面！2023/8/2《編譯原理與技術(shù)》講義41 輸入串 2023/8/2《編譯原理與技術(shù)》講義42e.g.11C聲明的“代碼段”

產(chǎn)生式 代碼段（只含綜合屬性）

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.in2023/8/2《編譯原理與技術(shù)》講義42e.g.112023/8/2《編譯原理與技術(shù)》講義43問(wèn)題1：繼承屬性的位置在構(gòu)造編譯器時(shí)不可預(yù)知（或不固定），如e.g.12

產(chǎn)生式 語(yǔ)義規(guī)則SaAC

C.i:=A.sSbA

B

C

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

用Cc歸約時(shí)，C.i的值可能在val[top-1]或者在val[top-2]的位置上。解決辦法是考慮將其統(tǒng)一。 引入標(biāo)記非終結(jié)符M和產(chǎn)生式M。模擬繼承屬性的計(jì)算bottomccABaAb……分析棧1分析棧2top2023/8/2《編譯原理與技術(shù)》講義43問(wèn)題1：繼承屬性的2023/8/2《編譯原理與技術(shù)》講義44產(chǎn)生式 語(yǔ)義規(guī)則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引入標(biāo)記非終結(jié)符bottomAMaB…A…b……分析棧1分析棧2topcc2023/8/2《編譯原理與技術(shù)》講義44產(chǎn)生式 2023/8/2《編譯原理與技術(shù)》講義45產(chǎn)生式 代碼段SaAC

SbA

B

M

C

Cc val[ntop]:=g(val[top-1])Mval[ntop]:=val[top-1]…可否將M放在SaAC產(chǎn)生式中？M.i2023/8/2《編譯原理與技術(shù)》講義45產(chǎn)生式 代2023/8/2《編譯原理與技術(shù)》講義46模擬繼承屬性的計(jì)算問(wèn)題2：語(yǔ)義規(guī)則不是簡(jiǎn)單的屬性復(fù)寫拷貝。e.g.13:將例12中的SaAC語(yǔ)義規(guī)則換為： 產(chǎn)生式 語(yǔ)義規(guī)則

SaAC C.i:=f(A.s)雖然在例12中引入了M使得“A.s”可在val[top-1]處找到，但在S的兩個(gè)產(chǎn)生式中C.i的取值方式不同，導(dǎo)致C.s的計(jì)算嘛…這次可以考慮引入標(biāo)記非終結(jié)符N和N2023/8/2《編譯原理與技術(shù)》講義46模擬繼承屬性的計(jì)算2023/8/2《編譯原理與技術(shù)》講義47e.g.13引入標(biāo)記非終結(jié)符N

產(chǎn)生式 語(yǔ)義規(guī)則

SaA

N

C C.i:=N.s

N.i:=A.s

N

N.s:=f(N.i)

(其他產(chǎn)生式和語(yǔ)義規(guī)則不變）

(代碼段略）

2023/8/2《編譯原理與技術(shù)》講義47e.g.13引入2023/8/2《編譯原理與技術(shù)》講義48

產(chǎn)生式 語(yǔ)義規(guī)則

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文字排版的語(yǔ)法制導(dǎo)定義2023/8/2《編譯原理與技術(shù)》講義48 產(chǎn)生式 2023/8/2《編譯原理與技術(shù)》講義49S：S.ht，綜合屬性；待排公式的整體高度B：B.ps，繼承屬性；公式（文本）中字體“點(diǎn)”的大小

B.ht，綜合屬性；公式排版高度text：text.h，文本高度max：求兩個(gè)排版公式的最大高度shrink(B)：將點(diǎn)大小縮小為B的30％disp(B1.ht，B2.ht)：向下調(diào)整B2的位置文字排版中的符號(hào)屬性E1Val2023/8/2《編譯原理與技術(shù)》講義49S：S.ht，2023/8/2《編譯原理與技術(shù)》講義50文字排版的翻譯方案（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}2023/8/2《編譯原理與技術(shù)》講義50文字排版的翻譯方案2023/8/2《編譯原理與技術(shù)》講義51文字排版中引入標(biāo)記符號(hào)為了自底向上計(jì)算：Btext {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

BBB1MB2BB1subNB2texttext.hLL.s=10分析棧屬性棧topbottom2023/8/2《編譯原理與技術(shù)》講義51文字排版中引入標(biāo)記2023/8/2《編譯原理與技術(shù)》講義52SL {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）2023/8/2《編譯原理與技術(shù)》講義52SL2023/8/2《編譯原理與技術(shù)》講義53

產(chǎn)生式 代碼段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])2023/8/2《編譯原理與技術(shù)》講義53產(chǎn)生式 代2023/8/2《編譯原理與技術(shù)》講義54（L-屬性定義）自頂向下翻譯刪除翻譯方案中的左遞歸

AA1Y{A.a:=g(A1.a,Y.y)} AX{A.a:=f(X.x)}

消除左遞歸：

AX {R.i:=f(X.x)}//傳遞“左”運(yùn)算量

R{A.a:=R.s} RY {R1.i:=g(R.i,Y.y)} R1 {R.s:=R1.s} R

{R.s:=R.i}//返回結(jié)果2023/8/2《編譯原理與技術(shù)》講義54（L-屬性定義）自2023/8/2《編譯原理與技術(shù)》講義55輸入串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.s2023/8/2《編譯原理與技術(shù)》講義55輸入串XY1Y2的2023/8/2《編譯原理與技術(shù)》講義56e.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:=