1、第四章第四章 語(yǔ)法制導(dǎo)的翻譯語(yǔ)法制導(dǎo)的翻譯 本章內(nèi)容本章內(nèi)容1、介紹一種形式化的語(yǔ)義描述方法：、介紹一種形式化的語(yǔ)義描述方法：語(yǔ)法制導(dǎo)的語(yǔ)法制導(dǎo)的翻譯翻譯，它包括兩種具體形式，它包括兩種具體形式語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義翻譯方案翻譯方案2、介紹語(yǔ)法制導(dǎo)翻譯的實(shí)現(xiàn)方法、介紹語(yǔ)法制導(dǎo)翻譯的實(shí)現(xiàn)方法4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義 例例 簡(jiǎn)單臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義簡(jiǎn)單臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(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.v

2、al = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.1 語(yǔ)法制導(dǎo)定義的形式語(yǔ)法制導(dǎo)定義的形式 基礎(chǔ)文法基礎(chǔ)文法 每個(gè)文法符號(hào)有一組屬性每個(gè)文法符號(hào)有一組屬性 每個(gè)文法產(chǎn)生式每個(gè)文法產(chǎn)生式A 有有一組形式為一組形式為b=f(c1, c2, , ck )的語(yǔ)義規(guī)則的語(yǔ)義規(guī)則，其中其中b和和c1, c2, , ck 是該產(chǎn)生式文法符號(hào)的屬性，是該產(chǎn)生式文法符號(hào)的屬性，f 是函數(shù)是函數(shù) 綜合屬性：綜合屬性：如果如果b是是A的屬性，的屬性，c1

3、, c2 , , ck 是產(chǎn)生式右部文法符號(hào)的屬性或是產(chǎn)生式右部文法符號(hào)的屬性或A的其它屬性的其它屬性 繼承屬性繼承屬性：如果：如果b是右部某文法符號(hào)是右部某文法符號(hào)X的屬性的屬性4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.2 綜合屬性綜合屬性S屬性定義屬性定義：僅使用綜合屬性的語(yǔ)法制導(dǎo)定義僅使用綜合屬性的語(yǔ)法制導(dǎo)定義產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(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

4、(E) F.val = E.val F digit F.val = digit.lexval4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義 例例 8+5* *2 n的注釋分析樹(shù)的注釋分析樹(shù)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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval = 2LE.val = 18

5、nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定

6、義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexv

7、al = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.l

8、exval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(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

9、= 54.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val =

10、8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(jié)點(diǎn)屬

11、性的計(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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹(shù)各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.

12、val = 2digit.lexval = 54.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義注釋分析樹(shù)注釋分析樹(shù): :結(jié)點(diǎn)的屬性值都標(biāo)注出來(lái)的分析樹(shù)結(jié)點(diǎn)的屬性值都標(biāo)注出來(lái)的分析樹(shù)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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.3 繼承屬性繼承屬性int id, id, id產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 D TL L.in = T.type T in

13、t 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 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義 例例 int id1, id2, id3的注釋分析樹(shù)的注釋分析樹(shù)DintT.type = integer,id3L.in = integerL.in = integerL.in = integerid2id1,4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.4 屬性依賴(lài)圖屬性依賴(lài)圖 例例 int id1, id2, id3的分析

14、樹(shù)的依賴(lài)圖的分析樹(shù)的依賴(lài)圖 D TL L.in = T.typeD intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.4 屬性依賴(lài)圖屬性依賴(lài)圖 例例 int id1, id2, id3的分析樹(shù)的依賴(lài)圖的分析樹(shù)的依賴(lài)圖L L1, id L1.in = L.in; addType (id.entry, L.in) D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.4

15、 屬性依賴(lài)圖屬性依賴(lài)圖 例例 int id1, id2, id3的分析樹(shù)的依賴(lài)圖的分析樹(shù)的依賴(lài)圖L id addType (id.entry, L.in) D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.5 屬性計(jì)算次序?qū)傩杂?jì)算次序1、拓?fù)渑判颉⑼負(fù)渑判颍航Y(jié)點(diǎn)的一種排序，使得邊只會(huì)從該次：結(jié)點(diǎn)的一種排序，使得邊只會(huì)從該次序中先出現(xiàn)的結(jié)點(diǎn)到后出現(xiàn)的結(jié)點(diǎn)序中先出現(xiàn)的結(jié)點(diǎn)到后出現(xiàn)的結(jié)點(diǎn) 例例 1，2，3，4，5，6，7，8，9，10D intT,id3LLLid2id1,1 en

16、try102 entry3 entryin 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.5 屬性計(jì)算次序?qū)傩杂?jì)算次序2、屬性計(jì)算次序：、屬性計(jì)算次序：構(gòu)造輸入的分析樹(shù)構(gòu)造輸入的分析樹(shù)D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.5 屬性計(jì)算次序?qū)傩杂?jì)算次序2、屬性計(jì)算次序：、屬性計(jì)算次序：構(gòu)造輸入的分析樹(shù)，構(gòu)造屬性依構(gòu)造輸入的分析樹(shù)，構(gòu)造屬性依賴(lài)圖賴(lài)圖D intT,id3LLLid2id1,1 entry102 entry3 entryi

17、n 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.5 屬性計(jì)算次序?qū)傩杂?jì)算次序2、屬性計(jì)算次序：、屬性計(jì)算次序：構(gòu)造輸入的分析樹(shù)，構(gòu)造屬性依構(gòu)造輸入的分析樹(shù)，構(gòu)造屬性依賴(lài)圖，對(duì)結(jié)點(diǎn)進(jìn)行拓?fù)渑判蛸?lài)圖，對(duì)結(jié)點(diǎn)進(jìn)行拓?fù)渑判駾 intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義4.1.5 屬性計(jì)算次序?qū)傩杂?jì)算次序2、屬性計(jì)算次序：、屬性計(jì)算次序：構(gòu)造輸入的分析樹(shù)，構(gòu)造屬性依構(gòu)造輸入的分析樹(shù)，構(gòu)造屬性依賴(lài)圖，對(duì)結(jié)點(diǎn)進(jìn)行拓?fù)渑判?，按拓?fù)渑判虻拇涡蛴?jì)賴(lài)圖，對(duì)結(jié)點(diǎn)進(jìn)行拓?fù)?/p>

18、排序，按拓?fù)渑判虻拇涡蛴?jì)算屬性算屬性D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語(yǔ)法制導(dǎo)的定義語(yǔ)法制導(dǎo)的定義語(yǔ)義規(guī)則的計(jì)算方法語(yǔ)義規(guī)則的計(jì)算方法 分析樹(shù)方法：剛才介紹的方法，動(dòng)態(tài)確定計(jì)分析樹(shù)方法：剛才介紹的方法，動(dòng)態(tài)確定計(jì)算次序，效率低算次序，效率低概念上的一般方法概念上的一般方法 基于規(guī)則的方法：基于規(guī)則的方法：（編譯器實(shí)現(xiàn)者）（編譯器實(shí)現(xiàn)者）靜態(tài)確靜態(tài)確定定（編譯器設(shè)計(jì)者提供的）（編譯器設(shè)計(jì)者提供的）語(yǔ)義規(guī)則的計(jì)算語(yǔ)義規(guī)則的計(jì)算次序次序 適用于手工構(gòu)造的方法適用于手工構(gòu)造的方法 忽略規(guī)則的方法：忽略規(guī)

19、則的方法：（編譯器實(shí)現(xiàn)者）（編譯器實(shí)現(xiàn)者）事先確事先確定屬性的計(jì)算策略（如邊分析邊計(jì)算）定屬性的計(jì)算策略（如邊分析邊計(jì)算）, ,（編（編譯器設(shè)計(jì)者提供的）譯器設(shè)計(jì)者提供的）語(yǔ)義規(guī)則必須符合所選語(yǔ)義規(guī)則必須符合所選分析方法的限制分析方法的限制 適用于自動(dòng)生成的方法適用于自動(dòng)生成的方法4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算4.2.1 語(yǔ)法樹(shù)語(yǔ)法樹(shù) 語(yǔ)法樹(shù)是分析樹(shù)的濃縮表示語(yǔ)法樹(shù)是分析樹(shù)的濃縮表示：算符和關(guān)鍵字是作為算符和關(guān)鍵字是作為內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn) 語(yǔ)法制導(dǎo)翻譯可以基于分析樹(shù)，也可以基于語(yǔ)法樹(shù)語(yǔ)法制導(dǎo)翻譯可以基于分析樹(shù)，也可以基于語(yǔ)法樹(shù) 語(yǔ)法樹(shù)的例子：語(yǔ)法樹(shù)的例子： if B th

20、en S1 else S2 8 + 5 2if-then-elseBS1S2+*2584.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算4.2.2 構(gòu)造語(yǔ)法樹(shù)的語(yǔ)法制導(dǎo)定義構(gòu)造語(yǔ)法樹(shù)的語(yǔ)法制導(dǎo)定義產(chǎn)產(chǎn) 生生 式式語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 E E1 + T E.nptr = mkNode( +, E1.nptr, T.nptr) E T 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 F id F.nptr = mkLeaf (id, id.

21、entry) F num F.nptr = mkLeaf (num, num.val) 4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnu

22、mididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.

23、nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+

24、F.nptrF.nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptrid

25、T.nptr+ F.nptrF.nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語(yǔ)法樹(shù)的構(gòu)造的語(yǔ)法樹(shù)的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算4.2.3 S屬性的自下而上計(jì)算屬性的自下而上計(jì)算LR分析器的棧分析器的棧增加增加一個(gè)

26、域來(lái)保存綜合屬性值一個(gè)域來(lái)保存綜合屬性值若產(chǎn)生式若產(chǎn)生式A XYZ的語(yǔ)義規(guī)則是的語(yǔ)義規(guī)則是A.a = f (X.x, Y.y, Z.z)，那么歸約后：那么歸約后：. . . . . .AA.a. . . . . .top. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 L

27、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.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 L E n

28、 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.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 L E n pr

29、int (val top 1 ) 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.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 L E n

30、print (val top 1 ) E E1 + T val top 2 =val top 2+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.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼

31、段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+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.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 L

32、E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段

33、段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) F.val = E.val F digit F.val = digit.lexval4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 L E n pr

34、int (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit F.val = digit.lexval4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼臺(tái)式計(jì)算器的語(yǔ)法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 L E n print

35、 (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算邊分析邊翻譯的方式能否用于繼承屬性邊分析邊翻譯的方式能否用于繼承屬性？ 屬性的計(jì)算次序一定受分析方法所限定的分析樹(shù)結(jié)屬性的計(jì)算次序一定受分析方法所限定的分析樹(shù)結(jié)點(diǎn)建立次序的限制點(diǎn)建立次序的限制 分析樹(shù)的結(jié)點(diǎn)是自左向右生成分析樹(shù)的結(jié)點(diǎn)是自左向右生成 如果屬性信息是自左向右流動(dòng)，那么就

36、有可能在分如果屬性信息是自左向右流動(dòng)，那么就有可能在分析的同時(shí)完成屬性計(jì)算析的同時(shí)完成屬性計(jì)算4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.1 L屬性定義屬性定義 如果每個(gè)產(chǎn)生式如果每個(gè)產(chǎn)生式A X1 X2 Xn 的每條語(yǔ)義的每條語(yǔ)義規(guī)則計(jì)算的屬性是規(guī)則計(jì)算的屬性是A的綜合屬性；或者是的綜合屬性；或者是Xj 的繼承屬性，的繼承屬性，1 j n, , 但它僅依賴(lài)：但它僅依賴(lài)： 該產(chǎn)生式中該產(chǎn)生式中Xj左邊符號(hào)左邊符號(hào)X1, X2, , Xj-1的屬性；的屬性； A的繼承屬性的繼承屬性 S屬性定義屬于屬性定義屬于L屬性定義屬性定義4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)

37、算變量類(lèi)型聲明的語(yǔ)法制導(dǎo)定義是一個(gè)變量類(lèi)型聲明的語(yǔ)法制導(dǎo)定義是一個(gè)L屬性定義屬性定義 產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(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.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.2 翻譯方案翻譯方案 例例 把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式如果輸入是如果輸入是8+

38、5 2，則輸出是，則輸出是8 5 + 2 E T RR addop T print (addop.lexeme) R1 | T num print (num.val)E T R num print (8) R numprint (8)addop Tprint (+)R numprint(8)addop numprint(5)print (+)R print(8)print(5)print(+)addop Tprint( )R print(8)print(5)print(+)print(2)print( )4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算 例例 數(shù)學(xué)排版語(yǔ)言數(shù)學(xué)排版語(yǔ)言EQ

39、N E sub 1 .val S B B B1 B2 B B1 sub B2 B text E1.val4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算 例例 數(shù)學(xué)排版語(yǔ)言數(shù)學(xué)排版語(yǔ)言EQN E sub 1 .val 產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 S B B.ps = 10; S.ht = B.ht B B1 B2 B1.ps = B.ps; B2.ps = B.ps; B.ht = max(B1.ht, B2.ht ) B B1 sub B2 B1.ps =B.ps; B2.ps = shrink(B.ps); B.ht = disp (B1.ht, B2.ht ) B t

40、ext B.ht = text.h B.ps E1.val4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算 例例 數(shù)學(xué)排版語(yǔ)言數(shù)學(xué)排版語(yǔ)言EQN S B.ps = 10 BS.ht = B.ht B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算 例例 數(shù)學(xué)排版語(yǔ)言數(shù)學(xué)排版語(yǔ)言E

41、QN S B.ps = 10 B繼承屬性的計(jì)算繼承屬性的計(jì)算BS.ht = B.ht 位于位于B的左邊的左邊 B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算 例例 數(shù)學(xué)排版語(yǔ)言數(shù)學(xué)排版語(yǔ)言EQN S B.ps = 10 BS.ht = B.ht B綜合屬性的計(jì)算綜合屬性的計(jì)算 B

42、B1.ps = B.ps 放在右部末端放在右部末端 B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算 例例 左遞歸的消除引起繼承屬性左遞歸的消除引起繼承屬性產(chǎn)產(chǎn) 生生 式式語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 E E1 + T E.nptr = mkNode( +, E1.nptr, T.nptr) E T E.nptr =

43、T.nptr T T1 F T.nptr = mkNode( , T1.nptr, F.nptr) T F T.nptr = F.nptr F (E) F.nptr = E.nptr F id F.nptr = mkLeaf (id, id.entry) F num F.nptr = mkLeaf (num, num.val) 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算E T R.i = T.nptrRE.nptr = R.sR +TR1.i = mkNode ( +, R.i, T.nptr)R1R.s = R1.sR R.s = R.i T F W.i = F.nptrWT.n

44、ptr = W.sW FW1.i = mkNode ( , W.i, F.nptr)W1W.s = W1.sW W.s = W.i F 產(chǎn)生式部分沒(méi)有給出產(chǎn)生式部分沒(méi)有給出4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算E T R.i = T.nptr T + T + T + RE.nptr = R.sR +TR1.i = mkNode ( +, R.i, T.nptr)R1R.s = R1.sR R.s = R.i T F W.i = F.nptrWT.nptr = W.sW FW1.i = mkNode ( , W.i, F.nptr)W1W.s = W1.sW W.s = W.i

45、F 產(chǎn)生式部分沒(méi)有給出產(chǎn)生式部分沒(méi)有給出4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性

46、定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnu

47、mididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向

48、符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號(hào)表中指向符號(hào)表中a的入口的入口指向符號(hào)表中指向符號(hào)表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.3 預(yù)測(cè)翻譯器的設(shè)計(jì)預(yù)測(cè)翻譯器的設(shè)計(jì)把預(yù)測(cè)分析器的構(gòu)造方法推廣到翻譯方案的實(shí)現(xiàn)把預(yù)測(cè)分析器的構(gòu)造方法推廣到翻譯方案的實(shí)現(xiàn)產(chǎn)生式產(chǎn)生式R +TR | 的分析過(guò)程的分析過(guò)程void R( ) if (loo

49、kahead = + ) match ( + ); T( ); R( );else / 什么也不做什么也不做 /4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算syntaxTreeNode R (syntaxTreeNode i) syntaxTreeNode nptr, i1, s1, s;char addoplexeme;if (lookahead = + ) / 產(chǎn)生式產(chǎn)生式 R +T R /addoplexeme = lexval;match(+ ); nptr = T();i1 = mkNode(addoplexeme, i , nptr);s1 = R (i1); s = s

50、1;else s = i; / 產(chǎn)生式產(chǎn)生式 R /return s;R : i, sT : nptr+ : addoplexeme4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.4 用綜合屬性代替繼承屬性用綜合屬性代替繼承屬性Pascal的聲明，如的聲明，如m, n : integerD L : TT integer | charL L, id | id4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.4 用綜合屬性代替繼承屬性用綜合屬性代替繼承屬性Pascal的聲明，如的聲明，如m, n : integerD L : TT integer | charL L, i

51、d | id改成從右向左歸約改成從右向左歸約D id LL , id L | : TT integer | charD:L,idLidintegerT4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算D id L addtype (id. entry, L. type)L , id L1 L. type = L1. Type; addtype (id. entry, L1. type)L : T L. type = T. typeT integer T. type = integerT real T. type = realD:L,idLidintegerT4.4 L屬性的自下而上計(jì)算屬性

52、的自下而上計(jì)算在自下而上分析的框架中實(shí)現(xiàn)在自下而上分析的框架中實(shí)現(xiàn)L屬性定義的方法屬性定義的方法 它能實(shí)現(xiàn)任何基于它能實(shí)現(xiàn)任何基于LL(1)文法的文法的L屬性定義屬性定義 也能實(shí)現(xiàn)許多（但不是所有的）基于也能實(shí)現(xiàn)許多（但不是所有的）基于LR(1) 的的L屬性定義屬性定義4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算4.4.1 刪除翻譯方案中嵌入的動(dòng)作刪除翻譯方案中嵌入的動(dòng)作E T RR + T print (+)R1 | T print ( )R1 | T num print (num.val)在文法中加入產(chǎn)生在文法中加入產(chǎn)生 的的標(biāo)記非終結(jié)符標(biāo)記非終結(jié)符，讓每個(gè)嵌入動(dòng)，讓每個(gè)嵌入動(dòng)作由不同標(biāo)

53、記非終結(jié)符作由不同標(biāo)記非終結(jié)符M代表，并把該動(dòng)作放在產(chǎn)代表，并把該動(dòng)作放在產(chǎn)生式生式M 的右端的右端E T RR + T M R1 | T N R1 | T num print (num.val)M print (+)N print ( ) 這些動(dòng)作的一個(gè)重要這些動(dòng)作的一個(gè)重要特點(diǎn)：特點(diǎn)：沒(méi)有引用原來(lái)產(chǎn)生式?jīng)]有引用原來(lái)產(chǎn)生式文法符號(hào)的屬性文法符號(hào)的屬性4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算4.4.2 分析棧上的繼承屬性分析棧上的繼承屬性例例 int p, q, r D T L.in = T.type LT int T. type = integerT real T. type = re

54、alL L1.in = L.in L1, id addtype (id.entry, L.in )L id addtype (id.entry, L.in )4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算4.4.2 分析棧上的繼承屬性分析棧上的繼承屬性1、屬性位置能預(yù)測(cè)、屬性位置能預(yù)測(cè)例例 int p, q, r D T L.in = T.type LT int T. type = integerT real T. type = realL L1.in = L.in L1, id addtype (id.entry, L.in )L id addtype (id.entry, L.in )DT

55、LL,rL,qpint type ininin4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算4.4.2 分析棧上的繼承屬性分析棧上的繼承屬性1、屬性位置能預(yù)測(cè)、屬性位置能預(yù)測(cè)例例 int p, q, r D T L.in = T.type LT int T. type = integerT real T. type = realL L1.in = L.in L1, id addtype (id.entry, L.in )L id addtype (id.entry, L.in )DTLL,rL,qpint type ininin繼承屬性的計(jì)算可繼承屬性的計(jì)算可以略去，以略去，引用繼承屬引用繼承

56、屬性的地方改成引用其性的地方改成引用其他符號(hào)的綜合屬性他符號(hào)的綜合屬性4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算DTLL,rL,qpint type ininin產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 D TL T int valtop = integer T real valtop = real L L1, id addType(valtop, valtop 3) L id addType(valtop, valtop 1) 4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算2、屬性的位置不能預(yù)測(cè)、屬性的位置不能預(yù)測(cè)S aACC.i = A.sS bABCC.i = A.sC cC.s = g(

57、C.i) 增加標(biāo)記非終結(jié)符，使得位置可以預(yù)測(cè)增加標(biāo)記非終結(jié)符，使得位置可以預(yù)測(cè)S aACC.i = A.sS bABMCM.i = A.s; C.i = M.sC cC.s = g(C.i)M M.s = M.i4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算2、屬性的位置不能預(yù)測(cè)、屬性的位置不能預(yù)測(cè)S aACC.i = A.sS bABCC.i = A.sC cC.s = g(C.i) 增加標(biāo)記非終結(jié)符，使得位置可以預(yù)測(cè)增加標(biāo)記非終結(jié)符，使得位置可以預(yù)測(cè)S aACC.i = A.sS bABMCM.i = A.s; C.i = M.sC cC.s = g(C.i) 還得考慮還得考慮M.sM M

58、.s = M.i 計(jì)算的可預(yù)測(cè)計(jì)算的可預(yù)測(cè)4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算4.4.3 模擬繼承屬性的計(jì)算模擬繼承屬性的計(jì)算繼承屬性是某個(gè)綜合屬性的一個(gè)函數(shù)繼承屬性是某個(gè)綜合屬性的一個(gè)函數(shù)S aACC.i = f (A.s)C cC.s = g(C.i) 增加標(biāo)記非終結(jié)符，把增加標(biāo)記非終結(jié)符，把f(A.s)的計(jì)算移到對(duì)標(biāo)的計(jì)算移到對(duì)標(biāo)記非終結(jié)符歸約時(shí)進(jìn)行記非終結(jié)符歸約時(shí)進(jìn)行S aANCN.i = A.s; C.i = N.sN N.s = f (N.i)C cC.s = g(C.i)4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 例例 數(shù)學(xué)排版語(yǔ)言數(shù)學(xué)排版語(yǔ)言EQN S B.ps

59、= 10 BS.ht = B.ht B B1.ps = B.ps B1B2.ps = B.ps B2B.ht = max(B1.ht, B2.ht ) B B1.ps =B.ps B1sub B2.ps = shrink(B.ps) B2B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps 4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 S LB B.ps = L.s; S.ht = B.ht L L.s = 10 將將B.ps存入棧中，便于引用存入棧中，便于引用B B1 MB2 B1.ps = B.

60、ps; M.i = B.ps;B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M M.s = M.iB B1 sub NB2 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 text B.ht = text.h B.ps 4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算產(chǎn)產(chǎn) 生生 式式 語(yǔ)語(yǔ) 義義 規(guī)規(guī) 則則 S LB B.ps = L.s; S.ht = B.ht L L.s = 10 將將B.ps存入棧中，便于引用存入棧中，便于引用B B1