編譯原理語(yǔ)法制導(dǎo)翻譯市公開(kāi)課一等獎(jiǎng)省賽課微課金獎(jiǎng)?wù)n件_第1頁(yè)
編譯原理語(yǔ)法制導(dǎo)翻譯市公開(kāi)課一等獎(jiǎng)省賽課微課金獎(jiǎng)?wù)n件_第2頁(yè)
編譯原理語(yǔ)法制導(dǎo)翻譯市公開(kāi)課一等獎(jiǎng)省賽課微課金獎(jiǎng)?wù)n件_第3頁(yè)
編譯原理語(yǔ)法制導(dǎo)翻譯市公開(kāi)課一等獎(jiǎng)省賽課微課金獎(jiǎng)?wù)n件_第4頁(yè)
編譯原理語(yǔ)法制導(dǎo)翻譯市公開(kāi)課一等獎(jiǎng)省賽課微課金獎(jiǎng)?wù)n件_第5頁(yè)
已閱讀5頁(yè),還剩93頁(yè)未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(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ì)自己和他人造成任何形式的傷害或損失。

評(píng)論

0/150

提交評(píng)論