編譯原理語法制導(dǎo)翻譯市公開課一等獎省賽課微課金獎?wù)n件

？？為何進行詞法和語法分析？？用A→α進行歸約表示是什么意思看：operand+termE→E1+TE1值+T值結(jié)果作為E值——即：取來E1值和T值做加法運算，結(jié)果作為E值E.val=E1.val+T.val第1頁第五章語法制導(dǎo)翻譯翻譯任務(wù)首先是語義分析和正確性檢驗，若正確，則翻譯成中間代碼或目標代碼?；舅枷胍罁?jù)翻譯需要設(shè)置文法符號屬性，以描述語法結(jié)構(gòu)語義。比如，一個變量屬性有類型，層次，存放地址等。表示式屬性有類型，值等。屬性值計算和產(chǎn)生式相聯(lián)絡(luò)。伴隨語法分析進行，執(zhí)行屬性值計算，完成語義分析和翻譯任務(wù)。第2頁5.1語法制導(dǎo)翻譯概述語法制導(dǎo)翻譯概念描述在進行語法分析同時，完成對應(yīng)語義處理E→E1+E2 E.val:=E1.val+E2.val語法結(jié)構(gòu)含有要求語義問題：怎樣依據(jù)被識別出語法成份進行語義處理？第3頁1.語義分析任務(wù)語義檢驗例：類型、運算、維數(shù)、越界語義處理例：變量存放分配例：表示式求值例：語句翻譯（中間代碼生成）總目標：生成等價中間代碼第4頁2.代碼結(jié)構(gòu)計算學(xué)科：對信息（數(shù)據(jù)表示）描述和變換算法系統(tǒng)研究變換：源、目標以及源與目標對應(yīng)關(guān)系語句代碼結(jié)構(gòu)語句分類：說明語句——符號表查填可執(zhí)行語句——指令代碼第5頁3.經(jīng)典處理方法對應(yīng)每一個產(chǎn)生式編制一個語義子程序，當一個產(chǎn)生式取得匹配時，調(diào)用對應(yīng)語義子程序?qū)崿F(xiàn)語義檢驗與翻譯E→E1+T E.val:=E1.val+T.valT→T1*F T.val:=T1.val*F.valF→id F.val:=id.val適宜在完成歸約時候進行第6頁3.經(jīng)典處理方法在產(chǎn)生式右部適當位置，插入對應(yīng)語義動作，按照分析進程，執(zhí)行碰到語義動作D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{…}語義——能夠看成是對應(yīng)文法符號屬性適宜在進行推導(dǎo)時完成第7頁語義翻譯流程輸入符號串

分析樹依賴圖語義規(guī)則計算實際上，編譯中語義翻譯實現(xiàn)并不是按圖中流程處理；而是隨語法分析進展，識別出一個語法結(jié)構(gòu)，就對它語義進行分析和翻譯。第8頁◆語法制導(dǎo)定義是對上下文無關(guān)文法推廣每個文法符號都有一個相關(guān)屬性集。綜合屬性:經(jīng)過分析樹中其子節(jié)點屬性值計算出來；繼承屬性:由該節(jié)點弟兄節(jié)點及父節(jié)點屬性值計算出來；◆依賴圖

語義規(guī)則建立了屬性之間依賴關(guān)系，這些關(guān)系能夠用圖來表示，這么圖稱為依賴圖。◆屬性5.1語法制導(dǎo)定義(Syntax-directeddefinitions)第9頁在一個語法制導(dǎo)定義中，

A→P都有與之相關(guān)聯(lián)一套語義規(guī)則，規(guī)則形式為

b：=f（c1，c2，…，ck），f是一個函數(shù)，而且或者

1．b是A一個綜合屬性而且c1，c2，…，ck是

中符號屬性，或者

2．b是

中符號一個繼承屬性而且c1，c2，…，ck是A或

中任何文法符號屬性。在兩種情況下，都說屬性b依賴于屬性c1，c2，…，ck。5.1.1語法制導(dǎo)定義形式第10頁例5.1臺式計算器程序語法制導(dǎo)定義（圖5－2)產(chǎn)生式語義規(guī)則LEnprint(Eval)(可看作是L虛屬性)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val*FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval第11頁S-屬性定義僅僅使用綜合屬性語法制導(dǎo)定義。結(jié)點屬性值計算恰好和自底向上分析建立分析樹結(jié)點同時進行。例5.2

輸入：3*5+4n5.1.2綜合屬性第12頁digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln第13頁

◆綜合屬性值計算方法 對于s-屬性定義，通常使用自底向上分析方法，在建立每一個結(jié)點處使用語義規(guī)則來計算綜合屬性值，即在用哪個產(chǎn)生式進行歸約后，就執(zhí)行那個產(chǎn)生式s-屬性定義計算屬性值，從葉結(jié)點到根結(jié)點進行計算。5.1.3繼承屬性

繼承屬性值是由此結(jié)點父結(jié)點和／或弟兄結(jié)點一些屬性值來決定。例5.3變量說明屬性定義

inta,b,c第14頁

表5.2帶有繼承屬性L.in語法制導(dǎo)定義

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

DTLL

in:=T

typeT

intT

type:=integerT

realT

type:=realLL1,idL1

in:=L

inaddtype(id

entry,L

in)Lidaddtype(id

entry,L

in)第15頁TLLid3Lid2Did1real,,1entry2entry3entry4typein56in78in910第16頁依賴圖結(jié)構(gòu)方法for分析樹中每個結(jié)點ndofor與結(jié)點n對應(yīng)文法符號每個屬性ado在依賴圖中為a結(jié)構(gòu)一個結(jié)點；

for分析樹每個結(jié)點ndofor結(jié)點n所用產(chǎn)生式對應(yīng)每條語義規(guī)則b:＝f（c1，c2，…，ck)dofori:=1tokdo

從結(jié)點ci到結(jié)點b結(jié)構(gòu)一條有向邊；

5.1.4依賴圖_取得語義規(guī)則計算次序

第17頁例5-5圖5－5分析樹依賴圖第18頁◆拓撲排序一個無環(huán)有向圖拓撲排序是圖中結(jié)點任何次序m1，m2，…，mk，使得邊必須是從序列中前面結(jié)點指向后面結(jié)點，也就是說，假如mi→mj是mi到mj一條邊,那么在序列中mi必須出現(xiàn)在mj前面。若依賴圖中無環(huán)，則存在一個拓撲排序，它就是屬性值計算次序。

5.1.5計算次序第19頁

1，2，3，4，5，6，7，8，9，10a4:=real;a5:=a4;addtype(id3entry,a5);a7:=a5;addtype(id2entry,a7);a9:=a7;addtype(id1entry,a9);例5.6圖5.7拓撲排序是：第20頁分析樹法:輸入串→分析樹→依賴圖→計算次序基于規(guī)則方法：在結(jié)構(gòu)編譯器時，用手工或?qū)ｉT工具來分析語義規(guī)則,確定屬性值計算次序。忽略語義規(guī)則方法：在分析過程中翻譯，那么計算次序由分析方法來確定而表面上與語義規(guī)則無關(guān)。這種方法限制了能被實現(xiàn)語法制導(dǎo)定義種類。后兩種方法無須顯式結(jié)構(gòu)依賴圖，所以時空效率更高。計算語義規(guī)則方法第21頁

◆抽象語法（abstractsyntax）從詳細語法中抽象出語言結(jié)構(gòu)本質(zhì)性東西，而不考慮語言詳細符號表示，從而可簡化語義形式描述。在不一樣語言中賦值語句有不一樣寫法：

x=y;

x:=y;

y→x

等等，能夠用抽象形式

assignment(variable,expression)把前面各種詳細形式統(tǒng)一起來。

5.2語法樹（syntaxtree）結(jié)構(gòu)第22頁

表示程序?qū)哟谓Y(jié)構(gòu)樹，它把分析樹中對語義無關(guān)緊要成份去掉，是分析樹抽象形式，也稱作語法結(jié)構(gòu)樹，或結(jié)構(gòu)樹。

語法樹是慣用一個中間表示形式。把語法分析和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點，但也有一些不足：

1.適于語法分析文法可能不完全反應(yīng)語言成份自然層次結(jié)構(gòu)；

2.因為語法分析方法限制，對分析樹結(jié)點訪問次序和翻譯需要訪問次序不一致。語法樹第23頁

產(chǎn)生式s→ifBthenS1elseS2語法樹

if-then-else

／|＼

BS1S2

賦值語句語法樹

assignmentvariableexpression

在語法樹中，運算符號和關(guān)鍵字都不在葉結(jié)點，而是在內(nèi)部結(jié)點中出現(xiàn)。5.2.1語法樹第24頁結(jié)構(gòu)表示式語法樹使用函數(shù)

1.mknode(op,left,right)建立一個標識為op運算符結(jié)點，兩個域left和right是指向左右運算對象指針。

2．mkleaf(id,entry)建立一個標識為id標識符結(jié)點,其域entry是指向該標識符在符號表中對應(yīng)表項指針。

3.mkleaf(num,val)建立一個標識為num數(shù)結(jié)點，域val用于保留該數(shù)值。返回指向新建立結(jié)點指針。

5.2.2結(jié)構(gòu)表示式語法樹第25頁idtoentryanum4

–

idtoentryc

+圖5-8a-4+c語法樹第26頁5.2.3結(jié)構(gòu)語法樹語法制導(dǎo)定義

產(chǎn)生式

語義規(guī)則

E

E1+TE.nptr:=mknode('+',E1.nptr,T.nptr)E

E1-TE.nptr:=mknode('-',E1.nptr,T.nptr)E

TE.nptr:=T.nptrT

(E)T.nptr:=E.nptrT

idT.nptr:=mkleaf(id,id.entry)T

numT.nptr:=mkleaf(num,num.val)第27頁圖5-10a-4+c語法樹結(jié)構(gòu)第28頁◆無環(huán)有向圖（DirectedAcyclicGraph，簡稱dag)

用途：提取表示式中公共子表示式，以取得目標程序局部優(yōu)化。方法：執(zhí)行mknode和mkleaf時，檢驗是否已經(jīng)有相同結(jié)點，若有，則返回對應(yīng)結(jié)點指針。5.2.4表示式無環(huán)有向圖第29頁例5.9表示式a＋a*(b-c)+(b-c)*ddag+*d+*a–cb第30頁在分析棧中使用一個附加域來存放綜合屬性值。下列圖為一個帶有綜合屬性值域分析棧：stateval...XX.xY...Y.y......ZZ.ztop5.3S-屬性定義及其自底向上計算第31頁

Ab:=f(c1,c2,…,ck)b是A綜合屬性，ci(1

ik)是中符號屬性。綜合屬性值是在自底向上分析過程中，每次歸約之前進行計算。

AXYZAa:=f(Xx,Yy,Zz)AaXxYyZz第32頁topstateval......XX.xYY.yZZ.zstateval......AA.atop定義式A.a:=f(X.x,Y.y,Z.z)（抽象）變成val[ntop]:=f(val[top-2],val[top-1],val[top])（詳細可執(zhí)行代碼）。在執(zhí)行代碼段之前執(zhí)行：

ntop:=top-r+1r是句柄長度執(zhí)行代碼段后執(zhí)行：top:=ntop;第33頁

產(chǎn)生式代碼段(和圖5－2對比）LEnprintf(val[ntop])EE+Tval[ntop]:=val[top-2]+val[top]ETTT*Fval[ntop]:=val[top-2]*val[top]TFF(E)val[ntop]:=val[top-1]Fdigit例5.10用LR分析器實現(xiàn)臺式計算器(圖5－16）第34頁表5.5翻譯輸入3*5+4n所做移動輸入

stateval使用產(chǎn)生式3*5+4n--*5+4n33*5+4nF3Fdigit

*5+4nT3TF

5+4nT*3-

+4nT*53-5

+4nT*F3-5Fdigit

第35頁

+4nT15T

T*F

+4nE15E

T

4nE+15-

nE+415-4

nE+F15-4F

digit

nE+T15-4T

F

nE19E

E+T

En19-

L19L

En第36頁采取自底向上分析，比如LR分析，首先給出S-屬性定義，然后，把S-屬性定義變成可執(zhí)行代碼段，這就組成了翻譯程序。象一座建筑，語法分析是構(gòu)架，歸約處有一個“掛鉤”，語義分析和翻譯代碼段（語義子程序）就掛在這個鉤子上。這么，伴隨語法分析進行，歸約前調(diào)用對應(yīng)語義子程序,完成翻譯任務(wù)?？偨Y(jié)第37頁在語法分析過程中進行語義分析和翻譯，屬性計算次序受到語法分析建立分析樹結(jié)點次序限制。一個自然計算屬性次序是按深度優(yōu)先訪問分析樹結(jié)點次序，它適應(yīng)各種自底向上和自頂向下翻譯方法。

L-屬性定義可用于按深度優(yōu)先次序計算屬性值。5.4L-屬性定義第38頁proceduredfvisit(n:node);beginforn每個子結(jié)點m(從左至右)dobegin

計算m繼承屬性；

dfvisit(m)end;

計算n綜合屬性

end;深度優(yōu)先次序計算屬性第39頁◆定義一個語法制導(dǎo)定義是L-屬性定義，假如

A→X1X2…XnP,其每一個語義規(guī)則中每一個屬性都是一個綜合屬性，或是Xj(1

j

n)一個繼承屬性，這個繼承屬性僅依賴于

1.產(chǎn)生式中Xj左邊符號X1，X2，…Xj-1屬性；

2．A繼承屬性。每一個S-屬性定義都是L-屬性定義。5.4.1L-屬性定義第40頁圖5－19非L-屬性語法制導(dǎo)定義產(chǎn)生式語義規(guī)則A

LMA

QRL.i:=l(A.i)M.i:=m(L.s)A.s:=f(M.s)R.i:=r(A.i)Q.i:=q(R.s)A.s:=f(Q.s)圖5－19語法制導(dǎo)定義不是L-屬性定義文法符號Q繼承屬性依賴于它右邊文法符號R屬性第41頁◆定義翻譯模式是語法制導(dǎo)定義一個便于翻譯書寫形式。其中屬性與文法符號相對應(yīng)，語義規(guī)則或語義動作用花括號｛｝括起來，可被插入到產(chǎn)生式右部任何適當位置上。這是一個語法分析和語義動作交織表示法，它表示在按深度優(yōu)先遍歷分析樹過程中何時執(zhí)行語義動作。翻譯模式給出了使用語義規(guī)則進行計算次序?？煽闯墒欠治鲞^程中翻譯注釋。5.4.2翻譯模式第42頁將帶有+號和-號中綴表示式翻譯成后綴表示式：E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}

把語義動作看成終止符號，輸入9-5+2,其分析樹如圖5－20，當按深度優(yōu)先遍歷它，執(zhí)行遍歷中訪問語義動作，將輸出

95-2+它是輸入表示式9-5+2后綴式。例5.12一個簡單翻譯模式第43頁圖5.109-5+2帶語義動作分析樹第44頁◆條件：語法制導(dǎo)定義是L-屬性定義

確保語義動作不會引用還沒有計算屬性值。1.只需要綜合屬性情況：為每一個語義規(guī)則建立一個包含賦值動作，并把這個動作放在對應(yīng)產(chǎn)生式右邊末尾。比如：TT1*FTval:=T1val*FvalTT1*F{Tval:=T1val*Fval}設(shè)計翻譯模式（依據(jù)語法制導(dǎo)定義）第45頁2.現(xiàn)有綜合屬性又有繼承屬性產(chǎn)生式右邊符號繼承屬性必須在這個符號以前動作中計算出來。一個動作不能引用這個動作右邊符號綜合屬性。產(chǎn)生式左邊非終止符號綜合屬性只有在它所引用全部屬性都計算出來以后才能計算。計算這種屬性動作通?？煞旁诋a(chǎn)生式右端末尾。設(shè)計翻譯模式（依據(jù)語法制導(dǎo)定義）第46頁

下面翻譯模式不滿足要求：

SA1A2{A1in:=1;A2in:=2}Aa{print(Ain)}例5.13從L-屬性制導(dǎo)定義建立一個滿足上面要求翻譯模式。使用文法產(chǎn)生語言是數(shù)學(xué)排版語言EQNEsub1

val編排結(jié)果E1

val第47頁

B.ps:=10S.ht:=B.htB1.ps:=B.psB2.ps:=B.psB.ht:=max(B1.ht,B2.ht)B1.ps:=B.psB2.ps:=shrink(B.ps)B.ht:=disp(B1.ht,B2.ht)B.ht:=text.h*B.ps

S

BB

B1B2B

B1subB2B

text產(chǎn)生式語義規(guī)則圖5-22盒子大小和高度語法制導(dǎo)定義第48頁

B是盒子；

BBB表示兩個盒子并置；

BBsubB表示第二個盒子是第一個盒子下標；

ps是繼承屬性，影響公式高度；正文實際高度 等于正文標準高度乘以B.ps；B高度由綜合屬性ht表示；

texth可依據(jù)text性質(zhì)查表得到；

shrink把B2尺寸縮小30%；

disp把B2向下偏置。第49頁

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}B1sub{B2.ps:=shrink(B.ps)}B2｛B.ht:=disp(B1.ht,B2.ht)}B→text｛B.ht:=text.h*B.ps}從圖5-22結(jié)構(gòu)翻譯模式第50頁用翻譯模式結(jié)構(gòu)自頂向下翻譯。5.5.1從翻譯模式中消除左遞歸對于一個翻譯模式，若采取自頂向下分析，必須消除左遞歸和提取左公因子，在改寫基本文法時考慮屬性值計算。例5.14圖5－24帶左遞歸文法翻譯模式被轉(zhuǎn)換成圖5－25帶右遞歸文法翻譯模式。5.5自頂向下翻譯第51頁

E

E1+T｛E

val:=E1

val+T

val}E

E1-T｛E

val:=E1

val-T

val｝

E

T{E.val:=T

val}T

(E)｛T

val:=E

val｝

T

num｛T

val:=num

val}帶左遞歸文法翻譯模式第52頁

E→T{R

i:=T

val}R｛E

val:=R

s｝

R→＋

T｛R1

i:=R.i+T.

val}R1｛R.

s:=R1

s}R→-T｛R1

i:=R

i-T

val}R1｛R

s:=R1

s}R→ε｛R

s:=R

i}T→（E）｛T

val:=E.

val}T→num{T

val:=num

val}經(jīng)過轉(zhuǎn)換帶有右遞歸文法翻譯模式第53頁Eval=6Tval=9Ri=9;Rs=69–Tval=55Ri=4;Rs=6+Tval=2R

i=6;Rs=62

圖5－26表示式9-5+2計算第54頁左遞歸翻譯模式

A→A1Y｛A.a:=g(A1.a,Y.y)}A→X｛A.a:=f(X.x)}（5.2）每一個文法符號都有一個綜合屬性，用對應(yīng)小寫字母表示，g和f是任意函數(shù)。消除左遞歸，文法轉(zhuǎn)換成

A→XRR→YR|ε（5.3）關(guān)于左遞歸翻譯模式更普通化討論第55頁再考慮語義動作，翻譯模式變?yōu)椋?/p>

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}（5.4）經(jīng)過轉(zhuǎn)換翻譯模式與圖5－25中一樣,使用R繼承屬性i和綜合屬性s。（5.2）和（5.4）結(jié)果是一樣,為何？關(guān)于左遞歸翻譯模式更普通化討論第56頁A

a=g(g(f(X

x),Y1

y),Y2

y)A

a=g(f(X

x),Y1

y)A

a=f(X

x)Y2Y1X(a)輸入：XY1Y2第57頁AR

i=f(X

x)R

i=g(f(X

x),Y1

y)R

i=g(g(f(X

x),Y1

y),Y2

y)εY2Y1X(b)第58頁

EE1+T{Enptr:=mknode(′+′,E1nptr,Tnptr)}

EE1-T{Enptr:=mknode(′-′,E1nptr,Tnptr)}ET{Enptr:=Tnptr}

從翻譯模式中消除左遞歸，變成圖5－28翻譯模式。例5.15表示式建立語法樹翻譯模式第59頁

E→T{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}T→(E){T

nptr:=E

nptr}T→id{T

nptr:=mkleaf(id,id

entry)}T→num｛T

nptr:=mkleaf(num,num

val)}第60頁使用繼承屬性結(jié)構(gòu)語法樹EiRsTidR-TnumiRTε+ididnum4id-+toentryforatoentryforcnptrnptrnptr第61頁算法5.1預(yù)測語法制導(dǎo)翻譯器建立

輸入：一個帶有適合預(yù)測分析基礎(chǔ)文法 語法制導(dǎo)翻譯模式。輸出：一個語法制導(dǎo)翻譯器代碼。方法：在預(yù)測分析器中加入語義動作代碼。

1．

AVN,建立一個可遞歸調(diào)用函數(shù)過程A。為A每一個繼承屬性都設(shè)置一個形式參數(shù)，函數(shù)返回值是A綜合屬性值。

2.函數(shù)過程A代碼（指用符號形式表示數(shù)據(jù)和程序）要依據(jù)當前輸入符號來決定使用哪一個產(chǎn)生式。

5.5.2預(yù)測翻譯器設(shè)計第62頁3．與每一個產(chǎn)生式相關(guān)代碼，從左到右根椐產(chǎn)生式右部是單詞符號、非終止符號還是語義動作，分別是：（a）對于帶有綜合屬性x單詞符號X，x存放在X.x中，Match(X)。（b）對于BVN，編寫一個賦值語句c：=B（b1,b2,…，bk)其中，b1,b2,…，bk是繼承屬性，c是綜合屬性。（c）對于每個動作，動作代碼抄進翻譯器中，用代表屬性變量來代替對屬性每一次引用。

5.5.2預(yù)測翻譯器設(shè)計第63頁例5.16：

R→addopT｛R1．i:=mknode（addop

lexeme，

R

i，T

nptr）｝

R1｛R.s:=R1.s}R→ε｛R.s:=R.i}（5．5）遞歸下降結(jié)構(gòu)語法樹

functionR（in:

syntax-tree-node）：

syntaX-tree-node；

varnptr,i1,s1,s：

syntax-tree-node;addoplexeme:char；第64頁

{IFlookahead=addopTHEN/*產(chǎn)生式R→addopTR*/{addoplexeme:=lexval;match(addop);nptr:=T;i1:=mknode(addoplexeme,in,nptr);s1:=R(i1);s:=s1;}ELSEs:=in;/*產(chǎn)生式R

*/return(s);}第65頁5.6L屬性自底向上計算在自底向上分析框架中實現(xiàn)L屬性定義方法它能實現(xiàn)任何基于LL(1)文法L屬性定義也能實現(xiàn)許多（但不是全部）基于LR(1)L屬性定義第66頁5.6L屬性自底向上計算5.6.1刪除翻譯方案中嵌入動作E

TRR

+T{print(‘+’)}R1|

T{print(‘

’)}R1|

T

num{print(num.val)}第67頁5.6L屬性自底向上計算5.6.1刪除翻譯方案中嵌入動作E

TRR

+T{print(‘+’)}R1|

T{print(‘

’)}R1|

T

num{print(num.val)} 在文法中加入產(chǎn)生

標識非終止符，讓每個嵌入動作由不一樣標識非終止符M代表，并把該動作放在產(chǎn)生式M

右端第68頁5.6L屬性自底向上計算5.6.1刪除翻譯方案中嵌入動作E

TRR

+T{print(‘+’)}R1|

T{print(‘

’)}R1|

T

num{print(num.val)} 在文法中加入產(chǎn)生

標識非終止符，讓每個嵌入動作由不一樣標識非終止符M代表，并把該動作放在產(chǎn)生式M

右端E

TRR

+TMR1|

TNR1|

T

num{print(num.val)}M

{print(‘+’)}N

{print(‘

’)}第69頁5.6L屬性自底向上計算5.6.2分析棧上繼承屬性屬性位置能預(yù)測例intp,q,rD

T{L.in=T.type} LT

int{T.type=integer}T

real{T.type=real}L

{L1.in=L.in}L1,id{addtype(id.entry,L.in)}L

id{addtype(id.entry,L.in)}DTLL,rL,qpint

type

ininin第70頁5.6L屬性自底向上計算DTLL,rL,qpint

type

ininin產(chǎn)生式

代碼段

D

TL

T

intval[top]=integer

T

realval[top]=real

L

L1,idaddType(val[top],val[top

3])L

idaddType(val[top],val[top

1])第71頁5.6L屬性自底向上計算屬性位置不能預(yù)測 S

aAC C.i=A.s S

bABC C.i=A.s C

c C.s=g(C.i)第72頁5.6L屬性自底向上計算屬性位置不能預(yù)測S

aAC C.i=A.sS

bABC C.i=A.sC

c C.s=g(C.i)增加標識非終止符S

aAC C.i=A.sS

bABMC M.i=A.s;C.i=M.sC

c C.s=g(C.i)M

M.s=M.i第73頁5.6L屬性自底向上計算5.6.3模擬繼承屬性計算繼承屬性是某個綜合屬性一個函數(shù) S

aAC C.i=f(A.s) C

c C.s=g(C.i)增加標識非終止符，把f(A.s)計算移到對標識非終止符歸約時進行 S

aANC N.i=A.s;C.i=N.s N

N.s=f(N.i) C

c C.s=g(C.i)

第74頁5.6L屬性自底向上計算例數(shù)學(xué)排版語言EQNS

{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}第75頁5.6L屬性自底向上計算產(chǎn)

生

式

語義規(guī)則

S

LB

B.ps=L.s;S.ht=B.ht

L

L.s=10B

B1MB2

B1.ps=B.ps;M.i=B.ps;B2.ps=M.s;B.ht=max(B1.ht,B2.ht)M

M.s=M.i

B

B1

subNB2

B1.ps=B.ps;N.i=B.ps;B2.ps=N.s;B.ht=disp(B1.ht,B2.ht)N

N.s=shrink(N.i)B

textB.ht=text.h

B.ps

第76頁5.6L屬性自底向上計算SMsB

Ls

BBtext

BsubNsBtext

text第77頁5.6L屬性自底向上計算產(chǎn)

生

式

代碼段S

LB

B.ps=L.s;S.ht=B.ht

L

L.s=10B

B1MB2

B1.ps=B.ps;M.i=B.ps;B2.ps=M.s;B.ht=max(B1.ht,B2.ht)M

M.s=M.i

B

B1

subNB2

B1.ps=B.ps;N.i=B.ps;B2.ps=N.s;B.ht=disp(B1.ht,B2.ht)N

N.s=shrink(N.i)B

textB.ht=text.h

B.ps

第78頁5.6L屬性自底向上計算產(chǎn)生式代碼段S

LBval[top

1]=val[top]L

L.s=10B

B1MB2B1.ps=B.ps;M.i=B.ps;B2.ps=M.s;B.ht=max(B1.ht,B2.ht)M

M.s=M.iB

B1subNB2B1.ps=B.ps;N.i=B.ps;B2.ps=N.s;B.ht=disp(B1.ht,B2.ht)N

N.s=shrink(N.i)B

textB.ht=text.h

B.ps第79頁5.6L屬性自底向上計算產(chǎn)生式代碼段S

LBval[top

1]=val[top]L

val[top+1]=10B

B1MB2B1.ps=B.ps;M.i=B.ps;B2.ps=M.s;B.ht=max(B1.ht,B2.ht)M

M.s=M.iB

B1subNB2B1.ps=B.ps;N.i=B.ps;B2.ps=N.s;B.ht=disp(B1.ht,B2.ht)N

N.s=shrink(N.i)B

textB.ht=text.h

B.ps第80頁5.6L屬性自底向上計算產(chǎn)生式代碼段S

LBval[top

1]=val[top]L

val[top+1]=10B

B1MB2val[top

2]=max(val[top

2],val[top])M

M.s=M.iB

B1subNB2B1.ps=B.ps;N.i=B.ps;B2.ps=N.s;B.ht=disp(B1.ht,B2.ht)N

N.s=shrink(N.i)B

textB.ht=text.h

B.ps第81頁5.6L屬性自底向上計算產(chǎn)生式代碼段S

LBval[top

1]=val[top]L

val[top+1]=10B

B1MB2val[top

2]=max(val[top

2],val[top])M

val[top+1]=val[top

1]B

B1subNB2B1.ps=B.ps;N.i=B.ps;B2.ps=N.s;B.ht=disp(B1.ht,B2.ht)N

N.s=shrink(N.i)B

textB.ht=text.h

B.ps第82頁5.6L屬性自底向上計算產(chǎn)生式代碼段S

LBval[top

1]=val[top]L

val[top+1]=10B

B1MB2val[top

2]=max(val[top

2],val[top])M

val[top+1]=val[top

1]B

B1subNB2val[top

3]=disp(val[top

3],val[top])N

N.s=shrink(N.i)B

textB.ht=text.h

B.ps第83頁5.6L屬性自底向上計算產(chǎn)

生

式

代碼段S

LB

val[top

1]=val[top]L

val[top+1]

=10B

B1MB2

val[top

2]=max(val[top

2],val[top])M

val[top+1]

=val[top

1]B

B1

subNB2

val[top

3]=disp(val[top

3],val[top]

)N

val[top+1]

=shrink(val[top

2])B

textB.ht=text.h

B.ps

第84頁5.6L屬性自底向上計算產(chǎn)

生

式

代碼段S

LB

val[top

1]=val[top]L

val[top+1]

=10B

B1MB2

val[top

2]=max(val[top

2],val[top])M

val[top+1]

=val[top

1]B

B1

subNB2

val[top

3]=disp(val[top

3],val[top]

)N

val[top+1]

=shrink(val[top

2])B

textval[top]=val[top]

val[top

1]第85頁5.7遞歸計算回顧：語法制導(dǎo)定義實現(xiàn)分析樹方法邊分析邊進行屬性計算，只能完成L屬性計算（忽略規(guī)則方法）本節(jié)介紹先分析后計算方法，不局限于L屬性計算（基于規(guī)則方法）為每個非終止符結(jié)構(gòu)一個屬性計算函數(shù)，不過該函數(shù)不含語法分析部分為非終止符不一樣綜合屬性結(jié)構(gòu)不一樣函數(shù)第86頁5.7遞歸計算5.7.1自左向右遍歷為B結(jié)構(gòu)一個屬性計算函數(shù)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}第87頁5.7遞歸計算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在結(jié)點n產(chǎn)生式of ‘B

B1B2’: ps1=ps; ht1=B(child(n,1),ps1); ps2=ps; ht2=B(child(n,2),ps2); returnmax(ht1,ht2);B

{B1.ps=B.ps}

B1 {B2.ps=B.ps}

B2 {B.ht=

max(B1.ht,B2.ht)}第88頁5.7遞歸計算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在結(jié)點n產(chǎn)生式of ‘B

B1subB2’: ps1=ps; ht1=B(child(n,1),ps1); ps2=shrink(ps); ht2=B(child(n,3),ps