編譯原理陳意云chapter

1、第四章第四章 語法制導(dǎo)的翻譯語法制導(dǎo)的翻譯 本章內(nèi)容本章內(nèi)容 介紹一種形式化的語義描述方法：介紹一種形式化的語義描述方法：語法制導(dǎo)語法制導(dǎo)的翻譯的翻譯，包括它的兩種具體形式：，包括它的兩種具體形式：語法制導(dǎo)語法制導(dǎo)的定義和翻譯方案的定義和翻譯方案 介紹語法制導(dǎo)翻譯的實(shí)現(xiàn)方法介紹語法制導(dǎo)翻譯的實(shí)現(xiàn)方法4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義例例簡單臺式計(jì)算器的語法制導(dǎo)定義簡單臺式計(jì)算器的語法制導(dǎo)定義產(chǎn)產(chǎn) 生生 式式 語語 義義 規(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 語法制導(dǎo)的定義語法制導(dǎo)的定義4.1.1 語法制導(dǎo)定義的形式語法制導(dǎo)定義的形式 基礎(chǔ)文法基礎(chǔ)文法 每個文法符號有一組屬性每個文法符號有一組屬性 每個文法產(chǎn)生式每個文法產(chǎn)生式A 有一組形式為有一組形式為b = f(c1, c2, , ck )的語義規(guī)則的語義規(guī)則，其中其中f 是函數(shù)，是函數(shù)，b和和c1, c2, , ck 是該產(chǎn)生式文法符號的屬性是該產(chǎn)生式文法符號的屬性 綜合屬性：綜合屬性：如果如果b是是A的屬性，的屬性，c

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

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

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

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

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

8、成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)的定義語法制導(dǎo)的定義分析樹各結(jié)點(diǎn)屬性的計(jì)算可以自下而上地完成分析樹各結(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

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

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

11、成分析樹各結(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)的定義語法制導(dǎo)的定義注釋分析樹注釋分析樹: :結(jié)點(diǎn)的屬性值都標(biāo)注出來的分析樹結(jié)點(diǎn)的屬性值都標(biāo)注出來的分析樹digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+

12、F.val = 5F.val = 2digit.lexval = 54.1 語法制導(dǎo)的定義語法制導(dǎo)的定義4.1.3 繼承屬性繼承屬性int id, id, id產(chǎn)產(chǎn) 生生 式式 語語 義義 規(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.1 語法制導(dǎo)的定義語法制導(dǎo)的定義int id1, id2, id3的注釋分析樹的注釋分析樹DintT.type

13、= integer,id3L.in = integerL.in = integerL.in = integerid2id1,4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義4.1.4 屬性依賴圖屬性依賴圖int id1, id2, id3的分析樹的依賴圖的分析樹的依賴圖 D TL L.in = T.typeD intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義4.1.4 屬性依賴圖屬性依賴圖int id1, id2, id3的分析樹的依賴圖的分析樹的依賴圖L L1, id L1.in = L.in;

14、 addType (id.entry, L.in) D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義4.1.5 屬性計(jì)算次序?qū)傩杂?jì)算次序拓?fù)渑判蛲負(fù)渑判颍航Y(jié)點(diǎn)的一種排序，使得邊只會從該次序中：結(jié)點(diǎn)的一種排序，使得邊只會從該次序中先出現(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 entry102 entry3 entryin 98in 76in 54 type4.1 語法制導(dǎo)的定義語法制導(dǎo)的

15、定義屬性計(jì)算次序?qū)傩杂?jì)算次序 構(gòu)造輸入的分析樹構(gòu)造輸入的分析樹D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義屬性計(jì)算次序?qū)傩杂?jì)算次序 構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義屬性計(jì)算次序?qū)傩杂?jì)算次序 構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點(diǎn)進(jìn)行構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點(diǎn)進(jìn)行拓?fù)渑判蛲?/p>

16、撲排序D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義屬性計(jì)算次序?qū)傩杂?jì)算次序 構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點(diǎn)進(jìn)行構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點(diǎn)進(jìn)行拓?fù)渑判?，按拓?fù)渑判虻拇涡蛴?jì)算屬性拓?fù)渑判?，按拓?fù)渑判虻拇涡蛴?jì)算屬性D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義語義規(guī)則的計(jì)算方法語義規(guī)則的計(jì)算方法 分析樹方法：前面介紹的方法分析樹方法：前面介紹的方

17、法4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義語義規(guī)則的計(jì)算方法語義規(guī)則的計(jì)算方法 分析樹方法：前面介紹的方法分析樹方法：前面介紹的方法 基于規(guī)則的方法：靜態(tài)確定基于規(guī)則的方法：靜態(tài)確定語義規(guī)則的計(jì)算語義規(guī)則的計(jì)算次序次序4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義語義規(guī)則的計(jì)算方法語義規(guī)則的計(jì)算方法 分析樹方法：前面介紹的方法分析樹方法：前面介紹的方法 基于規(guī)則的方法：靜態(tài)確定基于規(guī)則的方法：靜態(tài)確定語義規(guī)則的計(jì)算語義規(guī)則的計(jì)算次序次序 忽略規(guī)則的方法：忽略規(guī)則的方法：事先確定屬性的計(jì)算策略事先確定屬性的計(jì)算策略（如邊分析邊計(jì)算），那么語義規(guī)則的設(shè)計(jì)（如邊分析邊計(jì)算），那么語義規(guī)則的設(shè)計(jì)必須符合所選分析方法

18、的限制必須符合所選分析方法的限制4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算 4.2.1 語法樹語法樹 語法樹是分析樹的濃縮表示語法樹是分析樹的濃縮表示：算符和關(guān)鍵字是作為算符和關(guān)鍵字是作為內(nèi)部結(jié)點(diǎn)內(nèi)部結(jié)點(diǎn) 語法制導(dǎo)翻譯可以基于分析樹，也可以基于語法樹語法制導(dǎo)翻譯可以基于分析樹，也可以基于語法樹 語法樹的例子：語法樹的例子：if-then-elseBS1S2+*2584.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算4.2.2 構(gòu)造語法樹的語法制導(dǎo)定義構(gòu)造語法樹的語法制導(dǎo)定義產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則 E E1 + T E.nptr = mkNode( +, E1.n

19、ptr, 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.entry) F num F.nptr = mkLeaf (num, num.val) 4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算a+5 b的語法樹的構(gòu)造的語法樹的構(gòu)造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnu

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

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

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

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

24、dT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算4.2.3 S屬性的自下而上計(jì)算屬性的自下而上計(jì)算將將LR分析器分析器增加增加一個域來保存綜合屬性值一個域來保存綜合屬性值. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算4.2.3 S屬性的自下而上計(jì)算屬性的自下而上計(jì)算將將LR分析器分析器增加增加一個域來保存綜合屬性值一個域來保存綜

25、合屬性值. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop若產(chǎn)生式若產(chǎn)生式A XYZ的語義規(guī)則是的語義規(guī)則是A.a = f (X.x, Y.y, Z.z)4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算4.2.3 S屬性的自下而上計(jì)算屬性的自下而上計(jì)算將將LR分析器分析器增加增加一個域來保存綜合屬性值一個域來保存綜合屬性值. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop若產(chǎn)生式若產(chǎn)生式A XYZ的語義規(guī)則是的語義規(guī)則是A.a = f (X.x, Y.y, Z.z)，那么歸約后：那么歸

26、約后：. . . . . .AA.a. . . . . .top4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 語語 義義 規(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 (E) F.val = E.

27、val F digit F.val = digit.lexval4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(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

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

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

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

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

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

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

34、digit F.val = digit.lexval4.2 S屬性定義的自下而上計(jì)算屬性定義的自下而上計(jì)算臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼臺式計(jì)算器的語法制導(dǎo)定義改成棧操作代碼. . . . . .ZZ. zYY. yXX.x. . . . . .棧棧 state valtop產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段 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) val top 2 =val top 1 F dig

35、it 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算邊分析邊翻譯的方式能否用于繼承屬性邊分析邊翻譯的方式能否用于繼承屬性？ 屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制點(diǎn)建立次序的限制4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算邊分析邊翻譯的方式能否用于繼承屬性邊分析邊翻譯的方式能否用于繼承屬性？ 屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制點(diǎn)建立次序的限制 分析樹的結(jié)點(diǎn)是自左向右生成分析樹的結(jié)點(diǎn)是自左向右生成4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而

36、下計(jì)算邊分析邊翻譯的方式能否用于繼承屬性邊分析邊翻譯的方式能否用于繼承屬性？ 屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)屬性的計(jì)算次序一定受分析方法所限定的分析樹結(jié)點(diǎn)建立次序的限制點(diǎn)建立次序的限制 分析樹的結(jié)點(diǎn)是自左向右生成分析樹的結(jié)點(diǎn)是自左向右生成 如果屬性信息是自左向右流動，那么就有可能在分如果屬性信息是自左向右流動，那么就有可能在分析的同時完成屬性計(jì)算析的同時完成屬性計(jì)算4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.1 L屬性定義屬性定義 如果每個產(chǎn)生式如果每個產(chǎn)生式A X1 X2 Xn 的每條語義的每條語義規(guī)則計(jì)算的屬性是規(guī)則計(jì)算的屬性是A的綜合屬性；或者是的綜合屬性

37、；或者是Xj 的的繼承屬性，繼承屬性，1 j n, , 但它僅依賴：但它僅依賴： 該產(chǎn)生式中該產(chǎn)生式中Xj左邊符號左邊符號X1, X2, , Xj-1的屬性；的屬性； A的繼承屬性的繼承屬性4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.1 L屬性定義屬性定義 如果每個產(chǎn)生式如果每個產(chǎn)生式A X1 X2 Xn 的每條語義的每條語義規(guī)則計(jì)算的屬性是規(guī)則計(jì)算的屬性是A的綜合屬性；或者是的綜合屬性；或者是Xj 的的繼承屬性，繼承屬性，1 j n, , 但它僅依賴：但它僅依賴： 該產(chǎn)生式中該產(chǎn)生式中Xj左邊符號左邊符號X1, X2, , Xj-1的屬性；的屬性； A的繼承屬性的繼承屬性

38、S屬性定義屬于屬性定義屬于L屬性定義屬性定義4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算變量類型聲明的語法制導(dǎo)定義是一個變量類型聲明的語法制導(dǎo)定義是一個L屬性定義屬性定義 產(chǎn)產(chǎn) 生生 式式 語語 義義 規(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 翻譯方案翻譯方案例例 把有加

39、和減的中綴表達(dá)式翻譯成后綴表達(dá)式把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式如果輸入是如果輸入是8+5 2，則輸出是，則輸出是8 5 + 2 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.2 翻譯方案翻譯方案例例 把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式如果輸入是如果輸入是8+5 2，則輸出是，則輸出是8 5 + 2 E T RT + T + T + R addop T print (addop.lexeme) R1 | T num print (num.val)4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.2 翻譯方案翻譯方案例例

40、 把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式把有加和減的中綴表達(dá)式翻譯成后綴表達(dá)式如果輸入是如果輸入是8+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)pr

41、int( )4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算例例 數(shù)學(xué)排版語言數(shù)學(xué)排版語言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text E1.val4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算例例 數(shù)學(xué)排版語言數(shù)學(xué)排版語言EQN E sub 1 .val 產(chǎn)產(chǎn) 生生 式式 語語 義義 規(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.p

42、s = shrink(B.ps); B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps E1.val4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算例例 數(shù)學(xué)排版語言數(shù)學(xué)排版語言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

43、.ps 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算例例 左遞歸的消除引起繼承屬性左遞歸的消除引起繼承屬性產(chǎn)產(chǎn) 生生 式式語語 義義 規(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.entry) F num F.nptr = mkLeaf (num, num.val

44、) 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.nptr = W.sW FW1.i = mkNode ( , W.i, F.nptr)W1W.s = W1.sW W.s = W.i 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算E T R.i = T.nptr T + T + T + RE.nptr = R.sR +TR1.i = mkNode ( +, R.i,

45、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 4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.3 預(yù)測翻譯器的設(shè)計(jì)預(yù)測翻譯器的設(shè)計(jì)把預(yù)測

46、分析器的構(gòu)造方法推廣到翻譯方案的實(shí)現(xiàn)把預(yù)測分析器的構(gòu)造方法推廣到翻譯方案的實(shí)現(xiàn)產(chǎn)生式產(chǎn)生式R +TR | 的分析過程的分析過程void R( ) if (lookahead = + ) 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 = le

47、xval;match(+ ); nptr = T();i1 = mkNode(addoplexeme, i , nptr);s1 = R (i1); s = s1;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 用

48、綜合屬性代替繼承屬性用綜合屬性代替繼承屬性Pascal的聲明，如的聲明，如m, n : integerD L : TT integer | charL L, id | id改成從右向左歸約改成從右向左歸約D id LL , id L | : TT integer | char4.3 L屬性定義的自上而下計(jì)算屬性定義的自上而下計(jì)算4.3.4 用綜合屬性代替繼承屬性用綜合屬性代替繼承屬性Pascal的聲明，如的聲明，如m, n : integerD L : TT integer | charL L, id | id改成從右向左歸約改成從右向左歸約D id LL , id L | : TT inte

49、ger | 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ì)算屬性的自下而上計(jì)算 在自下而上分析的框架中實(shí)現(xiàn)在自下而上分析的框架中實(shí)現(xiàn)L屬性定義的方法屬性定義的方

50、法 它能實(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 刪除翻譯方案中嵌入的動作刪除翻譯方案中嵌入的動作E T RR + T print (+)R1 | T print ( )R1 | T num print (num.val)4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 4.4.1 刪除翻譯方案中嵌入的動作刪除翻譯方案中嵌入的動作E T RR + T print (+)R1 | T print ( )R1 | T

51、 num print (num.val)在文法中加入產(chǎn)生在文法中加入產(chǎn)生 的的標(biāo)記非終結(jié)符標(biāo)記非終結(jié)符，讓每個嵌入動，讓每個嵌入動作由不同標(biāo)記非終結(jié)符作由不同標(biāo)記非終結(jié)符M代表，并把該動作放在產(chǎn)代表，并把該動作放在產(chǎn)生式生式M 的右端的右端4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 4.4.1 刪除翻譯方案中嵌入的動作刪除翻譯方案中嵌入的動作E T RR + T print (+)R1 | T print ( )R1 | T num print (num.val)在文法中加入產(chǎn)生在文法中加入產(chǎn)生 的的標(biāo)記非終結(jié)符標(biāo)記非終結(jié)符，讓每個嵌入動，讓每個嵌入動作由不同標(biāo)記非終結(jié)符作由不同標(biāo)記非終結(jié)

52、符M代表，并把該動作放在產(chǎn)代表，并把該動作放在產(chǎn)生式生式M 的右端的右端E T RR + T M R1 | T N R1 | T num print (num.val)M print (+)N print ( ) 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 = realL L1.in = L.in L1, id addtype (id.entry, L.in )L id addtype (id.ent

53、ry, L.in )4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 4.4.2 分析棧上的繼承屬性分析棧上的繼承屬性屬性位置能預(yù)測屬性位置能預(yù)測例例 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 ininin4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 DTLL,rL,qpint type inini

54、n產(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ì)算 屬性的位置不能預(yù)測屬性的位置不能預(yù)測S aACC.i = A.sS bABCC.i = A.sC cC.s = g(C.i)4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 屬性的位置不能預(yù)測屬性的位置不能預(yù)測S aACC.i = A.sS bABCC.i = A.sC cC.s =

55、g(C.i)增加標(biāo)記非終結(jié)符增加標(biāo)記非終結(jié)符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ì)算 4.4.3 模擬繼承屬性的計(jì)算模擬繼承屬性的計(jì)算繼承屬性是某個綜合屬性的一個函數(shù)繼承屬性是某個綜合屬性的一個函數(shù)S aACC.i = f (A.s)C cC.s = g(C.i)4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 4.4.3 模擬繼承屬性的計(jì)算模擬繼承屬性的計(jì)算繼承屬性是某個綜合屬性的一個函數(shù)繼承屬性是某個綜合屬性的一個函數(shù)S aACC.i = f (A.s)

56、C cC.s = g(C.i)增加標(biāo)記非終結(jié)符，把增加標(biāo)記非終結(jié)符，把f(A.s)的計(jì)算移到對標(biāo)記的計(jì)算移到對標(biāo)記非終結(jié)符歸約時進(jìn)行非終結(jié)符歸約時進(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é)排版語言數(shù)學(xué)排版語言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

57、.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps 4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 產(chǎn)產(chǎn) 生生 式式 語語 義義 規(guī)規(guī) 則則 S LB B.ps = L.s; S.ht = B.ht L L.s = 10 B B1 MB2 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 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps = N.s; B.ht = disp (B1.ht, B2.ht )

58、N N.s = shrink(N.i) B text B.ht = text.h B.ps 4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算舉例說明舉例說明SM sB L s BBtext BsubN sBtext text4.4 L屬性的自下而上計(jì)算屬性的自下而上計(jì)算 產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段S LB B.ps = L.s; S.ht = B.ht L L.s = 10 B B1 MB2 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 sub NB2 B1.ps =B.ps

59、; 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) 生生 式式 代代 碼碼 段段S LB valtop 1 = valtopL L.s = 10 B B1 MB2 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 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps

60、 = 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) 生生 式式 代代 碼碼 段段S LB valtop 1 = valtopL valtop+1 = 10B B1 MB2 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 sub NB2 B1.ps =B.ps; N.i = B.ps;B2.ps = N.s; B.ht =