編譯原理課件chap6

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

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

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

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

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

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

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

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

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

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

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

一般來講，對出現(xiàn)在產(chǎn)生式右邊的繼承屬性和出現(xiàn)在產(chǎn)生式左邊的綜合屬性都必須提供一個計(jì)算規(guī)則，屬性計(jì)算規(guī)則中只能使用相應(yīng)產(chǎn)生式的文法符號的屬性，這有利于產(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ù)提供。第六章屬性文法和語法制導(dǎo)翻譯

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

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

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

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

對應(yīng)于產(chǎn)生式AXY的語義規(guī)則,這條語義規(guī)則確定了依賴于屬性X.x和Y.y的綜合屬性A.a。如果在語法樹中應(yīng)用這個產(chǎn)生式，那么在依賴圖中會有三個結(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對應(yīng)的語義規(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.第六章屬性文法和語法制導(dǎo)翻譯[例6.3]當(dāng)下面的產(chǎn)生式應(yīng)用于語法樹時(shí)，我們就像圖6.4所示的那樣把有向邊加到依賴圖中。產(chǎn)生式語義規(guī)則EE1+E2E.val:=E1.val+E2.val第六章屬性文法和語法制導(dǎo)翻譯

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

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

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

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

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

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

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

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

再考慮語義動作，翻譯模式變?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)過轉(zhuǎn)換的翻譯模式，使用了R的繼承屬性i和綜合屬性s.第六章屬性文法和語法制導(dǎo)翻譯

6.4.3遞歸下降翻譯器的設(shè)計(jì)6.5自下而上計(jì)算繼承屬性第六章屬性文法和語法制導(dǎo)翻譯例題與習(xí)題解答[例6.1]某程序設(shè)計(jì)語言說明部分的語法制導(dǎo)定義如下：D→TLT→intT→realL→L1,idL→id給出語法制導(dǎo)定義及自底向上的翻譯模式，并比較兩者的不同。解：語法制導(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)}第六章屬性文法和語法制導(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ū)別僅在于在翻譯模式中把語義動作插入在規(guī)則右部的任意位置。而語法制導(dǎo)中把語義動作都放在產(chǎn)生式的最后。第六章屬性文法和語法制導(dǎo)翻譯[例6.2]在一個移入——?dú)w約的分析中采用以下的語法制導(dǎo)的翻譯模式，在某產(chǎn)生式歸約時(shí)，立即執(zhí)行括號中的動作。A→aB{print“0”}A→c{print“1”}B→Ab{print“2”}當(dāng)分析器輸入為aacbb時(shí)，打印的字符串是什么?第六章屬性文法和語法制導(dǎo)翻譯解：分析器的分析過程如右圖：由于分析器采用移入歸約的方式進(jìn)行分析，符號串a(chǎn)acbb的分析過程將按標(biāo)號進(jìn)行，而按一產(chǎn)生式歸約時(shí)立即執(zhí)行括號中的動作所以分析器打印的字符為：12020語義動作E.nptr:=mknode(‘+’,E1.nptr,T.nptr)E.nptr:=mknode(‘*’,E1.nptr,T.np