第八章語法制導(dǎo)翻譯

1、第八章語法制導(dǎo)翻譯和中間代碼生成第八章語法制導(dǎo)翻譯和中間代碼生成8.1概述概述8.2屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯8.3中間代碼中間代碼概述概述 語義處理語義處理 程序設(shè)計程序設(shè)計 語言的語義語言的語義 u靜態(tài)語義是對程序約束的描述，這些約束無法通過抽象靜態(tài)語義是對程序約束的描述，這些約束無法通過抽象語法規(guī)則來妥善地描述，實質(zhì)上就是語法規(guī)則的良形式語法規(guī)則來妥善地描述，實質(zhì)上就是語法規(guī)則的良形式條件，它可以分為類型規(guī)則和作用域條件，它可以分為類型規(guī)則和作用域/可見性規(guī)則兩大類可見性規(guī)則兩大類 類型相容性類型相容性 變量先聲明后引用變量先聲明后引用 名稱相關(guān)要求名稱相關(guān)要求 動態(tài)語

2、義動態(tài)語義 程序單位描述的計算程序單位描述的計算u編譯程序的語義處理工作編譯程序的語義處理工作 靜態(tài)語義審查靜態(tài)語義審查 解釋執(zhí)行動態(tài)解釋執(zhí)行動態(tài)語義（計算）生成代碼語義（計算）生成代碼.語語 法法 分分 析析 后后 的的 源源 程程 序序 語義處理語義處理概述概述語義形式化語義形式化 語義建模語義建模u文法模型文法模型- 屬性文法屬性文法u命令式或操作式模型命令式或操作式模型 - 操作語義學(xué)操作語義學(xué)u應(yīng)用式模型應(yīng)用式模型-指稱語義學(xué)指稱語義學(xué)u公理式模型公理式模型-公理語義學(xué)公理語義學(xué)操作語義學(xué)操作語義學(xué)u操作語義學(xué)，是操作語義學(xué)，是形式語義學(xué)形式語義學(xué)的一個分支。的一個分支。程序程序設(shè)計

3、語言設(shè)計語言的實施是在具體的的實施是在具體的計算機系統(tǒng)計算機系統(tǒng)中按照中按照語言的語義編制語言的語言的語義編制語言的翻譯程序翻譯程序，將語言中各，將語言中各個成分翻譯成計算機系統(tǒng)中相應(yīng)的一組操作。個成分翻譯成計算機系統(tǒng)中相應(yīng)的一組操作。語言在計算機系統(tǒng)中的一種實施一旦完成，那語言在計算機系統(tǒng)中的一種實施一旦完成，那么對這個計算機系統(tǒng)而言，語言各個成分的含么對這個計算機系統(tǒng)而言，語言各個成分的含義也就完全確定了。因此語言的實施也可用來義也就完全確定了。因此語言的實施也可用來定義語言的語義，即將語言成分所對應(yīng)的計算定義語言的語義，即將語言成分所對應(yīng)的計算機系統(tǒng)的操作作為語言成分的語義，這種語義機系

4、統(tǒng)的操作作為語言成分的語義，這種語義被稱作操作語義。由于語言的語義應(yīng)該是標(biāo)準(zhǔn)被稱作操作語義。由于語言的語義應(yīng)該是標(biāo)準(zhǔn)的，不應(yīng)依附于一個特定的計算機和一種具體的，不應(yīng)依附于一個特定的計算機和一種具體的實施，因此操作語義學(xué)是用解釋執(zhí)行程序的的實施，因此操作語義學(xué)是用解釋執(zhí)行程序的抽象的機器來定義語言的語義。抽象的機器來定義語言的語義。指稱語義學(xué)指稱語義學(xué)（denotational semantics）u形式語義學(xué)的一個分支。人們用程序設(shè)計語言編制程序形式語義學(xué)的一個分支。人們用程序設(shè)計語言編制程序，命令計算機系統(tǒng)去加工數(shù)據(jù)。不同的計算機系統(tǒng)有不同的，命令計算機系統(tǒng)去加工數(shù)據(jù)。不同的計算機系統(tǒng)有不同

5、的結(jié)構(gòu)，因此對同一個命令的執(zhí)行過程可以不同，但最終效果結(jié)構(gòu)，因此對同一個命令的執(zhí)行過程可以不同，但最終效果應(yīng)該相同。指稱語義學(xué)方法認(rèn)為不應(yīng)該將程序設(shè)計語言中各應(yīng)該相同。指稱語義學(xué)方法認(rèn)為不應(yīng)該將程序設(shè)計語言中各個成分的執(zhí)行過程計入語言成分的語義中。語言成分的語義個成分的執(zhí)行過程計入語言成分的語義中。語言成分的語義，應(yīng)該是執(zhí)行語言成分所要得到的最終效果。這是語言成分，應(yīng)該是執(zhí)行語言成分所要得到的最終效果。這是語言成分所要表達(dá)的含義，是語言成分本身所固有的，不因計算機系所要表達(dá)的含義，是語言成分本身所固有的，不因計算機系統(tǒng)的不同而改變。執(zhí)行語言成分產(chǎn)生的最終效果被看作是語統(tǒng)的不同而改變。執(zhí)行語言成

6、分產(chǎn)生的最終效果被看作是語言成分的所指，稱作為語言成分的指稱物。這種語義學(xué)以語言成分的所指，稱作為語言成分的指稱物。這種語義學(xué)以語言成分的指稱物作為語言成分的語義，故名為指稱語義學(xué)。言成分的指稱物作為語言成分的語義，故名為指稱語義學(xué)。u指稱語義學(xué)中用于定義語義的指稱物多數(shù)是傳統(tǒng)的數(shù)學(xué)指稱語義學(xué)中用于定義語義的指稱物多數(shù)是傳統(tǒng)的數(shù)學(xué)對象，如整數(shù)、集合、映象等，故早期又稱為數(shù)學(xué)語義學(xué)。對象，如整數(shù)、集合、映象等，故早期又稱為數(shù)學(xué)語義學(xué)。這一名稱容易使人誤認(rèn)為其他形式語義學(xué)分支是非數(shù)學(xué)的，這一名稱容易使人誤認(rèn)為其他形式語義學(xué)分支是非數(shù)學(xué)的，后已不再使用。后已不再使用。 公理語義學(xué)公理語義學(xué)u形式語義

7、學(xué)的一個分支。不同的人在了形式語義學(xué)的一個分支。不同的人在了解程序的含義時有不同的要求。公理語解程序的含義時有不同的要求。公理語義學(xué)方法就是研究如何將這些不同的要義學(xué)方法就是研究如何將這些不同的要求形式化，并根據(jù)這些要求嚴(yán)格給出程求形式化，并根據(jù)這些要求嚴(yán)格給出程序設(shè)計語言的有關(guān)語義。序設(shè)計語言的有關(guān)語義。 屬性文法表達(dá)式文法表達(dá)式文法 ET+T| T or T Tn | b E ET T1 1 + T+ T2 2 T T1 1.type = int .type = int T T2 2.type= T.type= T1 1.type .type E.type :=int E.type :=i

8、nt E E T T1 1 or Tor T2 2 T T1 1.type = bool .type = bool T T2 2.type= T.type= T1 1.type.type E.type :=bool E.type :=bool T T n n T.type := int T.type := int T T b b T.type := bool T.type := bool 屬性文法和語法制導(dǎo)翻譯屬性文法和語法制導(dǎo)翻譯 雖然形式語義學(xué)雖然形式語義學(xué)(如指稱語義學(xué)、公理語義如指稱語義學(xué)、公理語義學(xué)、操作語義學(xué)等學(xué)、操作語義學(xué)等)的研究已取得了許多的研究已取得了許多重大的進(jìn)展，但目前

9、在實際應(yīng)用中比較重大的進(jìn)展，但目前在實際應(yīng)用中比較流行的語義描述和語義處理的方法主要流行的語義描述和語義處理的方法主要還是屬性文法和語法制導(dǎo)翻譯方法還是屬性文法和語法制導(dǎo)翻譯方法 屬性文法屬性文法屬性文法屬性文法(attribute grammar)是一個三元組是一個三元組:A=(G,V,F),其中其中 G:是一個上下文無關(guān)文法是一個上下文無關(guān)文法V:有窮的屬性集有窮的屬性集,每個屬性與文法的一個終結(jié)符或每個屬性與文法的一個終結(jié)符或非終結(jié)符相連非終結(jié)符相連,這些屬性代表與文法符號相關(guān)信這些屬性代表與文法符號相關(guān)信息，如它的類型、值、代碼序列、符號表內(nèi)容息，如它的類型、值、代碼序列、符號表內(nèi)容等

10、等等等 .屬性與變量一樣，可以進(jìn)行計算和傳遞。屬性與變量一樣，可以進(jìn)行計算和傳遞。屬性加工的過程即是語義處理的過程。屬性加工的過程即是語義處理的過程。F:關(guān)于屬性的屬性斷言或一組屬性的計算規(guī)則關(guān)于屬性的屬性斷言或一組屬性的計算規(guī)則(稱稱為語義規(guī)則為語義規(guī)則) . 斷言或語義規(guī)則與一個產(chǎn)生式相斷言或語義規(guī)則與一個產(chǎn)生式相聯(lián)聯(lián),只引用該產(chǎn)生式左端或右端的終結(jié)符或非終只引用該產(chǎn)生式左端或右端的終結(jié)符或非終結(jié)符相聯(lián)的屬性結(jié)符相聯(lián)的屬性. 屬性有兩種屬性有兩種 繼承的和綜合的屬性繼承的和綜合的屬性屬性通常分為兩類：綜合屬性和繼承屬性。簡單地說，綜屬性通常分為兩類：綜合屬性和繼承屬性。簡單地說，綜合屬性用

11、于合屬性用于“自下而上自下而上”傳遞信息，而繼承屬性用于傳遞信息，而繼承屬性用于“自上而下自上而下”傳遞信息。傳遞信息。出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合出現(xiàn)在產(chǎn)生式左邊的繼承屬性和出現(xiàn)在產(chǎn)生式右邊的綜合屬性不由所給定的產(chǎn)生式的屬性計算規(guī)則進(jìn)行計算，它屬性不由所給定的產(chǎn)生式的屬性計算規(guī)則進(jìn)行計算，它們由其它產(chǎn)生式的屬性規(guī)則計算或者由生計算器的參數(shù)們由其它產(chǎn)生式的屬性規(guī)則計算或者由生計算器的參數(shù)提供。提供。 AX1 X2 XnA的綜合屬性的綜合屬性,計算計算 S(A):=f(I(X1),I(Xn)Xj的繼承屬性的繼承屬性,計算計算 T(Xj):=f(I(A),. I(Xn) 1)

12、非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始非終結(jié)符既可有綜合屬性也可有繼承屬性，但文法開始符號沒有繼承屬性符號沒有繼承屬性. 2)終結(jié)符只有綜合屬性終結(jié)符只有綜合屬性.在一個屬性文法中，對應(yīng)于每個產(chǎn)生式在一個屬性文法中，對應(yīng)于每個產(chǎn)生式A都有一都有一套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為套與之相關(guān)聯(lián)的語義規(guī)則，每條規(guī)則的形式為b:=f(c1,c2ck)這里，這里，f是一個函數(shù)，而且或者是一個函數(shù)，而且或者（1）b是是A的一個綜合屬性并且的一個綜合屬性并且c1,c2ck是產(chǎn)生式是產(chǎn)生式右邊文法符號的屬性右邊文法符號的屬性;或者或者（2）b是產(chǎn)生式右邊某個文法符號的一個繼承屬是產(chǎn)生式右邊某

13、個文法符號的一個繼承屬性并且性并且c1,c2ck是是A或產(chǎn)生式右邊任何文法符號的或產(chǎn)生式右邊任何文法符號的屬性。屬性。在兩種情況下，我們都說屬性在兩種情況下，我們都說屬性b依賴于屬性依賴于屬性c1,c2ck 。 一個屬性文法的例子一個屬性文法的例子 例例8.1 P156 非終結(jié)符非終結(jié)符E、T及及F都有一個綜合屬性都有一個綜合屬性val,符號符號digit有一個綜合屬性有一個綜合屬性，它的值由詞法分析器提供。與產(chǎn)生式，它的值由詞法分析器提供。與產(chǎn)生式LEn對應(yīng)的語義規(guī)則僅對應(yīng)的語義規(guī)則僅僅是打印由僅是打印由E產(chǎn)生的算術(shù)表達(dá)式的值的一個過程，我們可認(rèn)為這產(chǎn)生的算術(shù)表達(dá)式的值的一個過程，我們可認(rèn)為

14、這條規(guī)則定義了條規(guī)則定義了L的一個虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分的一個虛屬性。某些非終結(jié)符加下標(biāo)是為了區(qū)分一個產(chǎn)生式中同一非終結(jié)符多次出現(xiàn)一個產(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) 生 式設(shè)表達(dá)式為設(shè)表達(dá)式為35+4，則語義動作打印數(shù)值，則語義動作打印數(shù)值19.LE.val=19E.val=15T

15、.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的帶注釋的分析樹的帶注釋的分析樹繼承屬性繼承屬性u一個結(jié)點的繼承屬性值是由此結(jié)點的父結(jié)點和一個結(jié)點的繼承屬性值是由此結(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

16、(id.entry,L.in) addtype(id.entry,L.in) DL.in= realL.in= realL.in= realT.type=realrealid2id1id3.Real id1,id2,id3，語法制導(dǎo)的翻譯語法制導(dǎo)的翻譯u一個一個翻譯是符號串對的一個集合。在一個編譯程是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串對是源程序和目標(biāo)程序序定義的翻譯中，符號串對是源程序和目標(biāo)程序。各個編譯階段定義一個翻譯，詞法分析：（字。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法

17、樹，匯編語言）代碼生成（語法樹，匯編語言）設(shè)設(shè) 是輸入字母表且是輸入字母表且 是輸出字母表。定義由語言是輸出字母表。定義由語言 L1 *到語言到語言L2 *的一個翻譯是由的一個翻譯是由 *到到 *的的一個關(guān)系一個關(guān)系T,使得使得T的定義域為的定義域為L1且且T的值域為的值域為L2 。 使使(x,y) T的句子的句子y叫做叫做x的一個輸出的一個輸出.語法制導(dǎo)的翻譯語法制導(dǎo)的翻譯u 直觀地說，一個語法制導(dǎo)翻譯的基礎(chǔ)是一個文法，其直觀地說，一個語法制導(dǎo)翻譯的基礎(chǔ)是一個文法，其中翻譯成分依附在每一產(chǎn)生式上。中翻譯成分依附在每一產(chǎn)生式上。 u例例8.5： 把下述產(chǎn)生式定義的算術(shù)表達(dá)式映射到后綴波蘭表把下

18、述產(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ī)則翻譯規(guī)則 u確定輸入確定輸入a+a a的輸出：的輸出： (E,E)(E+T,ET+) (T+T,TT+) (F+T,FT+) (a+T,aT+) (a+T F,aFF +) (a+F F,aFF +) (a+a F,aaF +) (a+a a,aaa +). . . 何謂中間代碼何謂中間代碼 ( Intermediate code ) ( Intermediate representation ) ( Intermedi

19、ate language ) 源程序的一種內(nèi)部表示，不依賴目標(biāo)機的結(jié)構(gòu)，易于機械生成源程序的一種內(nèi)部表示，不依賴目標(biāo)機的結(jié)構(gòu)，易于機械生成 目目 標(biāo)代碼的中間表示。標(biāo)代碼的中間表示。為什么要此階段？為什么要此階段？邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機上實現(xiàn)同一種語言；邏輯結(jié)構(gòu)清楚；利于不同目標(biāo)機上實現(xiàn)同一種語言； 利于進(jìn)行與機器無關(guān)的優(yōu)化利于進(jìn)行與機器無關(guān)的優(yōu)化 ；這些內(nèi)部形式也能用于解釋。；這些內(nèi)部形式也能用于解釋。中間代碼的幾種形式中間代碼的幾種形式逆波蘭逆波蘭 四元式四元式 三元式三元式 間接三元式間接三元式 樹樹 中間代碼中間代碼 逆波蘭逆波蘭 : A B C D - * + E C D N

20、/ + 四元式四元式 : (1) ( - C D T1 ) (2) ( * B T1 T2) (3) ( + A T2 T3) (4) ( - C D T4) (5) ( T4 N T5) (6) ( / E T5 T6) (7) ( + T3 T6 T7)例例 : A + B * ( C - D ) + E / ( C - D ) N 三三元元式式: (1) ( - C D ) (2) ( * B (1) ) (3) ( + A (2) ) (4) ( - C D ) (5) ( (4) N ) (6) ( / E (5) ) (7) ( + (3) (6) )例例 : A + B * ( C - D ) + E / ( C - D ) N間間接接三三元元式式 : 間間接接三三元元式式序序列列 間間接接碼碼表表 (1) ( -