1、第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成8.1 語(yǔ)義分析概述8.2 屬性文法8.3 S-屬性文法的自下而上翻譯8.4 L-屬性文法的自上而下翻譯8.5 中間代碼的形式8.6 簡(jiǎn)單賦值語(yǔ)句的翻譯8.7 控制結(jié)構(gòu)的翻譯本章內(nèi)容 11 語(yǔ)義分析的作用詞法分析和語(yǔ)法分析只檢查了源程序的拼寫(xiě)、結(jié)構(gòu)是否正確，但是對(duì)程序內(nèi)部的邏輯含義并未考慮。 要判斷語(yǔ)義是否正確，必須依靠語(yǔ)義分析。 8.1 語(yǔ)義分析概述21 語(yǔ)義分析的作用在第5章和第7章，我們介紹了自頂向下和自底向上的語(yǔ)法分析方法。程序設(shè)計(jì)語(yǔ)言的大多數(shù)語(yǔ)法現(xiàn)象屬于上下文無(wú)關(guān)文法（CFG），已經(jīng)有了很成熟的形式化描述方法和語(yǔ)法分析器的自動(dòng)生成工具。重點(diǎn)討論了LL

2、和LR語(yǔ)法分析方法。 LL和LR文法均是非歧義文法，且是上下文無(wú)關(guān)的。意味著要對(duì)編程語(yǔ)言進(jìn)行確定的自頂向下或自底向上語(yǔ)法分析，必須保證編程語(yǔ)言是嚴(yán)格的上下文無(wú)關(guān)語(yǔ)言（CFL） 。8.1 語(yǔ)義分析概述3 隨著語(yǔ)言形式定義技術(shù)的發(fā)展，人們證實(shí)，任何一種編程語(yǔ)言都不可能完全用CFG生成。編程語(yǔ)言中更重要的一面，是附著于語(yǔ)言結(jié)構(gòu)上的語(yǔ)義（上下文相關(guān)特性）。語(yǔ)義揭示了程序本身的涵義。一個(gè)語(yǔ)法上正確的句子，語(yǔ)義不一定正確。 應(yīng)用最廣的語(yǔ)義分析方法是語(yǔ)法制導(dǎo)翻譯。其基本思想是： 將語(yǔ)言結(jié)構(gòu)的語(yǔ)義以屬性的形式賦予代表此結(jié)構(gòu)的文法符號(hào)。在語(yǔ)法分析推導(dǎo)或歸約的每一步，通過(guò)語(yǔ)義規(guī)則完成對(duì)屬性的計(jì)算，以實(shí)現(xiàn)語(yǔ)義處理。

3、8.1 語(yǔ)義分析概述4 編程語(yǔ)言的語(yǔ)法和語(yǔ)義之間并沒(méi)有明確界限，語(yǔ)義可完成CFG無(wú)法描述的特性。如：標(biāo)識(shí)符先聲明后引用的語(yǔ)法規(guī)定，可用簡(jiǎn)單的抽象語(yǔ)言來(lái)說(shuō)明：L=WcW|W（a|b）*，第一個(gè)W是標(biāo)識(shí)符的聲明，第二個(gè)W代表它的引用。這不是一個(gè)上下文無(wú)關(guān)語(yǔ)言，無(wú)法用前面章節(jié)介紹的語(yǔ)法分析方法來(lái)處理。 再如：L=anbmcndm|n0，m0，它是檢查過(guò)程聲明的形參個(gè)數(shù)和過(guò)程引用的實(shí)參個(gè)數(shù)應(yīng)該一致的問(wèn)題的抽象。an 和bm代表兩個(gè)過(guò)程聲明的形參表中分別有n和m個(gè)參數(shù)；cn 和dm代表兩個(gè)過(guò)程調(diào)用的實(shí)參表。實(shí)參和形參個(gè)數(shù)的一致性檢查也是放在語(yǔ)義分析階段完成。8.1 語(yǔ)義分析概述56第8章 語(yǔ)法制導(dǎo)翻譯和

4、中間代碼生成1.語(yǔ)義審查（靜態(tài)語(yǔ)義）語(yǔ)義檢查 主要進(jìn)行一致性檢查和越界檢查。包括： 上下文相關(guān)性 類(lèi)型匹配 類(lèi)型轉(zhuǎn)換 例：Program P(); Var rate: real; procedure initial; position := initial+rate*60 /*error*/ /*error*/ /*warning*/2.如果靜態(tài)語(yǔ)義正確，執(zhí)行真正的翻譯（翻譯成中間代碼或直接生成實(shí)際目標(biāo)代碼）語(yǔ)義處理對(duì)說(shuō)明語(yǔ)句，將其中定義的名字及其屬性記錄在符號(hào)表中，以便進(jìn)行存儲(chǔ)分配；對(duì)執(zhí)行語(yǔ)句，生成語(yǔ)義上等價(jià)的中間代碼 。2 語(yǔ)義分析任務(wù)7第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成在語(yǔ)法分析中，根據(jù)

5、每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序（語(yǔ)義規(guī)則描述的動(dòng)作）進(jìn)行翻譯的方法稱(chēng)為語(yǔ)法制導(dǎo)翻譯（syntax-directed translation）。在描述語(yǔ)義動(dòng)作時(shí)，需要賦予每個(gè)文法符號(hào)X(非終極符和終極符)以各種不同的“值”，統(tǒng)稱(chēng)為屬性值。屬性可以是類(lèi)型、地址、值、符號(hào)表內(nèi)容等，用記號(hào)X.type, X.val等表示這些值。語(yǔ)法制導(dǎo)翻譯是目前大多數(shù)編譯程序普遍采用的一種技術(shù)，本書(shū)就是采用這種方法，來(lái)完成語(yǔ)義分析。并采用屬性文法描述編程語(yǔ)言的語(yǔ)義。3 語(yǔ)法制導(dǎo)定義8第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成語(yǔ)法制導(dǎo)定義是對(duì)上下文無(wú)關(guān)文法的推廣，其中每個(gè)文法符號(hào)都有一個(gè)相關(guān)的屬性集。如果把分析樹(shù)中的一個(gè)結(jié)點(diǎn)（對(duì)

6、應(yīng)某文法符號(hào)）看成一條記錄，那么一個(gè)屬性就相當(dāng)于記錄中一個(gè)域的名字。屬性間的約束用相應(yīng)產(chǎn)生式的語(yǔ)義規(guī)則來(lái)描述。屬性分為兩類(lèi): 1 綜合屬性 2 繼承屬性3 語(yǔ)法制導(dǎo)定義9第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成一個(gè)結(jié)點(diǎn)的綜合屬性值是從其子結(jié)點(diǎn)的綜合屬性值計(jì)算得來(lái)的，綜合屬性用于自下而上傳遞信息；而繼承屬性則是由語(yǔ)法樹(shù)中該結(jié)點(diǎn)的父結(jié)點(diǎn)和位于其左邊的兄弟結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的，繼承屬性用于自上而下傳遞信息。（1）非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開(kāi)始符號(hào)沒(méi)有繼承屬性。（2）終結(jié)符只有綜合屬性，它們由詞法分析程序提供。我們將每個(gè)結(jié)點(diǎn)都帶有屬性值的語(yǔ)法分析樹(shù)稱(chēng)為注釋分析樹(shù)。計(jì)算結(jié)點(diǎn)屬性值的相關(guān)活動(dòng)

7、稱(chēng)為注釋或裝飾語(yǔ)法樹(shù)。3 語(yǔ)法制導(dǎo)定義10第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成定義1 語(yǔ)法制導(dǎo)定義 在一個(gè)語(yǔ)法制導(dǎo)定義中，AP,都有與之相關(guān)聯(lián)的一套語(yǔ)義規(guī)則，每條規(guī)則的形式為b：= f（c1，c2，ck）。 f是一個(gè)函數(shù)，而且滿足下面兩種情況之一： 1b是A的一個(gè)綜合屬性并且c1，c2，ck是產(chǎn)生式右邊中的文法符號(hào)的屬性； 2b是產(chǎn)生式右部中的某個(gè)符號(hào)的一個(gè)繼承屬性，并且c1，c2，ck是A或中的任何文法符號(hào)的屬性。 在兩種情況下，都稱(chēng)屬性b依賴(lài)于屬性c1，c2，ck。3 語(yǔ)法制導(dǎo)定義11例1 表達(dá)式求值的語(yǔ)法制導(dǎo)定義產(chǎn)生式語(yǔ)義規(guī)則(0) LEPrint(E.val)(1)EE+TE.val:=

8、E.val+T.val(2)ETE.val:=T.val(3)TT*FT.val:=T.val * F.val(4)TFT.val:=F.val(5)F(E)F.val:=E.val(6)FdigitF.val:=digit.lexval通常，語(yǔ)義子程序不是計(jì)值程序，而是某種中間代碼生成程序。所以隨語(yǔ)法分析的進(jìn)行，中間代碼也逐步生成。而在本例中，語(yǔ)義處理不是翻譯，而是計(jì)算表達(dá)式的值。第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成12設(shè)表達(dá)式為3*5+4，則語(yǔ)義動(dòng)作打印數(shù)值19假定語(yǔ)法分析是自下而上的，在用某一規(guī)則進(jìn)行歸約的同時(shí)執(zhí)行相應(yīng)的語(yǔ)義動(dòng)作。在分析完一個(gè)句子時(shí)，句子的“值”也就產(chǎn)生了 綜合屬性值在分析

9、輸入串的同時(shí)自下而上地計(jì)算。每當(dāng)進(jìn)行歸約時(shí)，新的屬性值用棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來(lái)計(jì)算。第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成13LE.val=19+E.val=15T.val=4T.val=15T.val=3*F.val=5F.val=4digit.lexval=4F.val=3digit.lexval=3digit.lexval=5注：假定有一個(gè)LR分析器，擴(kuò)充分析棧，使每個(gè)文法符號(hào)都有語(yǔ)義值。這樣，LR分析器不僅執(zhí)行語(yǔ)法分析任務(wù)，且在歸約同時(shí)完成上例屬性文法描述的語(yǔ)義動(dòng)作。 圖1 3*5+4的注釋分析樹(shù) 第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成14例2. 類(lèi)型定義的語(yǔ)法制導(dǎo)定義（L.i

10、n為繼承屬性）。產(chǎn)生式語(yǔ)義規(guī)則(1)DTLL.in:=T.type(2)TintT.type:=integer(3)TrealT.type:=real(4)LL1,idL1.in:=L.in(5)Lidaddtype(id.entry, L.in)Type繼承屬性：一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父節(jié)點(diǎn)和（或）兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成DTLL1intid1id2繼承屬性綜合,15第8章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成 在語(yǔ)法制導(dǎo)翻譯中，我們可以用一個(gè)或多個(gè)子程序（稱(chēng)為語(yǔ)義動(dòng)作）來(lái)完成產(chǎn)生式的語(yǔ)義分析，并把這些語(yǔ)義動(dòng)作插入到產(chǎn)生式中相應(yīng)位置，從而形成翻譯文法。當(dāng)

11、在語(yǔ)法分析過(guò)程中使用該產(chǎn)生式時(shí)，就可以在適當(dāng)?shù)臅r(shí)機(jī)調(diào)用這些動(dòng)作，完成所需要的翻譯； 進(jìn)一步，可根據(jù)產(chǎn)生式所包含的語(yǔ)義，分析文法中每個(gè)符號(hào)的語(yǔ)義，并將這些語(yǔ)義以屬性的形式附加到相應(yīng)的符號(hào)上；再根據(jù)產(chǎn)生式所包含的語(yǔ)義，給出符號(hào)間屬性的求值規(guī)則，從而形成所謂的屬性翻譯文法，即屬性文法。這樣，當(dāng)在語(yǔ)法分析中使用該產(chǎn)生式時(shí)，可根據(jù)屬性求值規(guī)則對(duì)相應(yīng)屬性進(jìn)行求值，從而完成翻譯。3 語(yǔ)法制導(dǎo)定義168.2.1 翻譯文法 (P17-26 選讀) 翻譯文法是上下文無(wú)關(guān)文法的推廣，是在描述語(yǔ)言文法規(guī)則的右部適當(dāng)位置加入語(yǔ)義動(dòng)作得到的。將中綴表達(dá)式翻譯成波蘭后綴表達(dá)式的翻譯器將如何進(jìn)行翻譯？假設(shè)輸入串是a+b*c，

12、則翻譯器的輸入輸出動(dòng)作是：aa+bb*cc*+ 在該序列中，用輸入符號(hào)本身直接表示讀操作，用代表動(dòng)作，在此例子中代表輸出操作。動(dòng)作符號(hào)a可以看成是子程序的名字8.2 屬性文法1 翻譯文法定義178.2.1 翻譯文法為了能對(duì)所有中綴表達(dá)式翻譯，就必須研究中綴表達(dá)式文法，考慮能否在適當(dāng)位置加入動(dòng)作符號(hào)，使得能夠產(chǎn)生含有能翻譯成波蘭后綴表達(dá)式的活動(dòng)序列。假設(shè)中綴算術(shù)表達(dá)式文法為： EE+T F(E) ET Fa TT*F Fb TF Fc通過(guò)該文法，能推出終極符號(hào)串序列。例如： a+b*c1 翻譯文法定義188.2.1 翻譯文法在上下文無(wú)關(guān)文法中嵌入翻譯動(dòng)作的文法就稱(chēng)為翻譯文法。 下面的翻譯文法能把

13、中綴表達(dá)式翻譯成后綴表達(dá)式 EE+T+ F(E) ET Faa TT*F* Fbb TF Fcc對(duì)于輸入符號(hào)序列 a+b*c, 通過(guò)翻譯文法，能得到活動(dòng)序列， aa+bb*cc*+ 執(zhí)行其中的動(dòng)作，得到另一個(gè)輸入串：abc*+198.2.1 翻譯文法有了翻譯文法，我們就可以根據(jù)輸入符號(hào)串用翻譯文法得到一個(gè)活動(dòng)序列。執(zhí)行其中的動(dòng)作符號(hào)串，就可獲得一個(gè)新的符號(hào)串。這個(gè)新符號(hào)串就是翻譯的結(jié)果。 例如:根據(jù)前面的算術(shù)表達(dá)式翻譯文法，對(duì)于輸入符號(hào)串a(chǎn)+b*c，我們推導(dǎo)出活動(dòng)序列：aa+bb*cc*+ 其中： a+b*c 為輸入序列 abc*+ 為動(dòng)作序列如果執(zhí)行該動(dòng)作序列中的動(dòng)作，則產(chǎn)生輸出序列abc*

14、+,這就是輸入序列a+b*c的翻譯結(jié)果。208.2.1 翻譯文法所謂語(yǔ)法制導(dǎo)翻譯，就是給定一輸入序列，根據(jù)翻譯文法獲得翻譯該符號(hào)串的活動(dòng)序列，從活動(dòng)序列中分離出動(dòng)作符號(hào)串，然后執(zhí)行該動(dòng)作符號(hào)串所規(guī)定的動(dòng)作，從而得到翻譯結(jié)果。 或者說(shuō)在語(yǔ)法分析的同時(shí)執(zhí)行翻譯，稱(chēng)為語(yǔ)法制導(dǎo)翻譯。 218.2.1 翻譯文法 翻譯文法的構(gòu)造方法可通過(guò)對(duì)輸入文法修改得到。對(duì)輸入文法的產(chǎn)生式，在其右部的適當(dāng)位置插入動(dòng)作符號(hào)就形成翻譯文法。因此，翻譯文法產(chǎn)生的動(dòng)作序列實(shí)際上是受輸入語(yǔ)言的文法控制的。按語(yǔ)法制導(dǎo)翻譯的方法來(lái)實(shí)現(xiàn)語(yǔ)言的翻譯，就要根據(jù)輸入語(yǔ)言的文法，分析各條產(chǎn)生式的語(yǔ)義，即分析他們要求計(jì)算機(jī)所完成的操作，分別編出

15、完成這些操作的子程序或程序段(稱(chēng)為語(yǔ)義子程序或語(yǔ)義動(dòng)作)，并把這些子程序或程序段的名字作為動(dòng)作符號(hào)插入到輸入文法各產(chǎn)生式右部的適當(dāng)位置上，從而實(shí)現(xiàn)翻譯文法。 如何構(gòu)造翻譯文法？222 翻譯文法的自頂向下語(yǔ)法制導(dǎo)翻譯 自頂向下的語(yǔ)法制導(dǎo)翻譯有遞歸下降翻譯和LL(1)翻譯。遞歸下降翻譯例如，算術(shù)表達(dá)式翻譯文法如下： (代表的動(dòng)作是輸出其后的 符號(hào)串) E-E+T+ E-T T-T*F* T-F F-(E) F-ii由于文法中存在左遞歸，所以要修改文法，去掉左遞歸，修改后文法為： E-T+T+ T-F*F* F-(E)|ii8.2.1 翻譯文法232 翻譯文法的自頂向下語(yǔ)法制導(dǎo)翻譯 E-T+T+ T

16、 讀入下一個(gè)符號(hào) T OUT(“+”) SYM=+ 出口 Y N 處理E的遞歸下降翻譯程序流程圖 E242 遞歸下降翻譯F T讀下一個(gè)符號(hào) F OUT(“*”) SYM=* 出口 Y N 處理T的遞歸下降翻譯程序流程圖 T-F*F*8.2.1 翻譯文法252 遞歸下降翻譯 F讀下一個(gè)符號(hào) 出口 Y N Y N OUT(i) ERRORERRORN 處理F的遞歸下降翻譯程序流程圖 F-(E)|iisym=(讀下一個(gè)符號(hào) sym=)sym=i讀下一個(gè)符號(hào) Y 8.2.1 翻譯文法26Knuth在1968年首次提出屬性文法的概念。屬性文法是在上下文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)（VT或VN）配備若

17、干屬性，屬性實(shí)質(zhì)上是對(duì)翻譯目標(biāo)和獲得的中間信息等的抽象。屬性文法組成： （1）上下文無(wú)關(guān)文法 （2）一系列語(yǔ)義規(guī)則（附在G的每個(gè)產(chǎn)生式上）在語(yǔ)義分析中，完成附在所用產(chǎn)生式上的語(yǔ)義規(guī)則所描述的動(dòng)作，實(shí)現(xiàn)語(yǔ)義處理。8.2.2 屬性文法27屬性文法(attribute grammar)是一個(gè)三元組:A=(G,V,F),其中 ： G: 是一個(gè)上下文無(wú)關(guān)文法； V: 有窮的屬性集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連，這些屬性代表與文法符號(hào)相關(guān)的信息。如符號(hào)的類(lèi)型、值等等。屬性加工的過(guò)程即語(yǔ)義處理的過(guò)程； F: 關(guān)于屬性的斷言或一組屬性的計(jì)算規(guī)則(稱(chēng)為語(yǔ)義規(guī)則)。斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián)，只引

18、用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相關(guān)的屬性。8.2.2 屬性文法28例1 表達(dá)式文法：ET+T|T or T Tn|b 有關(guān)類(lèi)型匹配的屬性文法如下： ET1+T2 T1.type=int T2.type=T1.type E.type:=int ET1 or T2 T1.type=bool T2.type=T1.type E.type:=bool Tn T.type:=int Tb T.type:=bool8.2.2 屬性文法29我們見(jiàn)到的文法的所有符號(hào)（非終結(jié)符號(hào)，終結(jié)符號(hào)，動(dòng)作符號(hào)）都沒(méi)有值的概念。而屬性文法中的符號(hào)可以有值，這個(gè)值就叫做該符號(hào)的屬性。 在詞法分析中，所有無(wú)符號(hào)整數(shù)這一

19、類(lèi)單詞符號(hào)都用NUM作為記號(hào)，而具體的數(shù)值實(shí)際是符號(hào)NUM的屬性。如對(duì)于表達(dá)式3+5，經(jīng)詞法分析輸出為NUM3 + NUM5 ，其中3和5就是屬性的表示，意味著第一個(gè)NUM符號(hào)的值是3，第二個(gè)NUM符號(hào)的值是5。符號(hào)不但可以有屬性，而且其屬性還有類(lèi)型。符號(hào)的屬性分綜合屬性和繼承屬性?xún)煞N。 8.2.2 屬性文法308.2.2 屬性文法能夠完成輸出表達(dá)式值的符號(hào)串翻譯文法如下： SEANSWER EE+T ET TT*F TF F(E) FNUM 文法中的動(dòng)作符號(hào)ANSWER的動(dòng)作是輸出表達(dá)式的計(jì)算結(jié)果?，F(xiàn)在的問(wèn)題是如何將表達(dá)式的值傳遞給動(dòng)作符號(hào)ANSWER呢？ 1. 綜合屬性31 SEANSWE

20、R EE+T ET TT*F TF F(E) FNUM 設(shè)對(duì)于表達(dá)式3+2*3，詞法分析后的結(jié)果如下： NUM3+ NUM2* NUM3 其中NUM代表無(wú)符號(hào)整數(shù)， “數(shù)字串”是該符號(hào)的屬性部分。 可見(jiàn)詞法分析將所有無(wú)符號(hào)整數(shù)用一個(gè)統(tǒng)一符號(hào)NUM表示，而具體的數(shù)值則在屬性中體現(xiàn)。8.2.2 屬性文法1. 綜合屬性321.綜合屬性SET+EANSWER F*TTFNUM3 FNUM2 NUM3 圖 NUM3+ NUM2* NUM3的分析樹(shù) 根據(jù)所給定的翻譯文法，可畫(huà)出該輸入符號(hào)串的分析樹(shù) 331. 綜合屬性NUM3 SE9 T6 +E3 ANSWER9 F3 *T2 T3 F3 F2 NUM2

21、NUM3 首先計(jì)算各子表達(dá)式的值，然后計(jì)算父表達(dá)式的值，直到求得整個(gè)表達(dá)式的值。語(yǔ)法樹(shù)中非終結(jié)符E、T、F的每次出現(xiàn)都表示該輸入表達(dá)式的一個(gè)子表達(dá)式，其值部分應(yīng)是其子表達(dá)式的計(jì)算結(jié)果。根據(jù)這個(gè)思想，若有產(chǎn)生式EE+T，則產(chǎn)生式左邊的E的值等于產(chǎn)生式右邊E的值加上T的值。從語(yǔ)法樹(shù)上看，F(xiàn)、T、E這些符號(hào)的屬性符合自底向上的求值法則，所以用表示。最后對(duì)文法的第1個(gè)產(chǎn)生式，提供這樣的規(guī)則，即ANSWER的值部分等于E的值，這不符合自底向上的求值法則，所以，我們引進(jìn)一個(gè)向下的箭頭表示動(dòng)作符號(hào)ANSWER的屬性值。341.綜合屬性為了形式地表示上述表達(dá)式的求值過(guò)程，必須改寫(xiě)每一個(gè)產(chǎn)生式，使得對(duì)出現(xiàn)在產(chǎn)生

22、式中的每個(gè)屬性值都給它一個(gè)不同的名字，并使用這些名字定義這個(gè)產(chǎn)生式中各符號(hào)的屬性之間的關(guān)系即屬性求值規(guī)則。右列為相應(yīng)產(chǎn)生式的屬性求值規(guī)則 。 屬性求值規(guī)則 SEqANSWERrr=q Ep Eq+ Trp=q+r Ep Tq p=q Tp Tq* Frp=q*r Tp Fqp=q Fp (Eq)p=q Fp NUMq p=q 351. 綜合屬性 SEqANSWERrr=q Ep Eq+ Trp=q+r Ep Tq p=q Tp Tq* Frp=q*r Tp Fqp=q Fp (Eq)p=q Fp NUMq p=q 產(chǎn)生式中出現(xiàn)的p、q、r稱(chēng)為屬性變量名，且規(guī)定屬性變量名都局部于每個(gè)產(chǎn)生式。在它

23、的語(yǔ)法樹(shù)中，每個(gè)非終結(jié)符的屬性值都是由它下面的那些符號(hào)來(lái)確定。對(duì)于處于語(yǔ)法樹(shù)葉結(jié)點(diǎn)的終結(jié)符號(hào)，其綜合屬性具有初始值。如NUM3，綜合屬性3由詞法分析給出。 這種可通過(guò)自底向上進(jìn)行求值的屬性，就稱(chēng)為綜合屬性，用“”來(lái)表示。361.綜合屬性 注意：這里的語(yǔ)義子程序不是中間代碼生成程序，而是直接對(duì)輸入表達(dá)式進(jìn)行求值。實(shí)際上，語(yǔ)法制導(dǎo)翻譯方法既可以用來(lái)生成各種中間代碼或直接產(chǎn)生目標(biāo)代碼，也可以直接對(duì)輸入符號(hào)串解釋執(zhí)行。 屬性文法 屬性求值規(guī)則 SEqANSWERrr=q Ep Eq+ Trp=q+r Ep Tq p=q Tp Tq* Frp=q*r Tp Fqp=q Fp (Eq)p=q Fp NUM

24、q p=q 37SEqANSWERr，r=q其中動(dòng)作符號(hào)ANSWER的屬性來(lái)源于左邊非終結(jié)符號(hào)E的屬性，我們用一個(gè)向下的箭頭表示該動(dòng)作符號(hào)的屬性值，這就是繼承屬性的一個(gè)例子。 8.2.2 屬性文法2. 繼承屬性382. 繼承屬性 考慮下列聲明語(yǔ)句文法 TYPE ID ; ，ID 其中TYPE代表類(lèi)型，其值可為INT或 REAL或BOOL。 假設(shè)詞法分析程序在輸出單詞符號(hào)時(shí)，對(duì)變量除返回一個(gè)單詞類(lèi)別ID外，同時(shí)返回變量名V ，即每個(gè)變量具有兩個(gè)屬性：（1）類(lèi)型 （2）值。 詞法分析程序處理INT V;后返回的單詞屬性字： （int) （ ） 392. 繼承屬性 語(yǔ)法分析程序在處理聲明語(yǔ)句INT

25、V;時(shí)，假定調(diào)用SET_TYPE過(guò)程。該過(guò)程根據(jù)TYPE的屬性確定變量的類(lèi)型，并將該類(lèi)型與詞法分析程序得到的變量名（）一同插入到符號(hào)表中。 翻譯文法如下： (1) TYPE ID SET_TYPE ; (2) ，IDSET_TYPE (3) 從文法上看，動(dòng)作符號(hào)SET_TYPE有兩個(gè)屬性: SET_TYPE變量名，類(lèi)型402. 繼承屬性 用屬性變量來(lái)表示符號(hào)的屬性，對(duì)第1個(gè)產(chǎn)生式，TYPE和ID的屬性值可由詞法分析程序的返回值得到。定義屬性文法如下：(1)TYPEt IDn SET_TYPEn1,t1 ； 屬性求值規(guī)則： t2=t，t1=t ，n1=n 比如采用遞歸下降法完成屬性

26、文法的翻譯。 (1)若該非終結(jié)符具有屬性，那么該非終結(jié)符的分析過(guò)程 就有形參，且形參的數(shù)目就是該非終結(jié)符的屬性個(gè)數(shù)。 (2)對(duì)于繼承屬性，采用值形參的傳參方式將繼承屬性值傳入被調(diào)過(guò)程。412. 繼承屬性 (2) ，IDSET_TYPE 對(duì)第二個(gè)產(chǎn)生式，除從詞法分析程序得到ID的名字屬性n以外，無(wú)法求得動(dòng)作符號(hào)SET_TYPE和右邊的表示類(lèi)型的屬性值。為了解決這一問(wèn)題，可令第2個(gè)產(chǎn)生式左邊的的屬性值等于第1個(gè)產(chǎn)生式右邊的屬性值。即：(2) ，IDn SET_TYPEn1,t1 屬性求值規(guī)則： t2=t，t1=t ，n1=n 422. 繼承屬性如果輸入符號(hào)串為 int a,b ；詞法分析后輸出為：

27、 TYPE int ID a , , ID b ; ; 語(yǔ)法分析要分析的輸入串是：TYPE ID ，ID ； 帶有屬性的輸入串是： TYPEint IDa , IDb ；432. 繼承屬性 我們把這種按自頂向下或自左向右的方式求得的屬性稱(chēng)為繼承屬性。對(duì)這種屬性在其前面冠以“”表示。 聲明語(yǔ)句 ；SET_TYPEa, int IDa TYPEint 變量表intSET_TYPEb, int IDb變量表int ， TYPEint IDa ,IDb ；的語(yǔ)法樹(shù)如下圖： 448.2.2 屬性文法 3.屬性文法的求值規(guī)則 當(dāng)翻譯文法的符號(hào)具有屬性，并帶有屬性求值規(guī)則時(shí)，就稱(chēng)為屬性文法。其屬性求值規(guī)則定

28、義如下： 文法的終結(jié)符、非終結(jié)符和動(dòng)作符號(hào)都可以有一個(gè)有窮的屬性集。 每個(gè)非終結(jié)符和動(dòng)作符號(hào)屬性類(lèi)型可分為綜合屬性和繼承屬性。 繼承屬性的求值規(guī)則： 對(duì)產(chǎn)生式左部的非終結(jié)符，其繼承屬性繼承前面產(chǎn)生式中該符號(hào)已有的繼承屬性值。（上例(2) ，IDnSET_TYPEn1,t1） 對(duì)產(chǎn)生式右部的符號(hào)，其繼承屬性由產(chǎn)生式中其它符號(hào)屬性 值進(jìn)行計(jì)算。45 綜合屬性的求值規(guī)則： 對(duì)終結(jié)符號(hào)其綜合屬性具有指定的初始值。在具體實(shí)現(xiàn)中，該初始值將由詞法分析程序提供。 產(chǎn)生式右部的非終結(jié)符號(hào)的綜合屬性值，取自后面以該非終結(jié)符號(hào)為產(chǎn)生式左部時(shí)求得的綜合屬性值。 產(chǎn)生式左部的非終結(jié)符號(hào)的綜合屬性值，由產(chǎn)生式中左部或右

29、部的某些符號(hào)的屬性值進(jìn)行計(jì)算。 給定一動(dòng)作符號(hào)，其綜合屬性值將用該動(dòng)作符號(hào)的其它屬性值進(jìn)行計(jì)算。 8.2.2 屬性文法46屬性文法舉例算術(shù)表達(dá)式的翻譯 假定一個(gè)屬性翻譯文法的輸出是四元式代碼。要求翻譯程序產(chǎn)生的四元式具有下面的性質(zhì) 每個(gè)雙目運(yùn)算都用一個(gè)四元式表示。一組四元式的排列順序與執(zhí)行時(shí)要完成的運(yùn)算順序相同。每個(gè)四元式有三個(gè)參數(shù)，自左向右的順序?yàn)樽蟛僮鲾?shù)，右操作數(shù)，運(yùn)算結(jié)果。 例如：（，a, b ,t ) 中間代碼形式： 逆波蘭、三元式、四元式（三地址碼）、抽象機(jī)代碼。8.2.2 屬性文法47例如翻譯器處理表達(dá)式a+b將生成如下的四元式 ( + , a , b , t1) 其中t1是臨時(shí)變

30、量，保存表達(dá)式的結(jié)果。 對(duì)于表達(dá)式：a+a*b經(jīng)詞法分析后應(yīng)為 IDa+IDa * IDb希望經(jīng)屬性翻譯文法能輸出： (* , a , b , t1 ) ( +, a , t1 , t2 ) 屬性文法舉例算術(shù)表達(dá)式的翻譯 8.2.2 屬性文法48四元式的另一種形式： 簡(jiǎn)單賦值語(yǔ)句的形式（右部只有一種運(yùn)算）。例如：x=a+b*c翻譯成：(1)t1=b*c (2) t2=a+t1 (3) x=t2屬性文法舉例算術(shù)表達(dá)式的翻譯 8.2.2 屬性文法49第步，構(gòu)造表達(dá)式的翻譯文法如下：EE+TADDETTT*FMULTTFF(E)FID ADD 代表產(chǎn)生加法運(yùn)算的四元式。MULT 代表產(chǎn)生乘法運(yùn)算的四

31、元式。屬性文法舉例算術(shù)表達(dá)式的翻譯 8.2.2 屬性文法50第2步，構(gòu)造屬性和求值規(guī)則，把翻譯文法構(gòu)造成屬性翻譯文法。1)令每個(gè)非終結(jié)符有一個(gè)綜合屬性，該屬性為一個(gè)臨時(shí)變量，保存由它產(chǎn)生的表達(dá)式的結(jié)果。2)輸入符號(hào)ID有一個(gè)綜合屬性，它是該符號(hào)的變量名。3)每個(gè)動(dòng)作符號(hào)有三個(gè)繼承屬性，它們分別指向左操作數(shù)、右操作數(shù)和運(yùn)算結(jié)果。屬性文法舉例算術(shù)表達(dá)式的翻譯 8.2.2 屬性文法EE+TADDET51屬性文法舉例算術(shù)表達(dá)式的翻譯E為文法的開(kāi)始符號(hào)，則實(shí)現(xiàn)這個(gè)方案的屬性文法如下：Ex -Eq +Tr ADDy,z,t ， y=q, z=r, t=NEWT，x=tEx -Tp x=pTx -Tq *F

32、r MULTy,z,t ，y=q, z=r, t=NEWT，x=tTx -Fp ， x=pFx -(Ep) ， x=pFx -IDp ， x=p其中，NEWT是一個(gè)函數(shù)，每次調(diào)用它時(shí)返回一個(gè)新的臨時(shí)變量名，臨時(shí)變量名按產(chǎn)生順序分別為t1、t2、等等。動(dòng)作符號(hào)ADDy,z,t 輸出（, y,z,t）動(dòng)作符號(hào)MULTy,z,t 輸出 (*, y,z,t)52為了說(shuō)明這些動(dòng)作符號(hào)與特定的語(yǔ)法樹(shù)有關(guān)的屬性，圖給出了對(duì)輸入符號(hào)串a(chǎn)+a*b翻譯的屬性語(yǔ)法樹(shù)。 圖 表達(dá)式a+a*b的屬性語(yǔ)法樹(shù) IDa Et2 Tt1 +Ea Fb *Ta Ta Fa Fa IDa IDb MULTa,b,t1 ADDa,t

33、1,t2 產(chǎn)生新變量t2 產(chǎn)生新變量t1 屬性文法舉例算術(shù)表達(dá)式的翻譯538.3 S-屬性文法的自底向上翻譯 針對(duì)任意一個(gè)語(yǔ)法制導(dǎo)定義的翻譯器可能很難實(shí)現(xiàn)，但是有一大類(lèi)的語(yǔ)法制導(dǎo)定義的翻譯器很容易建立。首先，我們考慮這樣一類(lèi)語(yǔ)法制導(dǎo)定義：S-屬性定義，它的文法符號(hào)僅含有綜合屬性。8.3.1 S-屬性文法綜合屬性可以在分析輸入串的同時(shí)由自下而上的語(yǔ)法分析器來(lái)計(jì)算，這種語(yǔ)法分析器可以將文法符號(hào)的綜合屬性值保存在棧中，每當(dāng)進(jìn)行歸約時(shí)，新的綜合屬性值就由棧中正在歸約的產(chǎn)生式右部符號(hào)的屬性值來(lái)計(jì)算，通過(guò)擴(kuò)充語(yǔ)法分析棧，我們能夠保存這些綜合屬性的值。 548.3 S-屬性文法的自底向上翻譯 8.3.1 S

34、-屬性文法 文法符號(hào)僅使用綜合屬性的語(yǔ)法制導(dǎo)定義,稱(chēng)為S-屬性定義。 S屬性定義的翻譯器可以借助LR語(yǔ)法分析器及生成器來(lái)實(shí)現(xiàn)。在自下而上的分析中，我們?cè)谠瓲顟B(tài)棧、文法符號(hào)棧的基礎(chǔ)上增加一個(gè)值棧（稱(chēng)屬性棧），用來(lái)存放綜合屬性值，它保存已經(jīng)分析過(guò)的子樹(shù)的信息。55考慮如下算術(shù)表達(dá)式的屬性文法定義： S- Ex Ex -Eq +Tr ADDq,r,x x=NEWV Ex -Tx Tx -Tq *Fr MULTq,r,x x=NEWV Tx -Fx Fx -(Ex) Fx -ix 該文法符合S-屬性文法的條件, 因此是S-屬性文法。8.3.2 S-屬性文法翻譯的實(shí)現(xiàn)自下而上翻譯 56給定一個(gè)S-屬性翻

35、譯文法，如何構(gòu)造翻譯器呢？首先，我們將S-屬性翻譯文法中的屬性和動(dòng)作符號(hào)去掉，形成輸入文法。為輸入文法構(gòu)造LR分析表。然后，確定文法中每個(gè)符號(hào)的棧符號(hào)，并擴(kuò)充該分析表的移進(jìn)和歸約動(dòng)作，即可完成S-屬性翻譯文法翻譯器的構(gòu)造。在S-屬性翻譯文法的翻譯器中，每個(gè)棧符號(hào)由名字部分和屬性域組成。棧中任何符號(hào)的域都是一些存貯單元，當(dāng)該符號(hào)在棧內(nèi)時(shí)，這些域用于保存該符號(hào)的屬性信息。為了實(shí)現(xiàn)自底向上的屬性文法的翻譯，還需要對(duì)相應(yīng)分析器的移進(jìn)和歸約動(dòng)作做適當(dāng)?shù)臄U(kuò)充。8.3.2 S-屬性文法翻譯的實(shí)現(xiàn)自下而上翻譯57擴(kuò)充方法如下 移進(jìn)動(dòng)作的擴(kuò)充方案：把當(dāng)前輸入符號(hào)的屬性放在移進(jìn)操作壓入的那個(gè)棧符號(hào)的相應(yīng)屬性域中。

36、歸約動(dòng)作的擴(kuò)充方案：當(dāng)選用產(chǎn)生式p進(jìn)行歸約操作時(shí)，此時(shí)頂部的棧符號(hào)串表示輸入文法的產(chǎn)生式p的右部，且這些域含有文法符號(hào)的屬性?，F(xiàn)在擴(kuò)充這個(gè)歸約操作，使用這些屬性來(lái)計(jì)算與該產(chǎn)生式有關(guān)的所有動(dòng)作符號(hào)以及左部非終結(jié)符號(hào)的所有屬性。使用這些動(dòng)作符號(hào)屬性來(lái)產(chǎn)生所需要的輸出或完成有關(guān)的動(dòng)作。使用左部非終結(jié)符屬性來(lái)填寫(xiě)表示左部非終結(jié)符的屬性域，同時(shí)歸約操作把這左部非終結(jié)符壓入棧中。8.3.2 S-屬性文法翻譯的實(shí)現(xiàn)自下而上翻譯588.3.2 S-屬性文法翻譯的實(shí)現(xiàn)步驟 狀態(tài)棧 符號(hào)棧 輸入符號(hào)串 ACTION GOTO 說(shuō)明 10#i3+i5#S5開(kāi)始時(shí),0入狀態(tài)棧,#入符號(hào)棧,輸入符號(hào)為i.查動(dòng)作表0行i

37、列為S5,5入狀態(tài)棧,i入符號(hào)棧。205#i3+i5#R63輸入符號(hào)為+,查動(dòng)作表5行*列為R6,用Fi 歸約,i 出符號(hào)棧、F入符號(hào)棧,F的屬性取i的屬性3,5出狀態(tài)棧、0為棧頂,查GOTO表0行F列得3,3入狀態(tài)棧。303#F3+i5#R42輸入符號(hào)為+,查動(dòng)作表3行*列為R4,用TF 歸約,F出符號(hào)棧、T入符號(hào)棧,T的屬性取F的屬性,3出狀態(tài)棧、0為棧頂,查GOTO表0行T列得2,2入狀態(tài)棧。402#T3 +i5# R2 1輸入符號(hào)為+,查動(dòng)作表2行+列為R2,用ET 歸約,T 出符號(hào)棧、E入符號(hào)棧,E的屬性取T的屬性3,2出狀態(tài)棧、0為棧頂,查GOTO表0行E列得1,1入狀態(tài)棧 598

38、.3.2 S-屬性文法的翻譯實(shí)現(xiàn)步驟 狀態(tài)棧 符號(hào)棧 輸入符號(hào)串 ACTION GOTO 說(shuō)明 501#E3 +i5#S6輸入符號(hào)為+,查動(dòng)作表1行+列為S6,6入狀態(tài)棧,+ 入符號(hào)棧, 輸入符號(hào)為i.6016#E3+i5#S5輸入符號(hào)為i,查動(dòng)作表6行i列為S5,5入狀態(tài)棧,i 入符號(hào)棧, 輸入符號(hào)為#.70165#E3+i5#R63輸入符號(hào)為#,查動(dòng)作表5行#列為R6,用Fi 歸約,i 出符號(hào)棧、F入符號(hào)棧,F的屬性取i的屬性5,5出狀態(tài)棧、6為棧頂,查GOTO表6行F列得3,3入狀態(tài)棧。80163#E3+F5#R49輸入符號(hào)為#,查動(dòng)作表3行#列為R4,用TF 歸約,F 出符號(hào)棧、T入符

39、號(hào)棧,T的屬性取F的屬性5,3出狀態(tài)棧、6為棧頂,查GOTO表6行T列得9,9入狀態(tài)棧90169#E3+T5#R11輸入符號(hào)為#,查動(dòng)作表9行#列為R1,用EE+T 歸約,E+T出符號(hào)棧、E入符號(hào)棧,執(zhí)行ADD,用NEWV生成新變量t1,輸出ADD,3,5,t1 ,E的屬性為t1,169出狀態(tài)棧、0為棧頂,查GOTO表0行E列得1,1入狀態(tài)棧,1001#Et1#acc輸入符號(hào)為#,查動(dòng)作表1行#列為A,接受608.4 L-屬性文法的自頂向下翻譯 屬性文法由翻譯文法和有關(guān)的屬性計(jì)算規(guī)則組成。如果屬性計(jì)算規(guī)則給的不當(dāng)，就不能保證所有的屬性計(jì)算出來(lái)。 那么如何才能保證所有屬性都能計(jì)算出來(lái)呢？對(duì)于不同

40、的分析方法有不同的要求，下面我們介紹對(duì)于自頂向下的分析方法，如何保證所有屬性能計(jì)算出來(lái)，這就是L-屬性文法 。TYPEt IDn SET_TYPEn1,t1 ； 屬性求值規(guī)則： t2=t，t1=t ，n1=n618.4 L-屬性文法的自頂向下翻譯 L-屬性的作用是保證可以按照自頂向下的有序方式來(lái)計(jì)算屬性值，即按照自頂向下的有序方式對(duì)某個(gè)屬性求值時(shí)，所需要的基本值已知。 L-屬性文法定義：一個(gè)語(yǔ)法制導(dǎo)定義是L-屬性定義，如果對(duì)于屬性文法AG中的任一產(chǎn)生式 A-X1X2Xi. Xn ，其每個(gè)語(yǔ)義規(guī)則中的每一個(gè)屬性都是一個(gè)綜合屬性，或是Xi（1in） 的一個(gè)繼承屬性，這一繼承屬性只依賴(lài)于A的繼承屬性

41、和Xi的左邊符號(hào)X1，X2，Xi-1的屬性。8.4.1 L-屬性文法 628.4.1 L-屬性文法 L-屬性文法滿足如下的條件：（1）Xi 的繼承屬性只依賴(lài)于A的繼承屬性和Xi 的左邊符號(hào)X1X2Xi-1的屬性。（2）A的綜合屬性只依賴(lài)于A的繼承屬性和產(chǎn)生式右部符號(hào)的屬性。 條件1的重要性在于：使符號(hào)的繼承屬性只依賴(lài)于該符號(hào)左邊的信息(“L-屬性”中的“L”表示左邊的意思)。這有利于自頂向下地對(duì)屬性求值。因?yàn)槊總€(gè)符號(hào)都是在它右邊的輸入符號(hào)讀入之前進(jìn)行處理。 而條件2保證在求值過(guò)程中避免出現(xiàn)循環(huán)依賴(lài)性。 綜合上述，L屬性文法保證了當(dāng)我們按自頂向下的方式進(jìn)行翻譯時(shí)，所有屬性值都能夠被計(jì)算。8.4

42、L-屬性文法的自頂向下翻譯 638.4.2* L-屬性文法翻譯的實(shí)現(xiàn)遞歸下降翻譯 可采用遞歸下降法，完成L-屬性文法的翻譯。步驟如下： (1)若該非終結(jié)符具有屬性，那么該非終結(jié)符的分析過(guò)程就有形參，且形參的數(shù)目就是該非終結(jié)符的屬性個(gè)數(shù)。 (2)對(duì)于繼承屬性，采用值形參的傳參方式將繼承屬性值傳入被調(diào)過(guò)程。 (3)對(duì)于綜合屬性，采用變量形參的傳參方式以便將值回傳給主調(diào)過(guò)程。 如果用C語(yǔ)言實(shí)現(xiàn)屬性文法的翻譯，可用指針變量代表綜合屬性的形參。 8.4 L-屬性文法的自頂向下翻譯 64 為了進(jìn)行屬性翻譯的程序設(shè)計(jì)，我們采用下述約定： 1) 可以把屬性產(chǎn)生式中的屬性名字用作變量和參數(shù)的名字。這樣可以將屬性

43、的命名和遞歸下降過(guò)程的實(shí)現(xiàn)聯(lián)系起來(lái)。 2) 除屬性翻譯使用的常用記法約定以外，還必須加上一些屬性命名約定。這些約定是：所有出現(xiàn)在左部的同名非終結(jié)符，應(yīng)具有相同的屬性名表。在左部同名非終結(jié)符屬性名表的同一化過(guò)程中，屬性名稱(chēng)的改動(dòng)范圍僅局限于產(chǎn)生式左部。為了保證一致性，左部屬性重新命名以后，可使用新的記法約定來(lái)簡(jiǎn)化或刪去某些屬性求值規(guī)則。 3) 如果兩個(gè)屬性有相同的值，那么可給它們相同的名字，但對(duì)于左部符號(hào)的屬性值相等時(shí)，不能改變成相同的名字。 8.4 L-屬性文法的自頂向下翻譯 8.4.2* L-屬性文法翻譯的實(shí)現(xiàn)遞歸下降翻譯 65例如，產(chǎn)生式 Lab-e i Rj ， i, j=b, a=i+

44、2 L xy-H zw ， w=y,z=2,x=z+y 按約定第2條，必須改成 L ab-e iRj ， i,j=b, a=i+2 L ab -H zw ， w=b,z=2,a=z+b注意當(dāng)x、y改成a，b后，相應(yīng)的屬性求值規(guī)則中涉及x、y的屬性名也要進(jìn)行變化。8.4.2* L-屬性文法翻譯的實(shí)現(xiàn)遞歸下降翻譯 66而對(duì)規(guī)則S-AaB bC c ，當(dāng)b，c=a時(shí)，可寫(xiě)成S-A a B a C a對(duì)規(guī)則 La-A bf c ，當(dāng)a=b,c=b時(shí)，也可寫(xiě)成L a -A a f a但對(duì)規(guī)則Lab-aBcCd , 當(dāng)c,d=a時(shí)，可寫(xiě)成L ab -aB a C a 但當(dāng)b=a時(shí)， 不能寫(xiě)成 Laa-aB

45、 a C a這是因?yàn)樽蟛糠墙K結(jié)符號(hào)的屬性將作為該非終結(jié)符號(hào)分析過(guò)程的形參，而一個(gè)過(guò)程的形參不能重名，如過(guò)程L(int a, int b)不可寫(xiě)成L(int a, int a)。 8.4.2* L-屬性文法翻譯的實(shí)現(xiàn)遞歸下降翻譯 67種類(lèi)：逆波蘭式、三元式、四元式、抽象機(jī)代碼一逆波蘭表示法 (后綴式)表達(dá)式的后綴表示(逆波蘭式)的遞歸定義：（）如果是變量或常數(shù)，則的后綴表示即是自身（）如果是E1opE2的形式，其后綴表示為E1E2op. 其中op為 雙目運(yùn)算符，E1和E2分別是E1和E2的后綴表示 若是opE1的形式，則后綴表示為E1op，E1是E1的后綴表示（）如果是（E1）的形式， E1的后

46、綴表示即是的后綴表示8.5 中間代碼的形式 68表達(dá)式的逆波蘭式表示的實(shí)質(zhì)： 操作數(shù)出現(xiàn)的順序與原來(lái)順序一致，而運(yùn)算符則按運(yùn)算的先后順序放在相應(yīng)的操作數(shù)之后(又稱(chēng)后綴表示)這種表示不需要用括號(hào)來(lái)規(guī)定運(yùn)算的順序優(yōu)點(diǎn)：最易于計(jì)算機(jī)處理表達(dá)式，特別適用于解釋執(zhí)行的程序設(shè)計(jì)語(yǔ)言的中間表示，也方便具有堆棧體系的計(jì)算機(jī)的目標(biāo)代碼生成。 一、逆波蘭表示法8.5 中間代碼的形式 69表達(dá)式的逆波蘭式的求值過(guò)程：從左到右掃描逆波蘭式式：（1）掃描到運(yùn)算對(duì)象時(shí)，其值進(jìn)棧，并掃描下一個(gè)符號(hào)；（2）掃描到運(yùn)算符時(shí)，對(duì)棧頂兩個(gè)元素（二元運(yùn)算）或一個(gè)元素（一元運(yùn)算）執(zhí)行該運(yùn)算，并用運(yùn)算結(jié)果代替棧中的運(yùn)算對(duì)象。實(shí)例：表達(dá)式

47、：a*b-c*(d-e)逆波蘭式表示：ab*cde-*-一、逆波蘭表示法8.5 中間代碼的形式 70 擴(kuò)充逆波蘭式實(shí)例： ：= 逆波蘭式表示: ：= 二元運(yùn)算符“：=”與普通的算術(shù)運(yùn)算符不同，其含義是把表達(dá)式的值送到變量中去，所以在棧中只要變量的地址而不要值。此外，這個(gè)運(yùn)算符并不產(chǎn)生結(jié)果值，其運(yùn)算結(jié)果只是從棧中彈出它的兩個(gè)運(yùn)算對(duì)象。 實(shí)例：x=-a+b 逆波蘭式表示: xab+= ( 代表取負(fù)運(yùn)算) 實(shí)例：goto L1 逆波蘭式表示: L1 JP (JP是單目運(yùn)算符）一、逆波蘭表示法71擴(kuò)充逆波蘭式對(duì)于任何語(yǔ)句均可用逆波蘭表示： goto 10 運(yùn)算符 if e then x else y1

48、0geP1JFXP2JPy施加運(yùn)算假P1P2逆波蘭式規(guī)律：1）名字出現(xiàn)順序與原表達(dá)式相同2）運(yùn)算符出現(xiàn)的順序取決于計(jì)算的順序3）運(yùn)算符緊隨在運(yùn)算對(duì)象的后邊4）去掉括號(hào)不影響計(jì)算的順序72二、三元式和樹(shù)形表示逆波蘭(nbl)表示是一個(gè)符號(hào)串，每個(gè)符號(hào)為運(yùn)算對(duì)象或運(yùn)算符若分解成一個(gè)個(gè)基本運(yùn)算元組表示的中間語(yǔ)言1. 三元式格式 運(yùn)算符 運(yùn)算對(duì)象1、2 a:=b*c+b*d nbl: abc*bd*+=三元式含有對(duì)中間結(jié)果的顯示引用（計(jì)算結(jié)果與所加編號(hào)聯(lián)系）OPOP1OP2(*, b, c)(*, b, d)(+, (1), (2)(:=, a, (3)三元式編號(hào)三元式不必考慮臨時(shí)變量的分配，為克服三

49、元組不便于優(yōu)化的缺點(diǎn)，可使用間接三元組732. 樹(shù)形表示是三元式的翻版（運(yùn)算符為根，樹(shù)的中序遍歷為原表達(dá)式）:=a+*bcbd二、三元式和樹(shù)形表示（1）(*, b, c)（2）(*, b, d)（3）(+, (1), (2)（4）(:=, a, (3)74 3.間接三元式表示法 若考慮代碼優(yōu)化問(wèn)題，三元組表示并不適宜。因?yàn)榇a優(yōu)化時(shí)，通常需要?jiǎng)h除某些運(yùn)算，或者改變運(yùn)算的次序，這勢(shì)必要導(dǎo)致代碼的移動(dòng)。而三元式間的相互引用非常頻繁，每當(dāng)移動(dòng)一個(gè)三元式時(shí)，就必須改變所有引用它的三元式。因此說(shuō)，當(dāng)需要進(jìn)行代碼優(yōu)化時(shí)，三元組不是一種很好的中間語(yǔ)言形式。為了克服三元組表示不便于優(yōu)化的缺點(diǎn)，可使用一張額外的

50、表來(lái)保存三元組的執(zhí)行順序，即執(zhí)行表。當(dāng)需要完成優(yōu)化時(shí)，只改變執(zhí)行表中的項(xiàng)，而實(shí)際的三元組保持不變。 存放三元式本身的表，稱(chēng)為三元式表，如果有兩個(gè)相同的三元式，只需保留一個(gè)。 用一個(gè)三元式表連同執(zhí)行表來(lái)表示中間代碼，這種表示方式稱(chēng)為間接三元式。 二、三元式和樹(shù)形表示753間接三元式表示法例如：語(yǔ)句A：=B+C*D/E；F：=C*D 的間接三元組表示為： 執(zhí)行表 三元式表1 （1）（1）（*，C，D）2 （2）（2）（/，（1），E）3 （3）（3）（+，B，（2）4 （4）（4）（:=，A，（3）5 （1）（5）（:=，F(xiàn)，（1）6 （5）二、三元式和樹(shù)形表示76基本格式：（OP, OP1, O

51、P2, RESULT）其中：OP代表算符；OP1、OP2代表運(yùn)算對(duì)象；RESULT存放運(yùn)算結(jié)果。例如：a:=b*c+b*d(1) (*, b, c, t1)(2) (*, b, d, t2)(3) (+, t1, t2, t3)(4) (:=,t3,_, a)2簡(jiǎn)單賦值形式: （賦值語(yǔ)句的表達(dá)式中只有個(gè)運(yùn)算符）（1）t1:= b*c（1）t2:= b*d（2）t3:= t1+t2（4）a:= t3四元組中四元式的順序是按照相應(yīng)表達(dá)式的實(shí)際運(yùn)算順序出現(xiàn)的 三、四元式77擴(kuò)充四元式（jp, _, _, L） , 也可寫(xiě)成 goto L （j, A, B, L） , 也可寫(xiě)成 if A B goto

52、 L（jnz, A, _, L） , 也寫(xiě)成 if A goto L三、四元式78例如：if E or (BC) then S1 else S2經(jīng)翻譯后，可得如下的四元式序列：（1）（jnz,E,-,5）（2）（j,-,-,3）（3）（j,B,C,5）（4）（j,-,-,p+1）（5） 與S1相應(yīng)的四元式序列（p）（j,-,-,q）（p+1）與S2相應(yīng)的四元式序列（q）三、四元式79四、抽象機(jī)代碼PL/0編譯器PL/0語(yǔ)言程序類(lèi)pcode代碼（假想棧式計(jì)算機(jī)的匯編語(yǔ)言）如：即: 抽象機(jī)代碼808.6 賦值語(yǔ)句的翻譯語(yǔ)義分析語(yǔ)義檢查代碼生成（如：四元式）上下文相關(guān)性：id不能重復(fù)定義，先定義后使

53、用類(lèi)型匹配，類(lèi)型轉(zhuǎn)換例1 翻譯賦值語(yǔ)句的語(yǔ)義描述（目標(biāo)代碼為四元式）Sid := E P := lookup (); if Pnil then emit (P := E.place) else error EE1+E2 E.place := newtemp; emit (E.place := E1.place + E2.place) 或 emit (+, E.place, E2.place, E.place)81(3) EE1 * E2 E.place := newtemp; emit (E.place := E1.place * E2.place) (4) E-E E.plac

54、e := newtemp; emit (E.place = uminus E1.place) (5) E(E1) E.place := E1.place(6) Eid P := lookup (); if pnil then E.place := P else error 8.6 賦值語(yǔ)句的翻譯例1 翻譯賦值語(yǔ)句的語(yǔ)義描述（目標(biāo)代碼為四元式）82在語(yǔ)義分析時(shí)用到工作單元語(yǔ)義變量子程序語(yǔ)義函數(shù)(1) E.place 語(yǔ)義變量 表示存放E值的變量名在符號(hào)表的入口或一整數(shù)碼（臨時(shí)變量）(2) newtemp 函數(shù)過(guò)程 生成一個(gè)新的臨時(shí)變量(3) lookup(i) 函數(shù)過(guò)程 查符號(hào)表：

55、找到，返回變量i位置；否則出錯(cuò)(4) emit(OP, Arg1, Arg2, Result) 語(yǔ)義函數(shù) 生成一個(gè)四元式，并填入四元式表中，同時(shí)，四元式編號(hào)+18.6 賦值語(yǔ)句的翻譯83簡(jiǎn)單賦值語(yǔ)句的翻譯(算術(shù)表達(dá)式E及賦值語(yǔ)句的翻譯）語(yǔ)義分析： 語(yǔ)義檢查和 代碼生成翻譯賦值語(yǔ)句的語(yǔ)義描述（譯為四元式）：（1）Sid:=E p:=lookup(); If pnil then emit(p:=E.place) else error（2）EE1+E2 E.place:=newtemp; emit(E.place:=E1.place +E2.place)（3）EE1*E2 E.plac

56、e:=newtemp; emit(E.place:= E1.place * E2.place)（4）E-E1 E.place:=newtemp; emit(E.place:= uminusE1.place)（5）E（E1） E.place:= E1.place)（6）Eid p:=lookup(); if pnil then E.place:=p) else error類(lèi)型名稱(chēng)目標(biāo)地址intsum0inta2符號(hào)表t1t2臨時(shí)存儲(chǔ)區(qū)84布爾表達(dá)式的翻譯求布爾表達(dá)式邏輯值的語(yǔ)義翻譯（）例：翻譯布爾表達(dá)式a=d為四元式 100 (j=,c,d,107) 105 (=,0,_,t2)

57、106 (jp,_,_,108) 107 (=,1,_,t2) 108 (or,t1,t2,t3) 109a=dor85布爾表達(dá)式的翻譯不明確求值，根據(jù)布爾運(yùn)算特點(diǎn)實(shí)施某種優(yōu)化措施，快速得到邏輯結(jié)果 （185）(1)布爾表達(dá)式的翻譯圖E1 or E2FFTE1 and E2TTF(2) 翻譯要點(diǎn)對(duì)的翻譯是由一組條件真跳和無(wú)條件跳代碼組成待填地址采用回填、拉鏈方法實(shí)現(xiàn)。86布爾表達(dá)式的翻譯不明確求值，根據(jù)布爾運(yùn)算特點(diǎn)實(shí)施某種優(yōu)化措施，快速得到邏輯結(jié)果 （185）(3) 術(shù)語(yǔ)E.true:表示的真鏈把需要回填真出口的四元式拉成鏈，它們的真出口與的真出口一致，用E.true指向E.false:表示的

58、假鏈把需要回填假出口的四元式拉成鏈，它們的假出口與的假出口一致，用E.false指向87例：根據(jù)回填拉鏈技術(shù)， 把if ad and ef then S1else S2翻譯成四元式 100 if ad goto 104 103 goto p+1 E.false 104 if ef goto 106 E.true 105 goto p+1 E.false 106 與S1對(duì)應(yīng)的四元式序列 p: goto q p+1: 與S2對(duì)應(yīng)的四元式序列 q:888.7 控制語(yǔ)句的翻譯: 條件語(yǔ)句E的代碼S1的代碼if E then S1E的代碼S1的代碼S2的代碼Jump L1L1:if E then S1

59、else S2翻譯邏輯圖89利用回填拉鏈技術(shù)翻譯語(yǔ)句（翻譯文法見(jiàn)書(shū)上P185）例如： if a or bc then S1else S2翻譯成四元式 100 (jnz ,a ,_,104) 101 (jp,_,_102) 102 (j,b,c,104) 103 (jp,_,_,p+1) 104 與S1對(duì)應(yīng)的四元式序列 p: (jp,_,_q) p+1: 與S2對(duì)應(yīng)的四元式序列 q:8.7 控制語(yǔ)句的翻譯: 條件語(yǔ)句90利用布爾表達(dá)式求值和設(shè)置標(biāo)號(hào)避免回填的翻譯文法在遞歸下降語(yǔ)法制導(dǎo)翻譯方案中, 按如下的思路實(shí)現(xiàn)控制結(jié)構(gòu)的翻譯: 翻譯思路: 布爾表達(dá)式的翻譯采用求值的方式, 并設(shè)置標(biāo)號(hào)避免回填.

60、8.7 控制語(yǔ)句的翻譯: 條件語(yǔ)句91遞歸下降語(yǔ)法制導(dǎo)翻譯方案中實(shí)現(xiàn)控制結(jié)構(gòu)的翻譯:布爾表達(dá)式求值方式（翻譯文法見(jiàn)教材), 并設(shè)置標(biāo)號(hào)避免回填 if (E) getlabel gen(JZ, E.place,_,label1) S1 getlabel gen(JP,_,_,label2) setlabel(label1:) else S2 setlabel(label2:) while getlabel setlabel(label1:) ( E ) getlabel gen(JZ, E.place,_,label2) do S gen(JP,_,_,label1) setlabel(labe