網(wǎng)頁制作技巧chapter5語法制導(dǎo)翻譯

1、第五章第五章 語法制導(dǎo)翻譯語法制導(dǎo)翻譯 本章內(nèi)容本章內(nèi)容 介紹一種形式化的語義描述方法：介紹一種形式化的語義描述方法：語法制導(dǎo)語法制導(dǎo)的翻譯的翻譯，包括它的兩種具體形式：，包括它的兩種具體形式：語法制導(dǎo)語法制導(dǎo)的定義和翻譯方案的定義和翻譯方案 。介紹語法制導(dǎo)的翻譯的實現(xiàn)方法。介紹語法制導(dǎo)的翻譯的實現(xiàn)方法。第五章第五章 語法制導(dǎo)翻譯語法制導(dǎo)翻譯v 翻譯的任務(wù)：翻譯的任務(wù)：語義分析和正確性檢查，若語義分析和正確性檢查，若正確，則翻譯成中間代碼或目標代碼。正確，則翻譯成中間代碼或目標代碼。v 使用的方法使用的方法: :稱作語法制導(dǎo)翻譯。稱作語法制導(dǎo)翻譯。v 基本思想基本思想: :根據(jù)翻譯的需要設(shè)置文

2、法符號的根據(jù)翻譯的需要設(shè)置文法符號的屬性屬性，以描述語法結(jié)構(gòu)的語義。，以描述語法結(jié)構(gòu)的語義。第五章第五章 語法制導(dǎo)翻譯語法制導(dǎo)翻譯 屬性屬性1、定義：代表與文法符號(vt或vn)相關(guān)的信息。屬性可以為任何特性。例如：變量的類型、層次，存儲地址；表達式類型，值；程序的目標代碼等。2、屬性值：是指與屬性相關(guān)的信息，可以在語法分析過程中計算和傳遞。3、屬性的表示：x.屬性值。注意：產(chǎn)生式的左、右部有相同的符號時用下標或上標來區(qū)別。 例：ee1+te.val:=e1.val+t.val第五章第五章 語法制導(dǎo)翻譯語法制導(dǎo)翻譯 1、語義規(guī)則(屬性等式)為文法的每一個產(chǎn)生式(規(guī)則)配備的計算屬性的計算規(guī)則。

3、2、屬性文法為文法的每個符號引入一組屬性，且讓該文法附加上語義規(guī)則時，構(gòu)成了屬性文法。表示：文法規(guī)則(產(chǎn)生式)語義規(guī)則規(guī)則1相關(guān)的屬性等式.規(guī)則n相關(guān)的屬性等式據(jù)計算的依賴關(guān)系計算的依賴關(guān)系分成不相交不相交的兩類：在分析樹中，一個結(jié)點的綜合屬性值是從其的屬性值計算出來的一個結(jié)點的繼承屬性值是由該結(jié)點和的屬性值計算出來的。一般來說，語義翻譯可按圖的流程處理。一般來說，語義翻譯可按圖的流程處理。實際上，編譯中語義翻譯的實現(xiàn)并不是按圖實際上，編譯中語義翻譯的實現(xiàn)并不是按圖6.1 的流的流程處理的；而是隨語法分析的進展，識別出一個語法程處理的；而是隨語法分析的進展，識別出一個語法結(jié)構(gòu)，就對它的語義進行

4、分析和翻譯。結(jié)構(gòu)，就對它的語義進行分析和翻譯。4.1 語法制導(dǎo)的定義語法制導(dǎo)的定義例例簡單臺式計算器的語法制導(dǎo)定義簡單臺式計算器的語法制導(dǎo)定義產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則 l e n print (e.val)e e1 + te.val := e1 .val + t.vale te.val := t.valt t1 * * ft.val := t1.val * * f.valt ft.val := f.valf (e)f.val := e.val5.1.1 語法制導(dǎo)定義的形式語法制導(dǎo)定義的形式是對上下文無關(guān)文法的推廣 每個文法符號有一組屬性每個文法符號有一組屬性 每個文法產(chǎn)生式每個文

5、法產(chǎn)生式a 有一組形式為有一組形式為b := f (c1, c2, , ck )的語義規(guī)則的語義規(guī)則，其中其中f 是函數(shù)，是函數(shù)，b和和c1, c2, , ck 是該產(chǎn)生式文法符號的屬性。是該產(chǎn)生式文法符號的屬性。 綜合屬性：綜合屬性：如果如果b是是a的屬性，的屬性，c1 , c2 , , ck 是是產(chǎn)生式右部文法符號的屬性或產(chǎn)生式右部文法符號的屬性或a的其它屬性。的其它屬性。 繼承屬性繼承屬性：如果：如果b是產(chǎn)生式右部某個文法符號是產(chǎn)生式右部某個文法符號x的屬性。的屬性。5.1.2 綜合屬性綜合屬性s屬性定義屬性定義：僅僅使用綜合屬性的語法制導(dǎo)定義僅僅使用綜合屬性的語法制導(dǎo)定義產(chǎn)產(chǎn) 生生 式

6、式語語 義義 規(guī)規(guī) 則則 l e n print (e.val)e e1 + te.val := e1 .val + t.vale te.val := t.valt t1 * * ft.val := t1.val * * f.valt ft.val := f.valf (e)f.val := e.val5.1.2 綜合屬性綜合屬性每個結(jié)點的屬性值都標注出來的分析樹叫做每個結(jié)點的屬性值都標注出來的分析樹叫做注注釋分析樹釋分析樹（annotated parse tree)8+5* *2 n的注釋的注釋 分析樹分析樹digit.lexval = 2le.val = 18nt.val = 10e.va

7、l = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析

8、樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f

9、.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.va

10、l = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析

11、樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f

12、.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.va

13、l = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性分析樹各結(jié)點屬性的計算可以自下而上地完成分析樹各結(jié)點屬性的計算可以自下而上地完成digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.2 綜合屬性綜合屬性注釋分析樹注釋分析樹: :結(jié)點的屬性值都標注

14、出來的分析樹結(jié)點的屬性值都標注出來的分析樹digit.lexval = 2le.val = 18nt.val = 10e.val = 8t.val = 8f.val = 8digit.lexval = 8t.val = 5+*f.val = 5f.val = 2digit.lexval = 55.1.3 繼承屬性繼承屬性一結(jié)點的繼承屬性是由該結(jié)點的父結(jié)點和一結(jié)點的繼承屬性是由該結(jié)點的父結(jié)點和/ /或或兄弟結(jié)點的屬性來定義的兄弟結(jié)點的屬性來定義的 ,int id, id, id產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則 d tll.in := t.typetintt. type := integer

15、trealt. type := reall l1,idl1.in := l.in; addtype (id.entry, l.in )5.1.3 繼承屬性繼承屬性int id1, id2, id3的注釋分析樹的注釋分析樹dintt.type = integer,id3l.in = integerl.in = integerl.in = integerid2id1,屬性依賴圖屬性依賴圖屬性依賴圖屬性依賴圖,語義規(guī)則建立了屬性之間的依賴關(guān)屬性之間的依賴關(guān)系系，這些關(guān)系可以用圖來表示，這樣的圖稱為int id1, id2, id3 的分析樹的依賴圖的分析樹的依賴圖d intt,id3lllid2id

16、1,1 entry102entry3 entryin 98in 76in 54 type for 分析樹中每一結(jié)點分析樹中每一結(jié)點n do for 結(jié)點結(jié)點n的文法符號的每一個屬性的文法符號的每一個屬性a do 為為a在依賴圖中建立一個結(jié)點；在依賴圖中建立一個結(jié)點； for 分析樹中每一個結(jié)點分析樹中每一個結(jié)點n do for 結(jié)點結(jié)點n所用產(chǎn)生式對應(yīng)的每一條所用產(chǎn)生式對應(yīng)的每一條 語義規(guī)則語義規(guī)則 b:f（c1，c2，ck ) do for i:=1 to k do 從結(jié)點從結(jié)點ci到結(jié)點到結(jié)點b構(gòu)造一條有向邊；構(gòu)造一條有向邊；5.1.4 屬性計算次序?qū)傩杂嬎愦涡?拓撲排序拓撲排序是無環(huán)有向

17、圖的結(jié)點的一種排序m1, m2, mk，它使得邊只會從這個次序中先出現(xiàn)的結(jié)點到后出現(xiàn)的結(jié)點，也就是若mimj是從mi到mj的邊，那么在此排序中mi先于mj。 顯然，依賴圖的任何拓撲排序都是分析樹中結(jié)點屬性計算的一個正確次序，即按拓撲排序進行計算的話，用語義規(guī)則b:= f (c1,c2,ck)計算b時，屬性c1,c2,ck已經(jīng)計算過了。5.1.4 屬性計算次序?qū)傩杂嬎愦涡蛲負渑判蛲負渑判颍航Y(jié)點的一種排序，使得邊只會從該次序中：結(jié)點的一種排序，使得邊只會從該次序中先出現(xiàn)的結(jié)點到后出現(xiàn)的結(jié)點。先出現(xiàn)的結(jié)點到后出現(xiàn)的結(jié)點。例：例：1，2，3，4，5，6，7，8，9，10d intt,id3lllid2

18、id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 屬性計算次序?qū)傩杂嬎愦涡驅(qū)傩杂嬎愦涡驅(qū)傩杂嬎愦涡?構(gòu)造輸入的分析樹構(gòu)造輸入的分析樹d intt,id3lllid2id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 屬性計算次序?qū)傩杂嬎愦涡驅(qū)傩杂嬎愦涡驅(qū)傩杂嬎愦涡?構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖d intt,id3lllid2id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 屬性計算次序?qū)傩杂嬎愦涡驅(qū)傩?/p>

19、計算次序?qū)傩杂嬎愦涡?構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點進行構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點進行拓撲排序拓撲排序d intt,id3lllid2id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 屬性計算次序?qū)傩杂嬎愦涡驅(qū)傩杂嬎愦涡驅(qū)傩杂嬎愦涡?構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點進行構(gòu)造輸入的分析樹，構(gòu)造屬性依賴圖，對結(jié)點進行拓撲排序，按拓撲排序的次序計算屬性。拓撲排序，按拓撲排序的次序計算屬性。d intt,id3lllid2id1,1 entry102entry3 entryin 98in 76in 54 type5.

20、1.4 屬性計算次序?qū)傩杂嬎愦涡蛘Z義規(guī)則的計算方法語義規(guī)則的計算方法 分析樹方法：前面介紹的方法。分析樹方法：前面介紹的方法。 基于規(guī)則的方法：基于規(guī)則的方法：在構(gòu)造編譯器時，用在構(gòu)造編譯器時，用 手工或?qū)ｉT的工具來分析語義規(guī)則手工或?qū)ｉT的工具來分析語義規(guī)則,靜態(tài)確定靜態(tài)確定語語義規(guī)則的計算次序義規(guī)則的計算次序。 忽略規(guī)則的方法：忽略規(guī)則的方法：事先確定屬性的計算策略事先確定屬性的計算策略（如邊分析邊計算），那么語義規(guī)則的設(shè)計（如邊分析邊計算），那么語義規(guī)則的設(shè)計必須符合所選分析方法的限制必須符合所選分析方法的限制. .5.2 語法樹的構(gòu)造語法樹的構(gòu)造5.2.1 語法樹語法樹 語法樹是分析樹的

21、濃縮表示語法樹是分析樹的濃縮表示：算符和關(guān)鍵字是作為算符和關(guān)鍵字是作為內(nèi)部結(jié)點。內(nèi)部結(jié)點。 語法制導(dǎo)翻譯可以基于分析樹，也可以基于語法樹語法制導(dǎo)翻譯可以基于分析樹，也可以基于語法樹 語法樹的例子：語法樹的例子：if-then-elsebs1s2+*2585.2 語法樹的構(gòu)造語法樹的構(gòu)造語法樹是常用的一種中間表示形式，把語法分析語法樹是常用的一種中間表示形式，把語法分析和翻譯分開。語法分析過程中完成翻譯有許多和翻譯分開。語法分析過程中完成翻譯有許多優(yōu)點，但也有一些不足：優(yōu)點，但也有一些不足： 1.適于語法分析的文法可能不完全反映語言適于語法分析的文法可能不完全反映語言成分的自然層次結(jié)構(gòu)；成分的自

22、然層次結(jié)構(gòu)； 2. 語法分析方法限制，對分析樹結(jié)點的訪問語法分析方法限制，對分析樹結(jié)點的訪問序和翻譯需要的訪問序不一致。序和翻譯需要的訪問序不一致。5.2 語法樹的構(gòu)造語法樹的構(gòu)造 1. mknode(op,left,right) 建立一個建立一個結(jié)點，標號結(jié)點，標號是是op,兩個域兩個域left和和right指向運算分量結(jié)點的指針。指向運算分量結(jié)點的指針。 2mkleaf(id,entry) 建立一個建立一個結(jié)點結(jié)點,由標號由標號id標識，標識，一個域一個域entry指向標識符符號表中相應(yīng)的項。指向標識符符號表中相應(yīng)的項。 3. mkleaf(num,val) 建立一個建立一個結(jié)點，標號為結(jié)

23、點，標號為num，域，域val用于存放數(shù)的值。用于存放數(shù)的值。idto entry anum 4 idto entry c +5.2 語法樹的構(gòu)造語法樹的構(gòu)造產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則 e e1 + t e.nptr := mknode( +, e1.nptr, t.nptr)e te.nptr := t.nptrt t1* *ft.nptr := mknode( * *, t1.nptr, f.nptr)t ft.nptr := f.nptrf (e)f.nptr := e.nptrf idf.nptr := mkleaf (id, id.entry)idto entry anu

24、m 4 idto entry c +5.2 語法樹的構(gòu)造語法樹的構(gòu)造a+5* *b的語法樹的構(gòu)造的語法樹的構(gòu)造e.nptrt.nptre.nptrt.nptrf.nptridt.nptr+*f.nptrf.nptridnumididnum 5* *+ +指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口 而語法制導(dǎo)定義中語義規(guī)則的執(zhí)行受輸入的語法的制導(dǎo)，當識別出輸入串的一個語法結(jié)構(gòu)時（可以看成發(fā)生一個事件），執(zhí)行其相應(yīng)的動作，因此這是一種事件驅(qū)動的程序設(shè)計。（directedacyclicgraph，簡稱dag)提取表達式中的公共子表達式，以取提取表達式中的公共子表達

25、式，以取 得目標程序的局部優(yōu)化。得目標程序的局部優(yōu)化。 執(zhí)行執(zhí)行mknode和和mkleaf時，時， 檢查是否檢查是否已有相同的結(jié)點已有相同的結(jié)點， 若有，則返回相應(yīng)結(jié)點的指針。若有，則返回相應(yīng)結(jié)點的指針。+*d+*acb5.3 s屬性定義的自下而上計屬性定義的自下而上計算算 綜合屬性可以由自下而上的分析器在分析輸入時完成計算。分析器可以把文法符號的綜合屬性值放在它的棧里，每當歸約時，根據(jù)出現(xiàn)在棧頂?shù)漠a(chǎn)生式右部符號的屬性來計算左部符號的綜合屬性。我們說明如何擴展分析器的棧使之能夠保存綜合屬性 s屬性定義的翻譯器可以借助lr分析器的生成器來實現(xiàn)5.3 s屬性定義的自下而上計算屬性定義的自下而上計

26、算將將lr分析器分析器分析棧中增加分析棧中增加一個域來保存綜合屬性值一個域來保存綜合屬性值。. . . . . .zz. zyy. yxx.x. . . . . .棧棧 state valtop若產(chǎn)生式若產(chǎn)生式a xyz的語義規(guī)則是的語義規(guī)則是a.a := f (x.x, y.y, z.z)，那么歸約后：那么歸約后：. . . . . .aa.a. . . . . .top4.2 s屬性定義的自下而上計算屬性定義的自下而上計算臺式計算器的語法制導(dǎo)定義改成棧操作代碼臺式計算器的語法制導(dǎo)定義改成棧操作代碼. . . . . .zz. zyy. yxx.x. . . . . .棧棧 state va

27、ltop產(chǎn)產(chǎn) 生生 式式代代 碼碼 段段 l e nprint (e.val)e e1 + te.val :=e1 .val +t.vale te.val := t.valt t1 * * ft.val := t1.val * * f.valt ft.val := f.valf (e)f.val := e.valf digitf.val := digit.lexval4.2 s屬性定義的自下而上計算屬性定義的自下而上計算臺式計算器的語法制導(dǎo)定義改成棧操作代碼臺式計算器的語法制導(dǎo)定義改成棧操作代碼. . . . . .zz. zyy. yxx.x. . . . . .棧棧 state valto

28、p產(chǎn)產(chǎn) 生生 式式代代 碼碼 段段 l e nprint (val top 1 )e e1 + tval top 2 :=val top 2+val top e tt t1 * * fval top 2 := val top 2 val top t ff (e)val top 2 :=val top 13*5+4n-*5+4n33*5+4nf3fdigit*5+4nt3tf5+4nt*3-+4nt*53-5+4nt*f3-5fdigit+4nt15tt*f+4ne15et4ne+15-ne+415-4ne+f15-4fdigitne+t15-4tfne19ee+ten19-l19len 采用采

29、用，例如，例如lr分析，首先分析，首先給出給出，然后，把，然后，把s-屬性定義變成屬性定義變成可執(zhí)行的代碼段可執(zhí)行的代碼段，這就構(gòu)成了翻譯程序。，這就構(gòu)成了翻譯程序。一種自然的計算屬性的順序是按深度優(yōu)先一種自然的計算屬性的順序是按深度優(yōu)先訪問分析樹結(jié)點的順序，它適應(yīng)多種自底向上訪問分析樹結(jié)點的順序，它適應(yīng)多種自底向上和自頂向下的翻譯方法。和自頂向下的翻譯方法。 l-屬性定義屬性定義 可用于按深度優(yōu)先順序計算屬可用于按深度優(yōu)先順序計算屬性值。性值。procedure dfvisit(n:node); begin for n 的每個子結(jié)點的每個子結(jié)點m,從左至右從左至右 do begin 計算計算

30、m的的繼承繼承屬性；屬性； dfvisit(m) end; 計算計算n的的綜合綜合屬性屬性 end;定義定義 一個語法制導(dǎo)定義是一個語法制導(dǎo)定義是，如果，如果 p,其每一個語義規(guī)則中的每其每一個語義規(guī)則中的每一個屬性都是一個綜合屬性，或是一個屬性都是一個綜合屬性，或是xj(1 j n)的一個繼承屬性，這個繼承屬性僅依賴于的一個繼承屬性，這個繼承屬性僅依賴于 12變量類型聲明的語法制導(dǎo)定義是變量類型聲明的語法制導(dǎo)定義是一個一個l屬性定義屬性定義產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則 d tll.in := t.typetintt. type := integertrealt. type := r

31、eall l1,idl1.in := l.in; addtype (id.entry, l.in )lidaddtype (id.entry, l.in )alma 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) etr raddop t print(addop.lexeme)r1| tnumprint(num.val) 9 5 - 2 +例例 把有加和減的中綴表達式翻譯成后綴表達式把有加和減的中綴表達式翻譯成后綴表達式如果輸入是如果輸入是8+5 2，則輸出是，則輸出是8 5 + 2 。 e t rr a

32、ddop 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( )et9trr-5+t2r etr raddop t print(addop.lexeme)r1| tnum print(num.val) 例例 數(shù)

33、學(xué)排版語言數(shù)學(xué)排版語言eqn例例 數(shù)學(xué)排版語言數(shù)學(xué)排版語言eqn e sub 1 .val s b b b1 b2 b b1 sub b2 b text e1.val例例 數(shù)學(xué)排版語言數(shù)學(xué)排版語言eqn例例 數(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.ps:= shrink(b.ps); b.ht

34、:= disp (b1.ht, b2.ht ) b text b.ht := text.h b.ps e1.val例例 數(shù)學(xué)排版語言數(shù)學(xué)排版語言eqn例例 數(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.ps 為每一個語義規(guī)則建立一個包含賦值的

35、動作，并為每一個語義規(guī)則建立一個包含賦值的動作，并把這個動作放在相應(yīng)的產(chǎn)生式把這個動作放在相應(yīng)的產(chǎn)生式的的。例如：語法和語義規(guī)則如下，請寫出其翻譯模式：例如：語法和語義規(guī)則如下，請寫出其翻譯模式： tt1*f t val:=t1 val*f val解：解：tt1*f t val:=t1 val*f valsaaaa邊分析邊翻譯的方式能否用于繼承屬性邊分析邊翻譯的方式能否用于繼承屬性？ 屬性的計算次序一定受分析方法所限定的分析樹結(jié)屬性的計算次序一定受分析方法所限定的分析樹結(jié)點建立次序的限制。點建立次序的限制。 分析樹的結(jié)點是自左向右生成。分析樹的結(jié)點是自左向右生成。 如果屬性信息是自左向右流動，

36、那么就有可能在分如果屬性信息是自左向右流動，那么就有可能在分析的同時完成屬性計算。析的同時完成屬性計算。用翻譯模式構(gòu)造自頂向下翻譯。用翻譯模式構(gòu)造自頂向下翻譯。 對于一個翻譯模式，若采用自頂向下分析，對于一個翻譯模式，若采用自頂向下分析，和和，在改寫基本文法時考慮屬，在改寫基本文法時考慮屬性值的計算。性值的計算。 e e1+te 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 例例6.14 圖圖6.13的帶左遞歸的文法的翻譯模式的帶左遞歸的

37、文法的翻譯模式被轉(zhuǎn)換成圖被轉(zhuǎn)換成圖6.14的帶右遞歸的文法的翻譯模式。的帶右遞歸的文法的翻譯模式。 et r i:=t val re val:=r s r tr1 i:=r.i+t. val r1r. s:=r1 s r- tr1 i:=r i-t val r1r s:=r1 s rr s:=r i t（ e ） t val:=e. val tnum t val:=num val 繼承屬性繼承屬性i綜合屬性綜合屬性se val=6t val=9r i=9; r s= 69t val=55r i=4; r s= 6+ t val=2r i=6; r s= 62 t val=9r i=9t val

38、=5r i=4t val=2r i=6r s= 6r s= 6r s= 6e val=6關(guān)于左遞歸翻譯模式更一般化的討論關(guān)于左遞歸翻譯模式更一般化的討論左遞歸翻譯模式左遞歸翻譯模式 aa1ya.a:=g(a1.a,y.y) ax a.a:=f(x.x) （6.2） 每一個文法符號都有一個每一個文法符號都有一個綜合屬性綜合屬性，用，用相應(yīng)的小寫字母相應(yīng)的小寫字母表示，表示，g和和f是任意函數(shù)。是任意函數(shù)。 消除左遞歸消除左遞歸，文法轉(zhuǎn)換成，文法轉(zhuǎn)換成 ax r ry r| （6.3） 再考慮語義動作，翻譯模式變?yōu)椋涸倏紤]語義動作，翻譯模式變?yōu)椋?ax r i:=f(x x) r a. a:=r.

39、 s ry r1 i:=g（r i,y y） r1 r s:=r1 s rr s:=r i （6.4） 經(jīng)過轉(zhuǎn)換的翻譯模式，使用經(jīng)過轉(zhuǎn)換的翻譯模式，使用r的繼承屬性的繼承屬性i和綜合屬性和綜合屬性s。y2y1x采用左遞歸翻譯模式采用左遞歸翻譯模式aaaa a=g(g(f(x x),y1 y),y2 y)a a=g(f(x x),y1 y)a a=f(x x)ay y2 2y y1 1x xrrrr i=f(x x)r i=g(f(x x),y1 y)r i=g(g(f(x x),y1 y),y2 y)消除左遞歸后翻譯模式消除左遞歸后翻譯模式例例 左遞歸的消除引起繼承屬性左遞歸的消除引起繼承屬性

40、例例 左遞歸的消除引起繼承屬性左遞歸的消除引起繼承屬性產(chǎn)產(chǎn) 生生 式式語語 義義 規(guī)規(guī) 則則 e e1 + t e.nptr := mknode( +, e1.nptr, t.nptr)e te.nptr := t.nptrt t1* *ft.nptr := mknode( * *, t1.nptr, f.nptr)t ft.nptr := f.nptrf (e)f.nptr := e.nptr例例 左遞歸的消除引起繼承屬性左遞歸的消除引起繼承屬性e t r.i := t.nptrre.nptr := r.sr +tr1.i := mknode ( +, r.i, t.nptr)r1r.s :

41、= 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 例例 左遞歸的消除引起繼承屬性左遞歸的消除引起繼承屬性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

42、 ( * *, w.i, f.nptr)w1w.s := w1.sw w.s := w.i 例例 左遞歸的消除引起繼承屬性左遞歸的消除引起繼承屬性tf.nptrf.nptridi w*f.nptridnumididnum 5* * *指向符號表中指向符號表中a的入口的入口指向符號表中指向符號表中b的入口的入口i wsi w 略去了略去了e tr t 部分部分5.5.2 預(yù)測翻譯器的設(shè)計預(yù)測翻譯器的設(shè)計把預(yù)測分析器的構(gòu)造方法推廣到翻譯方案的實現(xiàn)把預(yù)測分析器的構(gòu)造方法推廣到翻譯方案的實現(xiàn)產(chǎn)生式產(chǎn)生式r +tr | 的分析過程的分析過程procdure r;beginif lookahead = +

43、 then beginmatch ( + ); t; rendelse begin /* * 什么也不做什么也不做 * */endend 5.5.2 預(yù)測翻譯器的設(shè)計預(yù)測翻譯器的設(shè)計function r (i : syntax_tree_node ) : syntax_tree_node;var nptr , i1, s1, s : syntax_tree_node; addoplexeme : char;begin if lookahead = + then begin /* * 產(chǎn)生式產(chǎn)生式 r +t r * */addoplexeme := lexval;match( + );nptr

44、:= t; i1 := mknode(addoplexme, i , nptr) ; s1 := r (i1 ); s : = s1endelse s := i; /* * 產(chǎn)生式產(chǎn)生式 r * */return send;r : i, st : nptr+ : addoplexeme4.3 l屬性定義的自上而下計算屬性定義的自上而下計算4.3.4 用綜合屬性代替繼承屬性用綜合屬性代替繼承屬性pascal的聲明，如的聲明，如m, n : integerd l : tt integer | charl l, id | id4.3 l屬性定義的自上而下計算屬性定義的自上而下計算4.3.4 用綜合屬

45、性代替繼承屬性用綜合屬性代替繼承屬性pascal的聲明，如的聲明，如m, n : integerd l : tt integer | charl l, id | id改成從右向左歸約改成從右向左歸約d id ll , id l | : tt integer | char4.3 l屬性定義的自上而下計算屬性定義的自上而下計算4.3.4 用綜合屬性代替繼承屬性用綜合屬性代替繼承屬性pascal的聲明，如的聲明，如m, n : integerd l : tt integer | charl l, id | id改成從右向左歸約改成從右向左歸約d id ll , id l | : tt integer

46、 | chard:l,idlidintegert4.3 l屬性定義的自上而下計算屬性定義的自上而下計算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屬性的自下而上計算屬性的自下而上計算 在自下而上分析的框架中實現(xiàn)在自下而上分析的框架中實現(xiàn)l屬性定義的方法屬性定義的

47、方法 它能實現(xiàn)任何基于它能實現(xiàn)任何基于ll(1)文法的文法的l屬性定義。屬性定義。 也能實現(xiàn)許多（但不是所有的）基于也能實現(xiàn)許多（但不是所有的）基于lr(1) 的的l屬性定義。屬性定義。4.4 l屬性的自下而上計算屬性的自下而上計算 4.4.1 刪除翻譯方案中嵌入的動作刪除翻譯方案中嵌入的動作e t rr + t print (+)r1 | t print ( )r1 | t num print (num.val)4.4 l屬性的自下而上計算屬性的自下而上計算 4.4.1 刪除翻譯方案中嵌入的動作刪除翻譯方案中嵌入的動作e t rr + t print (+)r1 | t print ( )r

48、1 | t num print (num.val)在文法中加入產(chǎn)生在文法中加入產(chǎn)生 的的標記非終結(jié)符標記非終結(jié)符，讓每個嵌入動，讓每個嵌入動作由不同標記非終結(jié)符作由不同標記非終結(jié)符m代表，并把該動作放在產(chǎn)代表，并把該動作放在產(chǎn)生式生式m 的右端。的右端。4.4 l屬性的自下而上計算屬性的自下而上計算 4.4.1 刪除翻譯方案中嵌入的動作刪除翻譯方案中嵌入的動作e t rr + t print (+)r1 | t print ( )r1 | t num print (num.val)在文法中加入產(chǎn)生在文法中加入產(chǎn)生 的的標記非終結(jié)符標記非終結(jié)符，讓每個嵌入動，讓每個嵌入動作由不同標記非終結(jié)符作由

49、不同標記非終結(jié)符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屬性的自下而上計算屬性的自下而上計算 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 ad

50、dtype (id.entry, l.in )4.4 l屬性的自下而上計算屬性的自下而上計算 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屬性的自下而上計算屬性的自下而上計算 dtll,rl

51、,qpint type ininin產(chǎn)產(chǎn) 生生 式式 代代 碼碼 段段d tl t int valtop := integer t real valtop := real l l1, id addtype(valtop, valtop 3) 4.4 l屬性的自下而上計算屬性的自下而上計算 屬性的位置不能預(yù)測屬性的位置不能預(yù)測s aacc.i := a.ss babcc.i := a.sc cc.s := g(c.i)4.4 l屬性的自下而上計算屬性的自下而上計算 屬性的位置不能預(yù)測屬性的位置不能預(yù)測s aacc.i := a.ss babcc.i := a.sc cc.s := g(c.i)增

52、加標記非終結(jié)符增加標記非終結(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屬性的自下而上計算屬性的自下而上計算 4.4.3 模擬繼承屬性的計算模擬繼承屬性的計算繼承屬性是某個綜合屬性的一個函數(shù)繼承屬性是某個綜合屬性的一個函數(shù)s aacc.i := f (a.s)c cc.s := g(c.i)4.4 l屬性的自下而上計算屬性的自下而上計算 4.4.3 模擬繼承屬性的計算模擬繼承屬性的計算繼承屬性是某個綜合屬性的一個函數(shù)繼承屬性是某個綜合屬性的一個函數(shù)s aacc.i := f (a.s

53、)c cc.s := g(c.i)增加標記非終結(jié)符，把增加標記非終結(jié)符，把f(a.s)的計算移到對標的計算移到對標記非終結(jié)符歸約時進行記非終結(jié)符歸約時進行。s aancn.i := a.s; c.i := n.sn n.s := f (n.i)c cc.s := g(c.i)4.4 l屬性的自下而上計算屬性的自下而上計算例例 數(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 := sh

54、rink(b.ps) b2b.ht := disp (b1.ht, b2.ht ) b text b.ht := text.h b.ps 4.4 l屬性的自下而上計算屬性的自下而上計算 產(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.h

55、t := disp (b1.ht, b2.ht ) n n.s := shrink(n.i) 4.4 l屬性的自下而上計算屬性的自下而上計算 產(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; n.i := b.ps;b2.ps := n.s; b.ht := disp (b1.ht, b2.ht )

56、 n n.s := shrink(n.i) 4.4 l屬性的自下而上計算屬性的自下而上計算 產(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 := n.s; b.ht := disp (b1.ht, b2.ht ) n n.s := shrink(n.i) 4.4 l屬性的自下而

57、上計算屬性的自下而上計算 產(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 := disp (b1.ht, b2.ht ) n n.s := shrink(n.i) 4.4 l屬性的自下而上計算屬性的自下而上計算 產(chǎn)產(chǎn) 生生 式式代代 碼碼 段段

58、s lb valtop 1 := valtopl valtop+1 := 10b b1 mb2 valtop 2 := max(valtop 2, valtop) 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 ) n n.s := shrink(n.i) b text b.ht := text.h b.ps 4.4 l屬性的自下而上計算屬性的自下而上計算 產(chǎn)產(chǎn) 生生 式式代代 碼碼 段段s lb valtop 1 := valtopl valtop+1 :

59、= 10b b1 mb2 valtop 2 := max(valtop 2, valtop) m valtop+1 := valtop 1b 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屬性的自下而上計算屬性的自下而上計算 產(chǎn)產(chǎn) 生生 式式代代 碼碼 段段s lb valtop 1 := valtopl valtop+1 := 10b b1 mb2 valtop 2 := m

60、ax(valtop 2, valtop) m valtop+1 := valtop 1b b1 sub nb2 valtop 3:= disp (valtop 3, valtop )n n.s := shrink(n.i) b text b.ht := text.h b.ps 4.4 l屬性的自下而上計算屬性的自下而上計算 產(chǎn)產(chǎn) 生生 式式代代 碼碼 段段s lb valtop 1 := valtopl valtop+1 := 10b b1 mb2 valtop 2 := max(valtop 2, valtop) m valtop+1 := valtop 1b b1 sub nb2 valt