中國科學(xué)技術(shù)大學(xué)陳意云編譯原理全套參考資料陳意云編譯原理全套參考資料chapter4

第四章語法制導(dǎo)的翻譯本章內(nèi)容介紹一種形式化的語義描述方法：語法制導(dǎo)的翻譯，包括它的兩種具體形式：語法制導(dǎo)的定義和翻譯方案。介紹語法制導(dǎo)的翻譯的實(shí)現(xiàn)方法。4.1語法制導(dǎo)的定義例 簡單臺式計(jì)算器的語法制導(dǎo)定義產(chǎn)

生

式

語

義

規(guī)

則

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.1語法制導(dǎo)的定義4.1.1語法制導(dǎo)定義的形式基礎(chǔ)文法每個(gè)文法符號有一組屬性每個(gè)文法產(chǎn)生式A

有一組形式為b:=f(c1,c2,…,ck)的語義規(guī)則，其中f

是函數(shù)，b和c1,c2,…,ck

是該產(chǎn)生式文法符號的屬性。綜合屬性：如果b是A的屬性，c1,c2,…,ck

是產(chǎn)生式右部文法符號的屬性或A的其它屬性。繼承屬性：如果b是產(chǎn)生式右部某個(gè)文法符號X的屬性。4.1語法制導(dǎo)的定義4.1.2綜合屬性S屬性定義：僅僅使用綜合屬性的語法制導(dǎo)定義產(chǎn)

生

式

語

義

規(guī)

則

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.1語法制導(dǎo)的定義8+5*2n的注釋分析樹digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義注釋分析樹:結(jié)點(diǎn)的屬性值都標(biāo)注出來的分析樹digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=54.1語法制導(dǎo)的定義

繼承屬性

intid,id,id產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

4.1語法制導(dǎo)的定義intid1,id2,id3的注釋分析樹DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,4.1語法制導(dǎo)的定義4.1.4屬性依賴圖 intid1,id2,id3的分析樹的依賴圖DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1語法制導(dǎo)的定義4.1.5屬性計(jì)算次序拓?fù)渑判颍航Y(jié)點(diǎn)的一種排序，使得邊只會從該次序中先出現(xiàn)的結(jié)點(diǎn)到后出現(xiàn)的結(jié)點(diǎn)。例：1，2，3，4，5，6，7，8，9，10DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1語法制導(dǎo)的定義屬性計(jì)算次序構(gòu)造輸入的分析樹DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1語法制導(dǎo)的定義屬性計(jì)算次序構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1語法制導(dǎo)的定義屬性計(jì)算次序構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點(diǎn)進(jìn)行拓?fù)渑判駾intT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1語法制導(dǎo)的定義屬性計(jì)算次序構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點(diǎn)進(jìn)行拓?fù)渑判颍赐負(fù)渑判虻拇涡蛴?jì)算屬性。DintT,id3LLLid2id1,1entry102entry3entryin98in76in54type4.1語法制導(dǎo)的定義語義規(guī)則的計(jì)算方法分析樹方法：前面介紹的方法。4.1語法制導(dǎo)的定義語義規(guī)則的計(jì)算方法分析樹方法：前面介紹的方法。基于規(guī)則的方法：靜態(tài)確定語義規(guī)則的計(jì)算次序。4.1語法制導(dǎo)的定義語義規(guī)則的計(jì)算方法分析樹方法：前面介紹的方法?；谝?guī)則的方法：靜態(tài)確定語義規(guī)則的計(jì)算次序。忽略規(guī)則的方法：事先確定屬性的計(jì)算策略（如邊分析邊計(jì)算），那么語義規(guī)則的設(shè)計(jì)必須符合所選分析方法的限制。4.2S屬性定義的自下而上計(jì)算

語法樹語法樹是分析樹的濃縮表示：算符和關(guān)鍵字是作為內(nèi)部結(jié)點(diǎn)。

語法制導(dǎo)翻譯可以基于分析樹，也可以基于語法樹語法樹的例子：if-then-elseBS1S2+*2584.2S屬性定義的自下而上計(jì)算

構(gòu)造語法樹的語法制導(dǎo)定義產(chǎn)生式語

義

規(guī)

則

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

ET

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F(E)

F.nptr:=E.nptr

Fid

F.nptr:=mkleaf(id,id.entry)

Fnum

F.nptr:=mkleaf(num,num.val)

4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算a+5*b的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符號表中a的入口指向符號表中b的入口4.2S屬性定義的自下而上計(jì)算4.2.3S屬性的自下而上計(jì)算

將LR分析器增加一個(gè)域來保存綜合屬性值。......ZZ.zYY.yXX.x......棧statevaltop4.2S屬性定義的自下而上計(jì)算4.2.3S屬性的自下而上計(jì)算

將LR分析器增加一個(gè)域來保存綜合屬性值。......ZZ.zYY.yXX.x......棧statevaltop若產(chǎn)生式A

→XYZ的語義規(guī)則是A.a:=f(X.x,Y.y,Z.z)4.2S屬性定義的自下而上計(jì)算4.2.3S屬性的自下而上計(jì)算

將LR分析器增加一個(gè)域來保存綜合屬性值。......ZZ.zYY.yXX.x......棧statevaltop若產(chǎn)生式A

→XYZ的語義規(guī)則是A.a:=f(X.x,Y.y,Z.z)，那么歸約后：......AA.a......top4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

語義規(guī)則

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(E.val)

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

E.val:=E1.val+T.val

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

E.val:=T.val

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

T.val:=T1.val

*

F.val

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

T.val:=F.val

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

F.val:=E.val

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

val[top2]

:=val[top1]

F

digit

F.val:=digit.lexval4.2S屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼

......ZZ.zYY.yXX.x......棧statevaltop產(chǎn)

生

式

代碼段

L

E

n

print(val[top1])

E

E1+T

val[top2]:=val[top2]+val[top]

E

T

T

T1*

F

val[top2]:=val[top2]val[top]

T

F

F(E)

val[top2]

:=val[top1]

F

digit

4.3L屬性定義的自上而下計(jì)算邊分析邊翻譯的方式能否用于繼承屬性？屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制。4.3L屬性定義的自上而下計(jì)算邊分析邊翻譯的方式能否用于繼承屬性？屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制。分析樹的結(jié)點(diǎn)是自左向右生成。4.3L屬性定義的自上而下計(jì)算邊分析邊翻譯的方式能否用于繼承屬性？屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制。分析樹的結(jié)點(diǎn)是自左向右生成。如果屬性信息是自左向右流動，那么就有可能在分析的同時(shí)完成屬性計(jì)算。4.3L屬性定義的自上而下計(jì)算4.3.1L屬性定義如果每個(gè)產(chǎn)生式AX1

X2…Xn

的每條語義規(guī)則計(jì)算的屬性是A的綜合屬性；或者是Xj

的繼承屬性，1

j

n,但它僅依賴：該產(chǎn)生式中Xj左邊符號X1,X2,…,Xj-1的屬性；A的繼承屬性。4.3L屬性定義的自上而下計(jì)算4.3.1L屬性定義如果每個(gè)產(chǎn)生式AX1

X2…Xn

的每條語義規(guī)則計(jì)算的屬性是A的綜合屬性；或者是Xj

的繼承屬性，1

j

n,但它僅依賴：該產(chǎn)生式中Xj左邊符號X1,X2,…,Xj-1的屬性；A的繼承屬性。S屬性定義屬于L屬性定義。4.3L屬性定義的自上而下計(jì)算變量類型聲明的語法制導(dǎo)定義是一個(gè)L屬性定義

產(chǎn)生式

語

義

規(guī)

則

D

TL

L.in:=T.type

T

int

T.type:=integer

T

real

T.type:=real

L

L1,

id

L1.in:=L.in;

addtype(id.entry,L.in)

L

id

addtype(id.entry,L.in)

4.3L屬性定義的自上而下計(jì)算4.3.2翻譯方案例把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式 如果輸入是8+52，則輸出是85+2。

4.3L屬性定義的自上而下計(jì)算4.3.2翻譯方案例把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式 如果輸入是8+52，則輸出是85+2。

E

TR

RaddopT{print(addop.lexeme)}R1|

Tnum{print(num.val)}

4.3L屬性定義的自上而下計(jì)算4.3.2翻譯方案例把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式 如果輸入是8+52，則輸出是85+2。

E

TR

RaddopT{print(addop.lexeme)}R1|

Tnum{print(num.val)} E

TRnum{print(8)}R

num{print(8)}addopT{print(+)}R

num{print(8)}addopnum{print(5)}{print(+)}R

…

{print(8)}{print(5)}{print(+)}addopT{print()}R…

{print(8)}{print(5)}{print(+)}{print(2)}{print()}4.3L屬性定義的自上而下計(jì)算例數(shù)學(xué)排版語言EQN

Esub1.valSBBB1B2

BB1

subB2BtextE1.val4.3L屬性定義的自上而下計(jì)算例數(shù)學(xué)排版語言EQN

Esub1.val產(chǎn)

生

式

語

義

規(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)BB1

subB2

B1.ps:=B.ps;B2.ps:=shrink(B.ps);B.ht:=disp(B1.ht,B2.ht)BtextB.ht:=text.h

B.ps

E1.val4.3L屬性定義的自上而下計(jì)算例數(shù)學(xué)排版語言EQN

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 {:=disp(B1.ht,B2.ht)}

Btext {B.ht:=text.h

B.ps}4.3L屬性定義的自上而下計(jì)算例左遞歸的消除引起繼承屬性產(chǎn)生式語

義

規(guī)

則

E

E1+T

E.nptr:=mknode(‘+’,E1.nptr,T.nptr)

ET

E.nptr:=T.nptr

T

T1*F

T.nptr:=mknode(‘*’,T1.nptr,F.nptr)

T

F

T.nptr:=F.nptr

F(E)

F.nptr:=E.nptr

Fid

F.nptr:=mkleaf(id,id.entry)

Fnum

F.nptr:=mkleaf(num,num.val)

4.3L屬性定義的自上而下計(jì)算ET {R.i:=T.nptr} R {E.nptr:=R.s}R+ T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr} W {T.nptr:=}W

* F {W1.i:=mknode(‘*’,W.i,F.nptr)} W1 {W.s:=W1.s}W

{W.s:=W.i}4.3L屬性定義的自上而下計(jì)算ET {R.i:=T.nptr} T+T+T+… R {E.nptr:=R.s}R+ T {R1.i:=mknode(‘+’,R.i,T.nptr)} R1 {R.s:=R1.s}R

{R.s:=R.i}T

F {W.i:=F.nptr} W {T.nptr:=}W

* F {W1.i:=mknode(‘*’,W.i,F.nptr)} W1 {W.s:=W1.s}W

{W.s:=W.i}4.3L屬性定義的自上而下計(jì)算TF.nptrF.nptridi

W**F.nptridnumididnum5**指向符號表中a的入口指向符號表中b的入口i

W

siW略去了E

TR

T

部分4.3L屬性定義的自上而下計(jì)算4.3.3預(yù)測翻譯器的設(shè)計(jì)把預(yù)測分析器的構(gòu)造方法推廣到翻譯方案的實(shí)現(xiàn)產(chǎn)生式R+TR|

的分析過程procdureR; begin iflookahead=‘+’thenbegin match(‘+’);T;R end elsebegin/*

什么也不做*/ end end

4.3L屬性定義的自上而下計(jì)算functionR(i:syntax_tree_node):syntax_tree_node; var nptr,i1,s1,s:syntax_tree_node;

addoplexeme:char; begin iflookahead=‘+’thenbegin /*

產(chǎn)生式R+TR

*/ addoplexeme:=lexval; match(‘+’); nptr:=T;

i1:=mknode(addoplexme,i,nptr);

s1:=R(i1);

s:=s1 end elses:=i;/*

產(chǎn)生式

R

*/ returns end;R:i,sT:nptr+:addoplexeme4.3L屬性定義的自上而下計(jì)算4.3.4用綜合屬性代替繼承屬性Pascal的聲明，如m,n:integer D

L:T

Tinteger|char

L

L,id|id4.3L屬性定義的自上而下計(jì)算4.3.4用綜合屬性代替繼承屬性Pascal的聲明，如m,n:integer D

L:T

Tinteger|char

L

L,id|id改成從右向左歸約 DidL

L,idL|:T

Tinteger|char4.3L屬性定義的自上而下計(jì)算4.3.4用綜合屬性代替繼承屬性Pascal的聲明，如m,n:integer D

L:T

Tinteger|char

L

L,id|id改成從右向左歸約 DidL

L,idL|:T

Tinteger|charD:L,idLidintegerT4.3L屬性定義的自上而下計(jì)算D

idL {addtype(id.entry,L.type)}L

,idL1{L.type:=L1.Type;

addtype(id.entry,L1.type)}L:T {L.type:=T.type}T

integer{T.type:=integer}T

real {T.type:=real}D:L,idLidintegerT4.4L屬性的自下而上計(jì)算在自下而上分析的框架中實(shí)現(xiàn)L屬性定義的方法它能實(shí)現(xiàn)任何基于LL(1)文法的L屬性定義。也能實(shí)現(xiàn)許多（但不是所有的）基于LR(1)的L屬性定義。4.4L屬性的自下而上計(jì)算

刪除翻譯方案中嵌入的動作E

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

T{print(‘’)}R1|

Tnum{print(num.val)}

4.4L屬性的自下而上計(jì)算

刪除翻譯方案中嵌入的動作E

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

T{print(‘’)}R1|

Tnum{print(num.val)} 在文法中加入產(chǎn)生的標(biāo)記非終結(jié)符，讓每個(gè)嵌入動作由不同標(biāo)記非終結(jié)符M代表，并把該動作放在產(chǎn)生式M

的右端。4.4L屬性的自下而上計(jì)算

刪除翻譯方案中嵌入的動作E

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

T{print(‘’)}R1|

Tnum{print(num.val)} 在文法中加入產(chǎn)生的標(biāo)記非終結(jié)符，讓每個(gè)嵌入動作由不同標(biāo)記非終結(jié)符M代表，并把該動作放在產(chǎn)生式M

的右端。E

TRR+TMR1|

TNR1|Tnum{print(num.val)}M

{print(‘+’)}N

{print(‘’)}

4.4L屬性的自下而上計(jì)算4.4.2分析棧上的繼承屬性例intp,q,rD

T{L.in:=T.type} LTint{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)}4.4L屬性的自下而上計(jì)算4.4.2分析棧上的繼承屬性屬性位置能預(yù)測例intp,q,rD

T{L.in:=T.type} LTint{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)}DTLL,rL,qpinttypeininin4.4L屬性的自下而上計(jì)算DTLL,rL,qpinttypeininin產(chǎn)生式

代碼段

D

TL

Tintval[top]:=integer

Trealval[top]:=real

L

L1,idaddtype(val[top],val[top3])Lidaddtype(val[top],val[top1])4.4L屬性的自下而上計(jì)算屬性的位置不能預(yù)測S

aAC C.i:=A.sS

bABC

C.i:=A.sC

c

C.s:=g(C.i)4.4L屬性的自下而上計(jì)算屬性的位置不能預(yù)測S

aAC C.i:=A.sS

bABC

C.i:=A.sC

c

C.s:=g(C.i)增加標(biāo)記非終結(jié)符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.i4.4L屬性的自下而上計(jì)算

模擬繼承屬性的計(jì)算繼承屬性是某個(gè)綜合屬性的一個(gè)函數(shù) S

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

C

c

C.s:=g(C.i)

4.4L屬性的自下而上計(jì)算

模擬繼承屬性的計(jì)算繼承屬性是某個(gè)綜合屬性的一個(gè)函數(shù) S

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

C

c

C.s:=g(C.i)

增加標(biāo)記非終結(jié)符，把f(A.s)的計(jì)算移到對標(biāo)記非終結(jié)符歸約時(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)4.4L屬性的自下而上計(jì)算例數(shù)學(xué)排版語言EQN

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 {:=disp(B1.ht,B2.ht)}

Btext {B.ht:=text.h

B.ps}4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

語義規(guī)則

SLB

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

L

L.s:=10BB1MB2

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

M.s:=M.i

BB1

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)BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

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

L

L.s:=10BB1MB2

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

M.s:=M.i

BB1

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)BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

val[top1]:=val[top]L

L.s:=10BB1MB2

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

M.s:=M.i

BB1

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)BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

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

M.s:=M.i

BB1

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)BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

M.s:=M.i

BB1

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)BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

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)BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

subNB2

val[top3]:=disp(val[top3],val[top]

)N

N.s:=shrink(N.i)BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

subNB2

val[top3]:=disp(val[top3],val[top]

)N

val[top+1]

:=shrink(val[top2])BtextB.ht:=text.h

B.ps

4.4L屬性的自下而上計(jì)算產(chǎn)

生

式

代碼段SLB

val[top1]:=val[top]L

val[top+1]

:=10BB1MB2

val[top2]:=max(val[top2],val[top])M

val[top+1]

:=val[top1]BB1

subNB2

val[top3]:=disp(val[top3],val[top]

)N

val[top+1]

:=shrink(val[top2])Btextval[top]:=val[top]val[top1]4.5遞歸計(jì)算

回顧：語法制導(dǎo)定義的實(shí)現(xiàn)分析樹方法。4.5遞歸計(jì)算

回顧：語法制導(dǎo)定義的實(shí)現(xiàn)分析樹方法。邊分析邊進(jìn)行屬性計(jì)算，只能完成L屬性計(jì)算（忽略規(guī)則的方法）。4.5遞歸計(jì)算

回顧：語法制導(dǎo)定義的實(shí)現(xiàn)分析樹方法。邊分析邊進(jìn)行屬性計(jì)算，只能完成L屬性計(jì)算（忽略規(guī)則的方法）。本節(jié)介紹先分析后計(jì)算的方法，不局限于L屬性計(jì)算（基于規(guī)則的方法）。4.5遞歸計(jì)算

回顧：語法制導(dǎo)定義的實(shí)現(xiàn)分析樹方法。邊分析邊進(jìn)行屬性計(jì)算，只能完成L屬性計(jì)算（忽略規(guī)則的方法）。本節(jié)介紹先分析后計(jì)算的方法，不局限于L屬性計(jì)算（基于規(guī)則的方法）。為每個(gè)非終結(jié)符構(gòu)造一個(gè)屬性計(jì)算函數(shù)，但是該函數(shù)不含語法分析部分。4.5遞歸計(jì)算

回顧：語法制導(dǎo)定義的實(shí)現(xiàn)分析樹方法。邊分析邊進(jìn)行屬性計(jì)算，只能完成L屬性計(jì)算（忽略規(guī)則的方法）。本節(jié)介紹先分析后計(jì)算的方法，不局限于L屬性計(jì)算（基于規(guī)則的方法）。為每個(gè)非終結(jié)符構(gòu)造一個(gè)屬性計(jì)算函數(shù)，但是該函數(shù)不含語法分析部分。為非終結(jié)符的不同綜合屬性構(gòu)造不同的函數(shù)。4.5遞歸計(jì)算4.5.1自左向右遍歷為B構(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 {:=disp(B1.ht,B2.ht)}

Btext {B.ht:=text.h

B.ps}4.5遞歸計(jì)算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在結(jié)點(diǎn)n的產(chǎn)生式

of ‘BB1B2’:

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)}4.5遞歸計(jì)算functionB(n,ps);varps1,ps2,ht1,ht2;begin case在結(jié)點(diǎn)n的產(chǎn)生式

of ‘BB1

subB2’:

ps1:=ps; ht1:=B(child(n,1),ps1);

ps2:=shrink(ps);

ht2:=B(child(n,3),ps2); returndisp(ht1,ht2);B {B1.ps:=B.ps