版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
??為何進(jìn)行詞法和語(yǔ)法分析??用A→α進(jìn)行歸約表示是什么意思看:operand+termE→E1+TE1值+T值結(jié)果作為E值——即:取來(lái)E1值和T值做加法運(yùn)算,結(jié)果作為E值E.val=E1.val+T.val第1頁(yè)第五章語(yǔ)法制導(dǎo)翻譯翻譯任務(wù)首先是語(yǔ)義分析和正確性檢驗(yàn),若正確,則翻譯成中間代碼或目標(biāo)代碼。基本思想依據(jù)翻譯需要設(shè)置文法符號(hào)屬性,以描述語(yǔ)法結(jié)構(gòu)語(yǔ)義。比如,一個(gè)變量屬性有類型,層次,存放地址等。表示式屬性有類型,值等。屬性值計(jì)算和產(chǎn)生式相聯(lián)絡(luò)。伴隨語(yǔ)法分析進(jìn)行,執(zhí)行屬性值計(jì)算,完成語(yǔ)義分析和翻譯任務(wù)。第2頁(yè)5.1語(yǔ)法制導(dǎo)翻譯概述語(yǔ)法制導(dǎo)翻譯概念描述在進(jìn)行語(yǔ)法分析同時(shí),完成對(duì)應(yīng)語(yǔ)義處理E→E1+E2 E.val:=E1.val+E2.val語(yǔ)法結(jié)構(gòu)含有要求語(yǔ)義問(wèn)題:怎樣依據(jù)被識(shí)別出語(yǔ)法成份進(jìn)行語(yǔ)義處理?第3頁(yè)1.語(yǔ)義分析任務(wù)語(yǔ)義檢驗(yàn)例:類型、運(yùn)算、維數(shù)、越界語(yǔ)義處理例:變量存放分配例:表示式求值例:語(yǔ)句翻譯(中間代碼生成)總目標(biāo):生成等價(jià)中間代碼第4頁(yè)2.代碼結(jié)構(gòu)計(jì)算學(xué)科:對(duì)信息(數(shù)據(jù)表示)描述和變換算法系統(tǒng)研究變換:源、目標(biāo)以及源與目標(biāo)對(duì)應(yīng)關(guān)系語(yǔ)句代碼結(jié)構(gòu)語(yǔ)句分類:說(shuō)明語(yǔ)句——符號(hào)表查填可執(zhí)行語(yǔ)句——指令代碼第5頁(yè)3.經(jīng)典處理方法對(duì)應(yīng)每一個(gè)產(chǎn)生式編制一個(gè)語(yǔ)義子程序,當(dāng)一個(gè)產(chǎn)生式取得匹配時(shí),調(diào)用對(duì)應(yīng)語(yǔ)義子程序?qū)崿F(xiàn)語(yǔ)義檢驗(yàn)與翻譯E→E1+T E.val:=E1.val+T.valT→T1*F T.val:=T1.val*F.valF→id F.val:=id.val適宜在完成歸約時(shí)候進(jìn)行第6頁(yè)3.經(jīng)典處理方法在產(chǎn)生式右部適當(dāng)位置,插入對(duì)應(yīng)語(yǔ)義動(dòng)作,按照分析進(jìn)程,執(zhí)行碰到語(yǔ)義動(dòng)作D→T{L.in:=T.type}LT→int{T.type:=integer}T→real{T.type:=real}L→{L1.in:=L.in}L1,id{…}語(yǔ)義——能夠看成是對(duì)應(yīng)文法符號(hào)屬性適宜在進(jìn)行推導(dǎo)時(shí)完成第7頁(yè)語(yǔ)義翻譯流程輸入符號(hào)串
分析樹(shù)依賴圖語(yǔ)義規(guī)則計(jì)算實(shí)際上,編譯中語(yǔ)義翻譯實(shí)現(xiàn)并不是按圖中流程處理;而是隨語(yǔ)法分析進(jìn)展,識(shí)別出一個(gè)語(yǔ)法結(jié)構(gòu),就對(duì)它語(yǔ)義進(jìn)行分析和翻譯。第8頁(yè)◆語(yǔ)法制導(dǎo)定義是對(duì)上下文無(wú)關(guān)文法推廣每個(gè)文法符號(hào)都有一個(gè)相關(guān)屬性集。綜合屬性:經(jīng)過(guò)分析樹(shù)中其子節(jié)點(diǎn)屬性值計(jì)算出來(lái);繼承屬性:由該節(jié)點(diǎn)弟兄節(jié)點(diǎn)及父節(jié)點(diǎn)屬性值計(jì)算出來(lái);◆依賴圖
語(yǔ)義規(guī)則建立了屬性之間依賴關(guān)系,這些關(guān)系能夠用圖來(lái)表示,這么圖稱為依賴圖。◆屬性5.1語(yǔ)法制導(dǎo)定義(Syntax-directeddefinitions)第9頁(yè)在一個(gè)語(yǔ)法制導(dǎo)定義中,
A→P都有與之相關(guān)聯(lián)一套語(yǔ)義規(guī)則,規(guī)則形式為
b:=f(c1,c2,…,ck),f是一個(gè)函數(shù),而且或者
1.b是A一個(gè)綜合屬性而且c1,c2,…,ck是
中符號(hào)屬性,或者
2.b是
中符號(hào)一個(gè)繼承屬性而且c1,c2,…,ck是A或
中任何文法符號(hào)屬性。在兩種情況下,都說(shuō)屬性b依賴于屬性c1,c2,…,ck。5.1.1語(yǔ)法制導(dǎo)定義形式第10頁(yè)例5.1臺(tái)式計(jì)算器程序語(yǔ)法制導(dǎo)定義(圖5-2)產(chǎn)生式語(yǔ)義規(guī)則LEnprint(Eval)(可看作是L虛屬性)EE1+TEval:=E1val+TvalETEval:=TvalTT1*FTval:=T1val*FvalTFTval:=FvalF(E)Fval:=EvalFdigitFval:=digitlexval第11頁(yè)S-屬性定義僅僅使用綜合屬性語(yǔ)法制導(dǎo)定義。結(jié)點(diǎn)屬性值計(jì)算恰好和自底向上分析建立分析樹(shù)結(jié)點(diǎn)同時(shí)進(jìn)行。例5.2
輸入:3*5+4n5.1.2綜合屬性第12頁(yè)digitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln第13頁(yè)
◆綜合屬性值計(jì)算方法 對(duì)于s-屬性定義,通常使用自底向上分析方法,在建立每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則來(lái)計(jì)算綜合屬性值,即在用哪個(gè)產(chǎn)生式進(jìn)行歸約后,就執(zhí)行那個(gè)產(chǎn)生式s-屬性定義計(jì)算屬性值,從葉結(jié)點(diǎn)到根結(jié)點(diǎn)進(jìn)行計(jì)算。5.1.3繼承屬性
繼承屬性值是由此結(jié)點(diǎn)父結(jié)點(diǎn)和/或弟兄結(jié)點(diǎn)一些屬性值來(lái)決定。例5.3變量說(shuō)明屬性定義
inta,b,c第14頁(yè)
表5.2帶有繼承屬性L.in語(yǔ)法制導(dǎo)定義
產(chǎn)生式語(yǔ)義規(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頁(yè)TLLid3Lid2Did1real,,1entry2entry3entry4typein56in78in910第16頁(yè)依賴圖結(jié)構(gòu)方法for分析樹(shù)中每個(gè)結(jié)點(diǎn)ndofor與結(jié)點(diǎn)n對(duì)應(yīng)文法符號(hào)每個(gè)屬性ado在依賴圖中為a結(jié)構(gòu)一個(gè)結(jié)點(diǎn);
for分析樹(shù)每個(gè)結(jié)點(diǎn)ndofor結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)每條語(yǔ)義規(guī)則b:=f(c1,c2,…,ck)dofori:=1tokdo
從結(jié)點(diǎn)ci到結(jié)點(diǎn)b結(jié)構(gòu)一條有向邊;
5.1.4依賴圖_取得語(yǔ)義規(guī)則計(jì)算次序
第17頁(yè)例5-5圖5-5分析樹(shù)依賴圖第18頁(yè)◆拓?fù)渑判蛞粋€(gè)無(wú)環(huán)有向圖拓?fù)渑判蚴菆D中結(jié)點(diǎn)任何次序m1,m2,…,mk,使得邊必須是從序列中前面結(jié)點(diǎn)指向后面結(jié)點(diǎn),也就是說(shuō),假如mi→mj是mi到mj一條邊,那么在序列中mi必須出現(xiàn)在mj前面。若依賴圖中無(wú)環(huán),則存在一個(gè)拓?fù)渑判颍褪菍傩灾涤?jì)算次序。
5.1.5計(jì)算次序第19頁(yè)
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拓?fù)渑判蚴牵旱?0頁(yè)分析樹(shù)法:輸入串→分析樹(shù)→依賴圖→計(jì)算次序基于規(guī)則方法:在結(jié)構(gòu)編譯器時(shí),用手工或?qū)iT工具來(lái)分析語(yǔ)義規(guī)則,確定屬性值計(jì)算次序。忽略語(yǔ)義規(guī)則方法:在分析過(guò)程中翻譯,那么計(jì)算次序由分析方法來(lái)確定而表面上與語(yǔ)義規(guī)則無(wú)關(guān)。這種方法限制了能被實(shí)現(xiàn)語(yǔ)法制導(dǎo)定義種類。后兩種方法無(wú)須顯式結(jié)構(gòu)依賴圖,所以時(shí)空效率更高。計(jì)算語(yǔ)義規(guī)則方法第21頁(yè)
◆抽象語(yǔ)法(abstractsyntax)從詳細(xì)語(yǔ)法中抽象出語(yǔ)言結(jié)構(gòu)本質(zhì)性東西,而不考慮語(yǔ)言詳細(xì)符號(hào)表示,從而可簡(jiǎn)化語(yǔ)義形式描述。在不一樣語(yǔ)言中賦值語(yǔ)句有不一樣寫法:
x=y;
x:=y;
y→x
等等,能夠用抽象形式
assignment(variable,expression)把前面各種詳細(xì)形式統(tǒng)一起來(lái)。
5.2語(yǔ)法樹(shù)(syntaxtree)結(jié)構(gòu)第22頁(yè)
表示程序?qū)哟谓Y(jié)構(gòu)樹(shù),它把分析樹(shù)中對(duì)語(yǔ)義無(wú)關(guān)緊要成份去掉,是分析樹(shù)抽象形式,也稱作語(yǔ)法結(jié)構(gòu)樹(shù),或結(jié)構(gòu)樹(shù)。
語(yǔ)法樹(shù)是慣用一個(gè)中間表示形式。把語(yǔ)法分析和翻譯分開(kāi)。語(yǔ)法分析過(guò)程中完成翻譯有許多優(yōu)點(diǎn),但也有一些不足:
1.適于語(yǔ)法分析文法可能不完全反應(yīng)語(yǔ)言成份自然層次結(jié)構(gòu);
2.因?yàn)檎Z(yǔ)法分析方法限制,對(duì)分析樹(shù)結(jié)點(diǎn)訪問(wèn)次序和翻譯需要訪問(wèn)次序不一致。語(yǔ)法樹(shù)第23頁(yè)
產(chǎn)生式s→ifBthenS1elseS2語(yǔ)法樹(shù)
if-then-else
/|\
BS1S2
賦值語(yǔ)句語(yǔ)法樹(shù)
assignmentvariableexpression
在語(yǔ)法樹(shù)中,運(yùn)算符號(hào)和關(guān)鍵字都不在葉結(jié)點(diǎn),而是在內(nèi)部結(jié)點(diǎn)中出現(xiàn)。5.2.1語(yǔ)法樹(shù)第24頁(yè)結(jié)構(gòu)表示式語(yǔ)法樹(shù)使用函數(shù)
1.mknode(op,left,right)建立一個(gè)標(biāo)識(shí)為op運(yùn)算符結(jié)點(diǎn),兩個(gè)域left和right是指向左右運(yùn)算對(duì)象指針。
2.mkleaf(id,entry)建立一個(gè)標(biāo)識(shí)為id標(biāo)識(shí)符結(jié)點(diǎn),其域entry是指向該標(biāo)識(shí)符在符號(hào)表中對(duì)應(yīng)表項(xiàng)指針。
3.mkleaf(num,val)建立一個(gè)標(biāo)識(shí)為num數(shù)結(jié)點(diǎn),域val用于保留該數(shù)值。返回指向新建立結(jié)點(diǎn)指針。
5.2.2結(jié)構(gòu)表示式語(yǔ)法樹(shù)第25頁(yè)idtoentryanum4
–
idtoentryc
+圖5-8a-4+c語(yǔ)法樹(shù)第26頁(yè)5.2.3結(jié)構(gòu)語(yǔ)法樹(shù)語(yǔ)法制導(dǎo)定義
產(chǎn)生式
語(yǔ)義規(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頁(yè)圖5-10a-4+c語(yǔ)法樹(shù)結(jié)構(gòu)第28頁(yè)◆無(wú)環(huán)有向圖(DirectedAcyclicGraph,簡(jiǎn)稱dag)
用途:提取表示式中公共子表示式,以取得目標(biāo)程序局部?jī)?yōu)化。方法:執(zhí)行mknode和mkleaf時(shí),檢驗(yàn)是否已經(jīng)有相同結(jié)點(diǎn),若有,則返回對(duì)應(yīng)結(jié)點(diǎn)指針。5.2.4表示式無(wú)環(huán)有向圖第29頁(yè)例5.9表示式a+a*(b-c)+(b-c)*ddag+*d+*a–cb第30頁(yè)在分析棧中使用一個(gè)附加域來(lái)存放綜合屬性值。下列圖為一個(gè)帶有綜合屬性值域分析棧:stateval...XX.xY...Y.y......ZZ.ztop5.3S-屬性定義及其自底向上計(jì)算第31頁(yè)
Ab:=f(c1,c2,…,ck)b是A綜合屬性,ci(1
ik)是中符號(hào)屬性。綜合屬性值是在自底向上分析過(guò)程中,每次歸約之前進(jìn)行計(jì)算。
AXYZAa:=f(Xx,Yy,Zz)AaXxYyZz第32頁(yè)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])(詳細(xì)可執(zhí)行代碼)。在執(zhí)行代碼段之前執(zhí)行:
ntop:=top-r+1r是句柄長(zhǎng)度執(zhí)行代碼段后執(zhí)行:top:=ntop;第33頁(yè)
產(chǎn)生式代碼段(和圖5-2對(duì)比)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分析器實(shí)現(xiàn)臺(tái)式計(jì)算器(圖5-16)第34頁(yè)表5.5翻譯輸入3*5+4n所做移動(dòng)輸入
stateval使用產(chǎn)生式3*5+4n--*5+4n33*5+4nF3Fdigit
*5+4nT3TF
5+4nT*3-
+4nT*53-5
+4nT*F3-5Fdigit
第35頁(yè)
+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頁(yè)采取自底向上分析,比如LR分析,首先給出S-屬性定義,然后,把S-屬性定義變成可執(zhí)行代碼段,這就組成了翻譯程序。象一座建筑,語(yǔ)法分析是構(gòu)架,歸約處有一個(gè)“掛鉤”,語(yǔ)義分析和翻譯代碼段(語(yǔ)義子程序)就掛在這個(gè)鉤子上。這么,伴隨語(yǔ)法分析進(jìn)行,歸約前調(diào)用對(duì)應(yīng)語(yǔ)義子程序,完成翻譯任務(wù)??偨Y(jié)第37頁(yè)在語(yǔ)法分析過(guò)程中進(jìn)行語(yǔ)義分析和翻譯,屬性計(jì)算次序受到語(yǔ)法分析建立分析樹(shù)結(jié)點(diǎn)次序限制。一個(gè)自然計(jì)算屬性次序是按深度優(yōu)先訪問(wèn)分析樹(shù)結(jié)點(diǎn)次序,它適應(yīng)各種自底向上和自頂向下翻譯方法。
L-屬性定義可用于按深度優(yōu)先次序計(jì)算屬性值。5.4L-屬性定義第38頁(yè)proceduredfvisit(n:node);beginforn每個(gè)子結(jié)點(diǎn)m(從左至右)dobegin
計(jì)算m繼承屬性;
dfvisit(m)end;
計(jì)算n綜合屬性
end;深度優(yōu)先次序計(jì)算屬性第39頁(yè)◆定義一個(gè)語(yǔ)法制導(dǎo)定義是L-屬性定義,假如
A→X1X2…XnP,其每一個(gè)語(yǔ)義規(guī)則中每一個(gè)屬性都是一個(gè)綜合屬性,或是Xj(1
j
n)一個(gè)繼承屬性,這個(gè)繼承屬性僅依賴于
1.產(chǎn)生式中Xj左邊符號(hào)X1,X2,…Xj-1屬性;
2.A繼承屬性。每一個(gè)S-屬性定義都是L-屬性定義。5.4.1L-屬性定義第40頁(yè)圖5-19非L-屬性語(yǔ)法制導(dǎo)定義產(chǎn)生式語(yǔ)義規(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語(yǔ)法制導(dǎo)定義不是L-屬性定義文法符號(hào)Q繼承屬性依賴于它右邊文法符號(hào)R屬性第41頁(yè)◆定義翻譯模式是語(yǔ)法制導(dǎo)定義一個(gè)便于翻譯書寫形式。其中屬性與文法符號(hào)相對(duì)應(yīng),語(yǔ)義規(guī)則或語(yǔ)義動(dòng)作用花括號(hào){}括起來(lái),可被插入到產(chǎn)生式右部任何適當(dāng)位置上。這是一個(gè)語(yǔ)法分析和語(yǔ)義動(dòng)作交織表示法,它表示在按深度優(yōu)先遍歷分析樹(shù)過(guò)程中何時(shí)執(zhí)行語(yǔ)義動(dòng)作。翻譯模式給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算次序??煽闯墒欠治鲞^(guò)程中翻譯注釋。5.4.2翻譯模式第42頁(yè)將帶有+號(hào)和-號(hào)中綴表示式翻譯成后綴表示式:E→TRR→addopT{print(addop.lexeme)}R1|εT→num{print(num.val)}
把語(yǔ)義動(dòng)作看成終止符號(hào),輸入9-5+2,其分析樹(shù)如圖5-20,當(dāng)按深度優(yōu)先遍歷它,執(zhí)行遍歷中訪問(wèn)語(yǔ)義動(dòng)作,將輸出
95-2+它是輸入表示式9-5+2后綴式。例5.12一個(gè)簡(jiǎn)單翻譯模式第43頁(yè)圖5.109-5+2帶語(yǔ)義動(dòng)作分析樹(shù)第44頁(yè)◆條件:語(yǔ)法制導(dǎo)定義是L-屬性定義
確保語(yǔ)義動(dòng)作不會(huì)引用還沒(méi)有計(jì)算屬性值。1.只需要綜合屬性情況:為每一個(gè)語(yǔ)義規(guī)則建立一個(gè)包含賦值動(dòng)作,并把這個(gè)動(dòng)作放在對(duì)應(yīng)產(chǎn)生式右邊末尾。比如:TT1*FTval:=T1val*FvalTT1*F{Tval:=T1val*Fval}設(shè)計(jì)翻譯模式(依據(jù)語(yǔ)法制導(dǎo)定義)第45頁(yè)2.現(xiàn)有綜合屬性又有繼承屬性產(chǎn)生式右邊符號(hào)繼承屬性必須在這個(gè)符號(hào)以前動(dòng)作中計(jì)算出來(lái)。一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊符號(hào)綜合屬性。產(chǎn)生式左邊非終止符號(hào)綜合屬性只有在它所引用全部屬性都計(jì)算出來(lái)以后才能計(jì)算。計(jì)算這種屬性動(dòng)作通??煞旁诋a(chǎn)生式右端末尾。設(shè)計(jì)翻譯模式(依據(jù)語(yǔ)法制導(dǎo)定義)第46頁(yè)
下面翻譯模式不滿足要求:
SA1A2{A1in:=1;A2in:=2}Aa{print(Ain)}例5.13從L-屬性制導(dǎo)定義建立一個(gè)滿足上面要求翻譯模式。使用文法產(chǎn)生語(yǔ)言是數(shù)學(xué)排版語(yǔ)言EQNEsub1
val編排結(jié)果E1
val第47頁(yè)
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)生式語(yǔ)義規(guī)則圖5-22盒子大小和高度語(yǔ)法制導(dǎo)定義第48頁(yè)
B是盒子;
BBB表示兩個(gè)盒子并置;
BBsubB表示第二個(gè)盒子是第一個(gè)盒子下標(biāo);
ps是繼承屬性,影響公式高度;正文實(shí)際高度 等于正文標(biāo)準(zhǔn)高度乘以B.ps;B高度由綜合屬性ht表示;
texth可依據(jù)text性質(zhì)查表得到;
shrink把B2尺寸縮小30%;
disp把B2向下偏置。第49頁(yè)
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頁(yè)用翻譯模式結(jié)構(gòu)自頂向下翻譯。5.5.1從翻譯模式中消除左遞歸對(duì)于一個(gè)翻譯模式,若采取自頂向下分析,必須消除左遞歸和提取左公因子,在改寫基本文法時(shí)考慮屬性值計(jì)算。例5.14圖5-24帶左遞歸文法翻譯模式被轉(zhuǎn)換成圖5-25帶右遞歸文法翻譯模式。5.5自頂向下翻譯第51頁(yè)
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頁(yè)
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)過(guò)轉(zhuǎn)換帶有右遞歸文法翻譯模式第53頁(yè)Eval=6Tval=9Ri=9;Rs=69–Tval=55Ri=4;Rs=6+Tval=2R
i=6;Rs=62
圖5-26表示式9-5+2計(jì)算第54頁(yè)左遞歸翻譯模式
A→A1Y{A.a:=g(A1.a,Y.y)}A→X{A.a:=f(X.x)}(5.2)每一個(gè)文法符號(hào)都有一個(gè)綜合屬性,用對(duì)應(yīng)小寫字母表示,g和f是任意函數(shù)。消除左遞歸,文法轉(zhuǎn)換成
A→XRR→YR|ε(5.3)關(guān)于左遞歸翻譯模式更普通化討論第55頁(yè)再考慮語(yǔ)義動(dòng)作,翻譯模式變?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)過(guò)轉(zhuǎn)換翻譯模式與圖5-25中一樣,使用R繼承屬性i和綜合屬性s。(5.2)和(5.4)結(jié)果是一樣,為何?關(guān)于左遞歸翻譯模式更普通化討論第56頁(yè)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頁(yè)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頁(yè)
EE1+T{Enptr:=mknode(′+′,E1nptr,Tnptr)}
EE1-T{Enptr:=mknode(′-′,E1nptr,Tnptr)}ET{Enptr:=Tnptr}
從翻譯模式中消除左遞歸,變成圖5-28翻譯模式。例5.15表示式建立語(yǔ)法樹(shù)翻譯模式第59頁(yè)
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頁(yè)使用繼承屬性結(jié)構(gòu)語(yǔ)法樹(shù)EiRsTidR-TnumiRTε+ididnum4id-+toentryforatoentryforcnptrnptrnptr第61頁(yè)算法5.1預(yù)測(cè)語(yǔ)法制導(dǎo)翻譯器建立
輸入:一個(gè)帶有適合預(yù)測(cè)分析基礎(chǔ)文法 語(yǔ)法制導(dǎo)翻譯模式。輸出:一個(gè)語(yǔ)法制導(dǎo)翻譯器代碼。方法:在預(yù)測(cè)分析器中加入語(yǔ)義動(dòng)作代碼。
1.
AVN,建立一個(gè)可遞歸調(diào)用函數(shù)過(guò)程A。為A每一個(gè)繼承屬性都設(shè)置一個(gè)形式參數(shù),函數(shù)返回值是A綜合屬性值。
2.函數(shù)過(guò)程A代碼(指用符號(hào)形式表示數(shù)據(jù)和程序)要依據(jù)當(dāng)前輸入符號(hào)來(lái)決定使用哪一個(gè)產(chǎn)生式。
5.5.2預(yù)測(cè)翻譯器設(shè)計(jì)第62頁(yè)3.與每一個(gè)產(chǎn)生式相關(guān)代碼,從左到右根椐產(chǎn)生式右部是單詞符號(hào)、非終止符號(hào)還是語(yǔ)義動(dòng)作,分別是:(a)對(duì)于帶有綜合屬性x單詞符號(hào)X,x存放在X.x中,Match(X)。(b)對(duì)于BVN,編寫一個(gè)賦值語(yǔ)句c:=B(b1,b2,…,bk)其中,b1,b2,…,bk是繼承屬性,c是綜合屬性。(c)對(duì)于每個(gè)動(dòng)作,動(dòng)作代碼抄進(jìn)翻譯器中,用代表屬性變量來(lái)代替對(duì)屬性每一次引用。
5.5.2預(yù)測(cè)翻譯器設(shè)計(jì)第63頁(yè)例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)語(yǔ)法樹(shù)
functionR(in:
syntax-tree-node):
syntaX-tree-node;
varnptr,i1,s1,s:
syntax-tree-node;addoplexeme:char;第64頁(yè)
{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頁(yè)5.6L屬性自底向上計(jì)算在自底向上分析框架中實(shí)現(xiàn)L屬性定義方法它能實(shí)現(xiàn)任何基于LL(1)文法L屬性定義也能實(shí)現(xiàn)許多(但不是全部)基于LR(1)L屬性定義第66頁(yè)5.6L屬性自底向上計(jì)算5.6.1刪除翻譯方案中嵌入動(dòng)作E
TRR
+T{print(‘+’)}R1|
T{print(‘
’)}R1|
T
num{print(num.val)}第67頁(yè)5.6L屬性自底向上計(jì)算5.6.1刪除翻譯方案中嵌入動(dòng)作E
TRR
+T{print(‘+’)}R1|
T{print(‘
’)}R1|
T
num{print(num.val)} 在文法中加入產(chǎn)生
標(biāo)識(shí)非終止符,讓每個(gè)嵌入動(dòng)作由不一樣標(biāo)識(shí)非終止符M代表,并把該動(dòng)作放在產(chǎn)生式M
右端第68頁(yè)5.6L屬性自底向上計(jì)算5.6.1刪除翻譯方案中嵌入動(dòng)作E
TRR
+T{print(‘+’)}R1|
T{print(‘
’)}R1|
T
num{print(num.val)} 在文法中加入產(chǎn)生
標(biāo)識(shí)非終止符,讓每個(gè)嵌入動(dòng)作由不一樣標(biāo)識(shí)非終止符M代表,并把該動(dòng)作放在產(chǎn)生式M
右端E
TRR
+TMR1|
TNR1|
T
num{print(num.val)}M
{print(‘+’)}N
{print(‘
’)}第69頁(yè)5.6L屬性自底向上計(jì)算5.6.2分析棧上繼承屬性屬性位置能預(yù)測(cè)例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頁(yè)5.6L屬性自底向上計(jì)算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頁(yè)5.6L屬性自底向上計(jì)算屬性位置不能預(yù)測(cè) S
aAC C.i=A.s S
bABC C.i=A.s C
c C.s=g(C.i)第72頁(yè)5.6L屬性自底向上計(jì)算屬性位置不能預(yù)測(cè)S
aAC C.i=A.sS
bABC C.i=A.sC
c C.s=g(C.i)增加標(biāo)識(shí)非終止符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頁(yè)5.6L屬性自底向上計(jì)算5.6.3模擬繼承屬性計(jì)算繼承屬性是某個(gè)綜合屬性一個(gè)函數(shù) S
aAC C.i=f(A.s) C
c C.s=g(C.i)增加標(biāo)識(shí)非終止符,把f(A.s)計(jì)算移到對(duì)標(biāo)識(shí)非終止符歸約時(shí)進(jìn)行 S
aANC N.i=A.s;C.i=N.s N
N.s=f(N.i) C
c C.s=g(C.i)
第74頁(yè)5.6L屬性自底向上計(jì)算例數(shù)學(xué)排版語(yǔ)言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頁(yè)5.6L屬性自底向上計(jì)算產(chǎn)
生
式
語(yǔ)義規(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頁(yè)5.6L屬性自底向上計(jì)算SMsB
Ls
BBtext
BsubNsBtext
text第77頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.6L屬性自底向上計(jì)算產(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頁(yè)5.7遞歸計(jì)算回顧:語(yǔ)法制導(dǎo)定義實(shí)現(xiàn)分析樹(shù)方法邊分析邊進(jìn)行屬性計(jì)算,只能完成L屬性計(jì)算(忽略規(guī)則方法)本節(jié)介紹先分析后計(jì)算方法,不局限于L屬性計(jì)算(基于規(guī)則方法)為每個(gè)非終止符結(jié)構(gòu)一個(gè)屬性計(jì)算函數(shù),不過(guò)該函數(shù)不含語(yǔ)法分析部分為非終止符不一樣綜合屬性結(jié)構(gòu)不一樣函數(shù)第86頁(yè)5.7遞歸計(jì)算5.7.1自左向右遍歷為B結(jié)構(gòu)一個(gè)屬性計(jì)算函數(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頁(yè)5.7遞歸計(jì)算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在結(jié)點(diǎn)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頁(yè)5.7遞歸計(jì)算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在結(jié)點(diǎn)n產(chǎn)生式of ‘B
B1subB2’: ps1=ps; ht1=B(child(n,1),ps1); ps2=shrink(ps); ht2=B(child(n,3),ps
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 沈陽(yáng)理工大學(xué)《化工環(huán)保安全創(chuàng)新學(xué)》2022-2023學(xué)年第一學(xué)期期末試卷
- 沈陽(yáng)理工大學(xué)《電力系統(tǒng)分析》2022-2023學(xué)年期末試卷
- 廣州市南沙區(qū)房屋租賃合同
- 2024正規(guī)廠房租賃合同書范本
- 2024水電安裝清包合同
- 2024鋼結(jié)構(gòu)工程施工合同范本
- 2024保潔服務(wù)合同模板
- 2024二手房購(gòu)買合同范文
- 沈陽(yáng)理工大學(xué)《DSP技術(shù)及應(yīng)用》2022-2023學(xué)年第一學(xué)期期末試卷
- 2024貸款公司借款合同范文
- 3.16謠言止于智者-正確處理同學(xué)關(guān)系班會(huì)解析
- 2024版全新勞動(dòng)仲裁證據(jù)目錄范本
- 小學(xué)數(shù)學(xué)北師大版六年級(jí)上冊(cè)《看圖找關(guān)系》課件
- 解讀退役軍人安置條例制定微課
- DL 5190.2-2019 電力建設(shè)施工技術(shù)規(guī)范 第2部分:鍋爐機(jī)組
- 二年級(jí)上冊(cè)數(shù)學(xué)應(yīng)用題100道及參考答案【黃金題型】
- (必會(huì))高級(jí)茶評(píng)員近年考試真題題庫(kù)(含答案)
- 可打印的離婚協(xié)議書模板(2024版)
- 2023年貴州省中考化學(xué)真題試卷(解析版)
- 視頻制作保密協(xié)議版
- 建工專業(yè)職業(yè)生涯規(guī)劃總結(jié)
評(píng)論
0/150
提交評(píng)論