編譯原理4.4L屬性自下而上計(jì)算

1、4.4 L屬性的自下而上計(jì)算引入標(biāo)記非終結(jié)符：從翻譯方案中去掉嵌入在產(chǎn)生式中間的動(dòng)作復(fù)寫規(guī)則綜合考慮標(biāo)記非終結(jié)符和復(fù)寫規(guī)則：模擬繼承屬性的計(jì)算改寫文法：用綜合屬性代替繼承屬性4.4.1 刪除嵌入在翻譯方案中的動(dòng)作引入標(biāo)記非終結(jié)符從翻譯方案中去掉嵌入在產(chǎn)生式中間的動(dòng)作：使所有嵌入的動(dòng)作都出現(xiàn)在產(chǎn)生式的末尾轉(zhuǎn)換方法：在基礎(chǔ)文法中加入新的產(chǎn)生式，這種產(chǎn)生式的形式為M (M為新引入的一個(gè)標(biāo)記非終結(jié)符)，將嵌入在產(chǎn)生式中的每個(gè)語義動(dòng)作用不同的標(biāo)記非終結(jié)符M代替，并把這個(gè)動(dòng)作放在產(chǎn)生式M 的末尾例： ETR R+T print(+)R1 | -T print(-)R1 | Tnum print(num.v

2、al) 轉(zhuǎn)換為 ETR R+TMR1 | -TNR1 | Tnum print(num.val) M print(+) N print(-)4.4.2 分析棧中的繼承屬性利用復(fù)寫規(guī)則分析棧中的繼承屬性：利用復(fù)寫規(guī)則使得在需要用到繼承屬性的地方用綜合屬性來代替例：AXY X有綜合屬性s，Y有繼承屬性i，如果Y.i:=X.s，則可以在需要Y.i的值的地方使用X.s的值例如：翻譯方案DT L.in:=T.type LT int T.type :=integerT real T.type :=realL L1.in :=L.in L1,id addtype(id.entry,L.in)L id add

3、type(id.entry,L.in)考慮real p,q,r的自下而上的分析過程輸入串 狀態(tài) 所用產(chǎn)生式real p,q,r - p,q,r real p,q,r T Treal ,q,r Tp ,q,r TL Lid q,r TL, ,r TL,q ,r TL LL,id r TL, r TL,r TL LL,id D DTL每次L的右部被歸約時(shí)，T恰好在這個(gè)右部的下面，由復(fù)寫規(guī)則L.in:=T.type，可以在需要L.in的地方使用T.type來代替改寫后的翻譯方案產(chǎn)生式 代碼段DTLTint valtop:=integerTreal valtop:=realLL,id addtype(

4、valtop,valtop-3)Lid addtype(valtop,valtop-1)4.4.3 模擬繼承屬性的計(jì)算例：以下翻譯方案產(chǎn)生式 語義規(guī)則SaAC C.i:=A.sSaABC C.i:=A.sCc C.s:=g(C.i)當(dāng)通過Cc進(jìn)行歸約時(shí)，C.i的值可能在valtop-1也可能在valtop-2對于產(chǎn)生式SaABC ，在C的前面引入一個(gè)標(biāo)記非終結(jié)符M，使得C.i的值只會(huì)出現(xiàn)在valtop-1改寫后的翻譯方案產(chǎn)生式 語義規(guī)則SaAC C.i:=A.sSaABMC M.i:=A.s;C.i:=M.sCc C.s:=g(C.i)M M.s:=M.iSbABC.s.iCSbABM s i

5、 s i 例，EQN的翻譯方案 S B.ps:=10 B S.ht:=B.ht B B1.ps:=B.ps B1 B2.ps:=B.ps B2 B.ht:=max(B1.ht,B2.ht) B B1.ps:=B.ps B1 sub B2.ps:=shrink(B.ps) B2 B.ht:=disp(B1.ht,B2.ht) B text B.ht:=text.h*B.ps引入標(biāo)記非終結(jié)符產(chǎn) 生 式 語 義 規(guī) 則 S LB B.ps := L.s; S.ht := B.ht L L.s := 10 B B1 MB2 B1.ps := B.ps; M.i := B.ps; B2.ps := M.

6、s;B.ht := max(B1.ht, B2.ht ) M M.s := M.i B B1 sub NB2 B1.ps :=B.ps; N.i := B.ps; B2.ps := N.s; B.ht := disp (B1.ht, B2.ht ) N N.s := shrink(N.i) B text B.ht := text.h B.ps 產(chǎn) 生 式 代 碼 段S LB valntop := valtopL valntop := 10B B1 MB2 valntop := max(valtop2, valtop) M valntop := valtop1B B1 sub NB2 valntop:= disp (valtop3, valtop )N valntop := shrink(valtop2)B text valntop := valtop valtop14.3.4 用綜合屬性代替繼承屬性改寫基礎(chǔ)文法例：Pascal語言的說明語句 DL:T Tinteger | char LL,id | id改寫成 Did L L,id L | :T Tinteger | charDid L enter(id.entry,L.type