編譯原理張晶版 第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成

1、課程名稱第七章語(yǔ)法制導(dǎo)翻譯和中間代碼生成第七章語(yǔ)法制導(dǎo)翻譯和中間代碼生成7.1概述7.2屬性文法和語(yǔ)法制導(dǎo)翻譯7.3語(yǔ)義分析7.4中間代碼7.5一些語(yǔ)句的翻譯第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1 1）課程名稱概述概述 語(yǔ)義處理語(yǔ)義處理程序設(shè)計(jì)程序設(shè)計(jì) 語(yǔ)言的語(yǔ)義語(yǔ)言的語(yǔ)義 靜態(tài)語(yǔ)義是對(duì)程序約束的描述，這些約束無(wú)法通過(guò)抽象語(yǔ)法規(guī)則來(lái)妥善靜態(tài)語(yǔ)義是對(duì)程序約束的描述，這些約束無(wú)法通過(guò)抽象語(yǔ)法規(guī)則來(lái)妥善地描述，實(shí)質(zhì)上就是語(yǔ)法規(guī)則的良形式條件，它可以分為類型規(guī)則和作地描述，實(shí)質(zhì)上就是語(yǔ)法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域用域/ /可見(jiàn)性規(guī)則兩大類可見(jiàn)性規(guī)則兩

2、大類 類型相容性類型相容性 變量先聲明后引用變量先聲明后引用 名稱相名稱相關(guān)要求關(guān)要求 動(dòng)態(tài)語(yǔ)義動(dòng)態(tài)語(yǔ)義 程序單位描述的計(jì)算程序單位描述的計(jì)算編譯程序的語(yǔ)義處理工作編譯程序的語(yǔ)義處理工作 靜態(tài)語(yǔ)義審查靜態(tài)語(yǔ)義審查 解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼生成代碼.語(yǔ)語(yǔ) 法法 分分 析析 后后 的的 源源 程程 序序 語(yǔ)義處理語(yǔ)義處理第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2 2）課程名稱概述語(yǔ)義形式化語(yǔ)義形式化 語(yǔ)義建模語(yǔ)義建模 文法模型文法模型- - 屬性文法屬性文法 命令式或操作式模型命令式或操作式模型 - - 操作語(yǔ)義學(xué)操作語(yǔ)義學(xué) 應(yīng)用式模型

3、應(yīng)用式模型-指稱語(yǔ)義學(xué)指稱語(yǔ)義學(xué) 公理式模型公理式模型-公理語(yǔ)義學(xué)公理語(yǔ)義學(xué)第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3 3）課程名稱屬性文法屬性文法表達(dá)式文法 ET+T| T or T Tn | b ET1 + T2 T1.type = int T2.type= T1.type E.type :=int E T1 or T2 T1.type = bool T2.type= T1.type E.type :=bool T n T.type := int T b T.type := bool 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4 4

4、）課程名稱 操作語(yǔ)義操作語(yǔ)義 描述一段程序的含義是通過(guò)執(zhí)行該段程序所改變的計(jì)算機(jī)（虛擬描述一段程序的含義是通過(guò)執(zhí)行該段程序所改變的計(jì)算機(jī)（虛擬計(jì)算機(jī)）狀態(tài)來(lái)反映。這個(gè)計(jì)算機(jī)的狀態(tài)與程序執(zhí)行時(shí)的狀態(tài)相對(duì)計(jì)算機(jī)）狀態(tài)來(lái)反映。這個(gè)計(jì)算機(jī)的狀態(tài)與程序執(zhí)行時(shí)的狀態(tài)相對(duì)應(yīng)：包括變量的所有值，可執(zhí)行程序本身，各種系統(tǒng)定義的內(nèi)部數(shù)應(yīng)：包括變量的所有值，可執(zhí)行程序本身，各種系統(tǒng)定義的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。計(jì)算機(jī)里所有的寄存器的值和存儲(chǔ)單元的值作為計(jì)算機(jī)的據(jù)結(jié)構(gòu)。計(jì)算機(jī)里所有的寄存器的值和存儲(chǔ)單元的值作為計(jì)算機(jī)的狀態(tài)，用一組形式定義的操作來(lái)說(shuō)明執(zhí)行一條指令相應(yīng)的狀態(tài)怎樣狀態(tài)，用一組形式定義的操作來(lái)說(shuō)明執(zhí)行一條指令相應(yīng)的狀

5、態(tài)怎樣變化。變化。For (expr1;expr2;expr3) expr1; . Loop:if expr2=0 goto out expr3; goto loop out: .第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5 5）課程名稱公理語(yǔ)義公理語(yǔ)義一個(gè)語(yǔ)言的每個(gè)語(yǔ)法成分的含義定義為公理和演繹規(guī)則，用于推導(dǎo)出該成一個(gè)語(yǔ)言的每個(gè)語(yǔ)法成分的含義定義為公理和演繹規(guī)則，用于推導(dǎo)出該成分執(zhí)行的效果。分執(zhí)行的效果。公理語(yǔ)義概念是隨著程序正確性的證明而發(fā)展的。當(dāng)正確性證明能構(gòu)造時(shí)公理語(yǔ)義概念是隨著程序正確性的證明而發(fā)展的。當(dāng)正確性證明能構(gòu)造時(shí)表明程序執(zhí)行它的規(guī)格說(shuō)明所描述的計(jì)

6、算。在一個(gè)證明中，每一個(gè)語(yǔ)句表明程序執(zhí)行它的規(guī)格說(shuō)明所描述的計(jì)算。在一個(gè)證明中，每一個(gè)語(yǔ)句之前之后都有一個(gè)邏輯表達(dá)式對(duì)程序的變量進(jìn)行約束之前之后都有一個(gè)邏輯表達(dá)式對(duì)程序的變量進(jìn)行約束, ,以此說(shuō)明這個(gè)語(yǔ)以此說(shuō)明這個(gè)語(yǔ)句的含義。句的含義。 一般的記號(hào)一般的記號(hào) P S Q P S Q 如果在語(yǔ)句如果在語(yǔ)句S S執(zhí)行前執(zhí)行前P P為真，則在語(yǔ)句為真，則在語(yǔ)句S S執(zhí)行并終止后執(zhí)行并終止后Q Q為真。為真。 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（6 6）課程名稱 演繹規(guī)則的例子 規(guī)則 前驅(qū) 后繼 賦值：x:=expr P(expr)x:=exprP(x) While:

7、 P B S P P while B do S end P (not B) if-then-else B P S1 Q, (not B) P S2 Q P if B then S1 else S2Q 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（7 7）課程名稱指稱語(yǔ)義指稱語(yǔ)義指稱語(yǔ)義的基本概念是給每一段程序?qū)嶓w定義一個(gè)數(shù)學(xué)意義上的指稱語(yǔ)義的基本概念是給每一段程序?qū)嶓w定義一個(gè)數(shù)學(xué)意義上的對(duì)象，和一個(gè)從實(shí)體實(shí)例向數(shù)學(xué)意義對(duì)象的映射的函數(shù)對(duì)象，和一個(gè)從實(shí)體實(shí)例向數(shù)學(xué)意義對(duì)象的映射的函數(shù)特點(diǎn)：特點(diǎn)： 不但對(duì)全部程序賦予全文而且對(duì)程序設(shè)計(jì)語(yǔ)法不但對(duì)全部程序賦予全文而且對(duì)程序設(shè)計(jì)

8、語(yǔ)法 每一個(gè)語(yǔ)法成分短語(yǔ)（表達(dá)式，命令，聲明每一個(gè)語(yǔ)法成分短語(yǔ)（表達(dá)式，命令，聲明） 都都給予含義。給予含義。 每一個(gè)語(yǔ)法成分（短語(yǔ)）的含義是以它的自每一個(gè)語(yǔ)法成分（短語(yǔ)）的含義是以它的自 成分的含義的術(shù)語(yǔ)來(lái)定義的。成分的含義的術(shù)語(yǔ)來(lái)定義的。 即即 語(yǔ)義結(jié)構(gòu)語(yǔ)義結(jié)構(gòu) 平行于語(yǔ)法結(jié)構(gòu)。平行于語(yǔ)法結(jié)構(gòu)。語(yǔ)義函數(shù)：語(yǔ)義函數(shù)： 程序設(shè)計(jì)語(yǔ)言的語(yǔ)義利用映射函數(shù)來(lái)證程序設(shè)計(jì)語(yǔ)言的語(yǔ)義利用映射函數(shù)來(lái)證 明。明。 語(yǔ)義函數(shù)將短語(yǔ)映射到它的指稱。語(yǔ)義函數(shù)將短語(yǔ)映射到它的指稱。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（8 8）課程名稱 例：例： 二進(jìn)制數(shù)語(yǔ)言 110或10101 語(yǔ)法實(shí)

9、體 指稱（自然數(shù)） 6 或 21 語(yǔ)義實(shí)體 二進(jìn)制數(shù)文法 Numeral:=0 :=1 := Numeral 0 :=Numeral 1 自然數(shù) Natrual=0,1,2,3, 語(yǔ)義函數(shù) Valuation:NumeralNatural第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（9 9）課程名稱 Valuation101 表示把Valuation施用于101 ValuationN - 把它施用于N 定義定義: Valuation（用四個(gè)方程)因?yàn)橛兴膫€(gè)形式numeral Valuation0 0 Valuation1 1 ValuationN0 2Valuation

10、 N ValuationN1 2Valuation N+1 所以：所以： Valuation110=2 Valuation11 = 2 (2 Valuation1+1) =2 (2 1+1) =6第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1010）課程名稱屬性文法和語(yǔ)法制導(dǎo)翻譯屬性文法和語(yǔ)法制導(dǎo)翻譯 雖然形式語(yǔ)義學(xué)雖然形式語(yǔ)義學(xué)( (如指稱語(yǔ)義學(xué)、公理語(yǔ)義學(xué)、如指稱語(yǔ)義學(xué)、公理語(yǔ)義學(xué)、操作語(yǔ)義學(xué)等操作語(yǔ)義學(xué)等) )的研究已取得了許多重大的進(jìn)展，的研究已取得了許多重大的進(jìn)展，但目前在實(shí)際應(yīng)用中比較流行的語(yǔ)義描述和語(yǔ)義但目前在實(shí)際應(yīng)用中比較流行的語(yǔ)義描述和語(yǔ)義處理的方法

11、主要還是屬性文法和語(yǔ)法制導(dǎo)翻譯方處理的方法主要還是屬性文法和語(yǔ)法制導(dǎo)翻譯方法法 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1111）課程名稱屬性文法屬性文法屬性文法屬性文法(attribute grammar)(attribute grammar)是一個(gè)三元組是一個(gè)三元組:A=(G,V,F),:A=(G,V,F),其中其中 G:G:是一個(gè)上下文無(wú)關(guān)文法是一個(gè)上下文無(wú)關(guān)文法V:V:有窮的屬性集有窮的屬性集, ,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連符相連, ,這些屬性代表與文法符號(hào)相關(guān)信息，如它的類這些屬性代表與文法符號(hào)相關(guān)信息，如

12、它的類型、值、代碼序列、符號(hào)表內(nèi)容等等型、值、代碼序列、符號(hào)表內(nèi)容等等 . .屬性與變量一樣，屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加工的過(guò)程即是語(yǔ)義處理的可以進(jìn)行計(jì)算和傳遞。屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。過(guò)程。F:F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則( (稱為語(yǔ)義稱為語(yǔ)義規(guī)則規(guī)則) . ) . 斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián)斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián), ,只引用該只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性. . 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（12

13、12）課程名稱屬性有兩種屬性有兩種 繼承的和綜合的屬性繼承的和綜合的屬性 屬性通常分為兩類：綜合屬性和繼承屬性。簡(jiǎn)單地說(shuō)，綜合屬性用屬性通常分為兩類：綜合屬性和繼承屬性。簡(jiǎn)單地說(shuō)，綜合屬性用于于“自下而上自下而上”傳遞信息，而繼承屬性用于傳遞信息，而繼承屬性用于“自上而下自上而下”傳遞信息。傳遞信息。 出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的由所給定的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由生計(jì)算器的參數(shù)提供屬性規(guī)則計(jì)算或者由生計(jì)算器的參數(shù)

14、提供。 AX1 X2 XnA的綜合屬性,計(jì)算 S(A):=f(I(X1),I(Xn)Xj的繼承屬性,計(jì)算 T(Xj):=f(I(A),. I(Xn) 1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開(kāi)始符號(hào)沒(méi)有繼承屬性. 2)終結(jié)符只有綜合屬性.第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1313）課程名稱 在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A A都有一套與之相關(guān)聯(lián)的語(yǔ)都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為義規(guī)則，每條規(guī)則的形式為b:=f(cb:=f(c1 1,c,c2 2c ck k) )這里，這里，f f是一個(gè)函數(shù)，而且或

15、者是一個(gè)函數(shù)，而且或者（1 1）b b是是A A的一個(gè)綜合屬性并且的一個(gè)綜合屬性并且c c1 1,c,c2 2c ck k是產(chǎn)生式右邊文法符號(hào)的屬性是產(chǎn)生式右邊文法符號(hào)的屬性; ;或者或者（2 2）b b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c c1 1,c,c2 2c ck k是是A A或或產(chǎn)生式右邊任何文法符號(hào)的屬性。產(chǎn)生式右邊任何文法符號(hào)的屬性。在兩種情況下，我們都說(shuō)屬性在兩種情況下，我們都說(shuō)屬性b b依賴于屬性依賴于屬性c c1 1,c,c2 2c ck k 。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1414）

16、課程名稱 一個(gè)屬性文法的例子一個(gè)屬性文法的例子 例例7.17.1 非終結(jié)符非終結(jié)符E E、T T及及F F都有一個(gè)綜合屬性都有一個(gè)綜合屬性valval, ,符號(hào)符號(hào)digitdigit有一個(gè)綜合屬性，它的有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式值由詞法分析器提供。與產(chǎn)生式LEnLEn對(duì)應(yīng)的語(yǔ)義規(guī)則僅僅是打印由對(duì)應(yīng)的語(yǔ)義規(guī)則僅僅是打印由E E產(chǎn)生的產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過(guò)程，我們可認(rèn)為這條規(guī)則定義了算術(shù)表達(dá)式的值的一個(gè)過(guò)程，我們可認(rèn)為這條規(guī)則定義了L L的一個(gè)虛屬性。某的一個(gè)虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一

17、非終結(jié)符多次出現(xiàn)語(yǔ) 義 規(guī) 則 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn) 生 式第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1515）課程名稱設(shè)表達(dá)式為設(shè)表達(dá)式為3 35+45+4，則，則語(yǔ)義動(dòng)作語(yǔ)義動(dòng)作打印數(shù)值打印數(shù)值1919.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F

18、.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹(shù)的帶注釋的分析樹(shù)第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1616）課程名稱繼承屬性繼承屬性一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/ /或兄弟結(jié)點(diǎn)的某些或兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。屬性來(lái)決定的。例7.2 繼承屬性繼承屬性L.in生 產(chǎn) 式語(yǔ) 義 規(guī) 則D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real

19、L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1717）課程名稱 DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.Real id1,id2,id3，第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1818）課程名稱例例7.37.3P DSD var V; D | S V := E; S | V x | y | z現(xiàn)在使用兩個(gè)屬性，現(xiàn)在使用兩個(gè)屬性，name和和dl，每當(dāng)一個(gè)

20、新的變量聲明時(shí)，就把它的，每當(dāng)一個(gè)新的變量聲明時(shí)，就把它的name屬性附屬性附給它，給它，name屬性是綜合屬性。屬性是綜合屬性。將所聲明的變量都放到一個(gè)變量名字清單中（用語(yǔ)義函數(shù)將所聲明的變量都放到一個(gè)變量名字清單中（用語(yǔ)義函數(shù)addlist實(shí)現(xiàn)），用屬性實(shí)現(xiàn)），用屬性dl綜合聲明塊中聲明的所有變量。然后這個(gè)綜合聲明塊中聲明的所有變量。然后這個(gè)dl屬性又作為繼承屬性傳到后面的語(yǔ)句屬性又作為繼承屬性傳到后面的語(yǔ)句部分，每個(gè)語(yǔ)句用到的變量都要進(jìn)行審查，看它是否在變量名字清單中部分，每個(gè)語(yǔ)句用到的變量都要進(jìn)行審查，看它是否在變量名字清單中 P DS S.dl = D.dlD1 var V; D2

21、| D1.dl = addlist(V.name, D2.dl) | D1.dl = NULLS1 V := E; S2 | check(V.name, S1.dl); S2.dl = S1.dlV x | y | z V.name = x | V.name = y | V.name = z第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（1919）課程名稱var x；var y；x:=e； P D dl=x,y S dl=x,yvar V ； D dl=y V := e ； S x var V ； D dl= y y 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯

22、和中間代碼生成（2020）課程名稱語(yǔ)法制導(dǎo)的翻譯語(yǔ)法制導(dǎo)的翻譯 一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。在一個(gè)編譯程序定義的翻譯中，符號(hào)串對(duì)是源程序和目標(biāo)程序。各個(gè)編譯階段定義一個(gè)翻譯，詞法分析：（字符串，單詞串）語(yǔ)法分析：（單詞串，語(yǔ)法樹(shù)）代碼生成（語(yǔ)法樹(shù)，匯編語(yǔ)言） 設(shè)是輸入字母表且是輸出字母表。定義由語(yǔ)言 L1 *到語(yǔ)言L2 *的一個(gè)翻譯是由*到 *的一個(gè)關(guān)系T,使得T的定義域?yàn)長(zhǎng)1且T的值域?yàn)長(zhǎng)2 。 使(x,y) T的句子y叫做x的一個(gè)輸出.第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2121）課程名稱語(yǔ)法制導(dǎo)的翻譯語(yǔ)法制導(dǎo)的翻譯 直觀地說(shuō)，一個(gè)語(yǔ)法制導(dǎo)翻譯的基礎(chǔ)是一

23、個(gè)文法，其中翻譯成分依附在直觀地說(shuō)，一個(gè)語(yǔ)法制導(dǎo)翻譯的基礎(chǔ)是一個(gè)文法，其中翻譯成分依附在每一產(chǎn)生式上。每一產(chǎn)生式上。例例7.47.4： 下列翻譯模式，它定義翻譯，即對(duì)每個(gè)輸入下列翻譯模式，它定義翻譯，即對(duì)每個(gè)輸入x x，其輸出，其輸出y y是是x x的的逆轉(zhuǎn)。定義此翻譯的規(guī)則是逆轉(zhuǎn)。定義此翻譯的規(guī)則是 產(chǎn)生式產(chǎn)生式 翻譯規(guī)則翻譯規(guī)則 (1)s0s(2)s1s (3)s (1)s=s0(2)s=s1 (3)s= 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2222）課程名稱 輸入輸出對(duì)可由(,)表示，其中是輸入句子形式而是輸出句子形式。 (S,S)開(kāi)始用產(chǎn)生式s0s來(lái)擴(kuò)

24、展得到(0S,S0). 再用一次規(guī)則(1)，得到(00S,S00)。 再用規(guī)則(2)，就得到(001S,S100). 然后應(yīng)用規(guī)則(3)并得到(001,100)。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2323）課程名稱 例例7.57.5： 把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表示：把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a 產(chǎn)生式 翻譯規(guī)則翻譯規(guī)則第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2424）課程名稱確定輸入

25、a+aa的輸出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,FT+) (a+T,aT+) (a+TF,aFF+) (a+FF,aFF+) (a+aF,aaF+) (a+aa,aaa+)第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2525）課程名稱 定義：定義： 一個(gè)語(yǔ)法制導(dǎo)的翻譯模式是一個(gè)五元組一個(gè)語(yǔ)法制導(dǎo)的翻譯模式是一個(gè)五元組T=(N, , ， R,S),其中其中 (1) N是非終結(jié)符的有限集。是非終結(jié)符的有限集。 (2) 是有限的輸入字母表。是有限的輸入字母表。 (3) 是有限的輸出字母表。是有限的輸出字母表。 (4) R是形如是形如A, 的規(guī)則

26、的有限集的規(guī)則的有限集,其中其中 (N )*, (N )*且且 中那組非終結(jié)符是中那組非終結(jié)符是 中中那組非終結(jié)符那組非終結(jié)符的置換。的置換。 (5) S是是N中一個(gè)特別的非終結(jié)符，即開(kāi)始符。中一個(gè)特別的非終結(jié)符，即開(kāi)始符。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2626）課程名稱 定義：定義： 若若T= (N,T= (N, , , , , R,S) R,S)是是SDTS,SDTS, (T)(T)則稱為語(yǔ)法制導(dǎo)的翻則稱為語(yǔ)法制導(dǎo)的翻譯譯(SDT)(SDT)，文法，文法GiGi=(N,=(N, ,P,S) ,P,S)，其中，其中P=AP=A| |A A, , 屬于屬

27、于R)R)，稱為稱為SDTS TSDTS T的基礎(chǔ)（或輸入）文法。文法的基礎(chǔ)（或輸入）文法。文法G G0 0=( N, =( N, ,P,P ,S),S), ，其中其中P P =A =A | | A A, , 屬于屬于R R ，稱為，稱為T(mén) T的輸出文法。的輸出文法。 把語(yǔ)法制導(dǎo)的翻譯方法看成是將輸入文法把語(yǔ)法制導(dǎo)的翻譯方法看成是將輸入文法GiGi中的推中的推導(dǎo)樹(shù)變換成輸出文法導(dǎo)樹(shù)變換成輸出文法G G0 0中的推導(dǎo)樹(shù)。給了輸入句子中的推導(dǎo)樹(shù)。給了輸入句子x x，可以按，可以按如下方式得到如下方式得到x x的一個(gè)翻譯：先為推導(dǎo)的一個(gè)翻譯：先為推導(dǎo)x x構(gòu)造一棵推導(dǎo)樹(shù)，再構(gòu)造一棵推導(dǎo)樹(shù)，再變換該樹(shù)

28、到輸出文法中的一棵樹(shù)，然后取此輸出樹(shù)的邊緣作變換該樹(shù)到輸出文法中的一棵樹(shù)，然后取此輸出樹(shù)的邊緣作為為x x的一個(gè)翻譯。的一個(gè)翻譯。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2727）課程名稱語(yǔ)義制導(dǎo)翻譯中的規(guī)則語(yǔ)義制導(dǎo)翻譯中的規(guī)則A A, , 對(duì)應(yīng)于每一個(gè)文法產(chǎn)生式對(duì)應(yīng)于每一個(gè)文法產(chǎn)生式A A 都有與之相都有與之相關(guān)聯(lián)的一套語(yǔ)義描述關(guān)聯(lián)的一套語(yǔ)義描述 屬性文法屬性文法(attribute grammar)(attribute grammar)是一個(gè)三元是一個(gè)三元組組:A=(G,V,F) :A=(G,V,F) 屬性文法可以看作是關(guān)于語(yǔ)言翻譯的高級(jí)規(guī)范說(shuō)屬性文法可以看作

29、是關(guān)于語(yǔ)言翻譯的高級(jí)規(guī)范說(shuō)明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說(shuō)明翻明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說(shuō)明翻譯順序的工作中解脫出來(lái)譯順序的工作中解脫出來(lái)第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2828）課程名稱語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn)從概念上講，語(yǔ)法制導(dǎo)翻譯即基于屬性文法的處理過(guò)程通常是這樣的：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然后根據(jù)需要遍歷語(yǔ)法樹(shù)并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算輸入符號(hào)串 分析樹(shù) 屬性依賴圖 語(yǔ)義規(guī)則的計(jì)算順序第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（2929）課程名稱依賴圖由稱為依賴圖的一個(gè)有向圖 描述分析樹(shù)中

30、的繼承屬性和屬性中間的相互依賴關(guān)系。 依賴圖的構(gòu)造算法：依賴圖的構(gòu)造算法： for分析樹(shù)中每一個(gè)結(jié)點(diǎn)n do for 結(jié)點(diǎn)的文法符號(hào)的每一個(gè)屬性a do 為a在依賴圖中建立一個(gè)結(jié)點(diǎn)； for 分析樹(shù)中每一個(gè)結(jié)點(diǎn)n do for結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語(yǔ)義規(guī)則 b:=f(c1,c2,ck) do for i :=1 to k do 從ci結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3030）課程名稱依賴圖-例7.2 例例7.2 7.2 繼承屬性繼承屬性L.inL.in生 產(chǎn) 式語(yǔ) 義 規(guī) 則D TL T int T real L L1,i

31、dL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3131）課程名稱例7.2 Real id1,id2,id3分析樹(shù)的依賴圖 5678910T4DLLLRealtypeininin3 entry2 entryentryid3id2id1.1第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3232）課程名稱 依賴圖中的結(jié)點(diǎn)由數(shù)字來(lái)標(biāo)識(shí)。從代表T.type的

32、結(jié)點(diǎn)4有一條有向邊連到代表L.in的結(jié)點(diǎn)5，因?yàn)楦鶕?jù)產(chǎn)生式ETL的語(yǔ)義規(guī)則L1.in=L.in，可知L1.in依賴于L.in，所以有兩條向下的有向邊分別進(jìn)入結(jié)點(diǎn)7和9。每一個(gè)與L產(chǎn)生式有關(guān)的語(yǔ)義規(guī)則addtype(id. Entry, L.in)都產(chǎn)生一個(gè)虛屬性，結(jié)點(diǎn) 6、8和10都是為這些虛屬性構(gòu)造的。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3333）課程名稱良定義的屬性文法。 很顯然，一條求值規(guī)則只有在其各變?cè)稻亚蟮玫那闆r下很顯然，一條求值規(guī)則只有在其各變?cè)稻亚蟮玫那闆r下才可以使用。但有時(shí)候可能會(huì)出現(xiàn)一個(gè)屬性對(duì)另一個(gè)屬性的才可以使用。但有時(shí)候可能會(huì)出現(xiàn)

33、一個(gè)屬性對(duì)另一個(gè)屬性的循環(huán)依賴關(guān)系。從事貿(mào)易如，循環(huán)依賴關(guān)系。從事貿(mào)易如，p p、c c1 1、c c2 2都是屬性，若有下求都是屬性，若有下求值規(guī)則：值規(guī)則：p: = fp: = f1 1(c(c1 1) )、c c1 1: = f: = f2 2(c(c2 2) )、c c2 2: = f: = f3 3(p)(p)時(shí)，就無(wú)時(shí)，就無(wú)法對(duì)法對(duì)p p求值。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)求值。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的。為了設(shè)計(jì)編譯程序，我們只系，那么稱該文法為良定義的。為了設(shè)計(jì)編譯程序，我們只處理良定義的屬性文法。處理良定義的屬性文法。 第七章

34、第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3434）課程名稱屬性的計(jì)算順序?qū)傩缘挠?jì)算順序一個(gè)有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點(diǎn)的任何順序一個(gè)有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點(diǎn)的任何順序m m1 1, m, m2 2, , , m, mk k，使得，使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。也就是說(shuō)，如果邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。也就是說(shuō)，如果m mi immj j是是m mi i到到m mj j的一條邊，那么在序列中的一條邊，那么在序列中m mi i必須出現(xiàn)在必須出現(xiàn)在m mj j之前。之前。 一個(gè)依賴圖的任何拓?fù)渑判蚨冀o出一個(gè)分析樹(shù)中結(jié)點(diǎn)的語(yǔ)一個(gè)依賴圖的任何

35、拓?fù)渑判蚨冀o出一個(gè)分析樹(shù)中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序。義規(guī)則計(jì)算的有效順序。這就是說(shuō)，在拓?fù)渑判蛑?，在一這就是說(shuō)，在拓?fù)渑判蛑?，在一個(gè)結(jié)點(diǎn)，語(yǔ)義規(guī)則個(gè)結(jié)點(diǎn)，語(yǔ)義規(guī)則b:=f(cb:=f(c1 1,c,c2 2, ,c ck k) )中的屬性中的屬性c c1 1,c,c2 2, ,c ck k在計(jì)算在計(jì)算b b以前都是可用的。以前都是可用的。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3535）課程名稱屬性文法屬性文法說(shuō)明的翻譯是很精確的。最基本的文法用于建立輸入符號(hào)串的分析樹(shù)。依賴說(shuō)明的翻譯是很精確的。最基本的文法用于建立輸入符號(hào)串的分析樹(shù)。依賴圖如上面討論的那樣建

36、立。從依賴圖的拓?fù)渑判蛑校覀兛梢缘玫接?jì)算語(yǔ)義規(guī)則的圖如上面討論的那樣建立。從依賴圖的拓?fù)渑判蛑校覀兛梢缘玫接?jì)算語(yǔ)義規(guī)則的順序。用這個(gè)順序來(lái)計(jì)算語(yǔ)義規(guī)則就得到輸入符號(hào)串的翻譯。順序。用這個(gè)順序來(lái)計(jì)算語(yǔ)義規(guī)則就得到輸入符號(hào)串的翻譯。例例7.2Real id1,id2,id37.2Real id1,id2,id3分析樹(shù)的依賴圖分析樹(shù)的依賴圖每一條邊都是從序號(hào)較低的結(jié)點(diǎn)指向序號(hào)較高的結(jié)點(diǎn)。歷此，依賴圖的一個(gè)拓?fù)渑判蛎恳粭l邊都是從序號(hào)較低的結(jié)點(diǎn)指向序號(hào)較高的結(jié)點(diǎn)。歷此，依賴圖的一個(gè)拓?fù)渑判蚩梢詮牡托蛱?hào)到高序號(hào)順序?qū)懗?。從這個(gè)拓?fù)渑判蛑形覀兛梢缘玫较铝谐绦?，用可以從低序?hào)到高序號(hào)順序?qū)懗觥倪@個(gè)拓?fù)渑?/p>

37、序中我們可以得到下列程序，用a an n來(lái)代表依賴圖中與序號(hào)來(lái)代表依賴圖中與序號(hào)n n的結(jié)點(diǎn)有關(guān)的屬性：的結(jié)點(diǎn)有關(guān)的屬性：a4: = reala5: = a4 addtype (id3, entry, a5); a7: = a5; addtype (id2,entry, a7)a9: = a7 addtype (id1,entry, a9)這些語(yǔ)義規(guī)則的計(jì)算將把這些語(yǔ)義規(guī)則的計(jì)算將把realreal類型填入到每個(gè)標(biāo)識(shí)符對(duì)應(yīng)的符號(hào)表項(xiàng)中。類型填入到每個(gè)標(biāo)識(shí)符對(duì)應(yīng)的符號(hào)表項(xiàng)中。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3636）課程名稱 屬性計(jì)算方法屬性計(jì)算方法樹(shù)遍歷的

38、屬性計(jì)算方法樹(shù)遍歷的屬性計(jì)算方法設(shè)語(yǔ)法樹(shù)已經(jīng)建立起了，并且樹(shù)中已帶有開(kāi)始符號(hào)的繼承屬性和終結(jié)符設(shè)語(yǔ)法樹(shù)已經(jīng)建立起了，并且樹(shù)中已帶有開(kāi)始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語(yǔ)法樹(shù)，直至計(jì)算出所有屬性。最常的綜合屬性。然后以某種次序遍歷語(yǔ)法樹(shù)，直至計(jì)算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。用多次遍歷（或稱遍）。 一遍掃描的處理方法一遍掃描的處理方法與樹(shù)遍歷的屬性計(jì)算文法不同，一遍掃描的處理方法是在語(yǔ)法分析的同時(shí)計(jì)與樹(shù)遍歷的屬性計(jì)算文法不同，一遍掃描的處理方法是

39、在語(yǔ)法分析的同時(shí)計(jì)算屬性值，而不是語(yǔ)法分析構(gòu)造語(yǔ)法樹(shù)之后進(jìn)行屬性的計(jì)算，而且無(wú)無(wú)算屬性值，而不是語(yǔ)法分析構(gòu)造語(yǔ)法樹(shù)之后進(jìn)行屬性的計(jì)算，而且無(wú)無(wú)需構(gòu)造實(shí)際的語(yǔ)法樹(shù)。需構(gòu)造實(shí)際的語(yǔ)法樹(shù)。因?yàn)橐槐閽呙璧奶幚矸椒ㄅc語(yǔ)法分析器的相互作用，它與下面兩個(gè)因素密切因?yàn)橐槐閽呙璧奶幚矸椒ㄅc語(yǔ)法分析器的相互作用，它與下面兩個(gè)因素密切相關(guān)：相關(guān)：（1 1）所采用的語(yǔ)法分析方法）所采用的語(yǔ)法分析方法（2 2）屬性的計(jì)算次序。）屬性的計(jì)算次序。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3737）課程名稱例：定義定點(diǎn)二進(jìn)制數(shù)的例：定義定點(diǎn)二進(jìn)制數(shù)的CFG:CFG:(1) NSS(2) SSB(

40、3) SB(4) B0(5) B1 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3838）課程名稱 非終結(jié)符非終結(jié)符N N表示整個(gè)二進(jìn)制數(shù)的數(shù)值，綜合屬表示整個(gè)二進(jìn)制數(shù)的數(shù)值，綜合屬性性v v附加在附加在N N上：上：N v N v 非終結(jié)符非終結(jié)符B B 表示一個(gè)二進(jìn)制數(shù)字，它有自己的表示一個(gè)二進(jìn)制數(shù)字，它有自己的值值v v ，但該值分配給，但該值分配給N N的值與它的位置有關(guān)，的值與它的位置有關(guān)，是與是與2 2成比例，比例因子成比例，比例因子f f是從是從S S繼承的屬性繼承的屬性, ,所所以：以：B v f B v f 非終結(jié)符非終結(jié)符S S 表示一個(gè)二進(jìn)制數(shù)字

41、串，它也有值，但該值與表示一個(gè)二進(jìn)制數(shù)字串，它也有值，但該值與串的位置有關(guān)，與串的位置有關(guān)，與f f有關(guān)與串的長(zhǎng)度有關(guān)與串的長(zhǎng)度l l有關(guān)有關(guān): S : S f v lf v l第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（3939）課程名稱構(gòu)造數(shù)值的屬性斷言可以如下構(gòu)造數(shù)值的屬性斷言可以如下: : N vS f1 v 1 l1 S f 2 v 2 l2 v=v1+v2; f 1 =1; f2=2-l2 S f v l S f1v1 l 1B f 2v2 f1=2f ; f 2=f; v=v 1+v2;l=l1+1 B f v l=1 B f v0 v=0 1 v=f第

42、七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4040）課程名稱 N v S i1 l1 “” S i2 l2 v= i1+ 2-l2 i2 S i l S i1 l 1 Bi2 i =2 i1+ i2; ;l=l1+1 B i l=1 B i “0” i =0 “1” i =1第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4141）課程名稱 在某些情況下可用一遍掃描實(shí)現(xiàn)屬性文法的語(yǔ)義規(guī)則計(jì)算。也就是說(shuō)在語(yǔ)法分析的同時(shí)完成語(yǔ)義規(guī)則的計(jì)算，無(wú)須明顯地構(gòu)造語(yǔ)法樹(shù)或構(gòu)造屬性之間的依賴圖。因?yàn)閱伪閷?shí)現(xiàn)對(duì)于編譯效率非常重要 具體的實(shí)現(xiàn)希望在單遍掃描中完成翻譯

43、具體的實(shí)現(xiàn)希望在單遍掃描中完成翻譯研究怎樣實(shí)現(xiàn)這種翻譯器。一個(gè)一般的屬性文法的翻譯器可能是很難建立的，然而有一大類屬性文法的翻譯器是很容易建立的 s-屬性屬性 適用于適用于自底向上的計(jì)算自底向上的計(jì)算 L-屬性屬性 適用于自頂向下的分析，也可用于適用于自頂向下的分析，也可用于自底向上。自底向上。 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4242）課程名稱S屬性文法的自下而上計(jì)算S屬性文法，它只含有綜合屬性。 綜合屬性可以在分析輸入符號(hào)串的同時(shí)自下而上的分析器來(lái)計(jì)算。分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊

44、符號(hào)的屬性值來(lái)計(jì)算。 S屬性文法的翻譯器通?？山柚贚R分析器實(shí)現(xiàn)。在S屬性文法的基礎(chǔ)上，LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4343）課程名稱產(chǎn)生式 語(yǔ)義規(guī)則） （.）1 . 1.） . .l）1* . 1. ）F . F.）（）（） . . ）ii .:.LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。 LR分析器增加語(yǔ)義棧增加語(yǔ)義棧 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4444）課程名稱 *的分析和計(jì)值過(guò)程步驟 動(dòng)作

45、狀態(tài)棧 語(yǔ)義棧(值棧) 符號(hào)棧 余留輸入串） 3*） 3 *） *） *） *） *） *） *） *） * ） * ） （）（） * #） （）（） ） （）（） ）接受）接受 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4545）課程名稱BOTTOMBOTTOMUPUP語(yǔ)義處理是作類型檢查，對(duì)二目運(yùn)算符的運(yùn)算對(duì)象語(yǔ)義處理是作類型檢查，對(duì)二目運(yùn)算符的運(yùn)算對(duì)象進(jìn)行類型匹配審查。進(jìn)行類型匹配審查。(LR(LR分分析）：增加語(yǔ)義棧析）：增加語(yǔ)義棧 歸約歸約時(shí)進(jìn)行語(yǔ)義動(dòng)作時(shí)進(jìn)行語(yǔ)義動(dòng)作. .例7.7GE: (1) E T+TT+T(2) E (2) E T or TT or

46、 T(3) T (3) T n n(4) T (4) T b b 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4646）課程名稱E ET T1 1 + T+ T2 2 if T if T1 1. .type = type = intint and T and T2 2. .type= type= intint then E then E. .type :=type :=intint else error else error E E T T1 1 or Tor T2 2 if T if T1 1. .type = type = boolbool and T and T

47、2 2. .type= type= boolbool then E then E. .type :=type :=boolbool else error else error T T n T.type := int n T.type := int T T b T.type := bool b T.type := bool 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4747）課程名稱w =n + n# 4ninto#-2Tinto#-5+-2Tinto#-4nint5+-2Tinto#-6Tint5+-2Tinto#-1Eint0#- GE:的 LR(0)分分析析表表

48、 action GOTO 狀狀態(tài)態(tài)+ o n b # E T 0 S4 S3 1 2 1 acc 2 s5 s7 3 r4 r4 r4 r4 r4 4 r3 r3 r3 r3 r3 5 s4 s3 6 6 r1 r1 r1 r1 r1 7 s4 s3 8 8 r2 r2 r2 r2 r2 GE: (1) E T+TT+T(2) E (2) E T or TT or T(3) T (3) T n n(4) T (4) T b b第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4848）課程名稱w =n +b4ninto#-2Tinto#-5+-2Tinto#-3bbool5

49、+-2Tinto#-6Tbool5+-2Tinto#-1Eerroro#-第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（4949）課程名稱L L屬性文法和自頂向下翻譯屬性文法和自頂向下翻譯一個(gè)屬性文法稱為一個(gè)屬性文法稱為L(zhǎng) L屬性文法，如果對(duì)于每個(gè)產(chǎn)生式屬性文法，如果對(duì)于每個(gè)產(chǎn)生式AXAX1 1X X2 2X Xn n，其每個(gè)語(yǔ)義規(guī)，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是則中的每個(gè)屬性或者是綜合屬性，或者是X Xj j（1jn1jn）的一個(gè)繼承屬性且這）的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于：個(gè)繼承屬性僅依賴于：（1 1）產(chǎn)生式）產(chǎn)生式X Xj j在左邊符號(hào)在左

50、邊符號(hào)X X1 1，X X2 2，X Xj-1j-1的屬性；的屬性；（2 2）A A的繼承屬性。的繼承屬性。S S屬性文法一定是屬性文法一定是L L屬性文法，因?yàn)椋▽傩晕姆?，因?yàn)椋? 1）、（）、（2 2）限制只用于繼承屬性。）限制只用于繼承屬性。L L屬性文法允許一次遍歷就計(jì)算出所有屬性值。屬性文法允許一次遍歷就計(jì)算出所有屬性值。LLLL（1 1）這種自上而下分析文法的分析過(guò)程，從概念上說(shuō)可以看成是深度優(yōu)先建立）這種自上而下分析文法的分析過(guò)程，從概念上說(shuō)可以看成是深度優(yōu)先建立語(yǔ)法樹(shù)的過(guò)程，因此，我們可以在自上而下語(yǔ)法分析的同時(shí)實(shí)現(xiàn)語(yǔ)法樹(shù)的過(guò)程，因此，我們可以在自上而下語(yǔ)法分析的同時(shí)實(shí)現(xiàn)L L

51、屬性文法的屬性文法的計(jì)算。計(jì)算。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5050）課程名稱例（中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式）例（中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式）ETRETRRaddop T print(addopRaddop T print(addop. Lexeme) R. Lexeme) R1 1|Tnum print(num.valTnum print(num.val) 翻譯模式（翻譯模式（Translation schemesTranslation schemes）適合語(yǔ)法制導(dǎo)翻譯的另一種描述形）適合語(yǔ)法制導(dǎo)翻譯的另一種描述形式。翻譯模式給出了使用語(yǔ)

52、義規(guī)則進(jìn)行計(jì)算的次序，可把某些實(shí)現(xiàn)細(xì)節(jié)式。翻譯模式給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序，可把某些實(shí)現(xiàn)細(xì)節(jié)表示出來(lái)。在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則（這里我表示出來(lái)。在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則（這里我們也稱語(yǔ)義動(dòng)作），用花括號(hào)括起來(lái)，插入到產(chǎn)生式右部的合適位們也稱語(yǔ)義動(dòng)作），用花括號(hào)括起來(lái)，插入到產(chǎn)生式右部的合適位置上置上。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5151）課程名稱輸入串95 + 2的語(yǔ)法樹(shù)，每個(gè)語(yǔ)義動(dòng)作都作為相應(yīng)產(chǎn)生式左部符號(hào)的結(jié)點(diǎn)的兒子，按深度優(yōu)先次序執(zhí)行圖中的動(dòng)作后，打印輸出952+。 ET R9 print(9) -

53、 T print(-) R 5 print(5) + T print(+) R 2 print(2) 第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5252）課程名稱L L屬性文法在自頂向下分析中的實(shí)現(xiàn)屬性文法在自頂向下分析中的實(shí)現(xiàn) 帶左遞歸的文法的翻譯模式EE1 + T E.val: = E1.val + T.valEE1T E.val: = E1.valT.valET E.val: = T.valT(E) T.val: = E.valTnum T.val: = num.val第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5353）課程名稱消除

54、左遞歸的同時(shí)考慮屬性，構(gòu)造新的消除左遞歸的同時(shí)考慮屬性，構(gòu)造新的翻譯模式翻譯模式 ETR.i: =T.val R E.val: = R.sR + T R1.i:=R.i + T.val R1 R.s: = R1.sR- T R1.i: = R.i -T.val R1 R.s: = R1.sRR.s: = R.iT(E) T.val: =E.valTnum T.val: = num.val第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5454）課程名稱計(jì)算表達(dá)式計(jì)算表達(dá)式9-5+29-5+2.ER.i=9T.val=5T.val=9R.i=4 R.i=6T.val=2nu

55、m.val=9num.val=5num.val=2_+第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5555）課程名稱在上頁(yè)的翻譯模式中，每個(gè)數(shù)都是由在上頁(yè)的翻譯模式中，每個(gè)數(shù)都是由T T產(chǎn)生的，并且產(chǎn)生的，并且T.valT.val的值就是的值就是由屬性由屬性num.valnum.val給出的數(shù)的詞法值。子表達(dá)式給出的數(shù)的詞法值。子表達(dá)式9 95 5中的數(shù)字中的數(shù)字9 9是由是由最左邊的最左邊的T T生成的，但是減號(hào)和生成的，但是減號(hào)和5 5是由根的右子結(jié)點(diǎn)是由根的右子結(jié)點(diǎn)R R生成的。繼生成的。繼承屬性承屬性R.iR.i從從T.valT.val得到值得到值9 9。計(jì)算

56、。計(jì)算9 95 5并把結(jié)果并把結(jié)果4 4傳遞到中間的傳遞到中間的R R結(jié)點(diǎn)這是通過(guò)產(chǎn)生式中嵌入的下面動(dòng)作實(shí)現(xiàn)：結(jié)點(diǎn)這是通過(guò)產(chǎn)生式中嵌入的下面動(dòng)作實(shí)現(xiàn)：RR1 1.i: = R.i.i: = R.iT.valT.val 類似的動(dòng)作把類似的動(dòng)作把2 2加到加到9 95 5的值上，在最下面的的值上，在最下面的R R結(jié)點(diǎn)處產(chǎn)生結(jié)果結(jié)點(diǎn)處產(chǎn)生結(jié)果R.iR.i6 6。這個(gè)結(jié)將成為根結(jié)點(diǎn)處。這個(gè)結(jié)將成為根結(jié)點(diǎn)處E.valE.val的值的值,R,R的的綜合屬性綜合屬性s s在圖中沒(méi)有在圖中沒(méi)有表示出來(lái)，它用來(lái)向上復(fù)制這一結(jié)果一直到樹(shù)根。表示出來(lái)，它用來(lái)向上復(fù)制這一結(jié)果一直到樹(shù)根。 第七章第七章 語(yǔ)法制導(dǎo)翻譯和

57、中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5656）課程名稱 對(duì)于自頂向下分析，我們假設(shè)動(dòng)作是在處于相同位置對(duì)于自頂向下分析，我們假設(shè)動(dòng)作是在處于相同位置上的符號(hào)被展開(kāi)（匹配成功）時(shí)執(zhí)行的。如圖中的第上的符號(hào)被展開(kāi)（匹配成功）時(shí)執(zhí)行的。如圖中的第二個(gè)產(chǎn)生式中，第一個(gè)動(dòng)作（對(duì)二個(gè)產(chǎn)生式中，第一個(gè)動(dòng)作（對(duì)R R1 1.i.i賦值）是在賦值）是在T T被完被完全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的，第二個(gè)動(dòng)作是在全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的，第二個(gè)動(dòng)作是在R R1 1被完被完全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的。正如前面我們所討論的，全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的。正如前面我們所討論的，一個(gè)符號(hào)的繼承屬性必須由出現(xiàn)在這個(gè)符號(hào)之前的動(dòng)一

58、個(gè)符號(hào)的繼承屬性必須由出現(xiàn)在這個(gè)符號(hào)之前的動(dòng)作來(lái)計(jì)算，產(chǎn)生式左邊非終結(jié)符的綜合屬性必須在它作來(lái)計(jì)算，產(chǎn)生式左邊非終結(jié)符的綜合屬性必須在它所依賴的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。所依賴的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5757）課程名稱轉(zhuǎn)換左遞歸翻譯模式的方法推廣到一般轉(zhuǎn)換左遞歸翻譯模式的方法推廣到一般 假設(shè)翻譯模式假設(shè)翻譯模式1 1：AAAA1 1Y Y A.a: = g(AA.a: = g(A1 1。a, Y.y)a, Y.y)AXAX A.a: = f(X.x) A.a: = f(X.x)每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用

59、相每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用相應(yīng)的小寫(xiě)字母表示，應(yīng)的小寫(xiě)字母表示，g g和和f f是任意函數(shù)是任意函數(shù) 消除左遞歸，文法轉(zhuǎn)換成：消除左遞歸，文法轉(zhuǎn)換成：AXR RYRAXR RYR再考慮語(yǔ)義動(dòng)作，翻譯模式變?yōu)樵倏紤]語(yǔ)義動(dòng)作，翻譯模式變?yōu)? 2AXAXR.i: = f(X.x)R.i: = f(X.x) R R A.a: =R.sA.a: =R.sRYRYRR1 1.i: = g(R.i,Y.y).i: = g(R.i,Y.y) R R1 1R.s: = RR.s: = R1 1.s.sRRR.s: = R.iR.s: = R.i第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間

60、代碼生成（5858）課程名稱 翻譯模式翻譯模式1 1和翻譯模式和翻譯模式2 2的結(jié)果是一樣的?？梢越o的結(jié)果是一樣的?？梢越o出串出串XYXY1 1Y Y2 2兩棵帶注釋的語(yǔ)法樹(shù)看出來(lái)，一棵是根據(jù)兩棵帶注釋的語(yǔ)法樹(shù)看出來(lái)，一棵是根據(jù)翻譯模式翻譯模式1 1自下而上計(jì)算屬性的。一棵是根據(jù)翻譯自下而上計(jì)算屬性的。一棵是根據(jù)翻譯模式模式2 2自上而下計(jì)算的。自上而下計(jì)算的。第七章第七章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成（語(yǔ)法制導(dǎo)翻譯和中間代碼生成（5959）課程名稱 AA1YA.a: = g(A1。a, Y.y)AX A.a: = f(X.x)A.a=g(g(f(X.x,Y1.y),Y2.y)A.a=g(f(X