第六章屬性文法和語法制導翻譯

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

2、7/19/20222中南大學軟件學院 陳志剛概述語義形式化 語義建模文法模型- 屬性文法命令式或操作式模型 - 操作語義學應用式模型-指稱語義學公理式模型-公理語義學7/19/20223中南大學軟件學院 陳志剛屬性文法表達式文法 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 7/19/20224中南大學軟件學院

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

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

5、語來定義的。 即 語義結(jié)構(gòu) 平行于語法結(jié)構(gòu)。語義函數(shù)： 程序設計語言的語義利用映射函數(shù)來證明。 語義函數(shù)將短語映射到它的指稱。7/19/20227中南大學軟件學院 陳志剛屬性文法 雖然形式語義學(如指稱語義學、公理語義學、操作語義學等)的研究已取得了許多重大的進展，但目前在實際應用中比較流行的語義描述和語義處理的方法主要還是屬性文法和語法制導翻譯方法 7/19/20228中南大學軟件學院 陳志剛屬性文法屬性文法(attribute grammar)是一個三元組:A=(G,V,F),其中 G:是一個上下文無關(guān)文法V:有窮的屬性集,每個屬性與文法的一個終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號相

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

7、計算器的參數(shù)提供。 AX1 X2 XnA的綜合屬性,計算 S(A):=f(I(X1),I(Xn)Xj的繼承屬性,計算 T(Xj):=f(I(A),. I(Xn) 1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號沒有繼承屬性. 2)終結(jié)符只有綜合屬性.7/19/202210中南大學軟件學院 陳志剛在一個屬性文法中，對應于每個產(chǎn)生式A都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為b:=f(c1,c2ck)這里，f是一個函數(shù)，而且或者（1）b是A的一個綜合屬性并且c1,c2ck是產(chǎn)生式右邊文法符號的屬性;或者（2）b是產(chǎn)生式右邊某個文法符號的一個繼承屬性并且c1,c2ck是A或產(chǎn)生式右邊任何

8、文法符號的屬性。在兩種情況下，我們都說屬性b依賴于屬性c1,c2ck 。7/19/202211中南大學軟件學院 陳志剛 一個屬性文法的例子 例6.1 非終結(jié)符E、T及F都有一個綜合屬性val,符號digit有一個綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式LEn對應的語義規(guī)則僅僅是打印由E產(chǎn)生的算術(shù)表達式的值的一個過程，我們可認為這條規(guī)則定義了L的一個虛屬性。某些非終結(jié)符加下標是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)語 義 規(guī) 則 L EE E1+TE TT T1 * FT FF (E)F digitPrint(E.val) E.val:=E1.val+T.val E.val:=T.val T

9、.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn) 生 式7/19/202212中南大學軟件學院 陳志剛設表達式為35+4，則語義動作打印數(shù)值19LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹7/19/202213中南大學軟件學院 陳志剛繼承屬性一個結(jié)點的繼承屬性值是由此結(jié)點的父結(jié)點和/或兄弟結(jié)點的某些屬性來決定的。例6.2 繼承屬性

10、L.in生 產(chǎn) 式語 義 規(guī) 則D TL T int T real L L1,idL idL.in:=T.typeT.type=integerT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)7/19/202214中南大學軟件學院 陳志剛 DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.Real id1,id2,id3，7/19/202215中南大學軟件學院 陳志剛語法制導的翻譯一個翻譯是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串

11、對是源程序和目標程序。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法樹，匯編語言）設是輸入字母表且是輸出字母表。定義由語言 L1 *到語言L2 *的一個翻譯是由*到 *的一個關(guān)系T,使得T的定義域為L1且T的值域為L2 。 使(x,y) T的句子y叫做x的一個輸出.6.2 基于屬性文法的處理方法7/19/202216中南大學軟件學院 陳志剛語法制導的翻譯 直觀地說，一個語法制導翻譯的基礎是一個文法，其中翻譯成分依附在每一產(chǎn)生式上。例6.3： 下列翻譯模式，它定義翻譯，即對每個輸入x，其輸出y是x的逆轉(zhuǎn)。定義此翻譯的規(guī)則是產(chǎn)生式翻譯規(guī)則(1)s0

12、s(2)s1s(3)s (1)s=s0(2)s=s1 (3)s= 7/19/202217中南大學軟件學院 陳志剛 輸入輸出對可由(,)表示，其中是輸入句子形式而是輸出句子形式。 (S,S)開始用產(chǎn)生式s0s來擴展得到(0S,S0). 再用一次規(guī)則(1)，得到(00S,S00)。 再用規(guī)則(2)，就得到(001S,S100). 然后應用規(guī)則(3)并得到(001,100)。7/19/202218中南大學軟件學院 陳志剛例6.4： 把下述產(chǎn)生式定義的算術(shù)表達式映射到后綴波蘭表示： EE+TE T T TFT F F (E) F a E=ET+ E=T T=TF T=F F=E F=a產(chǎn)生式翻譯規(guī)則7

13、/19/202219中南大學軟件學院 陳志剛 確定輸入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+)7/19/202220中南大學軟件學院 陳志剛 定義： 一個語法制導的翻譯模式是一個五元組T=(N,，R,S),其中 (1) N是非終結(jié)符的有限集。 (2) 是有限的輸入字母表。 (3) 是有限的輸出字母表。 (4) R是形如A,的規(guī)則的有限集,其中(N )*,(N )*且中那組非終結(jié)符是中那組非終結(jié)符的置換。 (5) S是N中一個特別的非終

14、結(jié)符，即開始符。7/19/202221中南大學軟件學院 陳志剛 定義： 若T= (N, R,S)是SDTS,(T)則稱為語法制導的翻譯(SDT)，文法Gi=(N, ,P,S)，其中P=A|A,屬于R)，稱為SDTS T的基礎（或輸入）文法。文法G0=( N, ,P,S), ，其中P =A | A,屬于R ，稱為T的輸出文法。 把語法制導的翻譯方法看成是將輸入文法Gi中的推導樹變換成輸出文法G0中的推導樹。給了輸入句子x，可以按如下方式得到x的一個翻譯：先為推導x構(gòu)造一棵推導樹，再變換該樹到輸出文法中的一棵樹，然后取此輸出樹的邊緣作為x的一個翻譯。7/19/202222中南大學軟件學院 陳志剛語

15、義制導翻譯中的規(guī)則A, 對應于每一個文法產(chǎn)生式A 都有與之相關(guān)聯(lián)的一套語義描述屬性文法(attribute grammar)是一個三元組:A=(G,V,F) 屬性文法可以看作是關(guān)于語言翻譯的高級規(guī)范說明，其中隱去實現(xiàn)細節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來7/19/202223中南大學軟件學院 陳志剛語法制導翻譯實現(xiàn)從概念上講，語法制導翻譯即基于屬性文法的處理過程通常是這樣的：對單詞符號串進行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要遍歷語法樹并在語法樹的各結(jié)點處按語義規(guī)則進行計算輸入符號串 分析樹 屬性依賴圖 語義規(guī)則的計算順序7/19/202224中南大學軟件學院 陳志剛依賴圖由稱為依賴

16、圖的一個有向圖 描述分析樹中的繼承屬性和屬性中間的相互依賴關(guān)系。 依賴圖的構(gòu)造算法： for分析樹中每一個結(jié)點n do for 結(jié)點的文法符號的每一個屬性a do 為a在依賴圖中建立一個結(jié)點； for 分析樹中每一個結(jié)點n do for結(jié)點n所用產(chǎn)生式對應的每一個語義規(guī)則 b:=f(c1,c2,ck) do for i :=1 to k do 從ci結(jié)點到b結(jié)點構(gòu)造一條有向邊 7/19/202225中南大學軟件學院 陳志剛依賴圖-例6.2 例6.2 繼承屬性L.in生 產(chǎn) 式語 義 規(guī) 則D TL T int T real L L1,idL idL.in:=T.typeT.type=integ

17、erT.type:=real L1.in:=L.in addtype(id.entry,L.in) addtype(id.entry,L.in)7/19/202226中南大學軟件學院 陳志剛例6.2 Real id1,id2,id3分析樹的依賴圖 5678910T4DLLLRealtypeininin3 entry2 entryentryid3id2id1.17/19/202227中南大學軟件學院 陳志剛依賴圖中的結(jié)點由數(shù)字來標識。從代表T.type的結(jié)點4有一條有向邊連到代表L.in的結(jié)點5，因為根據(jù)產(chǎn)生式ETL的語義規(guī)則L1.in=L.in，可知L1.in依賴于L.in，所以有兩條向下的有

18、向邊分別進入結(jié)點7和9。每一個與L產(chǎn)生式有關(guān)的語義規(guī)則addtype(id. Entry, L.in)都產(chǎn)生一個虛屬性，結(jié)點 6、8和10都是為這些虛屬性構(gòu)造的。7/19/202228中南大學軟件學院 陳志剛良定義的屬性文法很顯然，一條求值規(guī)則只有在其各變元值均已求得的情況下才可以使用。但有時候可能會出現(xiàn)一個屬性對另一個屬性的循環(huán)依賴關(guān)系。從事貿(mào)易如，p、c1、c2都是屬性，若有下求值規(guī)則：p: = f1(c1)、c1: = f2(c2)、c2: = f3(p)時，就無法對p求值。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的。為了設計編譯程序，我們只處理良定義的屬性文法。

19、 7/19/202229中南大學軟件學院 陳志剛屬性的計算順序一個有向非循環(huán)圖的拓撲序是圖中結(jié)點的任何順序m1, m2, , mk，使得邊必須是從序列中前面的結(jié)點指向后面的結(jié)點。也就是說，如果mimj是mi到mj的一條邊，那么在序列中mi必須出現(xiàn)在mj之前。 一個依賴圖的任何拓撲排序都給出一個分析樹中結(jié)點的語義規(guī)則計算的有效順序。這就是說，在拓撲排序中，在一個結(jié)點，語義規(guī)則b:=f(c1,c2,ck)中的屬性c1,c2,ck在計算b以前都是可用的。7/19/202230中南大學軟件學院 陳志剛 屬性文法說明的翻譯是很精確的。最基本的文法用于建立輸入符號串的分析樹。依賴圖如上面討論的那樣建立。從

20、依賴圖的拓撲排序中，我們可以得到計算語義規(guī)則的順序。用這個順序來計算語義規(guī)則就得到輸入符號串的翻譯。 例6.2 Real id1,id2,id3分析樹的依賴圖 每一條邊都是從序號較低的結(jié)點指向序號較高的結(jié)點。歷此，依賴圖的一個拓撲排序可以從低序號到高序號順序?qū)懗?。從這個拓撲排序中我們可以得到下列程序，用an來代表依賴圖中與序號n的結(jié)點有關(guān)的屬性：a4: = reala5: = a4 addtype (id3, entry, a5); a7: = a5; addtype (id2,entry, a7)a9: = a7 addtype (id1,entry, a9) 這些語義規(guī)則的計算將把real

21、類型填入到每個標識符對應的符號表項中。7/19/202231中南大學軟件學院 陳志剛 屬性計算方法樹遍歷的屬性計算方法 設語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語法樹，直至計算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。 一遍掃描的處理方法 與樹遍歷的屬性計算文法不同，一遍掃描的處理方法是在語法分析的同時計算屬性值，而不是語法分析構(gòu)造語法樹之后進行屬性的計算，而且無無需構(gòu)造實際的語法樹。 因為一遍掃描的處理方法與語法分析器的相互作用，它與下面兩個因素密切相關(guān)： （1）所采用的語法分析方法

22、 （2）屬性的計算次序。7/19/202232中南大學軟件學院 陳志剛例：定義定點二進制數(shù)的CFG:(1) NSS(2) SSB(3) SB(4) B0(5) B1 7/19/202233中南大學軟件學院 陳志剛 在某些情況下可用一遍掃描實現(xiàn)屬性文法的語義規(guī)則計算。也就是說在語法分析的同時完成語義規(guī)則的計算，無須明顯地構(gòu)造語法樹或構(gòu)造屬性之間的依賴圖。因為單遍實現(xiàn)對于編譯效率非常重要 具體的實現(xiàn)希望在單遍掃描中完成翻譯研究怎樣實現(xiàn)這種翻譯器。一個一般的屬性文法的翻譯器可能是很難建立的，然而有一大類屬性文法的翻譯器是很容易建立的 s-屬性 適用于自底向上的計算 L-屬性 適用于自頂向下的分析，也

23、可用于自底向上。7/19/202234中南大學軟件學院 陳志剛6.3 S屬性文法的自下而上計算S屬性文法，它只含有綜合屬性。綜合屬性可以在分析輸入符號串的同時自下而上的分析器來計算。分析器可以保存與棧中文法符號有關(guān)的綜合屬性值，每當進行歸約時，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號的屬性值來計算。S屬性文法的翻譯器通?？山柚贚R分析器實現(xiàn)。在S屬性文法的基礎上，LR分析器可以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算。7/19/202235中南大學軟件學院 陳志剛產(chǎn)生式 語義規(guī)則） （.）1 .1.） .l）1* .1. ）F .F.）（） .）ii .:.LR分析器可

24、以改造為一個翻譯器，在對輸入串進行語法分析的同時對屬性進行計算。 LR分析器增加語義棧 7/19/202236中南大學軟件學院 陳志剛 *的分析和計值過程步驟 動作 狀態(tài)棧 語義棧(值棧) 符號棧 余留輸入串） 3*） 3 *） *） *） *） *） *） *） *） * ） * ） （） * #） （） ） （） ）接受7/19/202237中南大學軟件學院 陳志剛BOTTOMUP語義處理是作類型檢查，對二目運算符的運算對象進行類型匹配審查。(LR分析）：增加語義棧 歸約時進行語義動作.例6.7GE: (1) E T+T(2) E T or T(3) T n(4) T b 7/19/202

25、238中南大學軟件學院 陳志剛ET1 + 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 := intT b T.type := bool 7/19/202239中南大學軟件學院 陳志剛 GE: (1) E T+T(2) E T or T(3) T n(4) T b7/19/202240中南大學軟件學院 陳志剛7/19/202241中南大

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

27、式翻譯成相應的后綴表達式）ETRRaddop T print(addop. Lexeme) R1|Tnum print(num.val)翻譯模式（Translation schemes）適合語法制導翻譯的另一種描述形式。翻譯模式給出了使用語義規(guī)則進行計算的次序，可把某些實現(xiàn)細節(jié)表示出來。在翻譯模式中，和文法符號相關(guān)的屬性和語義規(guī)則（這里我們也稱語義動作），用花括號括起來，插入到產(chǎn)生式右部的合適位置上。7/19/202243中南大學軟件學院 陳志剛 對于自頂向下分析，我們假設動作是在處于相同位置上的符號被展開（匹配成功）時執(zhí)行的。如圖中的第二個產(chǎn)生式中，第一個動作（對R1.i賦值）是在T被完全展

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

29、.i: = g(R.i,Y.y) R1R.s: = R1.sRR.s: = R.i7/19/202245中南大學軟件學院 陳志剛 翻譯模式1和翻譯模式2的結(jié)果是一樣的?？梢越o出串XY1Y2兩棵帶注釋的語法樹看出來，一棵是根據(jù)翻譯模式1自下而上計算屬性的。一棵是根據(jù)翻譯模式2自上而下計算的。7/19/202246中南大學軟件學院 陳志剛思考問題-把建立語法樹的翻譯模式變換成適合預測分析的模式EE1+T E.nptr:=mknode(+,E1.nptr,T.nptr)E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr)E T E.nptr:=T.nptr)7/19/202

30、247中南大學軟件學院 陳志剛 6.5 自下而上計算繼承屬性 討論在自下而上的分析過程中實現(xiàn)L屬性文法的方法。這種方法可以實現(xiàn)任何基于LL（1）文法的L屬性文法，它還可以實現(xiàn)許多（不是所有）基于LR（1）文法的L屬性文法。這種方法是S-屬性文法的自下而上翻譯技術(shù)的一般化 7/19/202248中南大學軟件學院 陳志剛自下而上分析器對產(chǎn)生式AXY的右部是通過把X和Y從分析棧中移出并用A代替它們。假設X有一個綜合屬性X.s，按照前面所介紹的方法我們把它與X一起放在分析棧中。由于X.s的值在Y以下的子樹中的任何歸約之前已經(jīng)放在棧中，這個值可以被Y繼承。也就是說，如果繼承屬性Y.i是由復寫規(guī)則Y.i:

31、 = X.s定義的，則可以在需要y.i值的地方使用X.s的值。在自下而上分析中計算屬性值時復寫規(guī)則起非常重要的作用?？聪旅胬?。7/19/202249中南大學軟件學院 陳志剛假設某翻譯模式為：DT L.in: = T.typeLTintT.type: = integerTrealT.type: = realL L1.in: = L.inL1, idaddtype(id.entry, L.in)Lidaddtype(id.entry,L.in)7/19/202250中南大學軟件學院 陳志剛回顧例6.2 Real id1,id2,id3分析樹的依賴圖 5678910T4DLLLRealtypein

32、inin3 entry2 entryentryid3id2id1.17/19/202251中南大學軟件學院 陳志剛例6.2輸入串real Real id1,id2,id3的分析過程當L的右部被歸約時，T恰好在這個右部的下面輸入 狀態(tài)(符號） 使用產(chǎn)生式Real id1,id2,id3# id1,id2,id3# real id1,id2,id3# T Treal ,id2,id3# Tid1 ,id2,id3# TL L id id2,id3# TL, ,id3# TL,id2 ,id3# TL L Li,d id3# TL, # TL,id3 # TL L Li,d # D D TL7/19

33、/202252中南大學軟件學院 陳志剛用綜合屬性代替繼承屬性 有時，改變基礎文法可能避免繼承屬性。例如，一個Pascal的說明由一標識符序列后跟類型組成，如, m, n: integer。這樣的說明的文法可由下面形式的產(chǎn)生式構(gòu)成DL：TTinteger|charLL, id|id 因為標識符由L產(chǎn)生而類型不在L的子樹中，我們不能僅僅使用綜合屬性就把類型與標識符聯(lián)系起來。事實上，如果非終結(jié)符L從第一個產(chǎn)生式中它的右邊T中繼承了類型，則我們得到的屬性文法就不是L屬性的，因此，基于這個屬性文法的翻譯工作不能在語法分析的同時進行。 7/19/202253中南大學軟件學院 陳志剛一個解決的方法是重新構(gòu)造

34、文法使類型作為標識符表的最后一個元素：Did LL, id L|: TTinteger|char 這樣，類型可以通過綜合屬性L.type進行傳遞，當通過L產(chǎn)生每個標識符時，它的類型就可以填入到符號表中。7/19/202254中南大學軟件學院 陳志剛語義制導翻譯的編譯實現(xiàn):例6.6E TEE A T E | T FTT M F T | F (E) | intA + | -M * | /7/19/202255中南大學軟件學院 陳志剛E - TEE - 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 - FTT - M F T rhs = PopOperand();lhs = PopOperand();switch (PopOperator() case MUL: PushOperand(lhs*rhs); break;case DIV: PushOperand(lhs/rhs); break;| /* empty, do nothing