1、第六章屬性文法和語(yǔ)法制導(dǎo)翻譯,6.1 屬性文法 6.2 基于屬性文法的處理方法 6.3 S屬性文法的自下而上計(jì)算 6.4 L屬性文法和自頂向下翻譯 6.5 自下而上計(jì)算繼承屬性,2,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,6.1 屬性文法 概述 語(yǔ)義處理,程序設(shè)計(jì) 語(yǔ)言的語(yǔ)義 靜態(tài)語(yǔ)義是對(duì)程序約束的描述，這些約束無(wú)法通過(guò)抽象語(yǔ)法規(guī)則來(lái)妥善地描述，實(shí)質(zhì)上就是語(yǔ)法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域/可見(jiàn)性規(guī)則兩大類 類型相容性 變量先聲明后引用 名稱相關(guān)要求 動(dòng)態(tài)語(yǔ)義 程序單位描述的計(jì)算 編譯程序的語(yǔ)義處理工作 靜態(tài)語(yǔ)義審查 解釋執(zhí)行動(dòng)態(tài)語(yǔ)義（計(jì)算）生成代碼.,3,2020/9/2

2、9,中南大學(xué)軟件學(xué)院 陳志剛,概述,語(yǔ)義形式化 語(yǔ)義建模 文法模型- 屬性文法 命令式或操作式模型 - 操作語(yǔ)義學(xué) 應(yīng)用式模型-指稱語(yǔ)義學(xué) 公理式模型-公理語(yǔ)義學(xué),4,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,屬性文法,表達(dá)式文法 ET+T| T or T Tn | b ET1 + T2 T1.type = int T2.type= T1.type E.type :=int E T1 or T2 T1.type = bool T2.type= T1.type E.type :=bool T n T.type := int T b T.type := bool,5,2020/9/29,中南大

3、學(xué)軟件學(xué)院 陳志剛,操作語(yǔ)義,描述一段程序的含義是通過(guò)執(zhí)行該段程序所改變的計(jì)算機(jī)（虛擬計(jì)算機(jī)）狀態(tài)來(lái)反映。這個(gè)計(jì)算機(jī)的狀態(tài)與程序執(zhí)行時(shí)的狀態(tài)相對(duì)應(yīng)：包括變量的所有值，可執(zhí)行程序本身，各種系統(tǒng)定義的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。計(jì)算機(jī)里所有的寄存器的值和存儲(chǔ)單元的值作為計(jì)算機(jī)的狀態(tài)，用一組形式定義的操作來(lái)說(shuō)明執(zhí)行一條指令相應(yīng)的狀態(tài)怎樣變化。 For (expr1;expr2;expr3) expr1; . Loop:if expr2=0 goto out expr3; goto loop out: .,6,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,公理語(yǔ)義,一個(gè)語(yǔ)言的每個(gè)語(yǔ)法成分的含義定義為公理和演繹規(guī)則，

4、用于推導(dǎo)出該成分執(zhí)行的效果。 公理語(yǔ)義概念是隨著程序正確性的證明而發(fā)展的。當(dāng)正確性證明能構(gòu)造時(shí)表明程序執(zhí)行它的規(guī)格說(shuō)明所描述的計(jì)算。在一個(gè)證明中，每一個(gè)語(yǔ)句之前之后都有一個(gè)邏輯表達(dá)式對(duì)程序的變量進(jìn)行約束,以此說(shuō)明這個(gè)語(yǔ)句的含義。 一般的記號(hào) P S Q 如果在語(yǔ)句S執(zhí)行前P為真，則在語(yǔ)句S執(zhí)行并終止后Q為真。,7,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,指稱語(yǔ)義,指稱語(yǔ)義的基本概念是給每一段程序?qū)嶓w定義一個(gè)數(shù)學(xué)意義上的對(duì)象，和一個(gè)從實(shí)體實(shí)例向數(shù)學(xué)意義對(duì)象的映射的函數(shù) 特點(diǎn)： 不但對(duì)全部程序賦予全文而且對(duì)程序設(shè)計(jì)語(yǔ)法每一個(gè)語(yǔ)法成分短語(yǔ)（表達(dá)式，命令，聲明） 都給予含義。 每一個(gè)語(yǔ)法成分（短

5、語(yǔ)）的含義是以它的自 成分的含義的術(shù)語(yǔ)來(lái)定義的。 即 語(yǔ)義結(jié)構(gòu) 平行于語(yǔ)法結(jié)構(gòu)。 語(yǔ)義函數(shù)： 程序設(shè)計(jì)語(yǔ)言的語(yǔ)義利用映射函數(shù)來(lái)證明。 語(yǔ)義函數(shù)將短語(yǔ)映射到它的指稱。,8,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,屬性文法,雖然形式語(yǔ)義學(xué)(如指稱語(yǔ)義學(xué)、公理語(yǔ)義學(xué)、操作語(yǔ)義學(xué)等)的研究已取得了許多重大的進(jìn)展，但目前在實(shí)際應(yīng)用中比較流行的語(yǔ)義描述和語(yǔ)義處理的方法主要還是屬性文法和語(yǔ)法制導(dǎo)翻譯方法,9,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,屬性文法,屬性文法(attribute grammar)是一個(gè)三元組:A=(G,V,F),其中 G:是一個(gè)上下文無(wú)關(guān)文法 V:有窮的屬性集,每個(gè)屬性與

6、文法的一個(gè)終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息，如它的類型、值、代碼序列、符號(hào)表內(nèi)容等等 .屬性與變量一樣，可以進(jìn)行計(jì)算和傳遞。屬性加工的過(guò)程即是語(yǔ)義處理的過(guò)程。 F:關(guān)于屬性的屬性斷言或一組屬性的計(jì)算規(guī)則(稱為語(yǔ)義規(guī)則) . 斷言或語(yǔ)義規(guī)則與一個(gè)產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性.,10,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,屬性有兩種 繼承的和綜合的屬性,屬性通常分為兩類：綜合屬性和繼承屬性。簡(jiǎn)單地說(shuō)，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。 出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定

7、的產(chǎn)生式的屬性計(jì)算規(guī)則進(jìn)行計(jì)算，它們由其它產(chǎn)生式的屬性規(guī)則計(jì)算或者由生計(jì)算器的參數(shù)提供。 AX1 X2 Xn A的綜合屬性,計(jì)算 S(A):=f(I(X1),I(Xn) Xj的繼承屬性,計(jì)算 T(Xj):=f(I(A),. I(Xn) 1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開(kāi)始符號(hào)沒(méi)有繼承屬性. 2)終結(jié)符只有綜合屬性.,11,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,在一個(gè)屬性文法中，對(duì)應(yīng)于每個(gè)產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語(yǔ)義規(guī)則，每條規(guī)則的形式為b:=f(c1,c2ck) 這里，f是一個(gè)函數(shù)，而且或者 （1）b是A的一個(gè)綜合屬性并且c1,c2ck是產(chǎn)生式右邊文法符號(hào)的屬性;或

8、者 （2）b是產(chǎn)生式右邊某個(gè)文法符號(hào)的一個(gè)繼承屬性并且c1,c2ck是A或產(chǎn)生式右邊任何文法符號(hào)的屬性。 在兩種情況下，我們都說(shuō)屬性b依賴于屬性c1,c2ck 。,12,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,一個(gè)屬性文法的例子 例6.1 非終結(jié)符E、T及F都有一個(gè)綜合屬性val,符號(hào)digit有一個(gè)綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式LEn對(duì)應(yīng)的語(yǔ)義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個(gè)過(guò)程，我們可認(rèn)為這條規(guī)則定義了L的一個(gè)虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個(gè)產(chǎn)生式中同一非終結(jié)符多次出現(xiàn),語(yǔ) 義 規(guī) 則,L E,E E1+T,E T,T T1 * F,T F,F (E)

9、,F digit,Print(E.val),E.val:=E1.val+T.val,E.val:=T.val,T.val:=T1.val F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,產(chǎn) 生 式,13,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,設(shè)表達(dá)式為35+4，則語(yǔ)義動(dòng)作打印數(shù)值19,L,E.val=19,E.val=15,T.val=4,T.val=15,F.val=4,T.val=3,F.val=3,F.val=5,digit.lexval=4,digit.lexval=5,digit.lexval=3,+,*,3*5+4的帶

10、注釋的分析樹,14,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,繼承屬性,一個(gè)結(jié)點(diǎn)的繼承屬性值是由此結(jié)點(diǎn)的父結(jié)點(diǎn)和/或兄弟結(jié)點(diǎn)的某些屬性來(lái)決定的。 例6.2 繼承屬性L.in,生 產(chǎn) 式,語(yǔ) 義 規(guī) 則,D TL,T int,T real,L L1,id,L id,L.in:=T.type,T.type=integer,T.type:=real,L1.in:=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in),15,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,D,L.in= real,L.in= real,L.in= real,T.type

11、=real,real,id2,id1,id3,.,Real id1,id2,id3,，,，,16,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,語(yǔ)法制導(dǎo)的翻譯,一個(gè)翻譯是符號(hào)串對(duì)的一個(gè)集合。在一個(gè)編譯程序定義的翻譯中，符號(hào)串對(duì)是源程序和目標(biāo)程序。各個(gè)編譯階段定義一個(gè)翻譯，詞法分析：（字符串，單詞串）語(yǔ)法分析：（單詞串，語(yǔ)法樹）代碼生成（語(yǔ)法樹，匯編語(yǔ)言） 設(shè)是輸入字母表且是輸出字母表。定義由語(yǔ)言 L1 *到語(yǔ)言L2 *的一個(gè)翻譯是由*到 *的一個(gè)關(guān)系T,使得T的定義域?yàn)長(zhǎng)1且T的值域?yàn)長(zhǎng)2 。 使(x,y) T的句子y叫做x的一個(gè)輸出.,6.2 基于屬性文法的處理方法,17,2020/9/29

12、,中南大學(xué)軟件學(xué)院 陳志剛,語(yǔ)法制導(dǎo)的翻譯,直觀地說(shuō)，一個(gè)語(yǔ)法制導(dǎo)翻譯的基礎(chǔ)是一個(gè)文法，其中翻譯成分依附在每一產(chǎn)生式上。 例6.3： 下列翻譯模式，它定義翻譯，即對(duì)每個(gè)輸入x，其輸出y是x的逆轉(zhuǎn)。定義此翻譯的規(guī)則是,產(chǎn)生式,翻譯規(guī)則,(1)s0s,(2)s1s,(3)s ,(1)s=s0,(2)s=s1,(3)s=,18,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,輸入輸出對(duì)可由(,)表示，其中是輸入句子形式而是輸出句子形式。 (S,S)開(kāi)始用產(chǎn)生式s0s來(lái)擴(kuò)展得到(0S,S0). 再用一次規(guī)則(1)，得到(00S,S00)。 再用規(guī)則(2)，就得到(001S,S100). 然后應(yīng)用規(guī)則(3

13、)并得到(001,100)。,19,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,例6.4： 把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表示：,EE+T,E T,T TF,T F,F (E),F a,E=ET+,E=T,T=TF,T=F,F=E,F=a,產(chǎn)生式,翻譯規(guī)則,20,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,確定輸入a+aa的輸出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,FT+) (a+T,aT+) (a+TF,aFF+) (a+FF,aFF+) (a+aF,aaF+) (a+aa,aaa+),21,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,定義： 一個(gè)

14、語(yǔ)法制導(dǎo)的翻譯模式是一個(gè)五元組T=(N,，R,S),其中 (1) N是非終結(jié)符的有限集。 (2) 是有限的輸入字母表。 (3) 是有限的輸出字母表。 (4) R是形如A,的規(guī)則的有限集,其中 (N )*,(N )*且中那組非終結(jié)符是中那組非終結(jié)符的置換。 (5) S是N中一個(gè)特別的非終結(jié)符，即開(kāi)始符。,22,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,定義： 若T= (N, R,S)是SDTS,(T)則稱為語(yǔ)法制導(dǎo)的翻譯(SDT)，文法Gi=(N, ,P,S)，其中P=A|A,屬于R)，稱為SDTS T的基礎(chǔ)（或輸入）文法。文法G0=( N, ,P,S), ，其中P =A | A,屬于R ，

15、稱為T的輸出文法。 把語(yǔ)法制導(dǎo)的翻譯方法看成是將輸入文法Gi中的推導(dǎo)樹變換成輸出文法G0中的推導(dǎo)樹。給了輸入句子x，可以按如下方式得到x的一個(gè)翻譯：先為推導(dǎo)x構(gòu)造一棵推導(dǎo)樹，再變換該樹到輸出文法中的一棵樹，然后取此輸出樹的邊緣作為x的一個(gè)翻譯。,23,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,語(yǔ)義制導(dǎo)翻譯中的規(guī)則A,對(duì)應(yīng)于每一個(gè)文法產(chǎn)生式A 都有與 之相關(guān)聯(lián)的一套語(yǔ)義描述 屬性文法(attribute grammar)是一個(gè)三元組:A=(G,V,F) 屬性文法可以看作是關(guān)于語(yǔ)言翻譯的高級(jí)規(guī)范說(shuō)明，其中隱去實(shí)現(xiàn)細(xì)節(jié)，使用戶從明確說(shuō)明翻譯順序的工作中解脫出來(lái),24,2020/9/29,中南大學(xué)

16、軟件學(xué)院 陳志剛,語(yǔ)法制導(dǎo)翻譯實(shí)現(xiàn),從概念上講，語(yǔ)法制導(dǎo)翻譯即基于屬性文法的處理過(guò)程通常是這樣的：對(duì)單詞符號(hào)串進(jìn)行語(yǔ)法分析，構(gòu)造語(yǔ)法分析樹，然后根據(jù)需要遍歷語(yǔ)法樹并在語(yǔ)法樹的各結(jié)點(diǎn)處按語(yǔ)義規(guī)則進(jìn)行計(jì)算 輸入符號(hào)串 分析樹 屬性依賴圖 語(yǔ)義規(guī)則的計(jì)算順序,25,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,依賴圖,由稱為依賴圖的一個(gè)有向圖 描述分析樹中的繼承屬性和屬性中間的相互依賴關(guān)系。 依賴圖的構(gòu)造算法： for分析樹中每一個(gè)結(jié)點(diǎn)n do for 結(jié)點(diǎn)的文法符號(hào)的每一個(gè)屬性a do 為a在依賴圖中建立一個(gè)結(jié)點(diǎn)； for 分析樹中每一個(gè)結(jié)點(diǎn)n do for結(jié)點(diǎn)n所用產(chǎn)生式對(duì)應(yīng)的每一個(gè)語(yǔ)義規(guī)則 b

17、:=f(c1,c2,ck) do for i :=1 to k do 從ci結(jié)點(diǎn)到b結(jié)點(diǎn)構(gòu)造一條有向邊,26,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,依賴圖-例6.2,例6.2 繼承屬性L.in,生 產(chǎn) 式,語(yǔ) 義 規(guī) 則,D TL,T int,T real,L L1,id,L id,L.in:=T.type,T.type=integer,T.type:=real,L1.in:=L.in,addtype(id.entry,L.in),addtype(id.entry,L.in),27,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,例6.2 Real id1,id2,id3分析樹的依賴圖,

18、5,6,7,8,9,10,T,4,D,L,L,L,Real,type,in,in,in,3 entry,2 entry,entry,id3,id2,id1,.,.,1,28,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,依賴圖中的結(jié)點(diǎn)由數(shù)字來(lái)標(biāo)識(shí)。從代表T.type的結(jié)點(diǎn)4有一條有向邊連到代表L.in的結(jié)點(diǎn)5，因?yàn)楦鶕?jù)產(chǎn)生式ETL的語(yǔ)義規(guī)則L1.in=L.in，可知L1.in依賴于L.in，所以有兩條向下的有向邊分別進(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)造的。,29,2020/9/29

19、,中南大學(xué)軟件學(xué)院 陳志剛,良定義的屬性文法,很顯然，一條求值規(guī)則只有在其各變?cè)稻亚蟮玫那闆r下才可以使用。但有時(shí)候可能會(huì)出現(xiàn)一個(gè)屬性對(duì)另一個(gè)屬性的循環(huán)依賴關(guān)系。從事貿(mào)易如，p、c1、c2都是屬性，若有下求值規(guī)則：p: = f1(c1)、c1: = f2(c2)、c2: = f3(p)時(shí)，就無(wú)法對(duì)p求值。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的。為了設(shè)計(jì)編譯程序，我們只處理良定義的屬性文法。,30,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,屬性的計(jì)算順序,一個(gè)有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點(diǎn)的任何順序m1, m2, , mk，使得邊必須是從序列中前面的結(jié)點(diǎn)指向后面

20、的結(jié)點(diǎn)。也就是說(shuō)，如果mimj是mi到mj的一條邊，那么在序列中mi必須出現(xiàn)在mj之前。 一個(gè)依賴圖的任何拓?fù)渑判蚨冀o出一個(gè)分析樹中結(jié)點(diǎn)的語(yǔ)義規(guī)則計(jì)算的有效順序。這就是說(shuō)，在拓?fù)渑判蛑?，在一個(gè)結(jié)點(diǎn)，語(yǔ)義規(guī)則b:=f(c1,c2,ck)中的屬性c1,c2,ck在計(jì)算b以前都是可用的。,31,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,屬性文法說(shuō)明的翻譯是很精確的。最基本的文法用于建立輸入符號(hào)串的分析樹。依賴圖如上面討論的那樣建立。從依賴圖的拓?fù)渑判蛑?，我們可以得到?jì)算語(yǔ)義規(guī)則的順序。用這個(gè)順序來(lái)計(jì)算語(yǔ)義規(guī)則就得到輸入符號(hào)串的翻譯。 例6.2 Real id1,id2,id3分析樹的依賴圖 每一

21、條邊都是從序號(hào)較低的結(jié)點(diǎn)指向序號(hào)較高的結(jié)點(diǎn)。歷此，依賴圖的一個(gè)拓?fù)渑判蚩梢詮牡托蛱?hào)到高序號(hào)順序?qū)懗?。從這個(gè)拓?fù)渑判蛑形覀兛梢缘玫较铝谐绦颍胊n來(lái)代表依賴圖中與序號(hào)n的結(jié)點(diǎn)有關(guān)的屬性： a4: = real a5: = a4 addtype (id3, entry, a5); a7: = a5; addtype (id2,entry, a7) a9: = a7 addtype (id1,entry, a9) 這些語(yǔ)義規(guī)則的計(jì)算將把real類型填入到每個(gè)標(biāo)識(shí)符對(duì)應(yīng)的符號(hào)表項(xiàng)中。,32,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,屬性計(jì)算方法,樹遍歷的屬性計(jì)算方法 設(shè)語(yǔ)法樹已經(jīng)建立起了，并且樹中

22、已帶有開(kāi)始符號(hào)的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語(yǔ)法樹，直至計(jì)算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。 一遍掃描的處理方法 與樹遍歷的屬性計(jì)算文法不同，一遍掃描的處理方法是在語(yǔ)法分析的同時(shí)計(jì)算屬性值，而不是語(yǔ)法分析構(gòu)造語(yǔ)法樹之后進(jìn)行屬性的計(jì)算，而且無(wú)無(wú)需構(gòu)造實(shí)際的語(yǔ)法樹。 因?yàn)橐槐閽呙璧奶幚矸椒ㄅc語(yǔ)法分析器的相互作用，它與下面兩個(gè)因素密切相關(guān)： （1）所采用的語(yǔ)法分析方法 （2）屬性的計(jì)算次序。,33,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,例：定義定點(diǎn)二進(jìn)制數(shù)的CFG:,(1) NSS (2) SSB (3)

23、SB (4) B0 (5) B1,34,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,在某些情況下可用一遍掃描實(shí)現(xiàn)屬性文法的語(yǔ)義規(guī)則計(jì)算。也就是說(shuō)在語(yǔ)法分析的同時(shí)完成語(yǔ)義規(guī)則的計(jì)算，無(wú)須明顯地構(gòu)造語(yǔ)法樹或構(gòu)造屬性之間的依賴圖。因?yàn)閱伪閷?shí)現(xiàn)對(duì)于編譯效率非常重要 具體的實(shí)現(xiàn)希望在單遍掃描中完成翻譯 研究怎樣實(shí)現(xiàn)這種翻譯器。一個(gè)一般的屬性文法的翻譯器可能是很難建立的，然而有一大類屬性文法的翻譯器是很容易建立的 s-屬性 適用于自底向上的計(jì)算 L-屬性 適用于自頂向下的分析，也可用于自底向上。,35,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,6.3 S屬性文法的自下而上計(jì)算,S屬性文法，它只含有綜

24、合屬性。 綜合屬性可以在分析輸入符號(hào)串的同時(shí)自下而上的分析器來(lái)計(jì)算。分析器可以保存與棧中文法符號(hào)有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時(shí)，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號(hào)的屬性值來(lái)計(jì)算。 S屬性文法的翻譯器通?？山柚贚R分析器實(shí)現(xiàn)。在S屬性文法的基礎(chǔ)上，LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。,36,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,產(chǎn)生式 語(yǔ)義規(guī)則 ） （.） ）1 .1. ） .l ）1* .1. ）F .F. ）（） . ）ii .:. LR分析器可以改造為一個(gè)翻譯器，在對(duì)輸入串進(jìn)行語(yǔ)法分析的同時(shí)對(duì)屬性進(jìn)行計(jì)算。 LR分析器增加語(yǔ)義棧,

25、37,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,*的分析和計(jì)值過(guò)程,步驟 動(dòng)作 狀態(tài)棧 語(yǔ)義棧(值棧) 符號(hào)棧 余留輸入串 ） 3* ） 3 * ） * ） * ） * ） * ） * ） * ） * ） * ） * ） （） * # ） （） ） （） ）接受,38,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,BOTTOMUP 語(yǔ)義處理是作類型檢查，對(duì)二目運(yùn)算符的運(yùn)算對(duì)象進(jìn)行類型匹配審查。 (LR分析）：增加語(yǔ)義棧 歸約時(shí)進(jìn)行語(yǔ)義動(dòng)作. 例6.7GE: (1) E T+T (2) E T or T (3) T n (4) T b,39,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,ET

26、1 + T2 if T1.type = int and T2.type= int then E.type :=int else error E T1 or T2 if T1.type = bool and T2.type= bool then E.type :=bool else error T n T.type := int T b T.type := bool,40,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,GE: (1) E T+T (2) E T or T (3) T n (4) T b,41,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,42,2020/9/29,中南大學(xué)軟件學(xué)院

27、 陳志剛,6.4 L屬性文法和自頂向下翻譯,一個(gè)屬性文法稱為L(zhǎng)屬性文法，如果對(duì)于每個(gè)產(chǎn)生式AX1X2Xn，其每個(gè)語(yǔ)義規(guī)則中的每個(gè)屬性或者是綜合屬性，或者是Xj（1jn）的一個(gè)繼承屬性且這個(gè)繼承屬性僅依賴于： （1）產(chǎn)生式Xj在左邊符號(hào)X1，X2，Xj-1的屬性； （2）A的繼承屬性。 S屬性文法一定是L屬性文法，因?yàn)椋?）、（2）限制只用于繼承屬性。 L屬性文法允許一次遍歷就計(jì)算出所有屬性值。 LL（1）這種自上而下分析文法的分析過(guò)程，從概念上說(shuō)可以看成是深度優(yōu)先建立語(yǔ)法樹的過(guò)程，因此，我們可以在自上而下語(yǔ)法分析的同時(shí)實(shí)現(xiàn)L屬性文法的計(jì)算。,43,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,

28、例（中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式）ETRRaddop T print(addop. Lexeme) R1|Tnum print(num.val),翻譯模式（Translation schemes）適合語(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)生式右部的合適位置上。,44,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,對(duì)于自頂向下分析，我們假設(shè)動(dòng)作是在處于相同位置上的符號(hào)被展開(kāi)（匹配成功）時(shí)執(zhí)行的。如圖中的第二個(gè)產(chǎn)生式中，第一個(gè)動(dòng)作（對(duì)R1.i

29、賦值）是在T被完全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的，第二個(gè)動(dòng)作是在R1被完全展開(kāi)成終結(jié)符號(hào)后執(zhí)行的。正如前面我們所討論的，一個(gè)符號(hào)的繼承屬性必須由出現(xiàn)在這個(gè)符號(hào)之前的動(dòng)作來(lái)計(jì)算，產(chǎn)生式左邊非終結(jié)符的綜合屬性必須在它所依賴的所有屬性都計(jì)算出來(lái)以后才能計(jì)算。,45,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,轉(zhuǎn)換左遞歸翻譯模式的方法推廣到一般,假設(shè)翻譯模式1： AA1YA.a: = g(A1。a, Y.y) AX A.a: = f(X.x)每個(gè)文法符號(hào)都有一個(gè)綜合屬性，用相應(yīng)的小寫字母表示，g和f是任意函數(shù) 消除左遞歸，文法轉(zhuǎn)換成： AXR RYR 再考慮語(yǔ)義動(dòng)作，翻譯模式變?yōu)? AXR.i: = f(X

30、.x) R A.a: =R.s RYR1.i: = g(R.i,Y.y) R1R.s: = R1.s RR.s: = R.i,46,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,翻譯模式1和翻譯模式2的結(jié)果是一樣的。可以給出串XY1Y2兩棵帶注釋的語(yǔ)法樹看出來(lái)，一棵是根據(jù)翻譯模式1自下而上計(jì)算屬性的。一棵是根據(jù)翻譯模式2自上而下計(jì)算的。,47,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,思考問(wèn)題-把建立語(yǔ)法樹的翻譯模式變換成適合預(yù)測(cè)分析的模式,EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr) E E1-T E.nptr:=mknode(-,E1.nptr,T.np

31、tr) E T E.nptr:=T.nptr),48,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,6.5 自下而上計(jì)算繼承屬性,討論在自下而上的分析過(guò)程中實(shí)現(xiàn)L屬性文法的方法。這種方法可以實(shí)現(xiàn)任何基于LL（1）文法的L屬性文法，它還可以實(shí)現(xiàn)許多（不是所有）基于LR（1）文法的L屬性文法。這種方法是S-屬性文法的自下而上翻譯技術(shù)的一般化,49,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,自下而上分析器對(duì)產(chǎn)生式AXY的右部是通過(guò)把X和Y從分析棧中移出并用A代替它們。假設(shè)X有一個(gè)綜合屬性X.s，按照前面所介紹的方法我們把它與X一起放在分析棧中。 由于X.s的值在Y以下的子樹中的任何歸約之前已經(jīng)放

32、在棧中，這個(gè)值可以被Y繼承。也就是說(shuō)，如果繼承屬性Y.i是由復(fù)寫規(guī)則Y.i: = X.s定義的，則可以在需要y.i值的地方使用X.s的值。在自下而上分析中計(jì)算屬性值時(shí)復(fù)寫規(guī)則起非常重要的作用?？聪旅胬印?50,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,假設(shè)某翻譯模式為： DT L.in: = T.type L TintT.type: = integer TrealT.type: = real L L1.in: = L.in L1, idaddtype(id.entry, L.in) Lidaddtype(id.entry,L.in),51,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,回

33、顧例6.2 Real id1,id2,id3分析樹的依賴圖,5,6,7,8,9,10,T,4,D,L,L,L,Real,type,in,in,in,3 entry,2 entry,entry,id3,id2,id1,.,.,1,52,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,例6.2輸入串real Real id1,id2,id3的分析過(guò)程當(dāng)L的右部被歸約時(shí)，T恰好在這個(gè)右部的下面,輸入 狀態(tài)(符號(hào)） 使用產(chǎn)生式 Real id1,id2,id3# id1,id2,id3# real id1,id2,id3# T Treal ,id2,id3# Tid1 ,id2,id3# TL L id

34、 id2,id3# TL, ,id3# TL,id2 ,id3# TL L Li,d id3# TL, # TL,id3 # TL L Li,d # D D TL,53,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,用綜合屬性代替繼承屬性,有時(shí)，改變基礎(chǔ)文法可能避免繼承屬性。例如，一個(gè)Pascal的說(shuō)明由一標(biāo)識(shí)符序列后跟類型組成，如, m, n: integer。這樣的說(shuō)明的文法可由下面形式的產(chǎn)生式構(gòu)成 DL：T Tinteger|char LL, id|id 因?yàn)闃?biāo)識(shí)符由L產(chǎn)生而類型不在L的子樹中，我們不能僅僅使用綜合屬性就把類型與標(biāo)識(shí)符聯(lián)系起來(lái)。事實(shí)上，如果非終結(jié)符L從第一個(gè)產(chǎn)生式中它的右

35、邊T中繼承了類型，則我們得到的屬性文法就不是L屬性的，因此，基于這個(gè)屬性文法的翻譯工作不能在語(yǔ)法分析的同時(shí)進(jìn)行。,54,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,一個(gè)解決的方法是重新構(gòu)造文法,使類型作為標(biāo)識(shí)符表的最后一個(gè)元素： Did L L, id L|: T Tinteger|char 這樣，類型可以通過(guò)綜合屬性L.type進(jìn)行傳遞，當(dāng)通過(guò)L產(chǎn)生每個(gè)標(biāo)識(shí)符時(shí)，它的類型就可以填入到符號(hào)表中。,55,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,語(yǔ)義制導(dǎo)翻譯的編譯實(shí)現(xiàn):,例6.6 E TE E A T E | T FT T M F T | F (E) | int A + | - M * |

36、 /,56,2020/9/29,中南大學(xué)軟件學(xué)院 陳志剛,E - TE E - A T E rhs = PopOperand();lhs = PopOperand(); switch (PopOperator() case ADD: PushOperand(lhs+rhs); break; case SUB: PushOperand(lhs-rhs); break; | /* empty, do nothing */ T - FT T - M F T rhs = PopOperand();lhs = PopOperand(); switch (PopOperator() case MUL: PushOperand(lhs*rhs); break; case DIV: PushOperand(lhs/rhs); break;