編譯原理6-5-自下而上計算繼承屬性.ppt

《編譯原理6-5-自下而上計算繼承屬性.ppt》由會員分享，可在線閱讀，更多相關(guān)《編譯原理6-5-自下而上計算繼承屬性.ppt（34頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、第六章 屬性文法和語法制導(dǎo)翻譯,6.1 屬性文法 6.2 基于屬性文法的處理方法 6.3 S-屬性文法的自下而上計算 6.4 L-樹性文法和自頂向下翻譯 6.5 自下而上計算繼承屬性,6.5 自下而上計算繼承屬性,討論在自下而上的分析過程中實現(xiàn)L-屬性文法的方法。 這種方法可以實現(xiàn)任何基于LL(1)文法的L-屬性文法，它還可以實現(xiàn)許多（不是所有）基于LR(1)文法的L-屬性文法。,從翻譯模式中去掉嵌入在產(chǎn)生式中間的動作,介紹一種轉(zhuǎn)換方法，它可以使所有嵌入的動作都出現(xiàn)在產(chǎn)生式的末尾，這樣就可以自下而上處理繼承屬性。 轉(zhuǎn)換方法是，在基礎(chǔ)文法中加入新的產(chǎn)生式，這種產(chǎn)生式的形式為M,其中M為新引入的一

2、個標記非終結(jié)符。我們把嵌入在產(chǎn)生式中的每個語義動作用不同的標記非終結(jié)符M代替，并把這個動作放在產(chǎn)生式M的末尾。,例如，下面翻譯模式,ET R R+T print（）R | -Tprint（） R | T numprint（num.val）,ETR R+ TMR | TNR | T num print（num.val） M print （） N print（）,使用標記非終結(jié)符號M和N轉(zhuǎn)換為,兩個翻譯模式中的文法接受相同的語言。通過畫出帶有表示動作的附加結(jié)點的分析樹，可以看到動作的執(zhí)行程序也是一樣的。 在經(jīng)過轉(zhuǎn)換的翻譯模式中，動作都在產(chǎn)生式右端的末尾，因此，可以在自下

3、而上分析過程中產(chǎn)生式右部被歸約時執(zhí)行相應(yīng)的動作。,分析棧中的繼承屬性,自下而上分析器對產(chǎn)生式AXY的右部是通過把X和Y從分析棧中移出并用A代替它們。 假設(shè)X有一個綜合屬性X.s，按照6.3節(jié)所介紹的方法我們把它與X一起放在分析棧中。,由于X.s的值在Y以下的子樹中的任何歸約之前已經(jīng)放在棧中，這個值可以被Y繼承。 也就是說，如果繼承屬性Y. i是由復(fù)寫規(guī)則Y. i := X.s定義的，則可以在需要Y.i值的地方使用X.s的值。 我們將會看到，在自下而上分析中計算屬性值時復(fù)寫規(guī)則起非常重要的作用,下面例子說明復(fù)寫規(guī)則的使用,假設(shè)某翻譯模式為,D T L.in := T.type L T int

4、 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 ),按照這個翻譯模式標識符的類型可以通過繼承屬性的復(fù)寫規(guī)則來傳遞。例如，對于輸入串 int p, q, r 其屬性的傳遞方向如圖,圖6.21 在每個L結(jié)點L.in =T.type,表6.9 int p, q, r的分析過程,從表6.9可以看出，當L的右部被歸約時，T恰好在這個右部的下面。 假設(shè)分析棧是由一對數(shù)組state和val來實現(xiàn)的。 如果sta

5、tei代表符號X，則val i存放X的綜合屬性X. s，則表6.9中給出了state數(shù)組的內(nèi)容。 由于在表6.9中，每次L的右部被歸約時，T恰好在這個右部的下面，因此這時可以方便地訪問到T.type的值。,由于T. type在棧中相對于棧頂?shù)奈恢檬且阎?，我們可以翻譯模式中語義動作的實現(xiàn)如下表所示。,表6.10 語義動作的實現(xiàn),模擬繼承屬性的計算,屬性的位置不能預(yù)測 產(chǎn)生式語義規(guī)則 S aACC.i := A.s S bABCC.i := A.s C cC.s := g(C.i),屬性C.i通過復(fù)寫規(guī)則繼承綜合屬性A.s的值。注意在棧中A和C之間可能有B也可能沒有B，當通過Cc進行歸約時，C.

6、i的值可能在valtop-1處也可能在valtop-2處，但我們不能確定究竟在哪個位置。,為了解決這個問題，我們在上述翻譯模式中的第二個產(chǎn)生式右部的C的前面插入一個新的標記非終結(jié)符M。,產(chǎn)生式語義規(guī)則 S aACC.i := A.s S bABMCM.i := A.s; C.i := M.s C cC.s := g(C.i) M M.s := M.i,圖6.22 通過標記M傳遞屬性值,（a）修改前,（b）修改后,模擬不是復(fù)寫規(guī)則的語義規(guī)則 繼承屬性是某個綜合屬性的一個函數(shù) S aACC.i := f (A.s) 增加標記非終結(jié)符，把f(A.s)的計算移到對標記非終結(jié)符歸約時進行。 S aANC

7、N.i := A.s; C.i := N.s N N.s := f (N.i),(6.4),例6.13 數(shù)學(xué)排版語言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 := disp (B1.ht, B2.ht ) B textB.ht := text.h B.ps ,文字排版中引入標記符號,為了自底向上計算： B text B.ht := text.

8、h B.ps 必須確定繼承屬性B.ps的（“屬性棧”）位置。為此引 入標記非終結(jié)符L、M和N及其屬性，包括相應(yīng)的空產(chǎn) 生式和有關(guān)屬性規(guī)則。這樣B.ps即可在緊靠“句柄”text 下方的位置上找到。(L的綜合屬性置為B.ps的初值) SL B BB1M B2 BB1 sub N B2,表6.11 所有繼承屬性都由復(fù)寫規(guī)則賦值,L 用于初始化，M的用法同圖6.22，N的用法同式(6.4),按照前面例子的做法，在必要的時候引進標記非終結(jié)符，可以實現(xiàn)在LR分析過程中對L-屬性文法進行計算。 對于一個給定的LL(1)文法引入標記非終結(jié)符后，因為每個標記非終結(jié)符只有一個產(chǎn)生式，所以文法仍然保持是LL(1）

9、文法。任何LL(1)文法也是LR（1)文法，因此，當標記非終結(jié)符加入到LL(1)文法時不會產(chǎn)生分析沖突。但對LR(1)文法引入標記非終結(jié)符之后，不能保證還是LR(1)的，因此可能引起分析沖突。,下面，我們給出一種帶繼承屬性的自下而上的分析和翻譯方法。對于一個基礎(chǔ)文法是LL(1)文法的L-屬性文法定義，通過下面方法可以得到一個計算分析棧中所有屬性值的分析程序。 為了簡單起見，假設(shè) 每一個非終結(jié)符A都有一個繼承屬性A.i 每個文法符號X都有一個綜合屬性X.s 如果X是一個終結(jié)符號，那么它的綜合屬性就是通過詞法分析器返回的詞法值，這個值將放在val棧中的適應(yīng)位置。,對于每個產(chǎn)生式AX1X2Xn，引入

10、n個新的標記非終結(jié)符M1，Mn，用產(chǎn)生式AM1X1MnXn代替上面的產(chǎn)生式。 綜合屬性Xj.s將放在分析棧中與Xj相應(yīng)的數(shù)組val的表項中。 如果有繼承屬性Xj.i,把它也放在數(shù)組val中，但放在與Mj相應(yīng)的項中。 一個重要事實是，當我們進行分析時，如果繼承屬性A.i存在的話，它將在數(shù)組val中緊挨M1位置下面的位置中存放。,由于標記非終結(jié)符可能引起分析沖突，進行下面的簡化是有益的。 (1) 如果Xj沒有繼承屬性，則無需使用標記符Mj。當然，如果Mj被省略，棧中屬性的位置會引起變化，但是這種變化可以通過對分析器稍加修改而適應(yīng)。 (2) 如果X1.i存在，但是由復(fù)寫規(guī)則X1.i:A.i計算，則可

11、省略M1。因為我們知道A.i已經(jīng)存放在棧中預(yù)定的位置，緊挨X1下面，因此這個值也可以作為X1.i使用。,用綜合屬性代替繼承屬性,有時，改變基礎(chǔ)文法可能避免繼承屬性。 例如，一個Pascal的說明由一標識符序列后跟類型組成，如 m, n: integer 相應(yīng)文法 D L: T T integer | char L L，id | id,因為標識符由L產(chǎn)生而類型不在L的子樹中，我們不能僅僅使用綜合屬性就把類型與標識符聯(lián)系起來。 事實上，如果非終結(jié)符L從第一個產(chǎn)生式中它的右邊T中繼承了類型，則我們得到的屬性文法就不是L-屬性的，因此，基于這個屬性文法的翻譯工作不能在語法分析的

12、同時進行。。,一個解決的方法是重新構(gòu)造文法，使類型作為標識符表的最后一個元素。這樣，類型可以通過綜合屬性L.type進行傳遞，當通過L產(chǎn)生每個標識符時，它的類型就可以填入到符號表中。,相應(yīng)文法 D id L L ，id L | : T T integer | char,例 題 4,給出把中綴表達式翻譯成沒有冗余括號的中綴表達式的語法制導(dǎo)定義。 例如，因為和是左結(jié)合，((a (b + c )) (d ))可以重寫成a (b + c ) d。 先把表達式的括號都去掉，然后在必要的地方再加括號。 去掉表達式中的冗余括號，保留必要的括號。,例 題 4,第一種方法 S E print

13、( E. code ) E E1 + T if T. op = plus then E.code:=E1.code||“+”||“(”||T.code||“)” else E. code := E1. code || “+” || T. code; E. op := plus E TE. code := T. code; E. op := T. op,例 題 4,T T1 F if (F. op = plus) or (F. op = times) then if T1. op := plus then T. code := “(” || T1. code || “)” || “” || “(

14、” || F. code || “)” else T. code := T1. code || “” || “(” || F. code || “)” else if T1. op := plus then T. code := “(” || T1. code || “)” || “” || F. code else T. code := T1. code || “” || F. code; T. op := times,例 題 4,T F T. code := F. code; T. op := F. op F id F. code := id. lexeme; F. op := id F

15、 ( E ) F. code := E. code; F. op := E. op,例 題 4,第二種方法 給E，T和F兩個繼承屬性left_op和right_op 分別表示左右兩側(cè)算符的優(yōu)先級 給它們一個綜合屬性self_op表示自身主算符的優(yōu)先級 再給一個綜合屬性code表示沒有冗余括號的代碼。 分別用1和2表示加和乘的優(yōu)先級，用3表示id和(E)的優(yōu)先級，用0表示左側(cè)或右側(cè)沒有運算對象的情況。,例 題 4,S E E. left_op := 0; E. right_op := 0; print ( E. code ) E E1 + T E1. left_op := E. left_op;

16、 E1. right_op := 1; T. left_op := 1; T. right_op := E. right_op; E.code:=E1.code|| “+” || T. code ; E. self_op := 1; E T T. left_op := E. left_op; T. right_op := E. right_op; E. code := T. code; E. self_op := T. self_op,例 題 4,T T1 F T1. left_op := T. left_op; T1. right_op := 2; F. left_op := 2; F.

17、right_op := T. right_op; T.code:=T1.code|| “*” || F. code ; T. self_op := 2; T F F. left_op := T. left_op; F. right_op := T. right_op; T. code := F. code; T. self_op := F. self_op F id F. code := id. lexeme; F. self_op := 3,例 題 4,F ( E ) E. left_op := 0; E. right_op := 0; F. self_op := if (F. left_op = F. right_op) thenE. self_op else 3 F. code := if (F. left_op = F. right_op) thenE. code else “(” || E. code || “)”,