編譯原理_07中間代碼及其他

1、1 語法制導翻譯和語法制導翻譯和 中間代碼生成中間代碼生成 主要內容 概述概述 屬性文法屬性文法 語法制導翻譯概述語法制導翻譯概述 中間語言中間語言 3 課題：課題：中間代碼及其他 目的要求：目的要求： 1.掌握中間代碼的表示方式； 2.了解 教學重點：教學重點： 中間代碼的表示方式。 教學難點教學難點 ： 教學課時：教學課時：2 教學方法：教學方法：多媒體教學 教學內容和步驟教學內容和步驟 ：（如下） 第 十五 講 4 概概 述述 編譯程序的任務編譯程序的任務是把源程序翻譯成語義上等價的目是把源程序翻譯成語義上等價的目 標程序。通常，在編譯過程中，經(jīng)過詞法分析和語法標程序。通常，在編譯過程中

2、，經(jīng)過詞法分析和語法 分析之后，分析之后， 接下來將進行語義分析與處理。接下來將進行語義分析與處理。 編譯中的編譯中的語義處理包括兩個功能語義處理包括兩個功能：第一，審查每個：第一，審查每個 語法結構的靜態(tài)語義，即驗證語法結構合法的程序是語法結構的靜態(tài)語義，即驗證語法結構合法的程序是 否真正有意義。有時把這個工作稱為否真正有意義。有時把這個工作稱為靜態(tài)語義分析靜態(tài)語義分析或或 靜態(tài)審查。第二，如果靜態(tài)語義正確，語義處理則要靜態(tài)審查。第二，如果靜態(tài)語義正確，語義處理則要 執(zhí)行真正的翻譯，即生成某種中間代碼或者實際的目執(zhí)行真正的翻譯，即生成某種中間代碼或者實際的目 標代碼。標代碼。 本章引入屬性文

3、法和語法制導翻譯方法的基本思想，本章引入屬性文法和語法制導翻譯方法的基本思想， 介紹幾種典型的中間代碼形式和一些常見語法成分的介紹幾種典型的中間代碼形式和一些常見語法成分的 翻譯方法。翻譯方法。 5 8.1 8.1 屬性文法屬性文法 屬性屬性，通常用來描述事物的特征、性質、品質等。，通常用來描述事物的特征、性質、品質等。 屬性文法的形式定義：一個屬性文法形式上可定義屬性文法的形式定義：一個屬性文法形式上可定義 為一個三元組為一個三元組A，A=A=（G G，V V，F(xiàn) F）。其中其中G表示一個上表示一個上 下文無關文法；下文無關文法；V表示屬性的有窮集；表示屬性的有窮集；F表示有關屬性表示有關屬

4、性 的斷言或謂詞的有窮集。的斷言或謂詞的有窮集。 在屬性文法中在屬性文法中: （1）每個屬性）每個屬性t都與某個文法符號都與某個文法符號N相關聯(lián)，用相關聯(lián)，用N.t來表來表 示。例如示。例如N.type表示與表示與N關聯(lián)的屬性關聯(lián)的屬性type。 （2）每個斷言與文法的某個規(guī)則相關聯(lián)。每個斷言與文法的某個規(guī)則相關聯(lián)。 （3）如果對）如果對G中的某一輸入串（句子）而言，中的某一輸入串（句子）而言， A中的中的 所有斷言對該輸入串的語法樹結點的屬性全為真，則所有斷言對該輸入串的語法樹結點的屬性全為真，則 該串也是該串也是A語言中的句子。語言中的句子。 6 編譯程序的靜態(tài)語義審查工作就是驗證關于所編

5、譯的編譯程序的靜態(tài)語義審查工作就是驗證關于所編譯的 程序的斷言是否全部為真程序的斷言是否全部為真。 如文法如文法GS： EF1F2F1 or F2 Fnumtrue false 與每個非終結符與每個非終結符F相聯(lián)的屬性有相聯(lián)的屬性有type，type為為int或者或者 bool。關于類型檢驗的屬性文法可以表示為：關于類型檢驗的屬性文法可以表示為： EFlF2 F1.type := int AND F2.type := int EF1 or F2 F1.type := bool AND F2.type := bool Fnum F.type := int Ftrue F.ype := bool

6、Ffalse F.ype := bool 由上可知，與非終結符由上可知，與非終結符E的產(chǎn)生式相聯(lián)的斷言指明：的產(chǎn)生式相聯(lián)的斷言指明： 兩個兩個F的屬性必須相同。的屬性必須相同。 7 屬性可以分為屬性可以分為綜合屬性綜合屬性和和繼承屬性繼承屬性兩類。綜合屬性一兩類。綜合屬性一 般用于自下而上傳遞信息，而繼承屬性常常用于自上而般用于自下而上傳遞信息，而繼承屬性常常用于自上而 下傳遞信息。下述為簡單算術表達式求值的屬性文法：下傳遞信息。下述為簡單算術表達式求值的屬性文法： 規(guī)則規(guī)則 語義規(guī)則語義規(guī)則 1. SE print（E.val） 2. EE1T E.val := E1.valT.val 3.

7、 ET E.va1 := T.valv 4. TT1 F T.val := T1.val F.val 5. TT1 T.val := T1.val 6. F（E） F.val := E.val 7. Fdigit F.val := digit.lexval 每一個非終結符都有一個表示整數(shù)值的屬性每一個非終結符都有一個表示整數(shù)值的屬性val。規(guī)規(guī) 則左部符號則左部符號E、T、F的屬性值取決于各自規(guī)則的右部，的屬性值取決于各自規(guī)則的右部， 稱為綜合屬性；對于文法符號稱為綜合屬性；對于文法符號S，其屬性是虛的或空的。其屬性是虛的或空的。 8 8.3 8.3 中間語言中間語言 所謂所謂中間語言中間語言

8、，也稱中間代碼，是復雜性介于源程序，也稱中間代碼，是復雜性介于源程序 語言和機器語言的一種記號系統(tǒng)。一般來說，快速編譯語言和機器語言的一種記號系統(tǒng)。一般來說，快速編譯 程序直接生成目標代碼，沒有將中間代碼翻譯成目標代程序直接生成目標代碼，沒有將中間代碼翻譯成目標代 碼的額外開銷。但是為了使編譯程序結構在邏輯上更為碼的額外開銷。但是為了使編譯程序結構在邏輯上更為 簡單明確，使生成的的目標代碼更為高效，通常采用中簡單明確，使生成的的目標代碼更為高效，通常采用中 間語言。間語言。 編譯程序所使用的中間語言形式較多。常見的有編譯程序所使用的中間語言形式較多。常見的有逆波逆波 蘭式蘭式、三元式三元式、四

9、元式四元式和和樹形表示樹形表示等等。等等。 9 8.3.1 8.3.1 逆波蘭式逆波蘭式 逆波蘭式是逆波蘭式是最簡單最簡單的一種中間語言形式，也稱做的一種中間語言形式，也稱做后綴后綴 式式。它的特點是將運算對象寫在前面，把運算符號寫在。它的特點是將運算對象寫在前面，把運算符號寫在 后面后面。對于簡單表達式對于簡單表達式E，相應的逆波蘭式相應的逆波蘭式E遵循下面遵循下面 的轉換規(guī)則：的轉換規(guī)則： 表達式表達式 逆波蘭式逆波蘭式 E E (E) E E E （負號負號“”是一元運算符，為了區(qū)別于減號是一元運算符，為了區(qū)別于減號“”， 通常寫成通常寫成） E1 op E2 E1 E2 op 10 用

10、逆波蘭式表示表達式，其最大的優(yōu)點是易于計算機用逆波蘭式表示表達式，其最大的優(yōu)點是易于計算機 進行計算處理。進行計算處理。 例例. .算術表達式算術表達式x xy y z z 的逆波蘭式為的逆波蘭式為xyzxyz ，在棧在棧 中的計值過程如圖所示。中的計值過程如圖所示。 t1:=t1:=x x x xt1t1 y y z z t2:=yt2:=y z z t1t1 t2t2 t3:=t1t3:=t1t2t2 同時同時y y、z z入棧入棧 t3t3 由于逆波蘭式表示上的簡單和計值的方便，因此特別由于逆波蘭式表示上的簡單和計值的方便，因此特別 適用于解釋執(zhí)行的程序設計語言的中間表示，也方便適用于解

11、釋執(zhí)行的程序設計語言的中間表示，也方便 具有堆棧體系的計算機的目標代碼生成。具有堆棧體系的計算機的目標代碼生成。 11 8.3.28.3.2三元式和樹形表示三元式和樹形表示 一三元式一三元式 三元式是中間語言的另一種形式，每個三元式由三個部三元式是中間語言的另一種形式，每個三元式由三個部 分組成分組成:op，arg1，arg2。其一般格式為：其一般格式為： （i i）（）（opop，arg1arg1，arg2arg2） 表達式表達式a bc d可用三元式表示為：可用三元式表示為： （1）（）（ ， a ， ） （2）（）（ ， （1），）， b ） （3）（）（ ， c ， d ） （4）（）

12、（ ， （2），（），（3） “”是一目運算符（這里用是一目運算符（這里用表示），用來使表示），用來使a取反，取反， 對于一目運算，不妨規(guī)定只用對于一目運算，不妨規(guī)定只用arg1。 12 二樹形表示二樹形表示 樹形表示實際上是三元式的另一種表示形式。表達式樹形表示實際上是三元式的另一種表示形式。表達式 的樹形表示非常容易實現(xiàn)：簡單直觀。的樹形表示非常容易實現(xiàn)：簡單直觀。 例如，表達式例如，表達式a bc d的樹形表示：的樹形表示： a a b b d d c c 13 三間接三元式三間接三元式 間接三元式是對三元式的一種補充。為了在進行代碼間接三元式是對三元式的一種補充。為了在進行代碼 優(yōu)化時

13、盡量不改變三元式表，于是另設一張間接碼表來優(yōu)化時盡量不改變三元式表，于是另設一張間接碼表來 表示有關三元式在三元式表的計值順序。用這種方法獲表示有關三元式在三元式表的計值順序。用這種方法獲 得的中間代碼稱為間接三元式。如表達式得的中間代碼稱為間接三元式。如表達式 a := xy z b := ty z 的間接三元式表示的間接三元式表示 ： 三元式列表三元式列表間接碼表間接碼表 （1）（）（ ，y，z） （2）（，）（，x，（，（1） （3）（）（:=，a，（，（2） （4）（，）（，t，（，（1） （5）（）（:=，（，（4） （1） （2） （3） （1） （4） （5） 14 8.8.3.

14、3 3.3 四元式和三地址碼四元式和三地址碼 一四元式一四元式 四元式是比較普遍采用的一種中間語言形式。與三元式四元式是比較普遍采用的一種中間語言形式。與三元式 類似，四元式由四個部分組成：類似，四元式由四個部分組成：op，arg1，arg2，t。 四元式的一般格式為：四元式的一般格式為： （i） （op， arg1， arg2， t） 例如，表達式例如，表達式a := bc d的四元式表示如下的四元式表示如下: （1）（）（ ， c， d， t1） （2）（）（ ， b， t1， t2） （3）（）（:= ， t2， b b， a ） 四元式和三元式的不同之處主要在于對中間結果的引四元式和三

15、元式的不同之處主要在于對中間結果的引 用方式：四元式之間的聯(lián)系是通過引入臨時變量來實現(xiàn)，用方式：四元式之間的聯(lián)系是通過引入臨時變量來實現(xiàn)， 而三元式則是通過三元式編號來傳遞中間結果的。而三元式則是通過三元式編號來傳遞中間結果的。 15 二三地址碼二三地址碼 三地址代碼也可以看成是四元式的另一種表示方式，三地址代碼也可以看成是四元式的另一種表示方式， 它比四元式更直觀、更易于理解。它比四元式更直觀、更易于理解。 三地址碼的一般格式為三地址碼的一般格式為 t:= arg1 op arg2t:= arg1 op arg2 其形式就是一個賦值語句，只是與賦值語句不同的是：其形式就是一個賦值語句，只是與

16、賦值語句不同的是： 在三地址碼中賦值符號的右邊最多只能有一個運算符。在三地址碼中賦值符號的右邊最多只能有一個運算符。 表達式表達式a := bc d的三地址碼序列的三地址碼序列: （1）t1 := c d （2）t2 := bt1 （3）a := t2 三地址碼簡單直觀，這種表示形式對中間代碼的優(yōu)化三地址碼簡單直觀，這種表示形式對中間代碼的優(yōu)化 和目標代碼的生成非常有利。和目標代碼的生成非常有利。 16 符號表符號表 運行時存儲空間的組織運行時存儲空間的組織 代碼優(yōu)化代碼優(yōu)化 目標代碼生成目標代碼生成 17 一一. .符號表符號表 一般來說符號表須保存如下一些內容：一般來說符號表須保存如下一些

17、內容： 1.1.類型名以及它的定義；類型名以及它的定義； 2.2.變量名以及類型；變量名以及類型； 3.3.常量名、類型和值常量名、類型和值； 4. .過程或函數(shù)名、形參和局部變量、值單元及過程入過程或函數(shù)名、形參和局部變量、值單元及過程入 口地址；口地址； 5.5.類；類； 6.6.繼承；繼承； 7.7.模塊的大小，名字，根源，成員以及時間標志。模塊的大小，名字，根源，成員以及時間標志。 1. 符號表的內容符號表的內容 18 (1)(1)名子名子 (2)(2)類型類型 (3)(3)存儲類別存儲類別 (4)(4)作用域及可視性作用域及可視性 (5)(5)存儲分配信息存儲分配信息 (6)(6)其

18、它屬性其它屬性: :數(shù)組內情向量、記錄結構型的成數(shù)組內情向量、記錄結構型的成 員信息、函數(shù)及過程的形參員信息、函數(shù)及過程的形參 3. 符號的主要屬性有：符號的主要屬性有： （1 1）下文語義的合法性檢查的依據(jù)）下文語義的合法性檢查的依據(jù) （2 2）代碼生成階段地址分配的依據(jù)）代碼生成階段地址分配的依據(jù) 2. 符號表的作用符號表的作用 19 大致可有如下幾類：大致可有如下幾類： 插入插入: : 往符號表中插入一個新的名字；往符號表中插入一個新的名字； 查找：查找： 查詢查詢: : 對給定名字，在符號表中查詢其有關信息；對給定名字，在符號表中查詢其有關信息； 更新：對給定名字，在符號表填寫或更新它

19、的某更新：對給定名字，在符號表填寫或更新它的某 些信息；些信息； 刪除：在符號表中刪除一個或多個無用項。刪除：在符號表中刪除一個或多個無用項。 4. 對符號表的操作對符號表的操作 20 運行時存儲空間劃分為：生成目標代運行時存儲空間劃分為：生成目標代 碼，數(shù)據(jù)對象和跟蹤過程活動的控制碼，數(shù)據(jù)對象和跟蹤過程活動的控制 棧。棧。 一個稱為堆（一個稱為堆（heap)的運行時存儲空間的運行時存儲空間 單獨區(qū)域用來存放動態(tài)數(shù)據(jù)。單獨區(qū)域用來存放動態(tài)數(shù)據(jù)。 運行時存儲空間劃分如圖所示運行時存儲空間劃分如圖所示 目標代碼區(qū)域目標代碼區(qū)域 靜態(tài)區(qū)域靜態(tài)區(qū)域 棧棧 自由空間自由空間 堆堆 1. 運行時存儲空間劃

20、分運行時存儲空間劃分 二二. .運行時存儲空間的組織運行時存儲空間的組織 21 如果一個程序語言不允許有遞歸過程，不允許含如果一個程序語言不允許有遞歸過程，不允許含 有可變體積的數(shù)據(jù)項目或待定性質的名字，那么就有可變體積的數(shù)據(jù)項目或待定性質的名字，那么就 能在編譯時完全確定其程序的每個數(shù)據(jù)項目存儲空能在編譯時完全確定其程序的每個數(shù)據(jù)項目存儲空 間的位置，這種策略叫做靜態(tài)分配策略。間的位置，這種策略叫做靜態(tài)分配策略。 程序運行時，每當進入一個過程或分程序，其所程序運行時，每當進入一個過程或分程序，其所 需的數(shù)據(jù)空間就動態(tài)地分配于棧頂，一旦該過程或需的數(shù)據(jù)空間就動態(tài)地分配于棧頂，一旦該過程或 分程

21、序運行結束，其所占用的空間就予以釋放，這分程序運行結束，其所占用的空間就予以釋放，這 種方法叫做動態(tài)分配策略。種方法叫做動態(tài)分配策略。 靜態(tài)分配策略和動態(tài)分配策略：靜態(tài)分配策略和動態(tài)分配策略： 2. 存儲分配策略存儲分配策略 22 從優(yōu)化的時間上來分，優(yōu)化可分為對源程序的優(yōu)從優(yōu)化的時間上來分，優(yōu)化可分為對源程序的優(yōu) 化、對中間代碼的有對目標代碼的優(yōu)化。從優(yōu)化與化、對中間代碼的有對目標代碼的優(yōu)化。從優(yōu)化與 源程序的關系出發(fā)，又可把優(yōu)化分為局部優(yōu)化、循源程序的關系出發(fā)，又可把優(yōu)化分為局部優(yōu)化、循 環(huán)優(yōu)化和全局優(yōu)化。環(huán)優(yōu)化和全局優(yōu)化。 三三. .代碼優(yōu)化代碼優(yōu)化 1. 優(yōu)化分類優(yōu)化分類 合并常量運算

22、；刪除公共子表達式；合并常量運算；刪除公共子表達式； 減少復寫傳播；消除無用代碼；減少復寫傳播；消除無用代碼； 削減運算強度；外提循環(huán)中的不變表達式；削減運算強度；外提循環(huán)中的不變表達式； 刪除歸納變量。刪除歸納變量。 2. 常用的優(yōu)化方法常用的優(yōu)化方法 23 合并常量運算；合并常量運算； 刪除公共子表達式；刪除公共子表達式； 減少復寫傳播；減少復寫傳播； 消除無用代碼；消除無用代碼； 削減運算強度；削減運算強度； 外提循環(huán)中的不變表達式；外提循環(huán)中的不變表達式； 刪除歸納變量刪除歸納變量 2. 常用的優(yōu)化方法常用的優(yōu)化方法 24 三三. .目標代碼生成目標代碼生成 將源程序的中間代碼作為輸入，生成等價目標程將源程序的中間代碼作為輸入，生成等價目標程 序的程序稱為目標代碼生成器（簡稱代碼生成器）。序的程序稱為目標代碼生成器（簡稱代碼生成器）。 一般而言目標代碼有以下三種形式：一般而言目標代碼有以下三種形式：(1) 能夠立即能夠立即 執(zhí)行的機器語言代碼，所有地址均已定位；執(zhí)行的機器語言代碼，所有地址均已定位； (2)待裝待裝 配的機器語言模塊；配的機器語言模