第八章語法制導(dǎo)翻譯和中間代碼生成PPT課件

1、概述語義形式化 語義建模 文法模型- 屬性文法 命令式或操作式模型 - 操作語義學(xué) 應(yīng)用式模型-指稱語義學(xué) 公理式模型-公理語義學(xué)第1頁/共125頁屬性文法表達(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 第2頁/共125頁 操作語義 描述一段程序的含義是通過執(zhí)行該段程序所改變的計算機(jī)（虛擬計算機(jī)）狀態(tài)

2、來反映。這個計算機(jī)的狀態(tài)與程序執(zhí)行時的狀態(tài)相對應(yīng)：包括變量的所有值，可執(zhí)行程序本身，各種系統(tǒng)定義的內(nèi)部數(shù)據(jù)結(jié)構(gòu)。計算機(jī)里所有的寄存器的值和存儲單元的值作為計算機(jī)的狀態(tài)，用一組形式定義的操作來說明執(zhí)行一條指令相應(yīng)的狀態(tài)怎樣變化。For (expr1;expr2;expr3) expr1; . Loop:if expr2=0 goto out expr3; goto loop out: .第3頁/共125頁公理語義一個語言的每個語法成分的含義定義為公理和演繹規(guī)則，用于推導(dǎo)出該成分執(zhí)行的效果。公理語義概念是隨著程序正確性的證明而發(fā)展的。當(dāng)正確性證明能構(gòu)造時表明程序執(zhí)行它的規(guī)格說明所描述的計算。在一個

3、證明中，每一個語句之前之后都有一個邏輯表達(dá)式對程序的變量進(jìn)行約束,以此說明這個語句的含義。 一般的記號 P S Q 如果在語句S執(zhí)行前P為真，則在語句S執(zhí)行并終止后Q為真。 第4頁/共125頁 演繹規(guī)則的例子 規(guī)則 前驅(qū) 后繼 賦值：x:=expr P(expr)x:=exprP(x) While: P B S P P while B do S end P (not B) if-then-else B P S1 Q, (not B) P S2 Q P if B then S1 else S2Q 第5頁/共125頁指稱語義 指稱語義的基本概念是給每一段程序?qū)嶓w定義一個數(shù)學(xué)意義上的對象，和一個從實

4、體實例向數(shù)學(xué)意義對象的映射的函數(shù) 特點： 不但對全部程序賦予全文而且對程序設(shè)計語法 每一個語法成分短語（表達(dá)式，命令，聲明） 都給予含義。 每一個語法成分（短語）的含義是以它的自 成分的含義的術(shù)語來定義的。 即 語義結(jié)構(gòu) 平行于語法結(jié)構(gòu)。 語義函數(shù)： 程序設(shè)計語言的語義利用映射函數(shù)來證 明。 語義函數(shù)將短語映射到它的指稱。第6頁/共125頁 例： 二進(jìn)制數(shù)語言 110或10101 語法實體 指稱（自然數(shù)） 6 或 21 語義實體 二進(jìn)制數(shù)文法 Numeral:=0 :=1 := Numeral 0 :=Numeral 1 自然數(shù) Natrual=0,1,2,3, 語義函數(shù) Valuation:

5、NumeralNatural第7頁/共125頁 Valuation101 表示把Valuation施用于101 ValuationN - 把它施用于N 定義: Valuation（用四個方程)因為有四個形式numeral Valuation0 0 Valuation1 1 ValuationN0 2Valuation N ValuationN1 2Valuation N+1 所以： Valuation110=2 Valuation11 = 2 (2 Valuation1+1) =2 (2 1+1) =6第8頁/共125頁屬性文法和語法制導(dǎo)翻譯 雖然形式語義學(xué)(如指稱語義學(xué)、公理語義學(xué)、操作語義

6、學(xué)等)的研究已取得了許多重大的進(jìn)展，但目前在實際應(yīng)用中比較流行的語義描述和語義處理的方法主要還是屬性文法和語法制導(dǎo)翻譯方法 第9頁/共125頁屬性文法屬性文法(attribute grammar)是一個三元組:A=(G,V,F),其中 G:是一個上下文無關(guān)文法V:有窮的屬性集,每個屬性與文法的一個終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號相關(guān)信息，如它的類型、值、代碼序列、符號表內(nèi)容等等 .屬性與變量一樣，可以進(jìn)行計算和傳遞。屬性加工的過程即是語義處理的過程。F:關(guān)于屬性的屬性斷言或一組屬性的計算規(guī)則(稱為語義規(guī)則) . 斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終

7、結(jié)符相聯(lián)的屬性. 第10頁/共125頁屬性有兩種 繼承的和綜合的屬性屬性通常分為兩類：綜合屬性和繼承屬性。簡單地說，綜合屬性用于“自下而上”傳遞信息，而繼承屬性用于“自上而下”傳遞信息。出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計算規(guī)則進(jìn)行計算，它們由其它產(chǎn)生式的屬性規(guī)則計算或者由生計算器的參數(shù)提供。 AX1 X2 XnA的綜合屬性,計算 S(A):=f(I(X1),I(Xn)Xj的繼承屬性,計算 T(Xj):=f(I(A),. I(Xn) 1)非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號沒有繼承屬性. 2)終結(jié)符只有綜合屬性.第11頁/共125頁在

8、一個屬性文法中，對應(yīng)于每個產(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)生式右邊任何文法符號的屬性。在 兩 種 情 況 下 ， 我 們 都 說 屬 性 b 依 賴 于 屬 性c1,c2ck 。第12頁/共125頁 一個屬性文法的例子 例8.1 非終結(jié)符E、T及F都有一個綜合屬性val,符號digit有一個綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式LEn對應(yīng)的語義規(guī)則僅僅是打印由E產(chǎn)生的算

9、術(shù)表達(dá)式的值的一個過程，我們可認(rèn)為這條規(guī)則定義了L的一個虛屬性。某些非終結(jié)符加下標(biāo)是為了區(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.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval產(chǎn) 生 式第13頁/共125頁設(shè)表達(dá)式為35+4，則語義動作打印數(shù)值19.LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.v

10、al=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹第14頁/共125頁繼承屬性 一個結(jié)點的繼承屬性值是由此結(jié)點的父結(jié)點和/或兄弟結(jié)點的某些屬性來決定的。例8.2 繼承屬性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)第15頁/共125頁 DL.in= realL.in= rea

11、lL.in= realT.type=realrealid2id1id3.Real id1,id2,id3，第16頁/共125頁例8.3P DSD var V; D | S V := E; S | V x | y | z現(xiàn)在使用兩個屬性，name和dl，每當(dāng)一個新的變量聲明時，就把它的name屬性附給它，name屬性是綜合屬性。將所聲明的變量都放到一個變量名字清單中（用語義函數(shù)addlist實現(xiàn)），用屬性dl綜合聲明塊中聲明的所有變量。然后這個dl屬性又作為繼承屬性傳到后面的語句部分，每個語句用到的變量都要進(jìn)行審查，看它是否在變量名字清單中 P DS S.dl = D.dlD1 var V; D

12、2 | D1.dl = addlist(V.name, D2.dl) | D1.dl = NULLS1 V := E; S2 | check(V.name, S1.dl); S2.dl = S1.dlV x | y | z V.name = x | V.name = y | V.name = z第17頁/共125頁var x；var y；x:=e； P D dl=x,y S dl=x,yvar V ； D dl=y V := e ； S x var V ； D dl= y y 第18頁/共125頁語法制導(dǎo)的翻譯 一個翻譯是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串對是源程序和目標(biāo)程

13、序。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法樹，匯編語言）設(shè)是輸入字母表且是輸出字母表。定義由語言 L1 *到語言L2 *的一個翻譯是由*到 *的一個關(guān)系T,使得T的定義域為L1且T的值域為L2 。 使(x,y) T的句子y叫做x的一個輸出.第19頁/共125頁語法制導(dǎo)的翻譯 直觀地說，一個語法制導(dǎo)翻譯的基礎(chǔ)是一個文法，其中翻譯成分依附在每一產(chǎn)生式上。 例8.4： 下列翻譯模式，它定義翻譯，即對每個輸入x，其輸出y是x的逆轉(zhuǎn)。定義此翻譯的規(guī)則是 產(chǎn)生式 翻譯規(guī)則 (1)s0s(2)s1s (3)s (1)s=s0(2)s=s1 (3)s=

14、 第20頁/共125頁 輸入輸出對可由(,)表示，其中是輸入句子形式而是輸出句子形式。 (S,S)開始用產(chǎn)生式s0s來擴(kuò)展得到(0S,S0). 再用一次規(guī)則(1)，得到(00S,S00)。 再用規(guī)則(2)，就得到(001S,S100). 然后應(yīng)用規(guī)則(3)并得到(001,100)。第21頁/共125頁 例8.5： 把下述產(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ī)則第22頁/共125頁 確定輸入a+aa的輸出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,

15、FT+) (a+T,aT+) (a+TF,aFF+) (a+FF,aFF+) (a+aF,aaF+) (a+aa,aaa+)第23頁/共125頁 定義： 一個語法制導(dǎo)的翻譯模式是一個五元組T=(N, , ， R,S),其中 (1) N是非終結(jié)符的有限集。 (2) 是有限的輸入字母表。 (3) 是有限的輸出字母表。 (4) R是形如A, 的規(guī)則的有限集,其中 (N )*, (N )*且 中那組非終結(jié)符是 中那組非終結(jié)符的置換。 (5) S是N中一個特別的非終結(jié)符，即開始符。第24頁/共125頁 定義： 若T= (N, , , R,S)是SDTS, (T)則稱為語法制導(dǎo)的翻譯(SDT)，文法Gi=

16、(N, ,P,S)，其中P=A|A, 屬于R)，稱為SDTS T的基礎(chǔ)（或輸入）文法。文法G0=( N, ,P ,S), ，其中P =A | A, 屬于R ，稱為T的輸出文法。 把語法制導(dǎo)的翻譯方法看成是將輸入文法Gi中的推導(dǎo)樹變換成輸出文法G0中的推導(dǎo)樹。給了輸入句子x，可以按如下方式得到x的一個翻譯：先為推導(dǎo)x構(gòu)造一棵推導(dǎo)樹，再變換該樹到輸出文法中的一棵樹，然后取此輸出樹的邊緣作為x的一個翻譯。第25頁/共125頁語義制導(dǎo)翻譯中的規(guī)則A, 對應(yīng)于每一個文法產(chǎn)生式A 都有與之相關(guān)聯(lián)的一套語義描述屬性文法(attribute grammar)是一個三元組:A=(G,V,F) 屬性文法可以看作是

17、關(guān)于語言翻譯的高級規(guī)范說明，其中隱去實現(xiàn)細(xì)節(jié)，使用戶從明確說明翻譯順序的工作中解脫出來第26頁/共125頁語法制導(dǎo)翻譯實現(xiàn)從概念上講，語法制導(dǎo)翻譯即基于屬性文法的處理過程通常是這樣的：對單詞符號串進(jìn)行語法分析，構(gòu)造語法分析樹，然后根據(jù)需要遍歷語法樹并在語法樹的各結(jié)點處按語義規(guī)則進(jìn)行計算輸入符號串 分析樹 屬性依賴圖 語義規(guī)則的計算順序第27頁/共125頁依賴圖由稱為依賴圖的一個有向圖 描述分析樹中的繼承屬性和屬性中間的相互依賴關(guān)系。 依賴圖的構(gòu)造算法： for分析樹中每一個結(jié)點n do for 結(jié)點的文法符號的每一個屬性a do 為a在依賴圖中建立一個結(jié)點； for 分析樹中每一個結(jié)點n do

18、 for結(jié)點n所用產(chǎn)生式對應(yīng)的每一個語義規(guī)則 b:=f(c1,c2,ck) do for i :=1 to k do 從ci結(jié)點到b結(jié)點構(gòu)造一條有向邊 第28頁/共125頁依賴圖-例8.2 例8.2 繼承屬性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)第29頁/共125頁例8.2 Real id1,id2,id3分析樹的依賴圖 5678910T4DLLLRea

19、ltypeininin3 entry2 entryentryid3id2id1.1第30頁/共125頁依賴圖中的結(jié)點由數(shù)字來標(biāo)識。從代表T.type的結(jié)點4有一條有向邊連到代表L.in的結(jié)點5，因為根據(jù)產(chǎn)生式ETL的語義規(guī)則L1.in=L.in，可知L1.in依賴于L.in，所以有兩條向下的有向邊分別進(jìn)入結(jié)點7和9。每一個與L產(chǎn)生式有關(guān)的語義規(guī)則addtype(id. Entry, L.in)都產(chǎn)生一個虛屬性，結(jié)點 6、8和10都是為這些虛屬性構(gòu)造的。第31頁/共125頁良定義的屬性文法。 很顯然，一條求值規(guī)則只有在其各變元值均已求得的情況下才可以使用。但有時候可能會出現(xiàn)一個屬性對另一個屬性的

20、循環(huán)依賴關(guān)系。從事貿(mào)易如，p、c1、c2都是屬性，若有下求值規(guī)則：p: = f1(c1)、c1: = f2(c2)、c2: = f3(p)時，就無法對p求值。如果一屬性文法不存在屬性之間的循環(huán)依賴關(guān)系，那么稱該文法為良定義的。為了設(shè)計編譯程序，我們只處理良定義的屬性文法。 第32頁/共125頁屬性的計算順序一個有向非循環(huán)圖的拓?fù)湫蚴菆D中結(jié)點的任何順序m1, m2, , mk，使得邊必須是從序列中前面的結(jié)點指向后面的結(jié)點。也就是說，如果mimj是mi到mj的一條邊，那么在序列中mi必須出現(xiàn)在mj之前。 一個依賴圖的任何拓?fù)渑判蚨冀o出一個分析樹中結(jié)點的語義規(guī)則計算的有效順序。這就是說，在拓?fù)渑判蛑?/p>

21、，在一個結(jié)點，語義規(guī)則b:=f(c1,c2,ck)中的屬性c1,c2,ck在計算b以前都是可用的。第33頁/共125頁屬性文法說明的翻譯是很精確的。最基本的文法用于建立輸入符號串的分析樹。依賴圖如上面討論的那樣建立。從依賴圖的拓?fù)渑判蛑校覀兛梢缘玫接嬎阏Z義規(guī)則的順序。用這個順序來計算語義規(guī)則就得到輸入符號串的翻譯。例8.2Real id1,id2,id3分析樹的依賴圖每一條邊都是從序號較低的結(jié)點指向序號較高的結(jié)點。歷此，依賴圖的一個拓?fù)渑判蚩梢詮牡托蛱柕礁咝蛱栱樞驅(qū)懗?。從這個拓?fù)渑判蛑形覀兛梢缘玫较铝谐绦颍胊n來代表依賴圖中與序號n的結(jié)點有關(guān)的屬性：a4: = reala5: = a4 a

22、ddtype (id3, entry, a5); a7: = a5; addtype (id2,entry, a7)a9: = a7 addtype (id1,entry, a9)這些語義規(guī)則的計算將把real類型填入到每個標(biāo)識符對應(yīng)的符號表項中。第34頁/共125頁 屬性計算方法 樹遍歷的屬性計算方法設(shè)語法樹已經(jīng)建立起了，并且樹中已帶有開始符號的繼承屬性和終結(jié)符的綜合屬性。然后以某種次序遍歷語法樹，直至計算出所有屬性。最常用的遍歷方法是深度優(yōu)先，從左到右的遍歷方法。如果需要的話，可使用多次遍歷（或稱遍）。 一遍掃描的處理方法與樹遍歷的屬性計算文法不同，一遍掃描的處理方法是在語法分析的同時計算

23、屬性值，而不是語法分析構(gòu)造語法樹之后進(jìn)行屬性的計算，而且無無需構(gòu)造實際的語法樹。因為一遍掃描的處理方法與語法分析器的相互作用，它與下面兩個因素密切相關(guān)：（1）所采用的語法分析方法（2）屬性的計算次序。第35頁/共125頁例：定義定點二進(jìn)制數(shù)的CFG:(1) NSS(2) SSB(3) SB(4) B0(5) B1 第36頁/共125頁 非終結(jié)符N表示整個二進(jìn)制數(shù)的數(shù)值，綜合屬性v附加在N上：N v 非終結(jié)符B 表示一個二進(jìn)制數(shù)字，它有自己的值v ，但該值分配給N的值與它的位置有關(guān)，是與2成比例，比例因子f是從S繼承的屬性,所以：B v f 非終結(jié)符S 表示一個二進(jìn)制數(shù)字串，它也有值，但該值與串

24、的位置有關(guān)，與f有關(guān)與串的長度l有關(guān): S f v l第37頁/共125頁構(gòu)造數(shù)值的屬性斷言可以如下: N vS f1 v 1 l1 S f 2 v 2 l2 v=v1+v2; f 1 =1; f2=2-l2 S f v l S f1v1 l 1B f 2v2 f1=2f ; f 2=f; v=v 1+v2;l=l1+1 B f v l=1 B f v0 v=0 1 v=f第38頁/共125頁 N v S i1 l1 “” S i2 l2 v= i1+ 2-l2 i2 S i l S i1 l 1 Bi2 i =2 i1+ i2; ;l=l1+1 B i l=1 B i “0” i =0 “1

25、” i =1第39頁/共125頁 在某些情況下可用一遍掃描實現(xiàn)屬性文法的語義規(guī)則計算。也就是說在語法分析的同時完成語義規(guī)則的計算，無須明顯地構(gòu)造語法樹或構(gòu)造屬性之間的依賴圖。因為單遍實現(xiàn)對于編譯效率非常重要 具體的實現(xiàn)希望在單遍掃描中完成翻譯研究怎樣實現(xiàn)這種翻譯器。一個一般的屬性文法的翻譯器可能是很難建立的，然而有一大類屬性文法的翻譯器是很容易建立的 s-屬性 適用于自底向上的計算 L-屬性 適用于自頂向下的分析，也可用于自底向上。 第40頁/共125頁S屬性文法的自下而上計算S屬性文法，它只含有綜合屬性。 綜合屬性可以在分析輸入符號串的同時自下而上的分析器來計算。分析器可以保存與棧中文法符號

26、有關(guān)的綜合屬性值，每當(dāng)進(jìn)行歸約時，新的屬性值就由棧中正在歸約的產(chǎn)生式右邊符號的屬性值來計算。 S屬性文法的翻譯器通?？山柚贚R分析器實現(xiàn)。在S屬性文法的基礎(chǔ)上，LR分析器可以改造為一個翻譯器，在對輸入串進(jìn)行語法分析的同時對屬性進(jìn)行計算。第41頁/共125頁產(chǎn)生式 語義規(guī)則） （.）1 .1.） .l）1* .1. ）F .F.）（） . ）ii .:.LR分析器可以改造為一個翻譯器，在對輸入串進(jìn)行語法分析的同時對屬性進(jìn)行計算。 LR分析器增加語義棧 第42頁/共125頁 *的分析和計值過程步驟 動作 狀態(tài)棧 語義棧(值棧) 符號棧 余留輸入串） 3*） 3 *） *） *） *） *） *）

27、 *） *） * ） * ） （） * #） （） ） （） ）接受第43頁/共125頁BOTTOMBOTTOMUPUP語義處理是作類型檢查，對二目運(yùn)算符的運(yùn)算對象進(jìn)行類型匹配審查。(LR(LR分析）：增加語義棧 歸約時進(jìn)行語義動作. .例8.7GE: (1) E T+TT+T(2) E (2) E T or TT or T(3) T (3) T n n(4) T (4) T b b 第44頁/共125頁E ET T1 1 + T+ T2 2 if T if T1 1. .type = type = intint and T and T2 2. .type= type= intint then

28、 E then E. .type :=type :=intint else error else error E E T T1 1 or Tor T2 2 if T if T1 1. .type = type = boolbool and T and T2 2. .type= type= boolbool then E then E. .type :=type :=boolbool else error else error T T n T.type := int n T.type := intT T b T.type := bool b T.type := bool 第45頁/共125頁w

29、=n + n# 4ninto#-2Tinto#-5+-2Tinto#-4nint5+-2Tinto#-6Tint5+-2Tinto#-1Eint0#- GE:的 LR(0)分分析析表表 action GOTO 狀狀態(tài)態(tài)+ o n b # E T 0 S4 S3 1 2 1 acc 2 s5 s7 3 r4 r4 r4 r4 r4 4 r3 r3 r3 r3 r3 5 s4 s3 6 6 r1 r1 r1 r1 r1 7 s4 s3 8 8 r2 r2 r2 r2 r2 GE: (1) E T+TT+T(2) E (2) E T or TT or T(3) T (3) T n n(4) T (4

30、) T b b第46頁/共125頁w =n +b4ninto#-2Tinto#-5+-2Tinto#-3bbool5+-2Tinto#-6Tbool5+-2Tinto#-1Eerroro#-第47頁/共125頁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）這種自上而下

31、分析文法的分析過程，從概念上說可以看成是深度優(yōu)先建立語法樹的過程，因此，我們可以在自上而下語法分析的同時實現(xiàn)L屬性文法的計算。第48頁/共125頁例（中綴表達(dá)式翻譯成相應(yīng)的后綴表達(dá)式）ETRRaddop T print(addop. Lexeme) R1|Tnum print(num.val)翻譯模式（Translation schemes）適合語法制導(dǎo)翻譯的另一種描述形式。翻譯模式給出了使用語義規(guī)則進(jìn)行計算的次序，可把某些實現(xiàn)細(xì)節(jié)表示出來。在翻譯模式中，和文法符號相關(guān)的屬性和語義規(guī)則（這里我們也稱語義動作），用花括號括起來，插入到產(chǎn)生式右部的合適位置上。第49頁/共125頁輸入串95 + 2

32、的語法樹，每個語義動作都作為相應(yīng)產(chǎn)生式左部符號的結(jié)點的兒子，按深度優(yōu)先次序執(zhí)行圖中的動作后，打印輸出952+。 ET R9 print(9) - T print(-) R 5 print(5) + T print(+) R 2 print(2) 第50頁/共125頁L屬性文法在自頂向下分析中的實現(xiàn) 帶左遞歸的文法的翻譯模式EE1 + T E.val: = E1.val + T.valEE1T E.val: = E1.valT.valET E.val: = T.valT(E) T.val: = E.valTnum T.val: = num.val第51頁/共125頁消除左遞歸的同時考慮屬性，構(gòu)造

33、新的翻譯模式 ET R.i: =T.val R E.val: = R.sR + T R1.i:=R.i + T.val R1 R.s: = R1.sR- T R1.i: = R.i -T.val R1 R.s: = R1.sR R.s: = R.iT(E) T.val: =E.valTnum T.val: = num.val第52頁/共125頁計算表達(dá)式9-5+2.ER.i=9T.val=5T.val=9R.i=4 R.i=6T.val=2num.val=9num.val=5num.val=2_+第53頁/共125頁在上頁的翻譯模式中，每個數(shù)都是由T產(chǎn)生的，并且T.val的值就是由屬性num.

34、val給出的數(shù)的詞法值。子表達(dá)式95中的數(shù)字9是由最左邊的T生成的，但是減號和5是由根的右子結(jié)點R生成的。繼承屬性R.i從T.val得到值9。計算95并把結(jié)果4傳遞到中間的R結(jié)點這是通過產(chǎn)生式中嵌入的下面動作實現(xiàn)：R1.i: = R.iT.val類似的動作把2加到95的值上，在最下面的R結(jié)點處產(chǎn)生結(jié)果R.i6。這個結(jié)將成為根結(jié)點處E.val的值,R的綜合屬性s在圖中沒有表示出來，它用來向上復(fù)制這一結(jié)果一直到樹根。 第54頁/共125頁對于自頂向下分析，我們假設(shè)動作是在處于相同位置上的符號被展開（匹配成功）時執(zhí)行的。如圖中的第二個產(chǎn)生式中，第一個動作（對R1.i賦值）是在T被完全展開成終結(jié)符號后

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

36、1R.s: = R1.sR R.s: = R.i第56頁/共125頁翻譯模式1和翻譯模式2的結(jié)果是一樣的?？梢越o出串XY1Y2兩棵帶注釋的語法樹看出來，一棵是根據(jù)翻譯模式1自下而上計算屬性的。一棵是根據(jù)翻譯模式2自上而下計算的。第57頁/共125頁 AA1YA.a: = g(A1。a, Y.y)AX A.a: = f(X.x)A.a=g(g(f(X.x,Y1.y),Y2.y)A.a=g(f(X.x,Y1.y) Y2A.a=f(X.x) Y1 X A A YA Y X第58頁/共125頁 AXR.i: = f(X.x) RYR1.i: = g(R.i),Y.y) R A.a: =R.s R1R.

37、s: = R1.s AXR RYR AX R Y1 R Y2 R AX R.i=f(X.x) Y1 R.i=g(f(X.x,Y1.y) Y2 R.i=g(g(f(X.x,Y1.y),Y2.y) 第59頁/共125頁思考問題-把建立語法樹的翻譯模式變換成適合預(yù)測分析的模式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)第60頁/共125頁 自下而上計算繼承屬性 討論在自下而上的分析過程中實現(xiàn)L屬性文法的方法。這種方法可以實現(xiàn)任何基于LL（1）文法的L屬性

38、文法，它還可以實現(xiàn)許多（不是所有）基于LR（1）文法的L屬性文法。這種方法是S-屬性文法的自下而上翻譯技術(shù)的一般化 第61頁/共125頁 自下而上分析器對產(chǎn)生式AXY的右部是通過把X和Y從分析棧中移出并用A代替它們。假設(shè)X有一個綜合屬性X.s，按照前面所介紹的方法我們把它與X一起放在分析棧中。 由于X.s的值在Y以下的子樹中的任何歸約之前已經(jīng)放在棧中，這個值可以被Y繼承。也就是說，如果繼承屬性Y.i是由復(fù)寫規(guī)則Y.i: = X.s定義的，則可以在需要y.i值的地方使用X.s的值。在自下而上分析中計算屬性值時復(fù)寫規(guī)則起非常重要的作用。看下面例子。第62頁/共125頁假設(shè)某翻譯模式為：DTL.in

39、: = T.typeLTintT.type: = integerTreal T.type: = realLL1.in: = L.inL1, idaddtype (id.entry, L.in)Lidaddtype (id.entry, L.in)第63頁/共125頁回顧例8.2 Real id1,id2,id3分析樹的依賴圖 5678910T4DLLLRealtypeininin3 entry2 entryentryid3id2id1.1第64頁/共125頁例8.2輸入串real Real id1,id2,id3的分析過程當(dāng)L的右部被歸約時，T恰好在這個右部的下面輸入 狀態(tài)(符號） 使用產(chǎn)生式

40、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 TL第65頁/共125頁 用綜合屬性代替繼承屬性有時，改變基礎(chǔ)文法可能避免繼承屬性。例如，一個Pascal的說明由一標(biāo)識符序列后跟類型組成，如, m, n: integer。這樣的說明的文法可由下面形式的產(chǎn)生式構(gòu)成DL：TTinteger|charLL, id|i

41、d因為標(biāo)識符由L產(chǎn)生而類型不在L的子樹中，我們不能僅僅使用綜合屬性就把類型與標(biāo)識符聯(lián)系起來。事實上，如果非終結(jié)符L從第一個產(chǎn)生式中它的右邊T中繼承了類型，則我們得到的屬性文法就不是L屬性的，因此，基于這個屬性文法的翻譯工作不能在語法分析的同時進(jìn)行。 第66頁/共125頁一個解決的方法是重新構(gòu)造文法使類型作為標(biāo)識符表的最后一個元素：Did LL, id L|: TTinteger|char這樣，類型可以通過綜合屬性L.type進(jìn)行傳遞，當(dāng)通過L產(chǎn)生每個標(biāo)識符時，它的類型就可以填入到符號表中。 第67頁/共125頁語義制導(dǎo)翻譯的編譯實現(xiàn): :例8.6E TEE A T E | T FTT M F

42、T | F (E) | intA + | -M * | /第68頁/共125頁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 MU

43、L: PushOperand(lhs*rhs); break;case DIV: PushOperand(lhs/rhs); break;| /* empty, do nothing */ A - + PushOperator(ADD);| - PushOperator(SUB);M - * PushOperator(MUL);| / PushOperator(DIV);F - int PushOperand(intval);| (E) /* handled during parsing of E */ 第69頁/共125頁parse 2 + 4 * 3:分析動作橋 分析棧 運(yùn)算對象棧 運(yùn)算符

44、棧Predict E TE E#Predict T FT TE#Predict F int FTE#Match int intTE#Predict T TE# 2Predict E ATE ATE # 2Predict A + ATE# 2Match + +TE# 2Predict T FT TE# 2 +Predict F int FTE# 2 +Match int intTE# 2 +Predict T MFT TE# 4 2 +Predict M * MFTE# 4 2 +Match * *FTE# 4 2 +Predict F int FTE# 4 2 * +Match int int

45、TE# 4 2 * +Predict T TE# 3 4 2 * +Predict E E# 12 2 +Success! # 14第70頁/共125頁Yacc或bison作為編譯程序的生成工具，利用的就是語法制導(dǎo)翻譯方法。它使用符號$表示產(chǎn)生式左端的屬性，$n表示存取產(chǎn)生式右端第n個文法符號相聯(lián)的屬性如例8.3作為Yacc的輸入，可寫成：P DS $2.dl=$1.dlD1 var V； D$.dl=addlist($2.name，$4.dl) | $.dl=nullS1 V:=e； Scheck($1.name，$.dl)； $5.dl=$.dl |V x $.name=x |y $.na

46、me=y |z $.name=z第71頁/共125頁如果數(shù)據(jù)結(jié)構(gòu)attribute定義屬性name和dl，可以具體化為：type struct_attribute char *name； struct_attribute *list； attribute； P DS $2.list=$1.listD1 var V； D$.list=add_to_list($2.name，$4.list) | $.list=nullS1 V:=e； Scheck($1.name，$.list)； $5.list=$.list |V x $.name=x |y $.name=y |z $.name=z第72頁/共

47、125頁語義分析 語義分析 屬性文法和語法制導(dǎo)翻譯方法和技術(shù)應(yīng)用于語義分析中。第73頁/共125頁語義分析通常包括：（1）類型檢查。驗證程序中執(zhí)行的每個操作是否遵守語言的類型系統(tǒng)的過程.，編譯程序必須報告不符合類型系統(tǒng)的信息。（2）控制流檢查?？刂屏髡Z句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語言中break語句使控制跳離包括該語句的最小while、for或switch語句。如果不存在包括它的這樣的語句，則就報錯。（3）一致性檢查。在很多場合要求對象只能被定義一次。例如Pascal語言規(guī)定同一標(biāo)識符在一個分程序中只能被說明一次，同一case語句的標(biāo)號不能相同，枚舉類型的元素不能重復(fù)出現(xiàn)等等。（4

48、）相關(guān)名字檢查。有時，同一名字必須出現(xiàn)兩次或多次。例如，Ada 語言程序中，循環(huán)或程序塊可以有一個名字，出現(xiàn)在這些結(jié)構(gòu)的開頭和結(jié)尾，編譯程序必須檢查這兩個地方用的名字是相同的。 (5)名字的作用域分析第74頁/共125頁類型和聲明（Types and declarations）一個類型是一組值和在這些值上的一組操作，程序設(shè)計語言中有三種類型:基本類型：int, float, double, char, bool等等. 也可能允許在基本類型基礎(chǔ)上用戶自己定義的類型，如枚舉型.復(fù)合類型：數(shù)組,指針，記錄/結(jié)構(gòu)/聯(lián)合,類等等.這些類型由基本類型構(gòu)成.復(fù)雜類型：鏈表，棧，隊，樹，堆，表格等等.可以把它

49、們組織成ADT. 一個語言不一定支持這類高級的抽象。聲明是程序中的一個語句,是把數(shù)據(jù)對象的名稱和類型，以及生命周期信息傳給編譯，聲明的地方傳遞生命周期信息也有些語言允許聲明初始化變量。如:double calculate(int a, double b); / function prototype int x = 0; / global variables available throughout double y; / the program int main() int m3; / local variables available only in main char *n; . 第75頁

50、/共125頁強(qiáng)類型的 -任何數(shù)據(jù)類型都可以在 編譯時確定弱類型的. 進(jìn)行類型檢查的時間：編譯時，運(yùn)行時，或者兩者結(jié)合.靜態(tài)類型檢查 編譯時進(jìn)行類型檢查動態(tài)類型檢查，將類型信息并到運(yùn)行時每個數(shù)據(jù)單元中.隱含類型轉(zhuǎn)換.第76頁/共125頁P(yáng)D；EDD；|id:TTchar | integer | aray numof T| TEliteral|num | id| E mod E| E E|EP代表程序；D代表說明；E代表表達(dá)式。如程序語句：key: integer;key mod 1999語言本身提供兩種基本類型：char和integer。除此之外還有缺省的基本類型type_ error和void

51、。假定所有數(shù)組都從下標(biāo)1開始第77頁/共125頁確定標(biāo)識符類型的部分翻譯模式（1）PD；E（2）DD；D（3）Did:T addtype (id. Entry, T. type)（4）Tchar T. Type:= char（5）Tinteger T. Type:= integer（6）TT1 T. Type:= pointer (T1. type)（7）Tarray numof T1 T . T y p e : = a r r a y ( n u m . V a l , T1.type)第78頁/共125頁 語句的類型檢查的翻譯模式Sid:=E if id. Type= E. Type Th

52、en S. Type:= void else S. Type:= type_ errorSif E then S1 if E. type= boolean then S. Type:= S1. type else S. type := type_ errorSwhile E do S1 if E. type= boolean Then S. type:= S1. Type else S. type:= type_ error第79頁/共125頁設(shè)計類型檢查程序1.辨認(rèn)語言中可用的類型2.辨認(rèn)具有類型的語言結(jié)構(gòu)3.辨認(rèn)語言的語義規(guī)則第80頁/共125頁In Decaf base types ：i

53、nt, double, bool, string compound types ：arrays and classes. An array can be made of any type (either a base type, a class, or out of other arrays).Classes are a bit special in that the class name must be declared before it can be used in a declaration. ADTs can be constructed using classes, but the

54、y arent handled in any way differently than classes, so we dont need to consider them specially.第81頁/共125頁In Decaf the relevant language constructs constants, every constant has an associated type. A scanner tells us these types as well as the associated lexeme. variables ：all variables (global, loc

55、al, and instance) must have a declared type of either int, double, bool, string, array, or class. functions ：functions have a return type, and each parameter in the function definition has a type, as does each argument in a function call. expressions an expression can be a constant, variable, functi

56、on call, or some operator (binary or unary) applied to expressions. Each of the various expressions have a type based on the type of the constant, variable, return type of the function, or type of operands. The other language constructs in Decaf (if, while, Print, assignments, etc.) also have types

57、associated with them, because somewhere in each of these we find an expression.第82頁/共125頁The semantic rules govern what types are allowable in the various language constructs. In Decaf, operand to a unary minus must either be double or int, the expression used in a loop test must be of bool type, ge

58、neral rules, such as all variables must be declared before use, all classes are global, and so on. arrays: the index used in an array selection expression must be of integer type expressions: the two operands to % must both be int. The result type is int. this is bound to the receiving object within

59、 class scope, it is an error outside class scope variables ： a variable declared of class type must refer to a defined class name functions ： the type of each actual argument in a function call must be compatible with the formal parameter。 if a function has a void return type, it may only use the em

60、pty return statement第83頁/共125頁實現(xiàn)類型檢查程序. 首先，將每個名字（標(biāo)識符）的類型信息記錄在符號表中第84頁/共125頁作用域檢查 作用域和可見性基本作用域規(guī)則（lexical rule) int a;void Binky(int a) int a;a = 2;. 作用域檢查實現(xiàn)：1每個作用域一個獨(dú)立的符號表，這些符號表組織成作用域棧2對所有作用域的全局符號表，每個作用域有一個作用域號？各自的優(yōu)缺點，PL/0用的是哪種第85頁/共125頁運(yùn)算符（函數(shù)）的重載 多態(tài)函數(shù)重載運(yùn)算符（overloading operator）根據(jù)上下文可以執(zhí)行不同的運(yùn)算。是重載符號，在