編譯原理課件chap6

第六章屬性文法和語(yǔ)法制導(dǎo)翻譯從本章開(kāi)始，我們介紹有關(guān)語(yǔ)義分析及翻譯的問(wèn)題。其處理的方法主要是屬性文法和語(yǔ)法制導(dǎo)翻譯方法。本章中，我們將首先介紹屬性文法的基本概念，然后介紹基于屬性文法的處理方法，討論如何自上而下分析和自下而上分析中實(shí)現(xiàn)屬性計(jì)算。本章重點(diǎn)掌握前四節(jié)6.1屬性文法，6.2基于屬性文法的處理方法，6.3S—屬性文法的自下而上計(jì)算，6.4L—屬性文法和自頂向下翻譯。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.1屬性文法屬性文法是在上下文無(wú)關(guān)文法的基礎(chǔ)上為每個(gè)文法符號(hào)（終結(jié)符或非終結(jié)符）配備若干個(gè)相關(guān)的“值”（稱為屬性）。這些屬性代表與文法符號(hào)相關(guān)的信息，例如它的類型、值、代碼序列、符號(hào)表內(nèi)容等等。屬性和變量一樣，可以進(jìn)行計(jì)算和傳遞。

第六章屬性文法和語(yǔ)法制導(dǎo)翻譯屬性一般分為兩類：綜合屬性和繼承屬性。簡(jiǎn)單的說(shuō)，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。

屬性加工加工的過(guò)程即是語(yǔ)義處理的過(guò)程，對(duì)于文法的每一個(gè)產(chǎn)生式都配備了一組屬性的計(jì)算規(guī)則，則稱為語(yǔ)義規(guī)則。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條語(yǔ)義規(guī)則的形式為：b:=f(c1,c2,…,ck)

這里f是一個(gè)函數(shù)，而且或者

（1）b是A的一個(gè)綜合屬性并且c1,c2,…ck是產(chǎn)生式右邊文法符號(hào)的屬性；或者

（2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1,c2,…ck是A或產(chǎn)生式右邊任何文法符號(hào)的屬性

在這兩種情況下，我們都說(shuō)屬性b依賴于屬性c1,c2…,ck.第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

要特別強(qiáng)掉的是：

（1）終結(jié)符只有綜合屬性，它由詞法分析器提供；

（2）非終結(jié)符既可以有綜合屬性也可以有繼承屬性，文法開(kāi)始符號(hào)的所有繼承屬性作為屬性計(jì)算前的初始值。

一般來(lái)講，對(duì)出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個(gè)計(jì)算規(guī)則，屬性計(jì)算規(guī)則中只能使用相應(yīng)產(chǎn)生式的文法符號(hào)的屬性，這有利于產(chǎn)生式范圍內(nèi)“封裝”屬性的依賴性。然而，出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算,由屬性計(jì)算器的參數(shù)提供。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

語(yǔ)義規(guī)則所描述的工作可以包括屬性計(jì)算、靜態(tài)語(yǔ)義檢查、符號(hào)表操作、代碼生成等。語(yǔ)義規(guī)則可能產(chǎn)生副作用（如產(chǎn)生代碼），也可能不是變?cè)膰?yán)格函數(shù)（如某個(gè)規(guī)則給出可用的下一個(gè)數(shù)據(jù)單元的地址）。這樣的語(yǔ)義規(guī)則通常寫(xiě)成過(guò)程調(diào)用，或過(guò)程段。

綜合屬性：在語(yǔ)法樹(shù)中，一個(gè)結(jié)點(diǎn)的綜合屬性的值由其子結(jié)點(diǎn)的屬性值確定。因此，通常使用自底向上的方法在每一個(gè)結(jié)點(diǎn)處使用語(yǔ)義規(guī)則計(jì)算綜合屬性的值。僅僅使用綜合屬性的屬性文法稱S—屬性文法。

繼承屬性：在語(yǔ)法樹(shù)中，一個(gè)結(jié)點(diǎn)的繼承屬性由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性確定。用繼承屬性來(lái)表示程序語(yǔ)言結(jié)構(gòu)中的上下文依賴關(guān)系很方便。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.2基于屬性文法的處理方法從概念上講，基于屬性文法的處理過(guò)程通常是這樣的：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹(shù)，然后根據(jù)需要遍歷語(yǔ)法樹(shù)，并在語(yǔ)法樹(shù)的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算。輸入串語(yǔ)法樹(shù)依賴圖語(yǔ)義規(guī)則計(jì)算次序這種由源程序的語(yǔ)法結(jié)構(gòu)所驅(qū)動(dòng)的處理辦法就是語(yǔ)法制導(dǎo)翻譯法。語(yǔ)義規(guī)則的計(jì)算可能產(chǎn)生代碼、在符號(hào)表中存放信息、給出錯(cuò)誤信息或執(zhí)行任何其它動(dòng)作。對(duì)輸入串的翻譯也就是根據(jù)語(yǔ)義規(guī)則進(jìn)行計(jì)算得出結(jié)果。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.2.1依賴圖

如果在一棵語(yǔ)法樹(shù)中一個(gè)結(jié)點(diǎn)的屬性b依賴于屬性c，那么這個(gè)結(jié)點(diǎn)處計(jì)算b的屬性規(guī)則必須在確定c的語(yǔ)義規(guī)則之后使用。在一顆語(yǔ)法樹(shù)中的結(jié)點(diǎn)的繼承屬性和綜合屬性之間的相互依賴關(guān)系可以用稱作依賴圖的一個(gè)有向圖來(lái)描述。在為一棵語(yǔ)法樹(shù)構(gòu)造依賴圖以前，我們?yōu)槊恳粋€(gè)包含過(guò)程調(diào)用的語(yǔ)義規(guī)則引入一個(gè)虛綜合屬性b，這樣把每一個(gè)語(yǔ)義規(guī)則都寫(xiě)成b:=f(c1,c2,…ck)的形式。依賴圖中為每一個(gè)屬性設(shè)置一個(gè)結(jié)點(diǎn)，如果屬性b依賴屬性c，則從屬性c的結(jié)點(diǎn)有一條有向邊連到屬性b的結(jié)點(diǎn)。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯這里要掌握依賴圖的畫(huà)法。例如，屬性A.a:=f(X.x,Y.y)

對(duì)應(yīng)于產(chǎn)生式AXY的語(yǔ)義規(guī)則,這條語(yǔ)義規(guī)則確定了依賴于屬性X.x和Y.y的綜合屬性A.a。如果在語(yǔ)法樹(shù)中應(yīng)用這個(gè)產(chǎn)生式，那么在依賴圖中會(huì)有三個(gè)結(jié)點(diǎn)A.a,X.x,和Y.y。由于A.a依賴X.x，所以有一條有向邊從X.x到A.a.由于A.a也依賴于Y.y，所以還有一條有向邊從Y.y連到A.a.如果與產(chǎn)生式AXY對(duì)應(yīng)的語(yǔ)義規(guī)則還有：X.i:=g(A.a,Y.y)那么，圖中還應(yīng)有兩條有向邊，一條從A.a連到X.i，另一條從Y.y連到X.i,因?yàn)閄.i依賴于A.a和Y.y.第六章屬性文法和語(yǔ)法制導(dǎo)翻譯[例6.3]當(dāng)下面的產(chǎn)生式應(yīng)用于語(yǔ)法樹(shù)時(shí)，我們就像圖6.4所示的那樣把有向邊加到依賴圖中。產(chǎn)生式語(yǔ)義規(guī)則EE1+E2E.val:=E1.val+E2.val第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

[例6.4]下頁(yè)的圖是書(shū)中圖6.2（P139）帶注釋語(yǔ)法樹(shù)的依賴圖。依賴圖中的結(jié)點(diǎn)由數(shù)字來(lái)標(biāo)識(shí)，這些數(shù)字將在討論屬性的計(jì)算次序時(shí)用到。從代表T.type的結(jié)點(diǎn)4有一條邊連到代表L.in的結(jié)點(diǎn)5，因?yàn)楦鶕?jù)產(chǎn)生式DTL的語(yǔ)義規(guī)則L1.in=L.in,可知L1.in依賴于L.in.第六章屬性文法和語(yǔ)法制導(dǎo)翻譯所以有兩條向下的邊分別進(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)造的。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么該文法為良定義的。為了設(shè)計(jì)編譯程序，我們只處理良定義的屬性文法。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

屬性的計(jì)算次序一個(gè)有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點(diǎn)的任何順序m1,m2,…mk,使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面的結(jié)點(diǎn)。也就是說(shuō)，如果mimj是mi到mj的一條邊，那么在序列中mi必須出現(xiàn)在mj之前。一個(gè)依賴圖的任何拓?fù)渑判蚨冀o出一個(gè)語(yǔ)法樹(shù)中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序。這就是說(shuō)，在拓?fù)渑判蛑?，在一個(gè)結(jié)點(diǎn)上，語(yǔ)義規(guī)則b:=f（c1,c2,…ck)中的屬性c1,c2…ck在計(jì)算b以前都是可用的。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.2.2樹(shù)遍歷的屬性計(jì)算方法通過(guò)樹(shù)遍歷計(jì)算屬性值得方法很多種。這些方法都假設(shè)語(yǔ)法樹(shù)已經(jīng)建立起了，并且樹(shù)中已帶有開(kāi)始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語(yǔ)法樹(shù)，直至計(jì)算出所有的屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.2.3一遍掃描的處理方法與樹(shù)遍歷的屬性計(jì)算方法不同，一遍掃描的方法是在語(yǔ)法分析的同時(shí)計(jì)算屬性值。如果按這種一遍掃描的編譯程序模型來(lái)理解語(yǔ)法制導(dǎo)翻譯方法的話，所謂語(yǔ)法制導(dǎo)翻譯法，直觀上說(shuō)是為文法中每個(gè)產(chǎn)生式配上一組語(yǔ)義規(guī)則，并且在語(yǔ)法分析的同時(shí)執(zhí)行這些語(yǔ)義規(guī)則.在自上而下的語(yǔ)義分析中,若一個(gè)產(chǎn)生式匹配輸入串成功,或者在自下而上分析中,當(dāng)一個(gè)產(chǎn)生式被用于進(jìn)行歸約時(shí),此產(chǎn)生式相應(yīng)的語(yǔ)義規(guī)則就被計(jì)算,完成有關(guān)語(yǔ)義分析和代碼生成的工作.第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.2.4抽象語(yǔ)法樹(shù)

建立表達(dá)式的抽象語(yǔ)法樹(shù),我們通過(guò)為每個(gè)運(yùn)算分量或運(yùn)算符號(hào)都建立一個(gè)結(jié)點(diǎn)來(lái)為子表達(dá)式建立子樹(shù).運(yùn)算符號(hào)結(jié)點(diǎn)的各子結(jié)點(diǎn)分別是表示該運(yùn)算符號(hào)的各個(gè)運(yùn)算分量的子表達(dá)式組成的子樹(shù)的根.第六章屬性文法和語(yǔ)法制導(dǎo)翻譯抽象語(yǔ)法樹(shù)中的每一個(gè)結(jié)點(diǎn)可以由包含幾個(gè)域的記錄來(lái)實(shí)現(xiàn)的.在一個(gè)運(yùn)算符號(hào)對(duì)應(yīng)的結(jié)點(diǎn)中,一個(gè)域標(biāo)識(shí)運(yùn)算符號(hào)，其它域包含指向運(yùn)算分量的結(jié)點(diǎn)的指針。運(yùn)算符號(hào)通常叫做這個(gè)結(jié)點(diǎn)的標(biāo)號(hào)。當(dāng)我們進(jìn)行翻譯時(shí)，抽象語(yǔ)法樹(shù)中的結(jié)點(diǎn)可能會(huì)用附加域來(lái)存放結(jié)點(diǎn)的屬性值(或指向?qū)傩缘闹羔槪?。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.3S—屬性文法的自下而上計(jì)算

這一節(jié)我們考慮這樣一類屬性文法：S—屬性文法，它只含有綜合屬性。下面我們討論分析棧中的綜合屬性。在自底向上的分析法中。我們使用一個(gè)棧來(lái)存放已經(jīng)分析過(guò)的子樹(shù)的信息?，F(xiàn)在我們可以在分析棧中使用一個(gè)附域來(lái)存放綜合屬性值。圖6.9表示的是一個(gè)帶有一個(gè)屬性值空間的分析棧的例子。Stateval……XX.xYY.yZZ.z……圖6.9top第六章屬性文法和語(yǔ)法制導(dǎo)翻譯我們假設(shè)圖中的棧是由一對(duì)數(shù)組state和val來(lái)實(shí)現(xiàn)的。每一個(gè)state元素都是一個(gè)指向LR(1)分析表的指針（或索引）。（注意，文法符號(hào)隱含在state中而不需要存儲(chǔ)在棧中）。然而，如果像第五章中的那樣把文法符號(hào)存入棧中時(shí)，那么當(dāng)?shù)趇個(gè)state對(duì)應(yīng)的符號(hào)為A時(shí)，val[i]中就存放語(yǔ)法樹(shù)中與結(jié)點(diǎn)A對(duì)應(yīng)的屬性值。設(shè)當(dāng)棧頂由指針top指示。我們假設(shè)綜合屬性是剛好在每次歸約前計(jì)算的。假設(shè)語(yǔ)義規(guī)則A.a:=f(X.x,Y.y,Z.z)是對(duì)應(yīng)于產(chǎn)生式AXYZ的。在把XYZ歸約成A以前，屬性Z.z的值放在val[top]中，Y.y的值放在val[top-1]中，X.x的值放在val[top-2]中。如果一個(gè)符號(hào)沒(méi)有綜合屬性，那么數(shù)組val中相應(yīng)的元素就不定義。歸約后，top值減2，A的狀態(tài)存放在state[top]中（也就是X的位置）綜合屬性A.a的值存放在val[top]中。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

6.4L—屬性文法和自頂向下翻譯

一個(gè)屬性文法稱為L(zhǎng)—屬性文法：如果對(duì)于每個(gè)產(chǎn)生式AX1X2…Xn其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj(1<=j<=n)的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于：（1）產(chǎn)生式Xj的左邊符號(hào)X1,X2,…Xj-1的屬性（2）A的繼承屬性。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.4.1翻譯模式

屬性文法可以看成是關(guān)于語(yǔ)言翻譯的高級(jí)規(guī)范說(shuō)明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說(shuō)明翻譯順序的工作中解脫出來(lái)。下面我們討論一種適合語(yǔ)法制導(dǎo)翻譯的另一種描述形式，稱為翻譯模式。翻譯模式給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的次序，這樣就可以把某些實(shí)現(xiàn)細(xì)節(jié)表示出來(lái)。在翻譯模式中，和文法符號(hào)相關(guān)的屬性和語(yǔ)義規(guī)則（這里我們也稱語(yǔ)義動(dòng)作），用花括號(hào){}括起來(lái)，插入到產(chǎn)生式右部的合適位置上。這樣翻譯模式給出了使用語(yǔ)義規(guī)則進(jìn)行計(jì)算的順序。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯如果既有綜合屬性又有繼承屬性，在建立翻譯模式時(shí)就必須特別小心：（1）產(chǎn)生式右邊的符號(hào)的繼承屬性必須在這個(gè)符號(hào)以前的動(dòng)作中計(jì)算出來(lái)。（2）一個(gè)動(dòng)作不能引用這個(gè)動(dòng)作右邊符號(hào)的綜合屬性。（3）產(chǎn)生式左邊非終結(jié)符的綜合屬性只有在它所引用的所有屬性都計(jì)算出來(lái)后才能計(jì)算。計(jì)算這種屬性的動(dòng)作通常可放在產(chǎn)生式右端的末尾。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯6.4.2自頂向下翻譯

在第四章我們知道，為了構(gòu)造不帶回溯的自頂向下語(yǔ)法分析，必須消除文法中的左遞歸?，F(xiàn)在我們把前面消除左遞歸的方法加以擴(kuò)充,當(dāng)消除一個(gè)翻譯模式的基本語(yǔ)法的左遞歸時(shí)同時(shí)考慮屬性。這種方法適合帶綜合屬性的翻譯模式。這樣許多文法可以使用自頂向下分析來(lái)實(shí)現(xiàn)。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯對(duì)于自頂向下的分析，我們假設(shè)動(dòng)作是在處于相同位置上的符號(hào)被展開(kāi)（匹配成功）時(shí)執(zhí)行的。一個(gè)符號(hào)的繼承屬性必須由出現(xiàn)這個(gè)符號(hào)之前的動(dòng)作來(lái)計(jì)算，產(chǎn)生式左邊非終結(jié)符的綜合屬性必須在它的所依賴的所有屬性都計(jì)算出來(lái)之后才能被計(jì)算。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯下面我們把轉(zhuǎn)換左遞規(guī)翻譯模式的方法推廣到一般，以便進(jìn)行自頂向下分析：假設(shè)我們有下面的翻譯模式：AA1Y{A.a:=g(A1.a,Y.y)}AX{A.a:=f(X.x)}其每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用小寫(xiě)字母表示，g和f是任意函數(shù)。利用第四章消除左遞歸的算法，可將其轉(zhuǎn)換成下面文法：AXRRYR|ε第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

再考慮語(yǔ)義動(dòng)作，翻譯模式變?yōu)椋篈→X{R.i:=f(X.x)}R{A.a:=R.s}R→Y{R1.i:=g((R.i),Y.y)}R1{R.s:=R1.s}R→ε{R.s:=R.i}經(jīng)過(guò)轉(zhuǎn)換的翻譯模式，使用了R的繼承屬性i和綜合屬性s.第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

6.4.3遞歸下降翻譯器的設(shè)計(jì)6.5自下而上計(jì)算繼承屬性第六章屬性文法和語(yǔ)法制導(dǎo)翻譯例題與習(xí)題解答[例6.1]某程序設(shè)計(jì)語(yǔ)言說(shuō)明部分的語(yǔ)法制導(dǎo)定義如下：D→TLT→intT→realL→L1,idL→id給出語(yǔ)法制導(dǎo)定義及自底向上的翻譯模式，并比較兩者的不同。解：語(yǔ)法制導(dǎo)定義為：D→TL{L.in:=T.type}T→int{T.type:=integer}T→real{T.type:=real}L→L1,id{L1.in:=L.in,addtype(id.entry,L.in)}L→id{addtype(id.entry,L.in)}第六章屬性文法和語(yǔ)法制導(dǎo)翻譯

自底向上分析的翻譯模式為：D→T{L.in:=T.type}LT→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)}從上述定義看兩者的區(qū)別僅在于在翻譯模式中把語(yǔ)義動(dòng)作插入在規(guī)則右部的任意位置。而語(yǔ)法制導(dǎo)中把語(yǔ)義動(dòng)作都放在產(chǎn)生式的最后。第六章屬性文法和語(yǔ)法制導(dǎo)翻譯[例6.2]在一個(gè)移入——?dú)w約的分析中采用以下的語(yǔ)法制導(dǎo)的翻譯模式，在某產(chǎn)生式歸約時(shí)，立即執(zhí)行括號(hào)中的動(dòng)作。A→aB{print“0”}A→c{print“1”}B→Ab{print“2”}當(dāng)分析器輸入為aacbb時(shí)，打印的字符串是什么?第六章屬性文法和語(yǔ)法制導(dǎo)翻譯解：分析器的分析過(guò)程如右圖：由于分析器采用移入歸約的方式進(jìn)行分析，符號(hào)串a(chǎn)acbb的分析過(guò)程將按標(biāo)號(hào)進(jìn)行，而按一產(chǎn)生式歸約時(shí)立即執(zhí)行括號(hào)中的動(dòng)作所以分析器打印的字符為：12020語(yǔ)義動(dòng)作E.nptr:=mknode(‘+’,E1.nptr,T.nptr)E.nptr:=mknode(‘*’,E1.nptr,T.np