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

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

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

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

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

5、譯的編譯程序的靜態(tài)語義審查工作就是驗(yàn)證關(guān)于所編譯的 程序的斷言是否全部為真程序的斷言是否全部為真。 如文法如文法GS： EF1F2F1 or F2 Fnumtrue false 與每個(gè)非終結(jié)符與每個(gè)非終結(jié)符F相聯(lián)的屬性有相聯(lián)的屬性有type，type為為int或者或者 bool。關(guān)于類型檢驗(yàn)的屬性文法可以表示為：關(guān)于類型檢驗(yàn)的屬性文法可以表示為： 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 由上可知，與非終結(jié)符由上可知，與非終結(jié)符E的產(chǎn)生式相聯(lián)的斷言指明：的產(chǎn)生式相聯(lián)的斷言指明： 兩個(gè)兩個(gè)F的屬性必須相同。的屬性必須相同。 7 屬性可以分為屬性可以分為綜合屬性綜合屬性和和繼承屬性繼承屬性兩類。綜合屬性一兩類。綜合屬性一 般用于自下而上傳遞信息，而繼承屬性常常用于自上而般用于自下而上傳遞信息，而繼承屬性常常用于自上而 下傳遞信息。下述為簡單算術(shù)表達(dá)式求值的屬性文法：下傳遞信息。下述為簡單算術(shù)表達(dá)式求值的屬性文法： 規(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 每一個(gè)非終結(jié)符都有一個(gè)表示整數(shù)值的屬性每一個(gè)非終結(jié)符都有一個(gè)表示整數(shù)值的屬性val。規(guī)規(guī) 則左部符號則左部符號E、T、F的屬性值取決于各自規(guī)則的右部，的屬性值取決于各自規(guī)則的右部， 稱為綜合屬性；對于文法符號稱為綜合屬性；對于文法符號S，其屬性是虛的或空的。其屬性是虛的或空的。 8 8.3 8.3 中間語言中間語言 所謂所謂中間語言中間語言

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

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

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

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

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

13、盡量不改變?nèi)奖恚谑橇碓O(shè)一張間接碼表來優(yōu)化時(shí)盡量不改變?nèi)奖?，于是另設(shè)一張間接碼表來 表示有關(guān)三元式在三元式表的計(jì)值順序。用這種方法獲表示有關(guān)三元式在三元式表的計(jì)值順序。用這種方法獲 得的中間代碼稱為間接三元式。如表達(dá)式得的中間代碼稱為間接三元式。如表達(dá)式 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 四元式和三地址碼四元式和三地址碼 一四元式一四元式 四元式是比較普遍采用的一種中間語言形式。與三元式四元式是比較普遍采用的一種中間語言形式。與三元式 類似，四元式由四個(gè)部分組成：類似，四元式由四個(gè)部分組成：op，arg1，arg2，t。 四元式的一般格式為：四元式的一般格式為： （i） （op， arg1， arg2， t） 例如，表達(dá)式例如，表達(dá)式a := bc d的四元式表示如下的四元式表示如下: （1）（）（ ， c， d， t1） （2）（）（ ， b， t1， t2） （3）（）（:= ， t2， b b， a ） 四元式和三元式的不同之處主要在于對中間結(jié)果的引四元式和三

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

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

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

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

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

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

21、序運(yùn)行結(jié)束，其所占用的空間就予以釋放，這分程序運(yùn)行結(jié)束，其所占用的空間就予以釋放，這 種方法叫做動(dòng)態(tài)分配策略。種方法叫做動(dòng)態(tài)分配策略。 靜態(tài)分配策略和動(dòng)態(tài)分配策略：靜態(tài)分配策略和動(dòng)態(tài)分配策略： 2. 存儲(chǔ)分配策略存儲(chǔ)分配策略 22 從優(yōu)化的時(shí)間上來分，優(yōu)化可分為對源程序的優(yōu)從優(yōu)化的時(shí)間上來分，優(yōu)化可分為對源程序的優(yōu) 化、對中間代碼的有對目標(biāo)代碼的優(yōu)化。從優(yōu)化與化、對中間代碼的有對目標(biāo)代碼的優(yōu)化。從優(yōu)化與 源程序的關(guān)系出發(fā)，又可把優(yōu)化分為局部優(yōu)化、循源程序的關(guān)系出發(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)化分類 合并常量運(yùn)算

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