編譯原理 5 語(yǔ)法制導(dǎo)翻譯學(xué)習(xí)課件

上傳人：o*** IP屬地：未知上傳時(shí)間：2024-12-31 格式：PPTX 頁(yè)數(shù)：88 大?。?.22MB 積分：6 舉報(bào) 版權(quán)申訴

編譯原理 5 語(yǔ)法制導(dǎo)翻譯學(xué)習(xí)課件_第2頁(yè)

編譯原理 5 語(yǔ)法制導(dǎo)翻譯學(xué)習(xí)課件_第3頁(yè)

編譯原理 5 語(yǔ)法制導(dǎo)翻譯學(xué)習(xí)課件_第4頁(yè)

編譯原理 5 語(yǔ)法制導(dǎo)翻譯學(xué)習(xí)課件_第5頁(yè)

已閱讀5頁(yè)，還剩83頁(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)介

語(yǔ)法制導(dǎo)翻譯

哈爾濱工業(yè)大學(xué)陳鄞第五章編譯的階段詞法分析語(yǔ)法分析語(yǔ)義分析中間代碼生成代碼優(yōu)化目標(biāo)代碼生成語(yǔ)義翻譯語(yǔ)法制導(dǎo)翻譯(Syntax-DirectedTranslation)語(yǔ)法制導(dǎo)翻譯使用CFG來(lái)引導(dǎo)對(duì)語(yǔ)言的翻譯，是一種面向文法的翻譯技術(shù)什么是語(yǔ)法制導(dǎo)翻譯如何表示語(yǔ)義信息？為CFG中的文法符號(hào)設(shè)置語(yǔ)義屬性，用來(lái)表示語(yǔ)法成分對(duì)應(yīng)的語(yǔ)義信息如何計(jì)算語(yǔ)義屬性？文法符號(hào)的語(yǔ)義屬性值是用與文法符號(hào)所在產(chǎn)生式（語(yǔ)法規(guī)則）相關(guān)聯(lián)的語(yǔ)義規(guī)則來(lái)計(jì)算的對(duì)于給定的輸入串x，構(gòu)建x的語(yǔ)法分析樹，并利用與產(chǎn)生式（語(yǔ)法規(guī)則）相關(guān)聯(lián)的語(yǔ)義規(guī)則來(lái)計(jì)算分析樹中各結(jié)點(diǎn)對(duì)應(yīng)的語(yǔ)義屬性值語(yǔ)法制導(dǎo)翻譯的基本思想將語(yǔ)義規(guī)則同語(yǔ)法規(guī)則（產(chǎn)生式）聯(lián)系起來(lái)涉及的兩個(gè)概念語(yǔ)法制導(dǎo)定義(Syntax-DirectedDefinitions,SDD)語(yǔ)法制導(dǎo)翻譯方案(SDT,Syntax-DirectedTranslationScheme)語(yǔ)法制導(dǎo)翻譯的基本思想SDD是對(duì)CFG的推廣將每個(gè)文法符號(hào)和一個(gè)語(yǔ)義屬性集合相關(guān)聯(lián)將每個(gè)產(chǎn)生式和一組語(yǔ)義規(guī)則相關(guān)聯(lián)，這些規(guī)則用于計(jì)算該產(chǎn)生式中各文法符號(hào)的屬性值如果X是一個(gè)文法符號(hào)，a是X的一個(gè)屬性，則用X.a表示屬性a在某個(gè)標(biāo)號(hào)為X的分析樹結(jié)點(diǎn)上的值例語(yǔ)法制導(dǎo)定義(SDD)

產(chǎn)生式

語(yǔ)義規(guī)則D→T

L.inh=T.type

T→int T.type=integerT→real T.type=realL→L1,id L1.inh=L.inhSDT是在產(chǎn)生式右部嵌入了程序片段的CFG，這些程序片段稱為語(yǔ)義動(dòng)作。按照慣例，語(yǔ)義動(dòng)作放在花括號(hào)內(nèi)例D→T

{L.inh=T.type}LT→int{T.type=int}T→real{T.type=real}L→{L1.inh=L.inh}L1,id一個(gè)語(yǔ)義動(dòng)作在產(chǎn)生式中的位置決定了這個(gè)動(dòng)作的執(zhí)行時(shí)間語(yǔ)法制導(dǎo)翻譯方案(SDT)SDD是關(guān)于語(yǔ)言翻譯的高層次規(guī)格說(shuō)明隱蔽了許多具體實(shí)現(xiàn)細(xì)節(jié)，使用戶不必顯式地說(shuō)明翻譯發(fā)生的順序SDT可以看作是對(duì)SDD的一種補(bǔ)充，是SDD的具體實(shí)施方案顯式地指明了語(yǔ)義規(guī)則的計(jì)算順序，以便說(shuō)明某些實(shí)現(xiàn)細(xì)節(jié)SDD與SDT5.1語(yǔ)法制導(dǎo)定義SDD5.2S-屬性定義與L-屬性定義5.3語(yǔ)法制導(dǎo)翻譯方案SDT5.4L-屬性定義的自頂向下翻譯5.5L-屬性定義的自底向上翻譯本章內(nèi)容語(yǔ)法制導(dǎo)定義SDD是對(duì)CFG的推廣將每個(gè)文法符號(hào)和一個(gè)語(yǔ)義屬性集合相關(guān)聯(lián)將每個(gè)產(chǎn)生式和一組語(yǔ)義規(guī)則相關(guān)聯(lián)，用來(lái)計(jì)算該產(chǎn)生式中各個(gè)文法符號(hào)的屬性值文法符號(hào)的屬性綜合屬性（synthesizedattribute）繼承屬性（inheritedattribute）5.1語(yǔ)法制導(dǎo)定義SDD綜合屬性（synthesizedattribute）在分析樹結(jié)點(diǎn)N上的非終結(jié)符A的綜合屬性只能通過(guò)N的子結(jié)點(diǎn)或N本身的屬性值來(lái)定義例

終結(jié)符可以具有綜合屬性。終結(jié)符的綜合屬性值是由詞法分析器提供的詞法值。因此在SDD中沒有計(jì)算終結(jié)符的屬性值的語(yǔ)義規(guī)則+TvalEvalE1val產(chǎn)生式語(yǔ)義規(guī)則E

E1+TEval=E1val+Tval繼承屬性(inheritedattribute)在分析樹結(jié)點(diǎn)N上的非終結(jié)符A的繼承屬性只能通過(guò)N的父結(jié)點(diǎn)、N的兄弟結(jié)點(diǎn)或N本身的屬性值來(lái)定義例終結(jié)符沒有繼承屬性。終結(jié)符從詞法分析器處獲得的屬性值被歸為綜合屬性值產(chǎn)生式語(yǔ)義規(guī)則D

inh=T.

typedigit.lexval=3F.val=3T.val=3digit.lexval=5F.val=5T.val=15*+digit.lexval=4F.val=4T.val=4E.val=19LnE.val=15注釋分析樹(Annotated

parsetree)：每個(gè)節(jié)點(diǎn)都帶有屬性值的分析樹輸入：3*5+4n產(chǎn)生式

語(yǔ)義規(guī)則(1)L

En print(Eval)(2)E

E1+T Eval=E1val+Tval(3)E

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

Tval=Fval(6)F(E) Fval=Eval(7)Fdigit Fval=digitlexval副作用(Sideeffect)SDD：例：帶有綜合屬性的SDD

id.lexeme=aid.lexeme=bid.lexeme=cDL.in=realT.type=realrealL.in=real,L.in=real,SDD：

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

TL L.inh=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.inh=L.inh

addtype(id.lexeme,L.inh)(5)

Lid addtype(id.lexeme,L.inh)輸入：reala

,b,c例：帶有繼承屬性L.in的SDD

一個(gè)沒有副作用的SDD有時(shí)也稱為屬性文法屬性文法的規(guī)則僅僅通過(guò)其它屬性值和常量來(lái)定義一個(gè)屬性值例產(chǎn)生式

語(yǔ)義規(guī)則(1)L

Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

Tval=Fval(6)F(E) Fval=Eval(7)F

digit

Fval=digit

lexval屬性文法(AttributeGrammar)SDD為CFG中的文法符號(hào)設(shè)置語(yǔ)義屬性。對(duì)于給定的輸入串x，應(yīng)用語(yǔ)義規(guī)則計(jì)算分析樹中各結(jié)點(diǎn)對(duì)應(yīng)的屬性值按照什么順序計(jì)算屬性值？語(yǔ)義規(guī)則建立了屬性之間的依賴關(guān)系，在對(duì)語(yǔ)法分析樹結(jié)點(diǎn)的一個(gè)屬性求值之前，必須首先求出這個(gè)屬性值所依賴的所有屬性值SDD的求值順序依賴圖是一個(gè)描述了分析樹中結(jié)點(diǎn)屬性間依賴關(guān)系的有向圖分析樹中每個(gè)標(biāo)號(hào)為X的結(jié)點(diǎn)的每個(gè)屬性a都對(duì)應(yīng)著依賴圖中的一個(gè)結(jié)點(diǎn)如果屬性X.a的值依賴于屬性Y.b的值，則依賴圖中有一條從Y.b的結(jié)點(diǎn)指向X.a的結(jié)點(diǎn)的有向邊依賴圖(DependencyGraph)typeinininlexemelexemelexeme，idLDTL，idLidrealSDD：

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

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)輸入：reala

,b,c例for分析樹中的每個(gè)結(jié)點(diǎn)ndofor與結(jié)點(diǎn)n對(duì)應(yīng)的文法符號(hào)的每個(gè)屬性ado在依賴圖中為a構(gòu)造一個(gè)結(jié)點(diǎn)；for

分析樹的每個(gè)結(jié)點(diǎn)n

for結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每條語(yǔ)義規(guī)則b:＝f(c1,c2,…,ck

)dofori:=1tok

從結(jié)點(diǎn)ci到結(jié)點(diǎn)b構(gòu)造一條有向邊；依賴圖的構(gòu)造方法typeinininlexemelexemelexeme，idLDTL，idLidrealSDD：

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

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)輸入：reala

,b,c例可行的求值順序是滿足下列條件的結(jié)點(diǎn)序列N1,N2,…,Nk

：如果依賴圖中有一條從結(jié)點(diǎn)Ni到

的邊(Ni→Nj),那么i<j（即：在節(jié)點(diǎn)序列中，Ni排在Nj前面）這樣的排序?qū)⒁粋€(gè)有向圖變成了一個(gè)線性排序，這個(gè)排序稱為這個(gè)圖的拓?fù)渑判?topologicalsort)屬性值的計(jì)算順序type4in5

in7

8in109lexeme

3lexeme

lexeme1，idLDTL，idLidrealSDD：

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

TL L.in=T.

type(2)T

int T.type=int(3)T

real

T.type=real(4)L

L1,id L1.in=L.in

addtype(id.lexeme,L.in)(5)

Lid addtype(id.lexeme,L.in)輸入：reala

,b,c例拓?fù)渑判颍?,2,3,4,5,6,7,8,9,104,3,2,1,5,7,6,9,8,10例如果圖中沒有環(huán)，那么至少存在一個(gè)拓?fù)渑判駻.sB.iAB產(chǎn)生式語(yǔ)義規(guī)則A

B A.s

=B.iB.i

=A.s+1對(duì)于只具有綜合屬性的SDD

，可以按照任何自底向上的順序計(jì)算它們的值對(duì)于同時(shí)具有繼承屬性和綜合屬性的SDD，不能保證存在一個(gè)順序來(lái)對(duì)各個(gè)節(jié)點(diǎn)上的屬性進(jìn)行求值從計(jì)算的角度看，給定一個(gè)SDD，很難確定是否存在某棵語(yǔ)法分析樹，使得SDD的屬性之間存在循環(huán)依賴關(guān)系幸運(yùn)的是，存在一個(gè)SDD的有用子類，它們能夠保證對(duì)每棵語(yǔ)法分析樹都存在一個(gè)求值順序，因?yàn)樗鼈儾辉试S產(chǎn)生帶有環(huán)的依賴圖不僅如此，接下來(lái)介紹的兩類SDD可以和自頂向下及自底向上的語(yǔ)法分析過(guò)程一起高效地實(shí)現(xiàn)S-屬性定義

(S-AttributedDefinitions,S-SDD)L-屬性定義

(L-AttributedDefinitions,L-SDD)5.1語(yǔ)法制導(dǎo)定義SDD5.2S-屬性定義與L-屬性定義5.3語(yǔ)法制導(dǎo)翻譯方案SDT5.4L-屬性定義的自頂向下翻譯5.5L-屬性定義的自底向上翻譯提綱S-屬性定義僅僅使用綜合屬性的SDD稱為S屬性的SDD，或S-屬性定義、S-SDD例如果一個(gè)SDD是S屬性的，可以按照語(yǔ)法分析樹節(jié)點(diǎn)的任何自底向上順序來(lái)計(jì)算它的各個(gè)屬性值S-屬性定義可以在自底向上語(yǔ)法分析的過(guò)程中實(shí)現(xiàn)

產(chǎn)生式

語(yǔ)義規(guī)則(1)L

En Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

Tval=Fval(6)F(E) Fval=Eval(7)Fdigit Fval=digitlexval5.2S-屬性定義與L-屬性定義L-屬性定義（也稱為L(zhǎng)屬性的SDD或L-SDD）的直觀含義：在一個(gè)產(chǎn)生式所關(guān)聯(lián)的各屬性之間，依賴圖的邊可以從左到右，但不能從右到左（因此稱為L(zhǎng)屬性的，L是Left的首字母）L-屬性定義一個(gè)SDD是L-屬性定義，當(dāng)且僅當(dāng)它的每個(gè)屬性要么是一個(gè)綜合屬性，要么是滿足如下條件的繼承屬性：假設(shè)存在一個(gè)產(chǎn)生式A→X1X2…Xn，其右部符號(hào)Xi(1

n)的繼承屬性僅依賴于下列屬性：A的繼承屬性產(chǎn)生式中Xi左邊的符號(hào)

X1,X2,…,Xi-1

的屬性Xi本身的屬性，但Xi的全部屬性不能在依賴圖中形成環(huán)路每個(gè)S-屬性定義都是L-屬性定義L-SDD的正式定義一個(gè)SDD是L-屬性定義，當(dāng)且僅當(dāng)它的每個(gè)屬性要么是一個(gè)綜合屬性，要么是滿足如下條件的繼承屬性：假設(shè)存在一個(gè)產(chǎn)生式A→X1X2…Xn，其右部符號(hào)Xi(1

n)的繼承屬性僅依賴于下列屬性：A的繼承屬性產(chǎn)生式中Xi左邊的符號(hào)

X1,X2,…,Xi-1

的屬性Xi本身的屬性，但Xi的全部屬性不能在依賴圖中形成環(huán)路為什么不能是綜合屬性？L-SDD的正式定義一個(gè)SDD是L-屬性定義，當(dāng)且僅當(dāng)它的每個(gè)屬性要么是一個(gè)綜合屬性，要么是滿足如下條件的繼承屬性：假設(shè)存在一個(gè)產(chǎn)生式A→X1X2…Xn，其右部符號(hào)Xi(1

n)的繼承屬性僅依賴于下列屬性：A的繼承屬性產(chǎn)生式中Xi左邊的符號(hào)

X1,X2,…,Xi-1

的屬性Xi本身的屬性，但Xi的全部屬性不能在依賴圖中形成環(huán)路XjAisisL-SDD的正式定義

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

FT′

T′.inh=F.val

T.val

=T′.syn(2)T′

*FT1′

T1′.inh=T′.inh×F.val

T′.syn=

T1′.syn

(3)T′

T′.syn=T′.inh(4)

Fdigit F.val=digit.lexval綜合屬性繼承屬性例：L-SDD非L屬性的SDD例

產(chǎn)生式

語(yǔ)義規(guī)則(1)A

LM L.i=l(A.i) M.i=m(L.s) A.s=f(M.s)(2)A

QR R.i=r(A.i) Q.i=q(R.s)

A.s=f(Q.s)綜合屬性繼承屬性×5.1語(yǔ)法制導(dǎo)定義SDD5.2S-屬性定義與L-屬性定義5.3語(yǔ)法制導(dǎo)翻譯方案SDT5.4L-屬性定義的自頂向下翻譯5.5L-屬性定義的自底向上翻譯提綱

語(yǔ)法制導(dǎo)翻譯方案(SDT)是在產(chǎn)生式右部中嵌入了程序片段(稱為語(yǔ)義動(dòng)作)的CFG例D→T

{L.inh=T.type}LT→int{T.type=integer}T→real{T.type=real}L→{L1.inh=L.inh}L1,id5.3語(yǔ)法制導(dǎo)翻譯方案SDT

語(yǔ)法制導(dǎo)翻譯方案(SDT)是在產(chǎn)生式右部中嵌入了程序片段(稱為語(yǔ)義動(dòng)作)的CFG語(yǔ)法制導(dǎo)翻譯方案SDTSDT可以看作是SDD的具體實(shí)施方案本節(jié)主要關(guān)注如何使用SDT來(lái)實(shí)現(xiàn)兩類重要的SDD，因?yàn)樵谶@兩種情況下，SDT可以在語(yǔ)法分析過(guò)程中實(shí)現(xiàn)基本文法可以使用LR分析技術(shù)，且SDD是S屬性的基本文法可以使用LL分析技術(shù)，且SDD是L屬性的

將一個(gè)S-SDD轉(zhuǎn)換為SDT的方法：將每個(gè)語(yǔ)義動(dòng)作都放在產(chǎn)生式的最后例SDT產(chǎn)生式

語(yǔ)義規(guī)則(1)L

Lval=Eval(2)E

E1+T Eval=E1val+Tval(3)E

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

Tval=Fval(6)F(E) Fval=Eval(7)F

digit

Fval=digit

lexval(1)L

{Lval=Eval}(2)E

E1+T{Eval=E1val+Tval}(3)E

{Eval=Tval}(4)T

T1*F

{Tval=T1val×Fval}(5)T

{Tval=Fval}(6)F(E){Fval=Eval}(7)F

digit

{Fval=digit

lexval}S-SDD將S-SDD轉(zhuǎn)換為SDT如果一個(gè)S-SDD的基本文法可以使用LR分析技術(shù)，那么它的SDT可以在LR語(yǔ)法分析過(guò)程中實(shí)現(xiàn)例

產(chǎn)生式

語(yǔ)義規(guī)則(1)L

Lval=Eval(2)E

E1+TEval=E1val+Tval(3)E

Eval=Tval(4)T

T1*F

Tval=T1val×Fval(5)T

Tval=Fval(6)F(E)Fval=Eval(7)F

digit

Fval=digit

lexvalS-SDDSLR自動(dòng)機(jī)當(dāng)歸約發(fā)生時(shí)執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作S-屬性定義的SDT實(shí)現(xiàn)狀態(tài)文法符號(hào)綜合屬性S0$.........Sm-2XX.xSm-1YY.ySmZZ.z.........top若支持多個(gè)屬性使棧記錄變得足夠大在棧記錄中存放指針擴(kuò)展的LR語(yǔ)法分析棧在分析棧中使用一個(gè)附加的域來(lái)存放綜合屬性值A(chǔ)

XYZ{A.a=f(X.x,Y.y,Z.z)}A.aX.X

Y.y

Z.zstack[top-2].symb=A

stack[top-2].val=f(stack[top-2].val,stack[top-1].val,stack[top].val)top=top-2;重寫語(yǔ)義動(dòng)作使其顯示地操作語(yǔ)法分析棧

產(chǎn)生式語(yǔ)義動(dòng)作(1)E′→E print(Eval) {print

(stack[top].val);}(2)E→E1+TEval=E1val+Tval {stack[top-2].val=stack[top-2].val+stack[top].val; top=top-2;}(3)E→T Eval=Tval(4)T→T1*

FTval=T1val×Fval {stack[top-2].val=stack[top-2].val×stack[top].val; top=top-2;}(5)T→F Tval=Fval(6)F→(E)Fval=Eval {stack[top-2].val=stack[top-1].val; top=top-2;}(7)F→digitFval=digitlexval

例：在自底向上語(yǔ)法分析棧中實(shí)現(xiàn)桌面計(jì)算器例狀態(tài)

符號(hào)

屬性輸入：3*5+40$_5d3SLR自動(dòng)機(jī)

產(chǎn)生式語(yǔ)義動(dòng)作(1)E′→E{print(stack[top].val);}(2)E→E1+T{stack[top-2].val=stack[top-2].val+stack[top].val;top=top-2;}(3)E→T(4)T→T1*