[工學]第4章 語法制導的翻譯.ppt

1、主講人：范 敏,陳意云 張 昱 高等教育出版社,編 譯 原 理 -4,2021/3/29,第4章 語法制導的翻譯,2,引入,復習 詞法分析的任務和正規(guī)式的作用 語法分析的任務和文法的作用 思考 語言結構的屬性如何計算？何時計算？屬性值如何存放？,2021/3/29,第4章 語法制導的翻譯,3,第1章 編譯器概述 第2章 詞法分析 第3章 語法分析 第4章 語法制導的翻譯 第5章 類型檢查 第6章 運行時存儲空間的組織和管理 第7章 中間代碼生成 第8章 代碼生成 第9章* 代碼優(yōu)化 第10章* 編譯系統(tǒng)和運行系統(tǒng) 第11章* 面向?qū)ο笳Z言的編譯 第12章* 函數(shù)式語言的編譯,目 錄,2021/

2、3/29,第4章 語法制導的翻譯,4,4.1 語法制導的定義 4.2 S屬性定義的自下而上計算 4.3 L屬性定義的自上而下計算 4.4 L屬性的自下而上計算 4.5 遞歸計算,第4章 語法制導的翻譯,2021/3/29,第4章 語法制導的翻譯,5,本章內(nèi)容,介紹一種形式化的語義描述方法 語法制導的翻譯，包括它的兩種具體形式：語法制導的定義和翻譯方案 介紹語法制導的翻譯的實現(xiàn)方法,2021/3/29,第4章 語法制導的翻譯,6,本章學習目標,掌握綜合屬性、繼承屬性、語法樹、翻譯方案等概念 掌握語法制導的定義方法 掌握S屬性和L屬性的計算方法,2021/3/29,第4章 語法制導的翻譯,7,4.

3、1 語法制導的定義,例：簡單臺式計算器的語法制導定義,注意基礎文法與拓廣文法的區(qū)別,2021/3/29,第4章 語法制導的翻譯,8,基礎文法 基礎文法是語法制導定義中的文法。其中，每個文法符號都有一組可以用于計算的屬性 每個產(chǎn)生式A 有一組形式為b := f(c1, c2, , ck )的語義規(guī)則。其中f 是函數(shù)，b, c1 , c2 , , ck 是文法符號的屬性 語義規(guī)則 一組計算表達式 計算相應產(chǎn)生式中文法符號的屬性值,4.1.1 語法制導定義的形式,2021/3/29,第4章 語法制導的翻譯,9,文法符號屬性分類 繼承屬性：如果b是產(chǎn)生式右部某個文法符號X的屬性，c1 , c2 , ,

4、 ck 是產(chǎn)生式左部文法符號A的屬性或產(chǎn)生式右部文法符號屬性 綜合屬性：如果b是A的屬性，c1 , c2 , , ck 是產(chǎn)生式右部文法符號屬性或A的繼承屬性,b,b := f(c1, c2, , ck ),A X ,B屬于子結點,B屬于父結點,2021/3/29,第4章 語法制導的翻譯,10,S屬性定義：僅使用綜合屬性的語法制導定義,4.1.2 綜合屬性,如何計算綜合屬性值？,2021/3/29,第4章 語法制導的翻譯,11,8+5*2 n的計算：1. 根據(jù)基礎文法畫出推導出句子的分析樹,2021/3/29,第4章 語法制導的翻譯,12,8+5*2 n的計算：2. 標出分析樹中每個結點的屬性

5、（如果有）,注意注釋分析樹與分析樹之間的區(qū)別,2021/3/29,第4章 語法制導的翻譯,13,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,14,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,15,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,16,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制

6、導的翻譯,17,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,18,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,19,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,20,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,21,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、

7、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,22,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,23,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,24,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,2021/3/29,第4章 語法制導的翻譯,25,8+5*2 n的計算：3. 分析樹各結點屬性的計算可以自下而上、從左到右地完成,打印E屬性值 Print(E.val),2021/3/29,第4

8、章 語法制導的翻譯,26,利用分析樹對S屬性定義中綜合屬性的計算方法小結 畫出句子（詞法記號流符號串）的分析樹 標出每個結點的屬性（如果有） 根據(jù)語義規(guī)則自下而上、從左到右完成各個結點屬性的計算,2021/3/29,第4章 語法制導的翻譯,27,int id, id, id,4.1.3 繼承屬性,如何計算繼承屬性值？,2021/3/29,第4章 語法制導的翻譯,28,int id1, id2, id3的注釋分析樹 分析樹,2021/3/29,第4章 語法制導的翻譯,29,int id1, id2, id3的注釋分析樹 在注釋分析樹每個L結點，除傳遞繼承屬性in給子結點L1外，addtype過程

9、在符號表中將L右子結點上標識符id的類型記為整型：addtype (id.entry, L.in ),L1.in := L.in,2021/3/29,第4章 語法制導的翻譯,30,int id1, id2, id3的分析樹的依賴圖 描述結點屬性間依賴關系的有向圖稱為依賴圖 D TL L.in := T.type ,4.1.4 屬性依賴圖,所有屬性可用結點表示,2021/3/29,第4章 語法制導的翻譯,31,int id1, id2, id3的分析樹的依賴圖 L L1, id L1.in := L.in; addtype (id.entry, L.in ),注意：L有兩個屬性(繼承屬性in和虛

10、擬屬性),2021/3/29,第4章 語法制導的翻譯,32,拓撲排序：屬性結點出現(xiàn)順序的一種排序，使得有向邊只從該次序中先出現(xiàn)的結點指向后出現(xiàn)的結點 例：1，2，3，4，5，6，7，8，9，10,4.1.5 屬性計算次序,只有結點屬性傳遞的方向性不夠,2021/3/29,第4章 語法制導的翻譯,33,屬性計算過程 （1）構造輸入串的分析樹,2021/3/29,第4章 語法制導的翻譯,34,屬性計算過程 （1）構造輸入串的分析樹；（2）構造屬性依賴圖,2021/3/29,第4章 語法制導的翻譯,35,屬性計算過程 （1）構造輸入串的分析樹；（2）構造屬性依賴圖；（3）對屬性結點進行拓撲排序,20

11、21/3/29,第4章 語法制導的翻譯,36,屬性計算過程 （1）構造輸入串的分析樹；（2）構造屬性依賴圖；（3）對屬性結點進行拓撲排序；（4）按拓撲排序的次序計算屬性,2021/3/29,第4章 語法制導的翻譯,37,屬性計算過程 a4:=integer; a5:=a4; addtype(id3.entry,a5); a7:=a5; addtype(id2.entry,a7); a9:=a7; addtype(id1.entry,a9);,2021/3/29,第4章 語法制導的翻譯,38,語義規(guī)則的計算方法,2021/3/29,第4章 語法制導的翻譯,39,語義規(guī)則的計算方法 分析樹方法：前

12、面介紹方法（編譯速度慢）,2021/3/29,第4章 語法制導的翻譯,40,語義規(guī)則的計算方法 分析樹方法：前面介紹方法（編譯速度慢） 基于規(guī)則的方法：基于事先靜態(tài)確定語義規(guī)則的計算次序（手工構造編譯器，時空改善）,2021/3/29,第4章 語法制導的翻譯,41,語義規(guī)則的計算方法 分析樹方法：前面介紹方法（編譯速度慢） 基于規(guī)則的方法：基于事先靜態(tài)確定語義規(guī)則的計算次序（手工構造編譯器，時空改善） 忽略規(guī)則的方法：事先確定屬性的計算策略（如邊分析邊計算），那么語義規(guī)則的設計必須符合所選分析方法的限制（時空改善）,2021/3/29,第4章 語法制導的翻譯,42,本節(jié)小結,介紹了語法制導定義

13、、繼承屬性、綜合屬性、屬性依賴圖、拓撲順序等概念 詳細介紹了利用分析樹計算屬性的方法 簡單對比了屬性計算的三種方法,2021/3/29,第4章 語法制導的翻譯,43,作業(yè),P140：1,2021/3/29,第4章 語法制導的翻譯,44,思考,語言結構屬性計算的基礎是什么？ 依賴圖和拓撲順序有什么作用？它們對計算S屬性定義中的綜合屬性是否有用？ 計算語言結構屬性的步驟是什么？ 本節(jié)在語法制導定義的基礎上通過分析樹研究了屬性計算次序的問題，那么如何在此基礎上編程實現(xiàn)呢？,2021/3/29,第4章 語法制導的翻譯,45,4.2 S屬性定義的自下而上計算,語法樹是分析樹的濃縮表示：算符和關鍵字作為內(nèi)

14、部結點 語法樹的例子：,if-then-else,B,S1,S2,4.2.1 語法樹,算符,運算 對象,if B then S1 else S2,復習 S屬性定義？,2021/3/29,第4章 語法制導的翻譯,46,4.2 S屬性定義的自下而上計算,語法樹是分析樹的濃縮表示：算符和關鍵字作為內(nèi)部結點 語法樹的例子：,if-then-else,B,S1,S2,4.2.1 語法樹,算符,運算 對象,if B then S1 else S2,8 + 5 * 2,算符優(yōu)先級別？,2021/3/29,第4章 語法制導的翻譯,47,4.2 S屬性定義的自下而上計算,語法樹是分析樹的濃縮表示：算符和關鍵字作

15、為內(nèi)部結點 語法樹的例子：,if-then-else,B,S1,S2,+,*,8,4.2.1 語法樹,算符,運算 對象,if B then S1 else S2,8 + 5 * 2,2021/3/29,第4章 語法制導的翻譯,48,4.2 S屬性定義的自下而上計算,語法樹是分析樹的濃縮表示：算符和關鍵字作為內(nèi)部結點 語法樹的例子：,4.2.1 語法樹,算符,運算 對象,if B then S1 else S2,8 + 5 * 2,2021/3/29,第4章 語法制導的翻譯,49,4.2 S屬性定義的自下而上計算,語法樹是分析樹的濃縮表示：算符和關鍵字是作為內(nèi)部結點 語法制導翻譯可以基于分析樹，

16、也可以基于語法樹,4.2.1 語法樹,算符,運算 對象,if B then S1 else S2,8 + 5 * 2,2021/3/29,第4章 語法制導的翻譯,50,4.2.2 構造語法樹的語法制導定義,語法樹的存儲 語法樹的結點可以用有若干域的記錄來實現(xiàn) 對于算符結點：一個域存放算符，該域作為該結點的標記，其余兩個域含指向運算對象的指針 三地址 對于基本運算對象結點：一個域存放運算對象類別，另一個域存放其值 二地址 用于語法制導翻譯時，一個結點可能還有其它域來保存加在該結點的其它屬性值（即域中保存屬性值存儲位置的指針）,結點的類型,2021/3/29,第4章 語法制導的翻譯,51,用于構造

17、算術表達式語法樹的語法制導定義,mkleaf(id,entry)：建立標識符id的結點，結點的entry域用于存放該標識符條目的指針,2021/3/29,第4章 語法制導的翻譯,52,用于構造算術表達式語法樹的語法制導定義,mkleaf(num,val)：建立數(shù)num的結點，結點的val域用于存放該數(shù)值,2021/3/29,第4章 語法制導的翻譯,53,用于構造算術表達式語法樹的語法制導定義,mknode(op,left,right)：建立算符op的結點，指針域left和right分別存放該算符左、右運算對象的指針,2021/3/29,第4章 語法制導的翻譯,54,a+5*b的語法樹的構造,2

18、021/3/29,第4章 語法制導的翻譯,55,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,56,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,57,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,58,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,59,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,60,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,61,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,62,a+5*b的語法樹的

19、構造,2021/3/29,第4章 語法制導的翻譯,63,a+5*b的語法樹的構造,2021/3/29,第4章 語法制導的翻譯,64,S屬性可以由自下而上分析器在語法分析輸入時完成計算，即“邊分析邊計算” 自下而上分析器用棧保存已經(jīng)分析的子樹的信息，S屬性定義的翻譯器可以借助LR分析器的生成器來實現(xiàn) LR分析器可以把文法符號的綜合屬性放在它的棧內(nèi)，每當歸約時，根據(jù)出現(xiàn)在棧頂?shù)漠a(chǎn)生式右部符號串中符號的屬性來計算左部符號的綜合屬性,4.2.3 S屬性的自下而上計算,復習LR分析器的工作原理：棧內(nèi)可以不存儲文法符號,綜合屬性來自于子節(jié)點或自身的繼承屬性,2021/3/29,第4章 語法制導的翻譯,65

20、,將LR分析器增加一個域來保存綜合屬性值,棧 state val,top,2021/3/29,第4章 語法制導的翻譯,66,將LR分析器增加一個域來保存綜合屬性值,棧 state val,top,若產(chǎn)生式A XYZ的語義規(guī)則是 A.a := f (X.x, Y.y, Z.z),右部符號從左至右壓入棧內(nèi),2021/3/29,第4章 語法制導的翻譯,67,將LR分析器增加一個域來保存綜合屬性值,若產(chǎn)生式A XYZ的語義規(guī)則是 A.a := f (X.x, Y.y, Z.z)， 那么歸約后：,2021/3/29,第4章 語法制導的翻譯,68,例：臺式計算器的語法制導定義改成棧操作代碼,棧 state

21、 val,top,2021/3/29,第4章 語法制導的翻譯,69,例：臺式計算器的語法制導定義改成棧操作代碼,棧 state val,top,2021/3/29,第4章 語法制導的翻譯,70,例：臺式計算器的語法制導定義改成棧操作代碼,2021/3/29,第4章 語法制導的翻譯,71,例：臺式計算器的語法制導定義改成棧操作代碼,2021/3/29,第4章 語法制導的翻譯,72,例：臺式計算器的語法制導定義改成棧操作代碼,2021/3/29,第4章 語法制導的翻譯,73,例：臺式計算器的語法制導定義改成棧操作代碼,2021/3/29,第4章 語法制導的翻譯,74,例：臺式計算器的語法制導定義改

22、成棧操作代碼,2021/3/29,第4章 語法制導的翻譯,75,例：臺式計算器的語法制導定義改成棧操作代碼,2021/3/29,第4章 語法制導的翻譯,76,例：臺式計算器的語法制導定義改成棧操作代碼,2021/3/29,第4章 語法制導的翻譯,77,4.3 L 屬性定義的自上而下計算,邊分析邊翻譯的方式能否用于繼承屬性？ 屬性的計算次序受分析方法所限定的分析樹結點建立次序的限制,2021/3/29,第4章 語法制導的翻譯,78,4.3 L屬性定義的自上而下計算,邊語法分析邊翻譯的方式能否用于繼承屬性？ 屬性的計算次序受分析方法所限定的分析樹結點建立次序的限制 語法分析方法的共同特點：分析樹的

23、結點是自左向右生成 如果屬性信息自左向右流動，那么就有可能在分析的同時完成 L 屬性計算 L代表屬性從左向右傳遞的方向,2021/3/29,第4章 語法制導的翻譯,79,（1）如果每個產(chǎn)生式A X1 X2 Xj Xn 的每條語義規(guī)則計算的屬性是A的綜合屬性；或者（2）如果是Xj 的繼承屬性，1 j n,但它僅依賴于： 該產(chǎn)生式中Xj左邊（兄弟結點）符號X1, X2, , Xj-1的屬性 A的繼承屬性 那么語法制導定義是L屬性定義,4.3.1 L屬性定義,2021/3/29,第4章 語法制導的翻譯,80,（1）如果每個產(chǎn)生式A X1 X2 Xj Xn 的每條語義規(guī)則計算的屬性是A的綜合屬性；或者

24、（2）如果是Xj 的繼承屬性，1 j n,但它僅依賴于： 該產(chǎn)生式中Xj左邊（兄弟結點）符號X1, X2, , Xj-1的屬性 A的繼承屬性 那么語法制導定義是L屬性定義 S屬性定義是L屬性定義的一個特例,2021/3/29,第4章 語法制導的翻譯,81,例：變量類型聲明的語法制導定義是一個L屬性定義,2021/3/29,第4章 語法制導的翻譯,82,計算屬性需要考慮執(zhí)行語義規(guī)則的時機 翻譯方案將語義動作放在 內(nèi)，并將它當作文法符號插入產(chǎn)生式右部任何位置 語義動作插入的位置就是產(chǎn)生式的項目中的點的位置 執(zhí)行時機：當語法分析到該文法符號（語義動作）而進行推導或歸約時，執(zhí)行該語義動作,4.3.2

25、翻譯方案,什么是項目？,2021/3/29,第4章 語法制導的翻譯,83,只有綜合屬性的翻譯方案的建立 首先為每條語義規(guī)則建立一個放在一對 括號內(nèi)賦值動作，然后把這些動作分別放在對應產(chǎn)生式右部的末端,2021/3/29,第4章 語法制導的翻譯,84,例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5 2，則輸出是8 5 + 2 E T R R addop T print (addop.lexeme) R1 | T num print (num.val),2021/3/29,第4章 語法制導的翻譯,85,例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5 2，則輸出是8 5

26、+ 2 E T R R 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(),2021/3/29,第4章 語法制導的翻譯,86,例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5 2，則輸

27、出是8 5 + 2 E T R R 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(),2021/3/29,第4章 語法制導的翻譯,87,例:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+

28、5 2，則輸出是8 5 + 2 E T R R 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(),2021/3/29,第4章 語法制導的翻譯,88,例:把有加和減的中綴表達式翻譯成后綴表達式 如

29、果輸入是8+5 2，則輸出是8 5 + 2 E T R R 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(),關注動作,2021/3/29,第4章 語法制導的翻譯,89,例:把有加和減的中綴表達

30、式翻譯成后綴表達式 如果輸入是8+5 2，則輸出是8 5 + 2 E T R R 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(),關注動作,2021/3/29,第4章 語法制導的翻譯,90,例

31、:把有加和減的中綴表達式翻譯成后綴表達式 如果輸入是8+5 2，則輸出是8 5 + 2 E T R R 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(),關注動作,2021/3/29,第4章 語

32、法制導的翻譯,91,有繼承屬性的翻譯方案的建立 建立含有繼承屬性翻譯方案的規(guī)則： （1）產(chǎn)生式右部符號的繼承屬性必須在先于該符號的動作中計算 （2）一個動作不能引用該動作右邊符號的綜合屬性 （3）左部非終結符的綜合屬性只能在它所引用的所有屬性都計算完后才能計算，且計算該屬性的動作通常放在產(chǎn)生式右部末端,2021/3/29,第4章 語法制導的翻譯,92,例：數(shù)學排版語言EQN E sub 1 .val S B B B1 B2 B B1 sub B2 B text,2021/3/29,第4章 語法制導的翻譯,93,例：數(shù)學排版語言EQN （B.ps為繼承屬性） E sub 1 .val,2021/

33、3/29,第4章 語法制導的翻譯,94,例：數(shù)學排版語言EQN （B.ps為繼承屬性） 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 B1 sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B textB.ht := text.h * B.ps ,規(guī) 則 一,規(guī)則三,2021/3/29,第4章 語法制導的翻譯,95,例：左遞歸的消除可能引起繼承屬性(可能原 來只有綜合屬性）

34、-算術表達式語法制導定義,2021/3/29,第4章 語法制導的翻譯,96,算術表達式文法 E E + T | T T T * F | F F ( E ) | id 消除左遞歸后文法： E TR R + TR1 | T FW W * F W1 | F ( E ) | id,AAa |b 消除直接左遞歸： A b A A a A | ,其中：R和W為引入的輔助文法符號,2021/3/29,第4章 語法制導的翻譯,97,E T R.i := T.nptr RE.nptr := R.s R + TR1.i := mknode ( +, R.i, T.nptr) R1R.s := R1.s R R.s

35、 := R.i T F W.i := F.nptr WT.nptr := W.s W * FW1.i := mknode ( *, W.i, F.nptr) W1W.s := W1.s W W.s := W.i F (E) F. nptr := E.nptr F idF. nptr := mkleaf(id, id.entry) F num F. nptr := mkleaf(num, num.entry),R和W的i屬性是繼承屬性,2021/3/29,第4章 語法制導的翻譯,98,E T R.i := T.nptr RE.nptr := R.s R + TR1.i := mknode ( +

36、, R.i, T.nptr) R1R.s := R1.s R R.s := R.i T F W.i := F.nptr WT.nptr := W.s W * FW1.i := mknode ( *, W.i, F.nptr) W1W.s := W1.s W W.s := W.i F (E) F. nptr := E.nptr F idF. nptr := mkleaf(id, id.entry) F num F. nptr := mkleaf(num, num.entry),2021/3/29,第4章 語法制導的翻譯,99,用算術表達式語法制導定義構造a*5*b語法樹,1,2,3,4,5,6,

37、7,8,9,10,11,12,13,14,15,16,略去了E TR T 部分,遞歸： 自上而下 從左到右,推導而非歸約,2021/3/29,第4章 語法制導的翻譯,100,把預測分析器的構造方法推廣到翻譯方案的 實現(xiàn)（每個非終結符都對應一個過程或函數(shù)） 參見p126算法4.1）：適用于自上而下分析 例：產(chǎn)生式R +TR | 的分析過程： procedure R; begin if lookahead = + then begin match ( + ); T; R end else begin /* 什么也不做 */ end end,4.3.3 預測分析器的設計,預測分析器的特點？,2021

38、/3/29,第4章 語法制導的翻譯,101,產(chǎn)生式R +TR | 的語法樹的遞歸下降構造： 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)生式 R +T R */ addoplexeme := lexval; /* 載入運算符*/ match( + ); nptr := T; i1 := mknode(addoplexme, i , n

39、ptr) ; s1 := R (i1); s : = s1 end else s := i; /* 產(chǎn)生式 R */ return s end;,R : i, s T : nptr + : addoplexeme,2021/3/29,第4章 語法制導的翻譯,102,改變文法可能導致繼承屬性或綜合屬性 例如：消除左遞歸可能產(chǎn)生繼承屬性 Pascal的聲明，如m, n : integer D L : T T integer | char L L, id | id,4.3.4 用綜合屬性代替繼承屬性,2021/3/29,第4章 語法制導的翻譯,103,Pascal的聲明，如m, n : intege

40、r D L : T T integer | char L L, id | id 改成從右向左歸約 D id L L , id L | : T T integer | char,2021/3/29,第4章 語法制導的翻譯,104,Pascal的聲明，如m, n : integer D L : T T integer | char L L, id | id 改成從右向左歸約 D id L L , id L | : T T integer | char,2021/3/29,第4章 語法制導的翻譯,105,D id L addtype (id. entry, L. type) L , id L1 L.

41、 type := L1. Type; addtype (id. entry, L1. type) L : T L. type := T. type T integer T. type := integer T real T. type := real,修改后文法從右向左歸約，信息流向和歸約方向的一致性使屬性可以實現(xiàn)“邊分析邊計算”,2021/3/29,第4章 語法制導的翻譯,106,在自下而上分析的框架中實現(xiàn)L屬性定義的方法 它能實現(xiàn)任何基于LL(1)文法的L屬性定義 也能實現(xiàn)許多（但不是所有的）基于LR(1) 的L屬性定義,4.4 L屬性的自下而上計算,2021/3/29,第4章 語法制導的

42、翻譯,107,自下而上翻譯方案中，S屬性定義的語義動作位于產(chǎn)生式最右端；L屬性定義嵌在產(chǎn)生式右部不同位置的動作可以通過修改文法而把這些動作也放在產(chǎn)生式最右端 修改方法 在文法中加入產(chǎn)生的標記非終結符，讓每個嵌入動作由不同標記非終結符M代表 把該動作放在產(chǎn)生式M 的最右端,4.4.1 刪除翻譯方案中嵌入的動作,2021/3/29,第4章 語法制導的翻譯,108,例： E T R R + T print (+)R1 | T print ()R1 | T num print (num.val) E T R R + T M R1 | T N R1 | T num print (num.val) M p

43、rint (+) N print (),2021/3/29,第4章 語法制導的翻譯,109,屬性位置能準確預測 （棧中） 例：int p, q, r D T L.in := T.type L T int T. type := integer T real T. type := real L L1.in := L.in L1, id addtype (id.entry, L.in ) L id addtype (id.entry, L.in ),4.4.2 分析棧上的繼承屬性,2021/3/29,第4章 語法制導的翻譯,110,屬性位置能準確預測 （棧中） 例：int p, q, r D T L

44、.in := T.type L T int T. type := integer T real T. type := real L L1.in := L.in L1, id addtype (id.entry, L.in ) L id addtype (id.entry, L.in ),移進-歸約特點 每次歸約L產(chǎn)生式右部時，T剛好在該右部下面，因此T.type在棧中位置可以靜態(tài)確定(位置能預測),DTL,2021/3/29,第4章 語法制導的翻譯,111,移進-歸約特點 每次歸約L產(chǎn)生式右部時，T剛好在該右部下面，因此T.type在棧中位置可以靜態(tài)確定(位置能預測),2021/3/29,第4

45、章 語法制導的翻譯,112,移進-歸約特點 每次歸約L產(chǎn)生式右部時，T剛好在該右部下面，因此T.type在棧中位置可以靜態(tài)確定(位置能預測),2021/3/29,第4章 語法制導的翻譯,113,屬性的位置不能預測（棧中） S aACC.i := A.s S bABCC.i := A.s C cC.s := g(C.i),分析棧中，B使C.i繼承屬性值無法肯定從棧中哪個位置獲取,2021/3/29,第4章 語法制導的翻譯,114,屬性的位置不能預測（棧中） S aACC.i := A.s S bABCC.i := A.s C cC.s := g(C.i) 解決辦法：增加標記非終結符 S aACC

46、.i := A.s S bABMCM.i := A.s; C.i := M.s M M.s := M.i C cC.s := g(C.i),M使C.i值從棧中valtop-1處獲取，并使M 歸約時M.i值從valtop-2處獲得（此時M處于棧頂）,2021/3/29,第4章 語法制導的翻譯,115,繼承屬性是某個綜合屬性的一個函數(shù) S aACC.i := f (A.s) C cC.s := g(C.i),4.4.3 模擬繼承屬性的計算,2021/3/29,第4章 語法制導的翻譯,116,繼承屬性是某個綜合屬性的一個函數(shù) S aACC.i := f (A.s) C cC.s := g(C.i)

47、問題：繼承屬性不能通過屬性簡單復制計算辦法：增加標記非終結符，把f(A.s)的計算移到對標記非終結符歸約時進行 S aANCN.i := A.s; C.i := N.s N N.s := f (N.i) C cC.s := g(C.i),2021/3/29,第4章 語法制導的翻譯,117,例：數(shù)學排版語言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 B1 sub B2.ps := shrink(B.ps) B2B.ht := d

48、isp (B1.ht, B2.ht ) B textB.ht := text.h B.ps ,2021/3/29,第4章 語法制導的翻譯,118,L,M,N保證了在任何情況下向B歸約時，B.ps的值總是正好在右部下面,N模擬繼承屬性,2021/3/29,第4章 語法制導的翻譯,119,2021/3/29,第4章 語法制導的翻譯,120,S.ht := B.ht,2021/3/29,第4章 語法制導的翻譯,121,B.ps := L.s; L.s := 10,2021/3/29,第4章 語法制導的翻譯,122,B.ht := max(B1.ht, B2.ht ),2021/3/29,第4章 語法

49、制導的翻譯,123,B2.ps := M.s;M.s := M.i; M.i := B.ps;B1.ps := B.ps,2021/3/29,第4章 語法制導的翻譯,124,B.ht := disp (B1.ht, B2.ht ),2021/3/29,第4章 語法制導的翻譯,125,B2.ps := N.s; N.s := shrink(N.i); N.i := B.ps;,2021/3/29,第4章 語法制導的翻譯,126,向B歸約時，B.ps的值正好在右部下面,2021/3/29,第4章 語法制導的翻譯,127,算法4.2（p134）： 對基礎文法是LL(1)的L屬性定義的有繼承屬性的自下

50、而上翻譯 方法：把問題簡化為每個非終結符A只有一個繼承屬性A.i，且每個文法符號X都有一個綜合屬性X.s。如果X是終結符，則綜合屬性是詞法分析器的記號屬性 操作說明：（1）對每個產(chǎn)生式AX1Xn引入n個標記非終結符M1Mn，用A M1 X1 Mn Xn代替。綜合屬性Xj.s進入分析棧val數(shù)組相應于Xj的條目；繼承屬性Xj.出現(xiàn)在val數(shù)組相應于Mj的條目。（2）如果繼承屬性A.i存在，則它的值位于val數(shù)組M1下面且緊帖M1的條目處,2021/3/29,第4章 語法制導的翻譯,128,4.5 遞 歸 計 算,回顧：語法制導定義的實現(xiàn) 分析樹方法,2021/3/29,第4章 語法制導的翻譯,1

51、29,4.5 遞 歸 計 算,回顧：語法制導定義的實現(xiàn) 分析樹方法 邊分析邊進行屬性計算，只能完成L屬性計算（忽略規(guī)則的方法）,2021/3/29,第4章 語法制導的翻譯,130,4.5 遞 歸 計 算,回顧：語法制導定義的實現(xiàn) 分析樹方法 邊分析邊進行屬性計算，只能完成L屬性計算（忽略規(guī)則的方法） 本節(jié)介紹先分析后計算的方法，不局限于L屬性計算（基于規(guī)則的方法）,2021/3/29,第4章 語法制導的翻譯,131,4.5 遞 歸 計 算,回顧：語法制導定義的實現(xiàn) 分析樹方法 邊分析邊進行屬性計算，只能完成L屬性計算（忽略規(guī)則的方法） 本節(jié)介紹先分析后計算的方法，不局限于L屬性計算（基于規(guī)則的

52、方法） 為每個非終結符構造一個屬性計算函數(shù)，但是該函數(shù)不含語法分析部分,2021/3/29,第4章 語法制導的翻譯,132,4.5 遞 歸 計 算,回顧：語法制導定義的實現(xiàn) 分析樹方法 邊分析邊進行屬性計算，只能完成L屬性計算（忽略規(guī)則的方法） 本節(jié)介紹先分析后計算的方法，不局限于L屬性計算（基于規(guī)則的方法） 為每個非終結符構造一個屬性計算函數(shù)，但是該函數(shù)不含語法分析部分 為非終結符的不同綜合屬性構造不同的函數(shù),2021/3/29,第4章 語法制導的翻譯,133,為B構造一個屬性計算函數(shù) S B.ps := 10 BS.ht := B.ht B B1.ps := B.ps B1B2.ps :=

53、 B.ps B2B.ht := max(B1.ht, B2.ht ) B B1.ps :=B.ps B1 sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B textB.ht := text.h B.ps ,4.5.1 自左向右遍歷,2021/3/29,第4章 語法制導的翻譯,134,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結點n的產(chǎn)生式 of B B1 B2: ps1 := ps; ht1 := B(child(n,1), ps1); ps2 := ps;

54、ht2 := B(child(n,2), ps2); return max(ht1, ht2);,B B1.ps := B.ps B1B2.ps := B.ps B2B.ht := max(B1.ht, B2.ht ) ,函數(shù)以結點n和它的繼承屬性ps為參數(shù)，返回結點n的綜合屬性值,非終結符繼承屬性的計算必須先于對該非終結符的函數(shù)調(diào)用,2021/3/29,第4章 語法制導的翻譯,135,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結點n的產(chǎn)生式 of B B1 sub B2: ps1 := ps; ht1 := B(child(

55、n,1), ps1); ps2 := shrink(ps); ht2 := B(child(n,3), ps2); return disp(ht1, ht2);,B B1.ps := B.ps B1sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) ,函數(shù)以結點n和它的繼承屬性ps為參數(shù)，返回結點n的綜合屬性值,非終結符繼承屬性的計算必須先于對該非終結符的函數(shù)調(diào)用,2021/3/29,第4章 語法制導的翻譯,136,function B(n, ps); var ps1, ps2, ht1, ht2; begin case 在結點n的

56、產(chǎn)生式 of B text: return ps text.h; default: error end,B textB.ht := text.h B.ps ,函數(shù)以結點n和它的繼承屬性ps為參數(shù)，返回結點n的綜合屬性值,非終結符繼承屬性的計算必須先于對該非終結符的函數(shù)調(diào)用,2021/3/29,第4章 語法制導的翻譯,137,按所需次序訪問結點的子結點，可用于非L屬性定義 A LM L.i := l(A.i); M.i := m(L.s); A.s := f (M.s) A QR R.i := r(A.i); Q.i := q(R.s); A.s := f (Q.s),4.5.2 其它遍歷方法,

57、2021/3/29,第4章 語法制導的翻譯,138,A LM:/* 從左到右的次序 */ li := l(ai); ls := L(child(n,1), li); mi := m(ls); ms := M(child(n,2), mi); return f (ms);,2021/3/29,第4章 語法制導的翻譯,139,A QR:/* 從右到左的次序 */ ri := r(ai); rs := R(child(n,2), ri); qi := q(rs); qs := Q(child(n,1), qi); return f (qs);,2021/3/29,第4章 語法制導的翻譯,140,S

58、E E.i := g(E.s); S.r := E.t E E1E2 E.s := fs(E1.s, E2.s); E1.i := fi1(E.i); E2.i := fi2(E.i); E.t := ft (E1.t, E2.t) E id E.s := id.s; E.t := h(E.i),2021/3/29,第4章 語法制導的翻譯,141,綜合屬性t不可能和s在同一遍掃描中完成計算,2021/3/29,第4章 語法制導的翻譯,142,function Sr(n); begin s := Es(child(n,1); i := g(s); t := Et(child(n,1), i);

59、return t end;,2021/3/29,第4章 語法制導的翻譯,143,function Es(n); | function Et(n, i); begin | begin case 在結點n的產(chǎn)生式 of | case 在結點n的產(chǎn)生式 of E E1 E2: |E E1 E2: s1 := Es(child(n,1); | i1:= fi1(i); s2 := Es(child(n,2); | t1 := Et(child(n,1), i1); return fs(s1, s2); | i2:= fi2(i); E id: | t2 := Et(child(n,2), i2); r

60、eturn id.s; | return ft(t1, t2); default: |E id: error | return h(i); end |default: end; | error |end | end;,2021/3/29,第4章 語法制導的翻譯,144,本 章 要 點,語義規(guī)則的兩種描述方法：語法制導的定義和翻譯方案 設計簡單問題的語法制導定義和翻譯方案，這是本章的重點和難點 語義規(guī)則的三種計算方法：分析樹方法、基于規(guī)則的方法和忽略規(guī)則的方法。 S屬性的自下而上計算（邊分析邊計算） L屬性的自上而下計算（邊分析邊計算） L屬性的自下而上計算（邊分析邊計算） 遞歸計算（先分析后計