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

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

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

4、統的操作作為語言成分的語義，這種語義被稱作操作語義。由于語言的語義應該是標準被稱作操作語義。由于語言的語義應該是標準的，不應依附于一個特定的計算機和一種具體的，不應依附于一個特定的計算機和一種具體的實施，因此操作語義學是用解釋執行程序的的實施，因此操作語義學是用解釋執行程序的抽象的機器來定義語言的語義。抽象的機器來定義語言的語義。指稱語義學指稱語義學（denotational semantics）u形式語義學的一個分支。人們用程序設計語言編制程序形式語義學的一個分支。人們用程序設計語言編制程序，命令計算機系統去加工數據。不同的計算機系統有不同的，命令計算機系統去加工數據。不同的計算機系統有不同

5、的結構，因此對同一個命令的執行過程可以不同，但最終效果結構，因此對同一個命令的執行過程可以不同，但最終效果應該相同。指稱語義學方法認為不應該將程序設計語言中各應該相同。指稱語義學方法認為不應該將程序設計語言中各個成分的執行過程計入語言成分的語義中。語言成分的語義個成分的執行過程計入語言成分的語義中。語言成分的語義，應該是執行語言成分所要得到的最終效果。這是語言成分，應該是執行語言成分所要得到的最終效果。這是語言成分所要表達的含義，是語言成分本身所固有的，不因計算機系所要表達的含義，是語言成分本身所固有的，不因計算機系統的不同而改變。執行語言成分產生的最終效果被看作是語統的不同而改變。執行語言成

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

7、學的一個分支。不同的人在了形式語義學的一個分支。不同的人在了解程序的含義時有不同的要求。公理語解程序的含義時有不同的要求。公理語義學方法就是研究如何將這些不同的要義學方法就是研究如何將這些不同的要求形式化，并根據這些要求嚴格給出程求形式化，并根據這些要求嚴格給出程序設計語言的有關語義。序設計語言的有關語義。 屬性文法表達式文法表達式文法 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 屬性文法和語法制導翻譯屬性文法和語法制導翻譯 雖然形式語義學雖然形式語義學(如指稱語義學、公理語義如指稱語義學、公理語義學、操作語義學等學、操作語義學等)的研究已取得了許多的研究已取得了許多重大的進展，但目前

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

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

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

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

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

14、這條規則定義了條規則定義了L的一個虛屬性。某些非終結符加下標是為了區分的一個虛屬性。某些非終結符加下標是為了區分一個產生式中同一非終結符多次出現一個產生式中同一非終結符多次出現語 義 規 則 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產 生 式設表達式為設表達式為35+4，則語義動作打印數值，則語義動作打印數值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一個結點的繼承屬性值是由此結點的父結點和一個結點的繼承屬性值是由此結點的父結點和/或兄弟或兄弟結點的某些屬性來決定的。結點的某些屬性來決定的。例例8.2 繼承屬性L.in生 產 式語 義 規 則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，語法制導的翻譯語法制導的翻譯u一個一個翻譯是符號串對的一個集合。在一個編譯程是符號串對的一個集合。在一個編譯程序定義的翻譯中，符號串對是源程序和目標程序序定義的翻譯中，符號串對是源程序和目標程序。各個編譯階段定義一個翻譯，詞法分析：（字。各個編譯階段定義一個翻譯，詞法分析：（字符串，單詞串）語法分析：（單詞串，語法樹）符串，單詞串）語法分析：（單詞串，語法樹）代碼生成（語法

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

18、述產生式定義的算術表達式映射到后綴波蘭表示：示： EE+T E T T TF T F F (E) F a E=ET+ E=T T=TF T=F F=E F=a 產生式 翻譯規則翻譯規則 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 ) 源程序的一種內部表示，不依賴目標機的結構，易于機械生成源程序的一種內部表示，不依賴目標機的結構，易于機械生成 目目 標代碼的中間表示。標代碼的中間表示。為什么要此階段？為什么要此階段？邏輯結構清楚；利于不同目標機上實現同一種語言；邏輯結構清楚；利于不同目標機上實現同一種語言； 利于進行與機器無關的優化利于進行與機器無關的優化 ；這些內部形式也能用于解釋。；這些內部形式也能用于解釋。中間代碼的幾種形式中間代碼的幾種形式逆波蘭逆波蘭 四元式四元式 三元式三元式 間接三元式間接三元式 樹樹 中間代碼中間代碼 逆波蘭逆波蘭 : 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) ( -