1、第7章 語(yǔ)法制導(dǎo)翻譯和中間代碼生成,7.1 屬性文法 7.2 語(yǔ)法制導(dǎo)翻譯 7.3 中間代碼的形式 7.4 一些語(yǔ)句的翻譯,語(yǔ)義處理,編譯程序的語(yǔ)義處理功能： 1、審查每個(gè)語(yǔ)法結(jié)構(gòu)的靜態(tài)語(yǔ)義，即驗(yàn)證語(yǔ)法結(jié)構(gòu)合理的程序是否真正有意義。稱靜態(tài)語(yǔ)義審查。 2、如果靜態(tài)語(yǔ)義正確，要執(zhí)行真正的翻譯，即要么生成一種中間代碼形式，要么生成實(shí)際的目標(biāo)代碼。稱解釋執(zhí)行動(dòng)態(tài)語(yǔ)義、生成代碼。,靜態(tài)語(yǔ)義分析通常包括, 類(lèi)型檢查。驗(yàn)證程序中執(zhí)行的每個(gè)操作是否遵守語(yǔ)言的類(lèi)型系統(tǒng)的過(guò)程.編譯程序必須報(bào)告不符合類(lèi)型系統(tǒng)的信息。 控制流檢查?？刂屏髡Z(yǔ)句必須使控制轉(zhuǎn)移到合法的地方。例如，在C語(yǔ)言中break語(yǔ)句使控制跳離包括該語(yǔ)

2、句的最小while、for或switch語(yǔ)句。如果不存在包括它的這樣的語(yǔ)句，則就報(bào)錯(cuò)。 一致性檢查。在很多場(chǎng)合要求對(duì)象只能被定義一次。例如Pascal語(yǔ)言規(guī)定同一標(biāo)識(shí)符在一個(gè)分程序中只能被說(shuō)明一次，同一case語(yǔ)句的標(biāo)號(hào)不能相同，枚舉類(lèi)型的元素不能重復(fù)出現(xiàn)等等。 相關(guān)名字檢查。有時(shí)，同一名字必須出現(xiàn)兩次或多次。例如，Ada 語(yǔ)言程序中，循環(huán)或程序塊可以有一個(gè)名字，出現(xiàn)在這些結(jié)構(gòu)的開(kāi)頭和結(jié)尾，編譯程序必須檢查這兩個(gè)地方用的名字是相同的。 名字的作用域分析,語(yǔ)義處理方法,對(duì)應(yīng)每一個(gè)產(chǎn)生式編制一個(gè)語(yǔ)義子程序，當(dāng)一個(gè)產(chǎn)生式獲得匹配時(shí)，調(diào)用相應(yīng)的語(yǔ)義子程序?qū)崿F(xiàn)語(yǔ)義檢查與翻譯。 在產(chǎn)生式的右部的適當(dāng)位置，

3、插入相應(yīng)的語(yǔ)義動(dòng)作，按照分析的進(jìn)程，執(zhí)行遇到的語(yǔ)義動(dòng)作。 語(yǔ)義可以看成是相應(yīng)文法符號(hào)的屬性,雖然形式語(yǔ)義學(xué)(如指稱語(yǔ)義學(xué)、公理語(yǔ)義學(xué)、操作語(yǔ)義學(xué)等)的研究已取得了許多重大的進(jìn)展，但目前在實(shí)際應(yīng)用中比較流行的語(yǔ)義描述和語(yǔ)義處理的方法主要還是屬性文法和語(yǔ)法制導(dǎo)翻譯方法.,7.1 屬性(Attribute)文法(1),屬性文法是Knuth在1968年提出的. 所謂屬性，其涉及的概念比較廣泛，常用以描述事物或人的特征、性質(zhì)，品質(zhì)等等。比如，談到一個(gè)物體，可以用“顏色”描述它，談起某人，可以使用“有幽默感”來(lái)形容他。對(duì)編譯程序使用的語(yǔ)法樹(shù)的結(jié)點(diǎn)，可以用“類(lèi)型”、“值”或“存儲(chǔ)位置”來(lái)描述它。 它是在上下

4、文無(wú)關(guān)文法的基礎(chǔ)上，為每個(gè)文法符號(hào)(終結(jié)符或非終結(jié)符)配備若干相關(guān)的“值”（稱為屬性）。,屬性(Attribute)文法(2),1、屬性文法定義,屬性文法(attribute grammar)是一個(gè)三元組:A=(G,V,F),其中 G:是一個(gè)上下文無(wú)關(guān)文法 V:有窮的屬性集,每個(gè)屬性與文法的一個(gè)終結(jié)符或非終結(jié)符相連,這些屬性代表與文法符號(hào)相關(guān)信息，如它的類(lèi)型、值、代碼序列、符號(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é)符或非終

5、結(jié)符相聯(lián)的屬性. 編譯程序的靜態(tài)語(yǔ)義審查工作就是驗(yàn)證關(guān)于所編譯的程序的斷言是否全部為真。,屬性文法舉例,有文法G為：ET1 + T2|T1 or T2Tnum|true|false（因?yàn)門(mén)在同一個(gè)產(chǎn)生式里出現(xiàn)了兩次，使用上角標(biāo)將它們區(qū)分開(kāi)。）對(duì)輸入串3+4的語(yǔ)法樹(shù)如圖7.1（A）,屬性文法記號(hào)中常使用Nt的形式表示與非終結(jié)符N相聯(lián)的屬性t。比如可把對(duì)上面表達(dá)式的類(lèi)型檢查的屬性文法寫(xiě)成圖7.2的形式。,圖7.2類(lèi)型檢查的屬性文法 ET1+T2 T1.tintANDT2.tintET1orT2 T1.tboolAND T2.tboolTnumT.tintTtrueT.tboolTfalseT.tb

6、ool,與每個(gè)非終結(jié)符T相聯(lián)的有屬性t，t要么是int，要么是bool。 與非終結(jié)符E的產(chǎn)生式相聯(lián)的斷言指明：兩個(gè)T的屬性必須相同。,2、屬性分類(lèi)（1）,設(shè) AX1X2Xn 為一個(gè)產(chǎn)生式 A.s=f(c1,c2,ck) c1,c2,ck是X1，X2，Xn的屬性 A.s是從其子結(jié)點(diǎn)的屬性值計(jì)算出來(lái)的 這種屬性叫做綜合(Synthesized)屬性 適應(yīng)：歸約分析,例: 簡(jiǎn)單算術(shù)表達(dá)式求值的語(yǔ)義描述,文法描述 L E E E1 + T | T T T1 * F | F F ( E ) | digit ？如何描述翻譯過(guò)程,每個(gè)非終結(jié)符都有一個(gè)整數(shù)值的稱作val的屬性。,屬性文法（語(yǔ)法制導(dǎo)定義）,與L

7、 E相連的語(yǔ)義規(guī)則是一個(gè)過(guò)程，打印E的值，理解為L(zhǎng)的屬性是虛的或空的。 E,T,F的屬性val都為綜合屬性。 lexval 是單詞 digit 的屬性。,屬性分類(lèi)（2）,設(shè)AX1X2Xn為一個(gè)產(chǎn)生式 B.in=f(c1,c2,ck) B為Xi， c1,c2,ck是A, X1，X2，Xi-1的屬性 這種屬性叫做繼承(Inherited)屬性,例：說(shuō)明語(yǔ)句,說(shuō)明語(yǔ)句的文法 D T L T int T real L L1,id L id,將類(lèi)型信息作為類(lèi)型描述 T 的綜合屬性 type 和變量表 L 的繼承屬性 in。,語(yǔ)法制導(dǎo)定義(屬性文法),D T L L.in := T.type T int

8、T.type := integer T real T.type := real L L1,id L1.in := L.in addtype( id.entry, L.in ) L id addtype( id.entry, L.in ),entry 單詞 id 的屬性 addtype 在符號(hào)表中為變量填加標(biāo)識(shí)符的類(lèi)型信息,屬性的計(jì)算,綜合屬性 自底向上按照語(yǔ)義規(guī)則來(lái)計(jì)算各結(jié)點(diǎn)的綜合屬性值 繼承屬性 根據(jù)依賴關(guān)系決定計(jì)算順序 依賴圖的任意一個(gè)拓?fù)渑判颍═opological Sort),例：3*5+4 的分析樹(shù)與屬性計(jì)算,例:real id1,id2,id3 的分析樹(shù)和屬性計(jì)算,在語(yǔ)法分析的過(guò)程

9、中，隨著分析的步步進(jìn)展，根據(jù)每個(gè)產(chǎn)生式所對(duì)應(yīng)的語(yǔ)義子程序邊分析邊翻譯的方法。 注：1)語(yǔ)法制導(dǎo)翻譯時(shí)會(huì)根據(jù)文法產(chǎn)生式右部符號(hào)串的含義，進(jìn)行翻譯，翻譯的結(jié)果是生成相應(yīng)中間代碼。 2)語(yǔ)法制導(dǎo)翻譯的依據(jù)是語(yǔ)義子程序。 3)每個(gè)產(chǎn)生式均配置一個(gè)語(yǔ)義子程序，當(dāng)語(yǔ)法分析進(jìn)行歸約和推導(dǎo)時(shí)，就調(diào)用相應(yīng)語(yǔ)義子程序，完成一部分翻譯任務(wù)。 4)語(yǔ)法分析完成，翻譯工作也告結(jié)束。,7.2 語(yǔ)法制導(dǎo)翻譯,何謂中間代碼： 源程序的一種內(nèi)部表示，不依賴目標(biāo)機(jī)的結(jié)構(gòu)，易于機(jī)械生成目標(biāo)代碼的中間表示。,為什麼要此階段 邏輯結(jié)構(gòu)清楚； 利于不同目標(biāo)機(jī)上實(shí)現(xiàn)同一種語(yǔ)言； 利于進(jìn)行與機(jī)器無(wú)關(guān)的優(yōu)化； 這些內(nèi)部形式也能用于解釋；,7.

10、3 中間代碼的形式,常用的中間代碼(語(yǔ)言),三地址代碼（四元式） 語(yǔ)法(結(jié)構(gòu))樹(shù)（三元式） 后綴式逆波蘭表示 特點(diǎn) 形式簡(jiǎn)單、語(yǔ)義明確、便于翻譯 獨(dú)立于目標(biāo)語(yǔ)言,形式： Operand1 Operand2 Operator,1、后綴表示式(逆波蘭表達(dá)式),最簡(jiǎn)單的一種中間代碼形式。 是波蘭邏輯學(xué)家盧卡西維奇發(fā)明的。 優(yōu)點(diǎn)：易于計(jì)算機(jī)處理表達(dá)式。,語(yǔ)句相應(yīng)的逆波蘭表示形式：,表達(dá)式求值的算法,常用的算法是使用一個(gè)棧，自左至右掃描算術(shù)表達(dá)式（后綴表示），每掃描到運(yùn)算對(duì)象，就把它推進(jìn)棧；掃描到運(yùn)算符，若該運(yùn)算符是二目的，則對(duì)棧頂部的兩個(gè)運(yùn)算對(duì)象實(shí)施該運(yùn)算，并將運(yùn)算結(jié)果代替這兩個(gè)運(yùn)算對(duì)象而進(jìn)棧；若是一

11、目運(yùn)算符，則對(duì)棧頂元素執(zhí)行該運(yùn)算，并以運(yùn)算結(jié)果代替該元素進(jìn)棧，最后的結(jié)果留在棧頂。,逆波蘭: A B C D - * + E C D -N / +,例 : A + B * ( C - D ) + E / ( C - D ) N,形式：(Operator,Operand1,Operand2) 注： 1)這里三元式本身作為存放結(jié)果的單元 2)為了在其它三元式中利用當(dāng)前三元式的結(jié)果，需要對(duì)三元式進(jìn)行編號(hào)。 3)三元式的編號(hào)就作為相應(yīng)三元式的結(jié)果值。,2、三元式,例 : A + B * ( C - D ) + E / ( C - D ) N,3、樹(shù)形表示,形式：,簡(jiǎn)單變量或常數(shù)的樹(shù)是其自身。如果e1和

12、e2的樹(shù)分別為T(mén)1和T2，那么e1+e2,e1*e2,e1-e2的樹(shù)分別為：,例 : A + B * ( C - D ) + E / ( C - D ) N,+,+,*,-,-,/,A,B,C,D,C D,E,N,形式： (Operator,Operand1,Operand2,Result) 注：1) 通過(guò)語(yǔ)法制導(dǎo)翻譯所生成的四元式中， Operand1,Operand2,Result 可能是用戶自定義的變量，也可能是編譯時(shí)引進(jìn)的變量。 2)四元式中變量采用符號(hào)表入口的地址，而不用變量的地址，因?yàn)檎Z(yǔ)義分析不僅需要變量的地址，還需要從符號(hào)表查到的變量的屬性、類(lèi)型和地址等。 3)四元式的優(yōu)點(diǎn)是容易

13、轉(zhuǎn)換為目標(biāo)代碼和容易進(jìn)行優(yōu)化。,4、四元式,例 : A + B * ( C - D ) + E / ( C - D ) N,常用的三地址語(yǔ)句對(duì)應(yīng)的四元式,X=y op z = (op,y,z,x) X=-y =(uminus,y,_,x) X=y =(=,y,_,x) Par x1 =(par,x1,_,_) /過(guò)程調(diào)用語(yǔ)句 Goto L =(j,_,_,L) If x rop y goto L =(jrop,x,y,L),四元式形式:,相關(guān)語(yǔ)義屬性： : id表示的單詞名字。 E.place：存放E值的變量名在符號(hào)表的登錄項(xiàng)或一整數(shù)碼（臨時(shí)變量時(shí)）。 相關(guān)函數(shù)： lookup(

14、) 檢查 是否出現(xiàn)在符號(hào)表中，如在返回指向該登錄項(xiàng)的指針，否則返回nil; 相關(guān)過(guò)程： emit(op ，arg1，arg2，result) 表示產(chǎn)生一個(gè)四元式并填入四元式表中; Newtemp：生成一個(gè)新的臨時(shí)變量的整數(shù)碼，變量名可設(shè)為T(mén)1、T2、,(op ,arg1,arg2,result) 或 result := arg1 op arg2,7.4、簡(jiǎn)單賦值語(yǔ)句的翻譯,產(chǎn)生式和語(yǔ)義描述：,(,1,) S,id : = E,P,:=lookup,(,),;,if P,nil then emit( =,E.place,_,P),else error()

15、 ,翻譯賦值語(yǔ)句到四元式的語(yǔ)義描述,包括對(duì)先定義后使用的檢查,(2) EE1+E2 E.place:= newtemp; emit(+, E1.place , E2.place ,E.place); (3) EE1*E2 E.place:= newtemp; emit(*, E1.place , E2.place ,E.place); （4）E - E1 E.place:=newtemp; emit(uminus , E1.place ,_,E.place); (5) E( E1) E.place:=newtemp; E.place:= E1.place (6) Eid E.place:=ne

16、wtemp; P:=lookup(); if Pnil then E.place:=P else error();,每個(gè)表達(dá)式中可能出現(xiàn)各種不同類(lèi)型的變量或常數(shù)，此時(shí)應(yīng)該進(jìn)行類(lèi)型轉(zhuǎn)換的語(yǔ)義處理。 為此增加： E.type:E的類(lèi)型信息 itr:將整型轉(zhuǎn)換成實(shí)型 *i， *r分別表示int和real類(lèi)型的乘法運(yùn)算； 對(duì)第3條產(chǎn)生式的語(yǔ)義描述為：,(3) EE1*E2 E.place:= newtemp; if E1 . type=int AND E2. type=int then begin emit(E.place“:=” E1.place“*i”E2.place); E.typ

17、e=int end,else if E1 . type=real AND E2. type=real then begin emit(E.place“:=”E1.place“*r”E2.place); E.type=real end else if E1 . type=int / AND E2. type=real then begin t:=newtemp; emit(t “:=” “ itr” E1.place ); emit(E.place“:=”t“*r”E2.place); E.type=real end Else begin t:=newtemp; emit(t“:=” “ itr

18、” E2.place ); emit(E.place“:=”E1.place “*r” t); E.type=real end ,7.5 布爾表達(dá)式的翻譯,在程序設(shè)計(jì)語(yǔ)言中，布爾表達(dá)式有兩個(gè)基本作用： 計(jì)算邏輯值； 用作控制流語(yǔ)句如 if-then、if-then-else和 while-do等之中的條件表達(dá)式。 布爾表達(dá)式是用布爾運(yùn)算符號(hào)（and、 or、not )作用到布爾變量或關(guān)系表達(dá)式上而組成的。 關(guān)系表達(dá)式形式如：E1 relop E2, 其中E1和E2是算術(shù)表達(dá)式， relop為關(guān)系運(yùn)算符 （ =, , =, ）。,在本節(jié)中我們考慮由下列文法產(chǎn)生的布爾表達(dá)式： EE or E |

19、E and E | not E | (E) | id relop id |true|false 說(shuō)明： 我們使用relop的屬性relop.op來(lái)確定relop所指的六中關(guān)系運(yùn)算中的哪一個(gè)。 按慣例，我們假定or和and 是左結(jié)合的， 并且規(guī)定or 的優(yōu)先級(jí)最低，其次是and, not的優(yōu)先級(jí)最高。,一、布爾表達(dá)式的翻譯方法,考慮用1表示真，0表示假來(lái)實(shí)現(xiàn)布爾表達(dá)式的翻譯。一個(gè)形如 ab的關(guān)系表達(dá)式可等價(jià)的寫(xiě)成: if ab then 1 else 0 ,并將它翻譯成如下三地址語(yǔ)句序列： 100： if ab goto 103 101 T:=0 102 goto 104 103 T:= 1 104,EE1 or E2Eplace=newtemp；emit（Eplace=E1placeorE2place）EE1 and E2Eplace =newtemp；emit（Eplace=E1place andE2place） Enot E1Eplace =newtemp：；emit（Eplace=notE1place）E（E1）Eplace=E1placeEid1 relop id2Eplace=newtemp；emit（ifid1place relop id