編譯原理簡(jiǎn)明教程（第3版）-課件 第9章 目標(biāo)代碼的生成

新工科建設(shè)·計(jì)算機(jī)類系列教材

免費(fèi)提供編譯原理16目錄第一章概述第二章形式語(yǔ)言理論基礎(chǔ)第三章自動(dòng)機(jī)理論基礎(chǔ)第四章詞法分析第五章語(yǔ)法分析—自頂向下分析方法第六章語(yǔ)法分析—自底向上分析方法第七章語(yǔ)義分析及中間代碼的生成第八章代碼優(yōu)化第九章目標(biāo)代碼的生成第十章符號(hào)表和出錯(cuò)處理第十一章

面向?qū)ο笳Z(yǔ)言的編譯第十二章

并行編譯技術(shù)第十三章

軟件構(gòu)造22024/11/63學(xué)習(xí)目標(biāo)了解和掌握目標(biāo)代碼生成程序中的有關(guān)問(wèn)題了解和掌握虛擬機(jī)了解和掌握從中間代碼生成目標(biāo)代碼9目標(biāo)代碼的生成重點(diǎn)：虛擬機(jī)、目標(biāo)代碼生成難點(diǎn)：從中間代碼生成目標(biāo)代碼

目錄9.1目標(biāo)代碼生成概述9.2一個(gè)計(jì)算機(jī)模型——虛擬機(jī)9.3從中間代碼生成目標(biāo)代碼9.4目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)管理9.5本章小結(jié)49.1目標(biāo)代碼生成概述目標(biāo)代碼生成是編譯程序的最后一個(gè)工作階段。它取先行階段所產(chǎn)生的源程序的中間語(yǔ)言或優(yōu)化后的中間語(yǔ)言表示作為輸入，產(chǎn)生等價(jià)的目標(biāo)代碼作為輸出，如下圖所示。9.1目標(biāo)代碼生成概述好的代碼生成程序:

生成的目標(biāo)代碼盡可能地短，

能較充分地發(fā)揮目標(biāo)計(jì)算機(jī)可用資源的效率。熟悉目標(biāo)機(jī)器和它的指令系統(tǒng)是設(shè)計(jì)一個(gè)好的代碼生成程序的先決條件，不以某一臺(tái)具體的計(jì)算機(jī)做背景，只是針對(duì)一個(gè)假想的計(jì)算機(jī)模型——虛擬機(jī)給出生成目標(biāo)代碼的算法。9.1.1目標(biāo)代碼的生成7①能夠立即執(zhí)行的機(jī)器語(yǔ)言代碼，所有地址均已定位。即具有絕對(duì)地址的機(jī)器語(yǔ)言代碼。

②待裝配的機(jī)器語(yǔ)言模塊。需要執(zhí)行時(shí)，由連接裝配程序把它們和某些運(yùn)行程序連接起來(lái)，裝配成可以執(zhí)行的機(jī)器語(yǔ)言代碼。即可浮動(dòng)的機(jī)器語(yǔ)言代碼。

代碼生成程序的輸出的形式一般有以下三種形式：③匯編語(yǔ)言形式的代碼。需要經(jīng)過(guò)匯編程序匯編轉(zhuǎn)換成可執(zhí)行的機(jī)器語(yǔ)言代碼。9.1.1目標(biāo)代碼的生成8本章采用匯編語(yǔ)言代碼作為目標(biāo)代碼，但不針對(duì)某種特定的目標(biāo)機(jī)指令系統(tǒng)或匯編語(yǔ)言來(lái)生成目標(biāo)代碼，而是假設(shè)有一臺(tái)計(jì)算機(jī)，其指令系統(tǒng)等均按某種需要而設(shè)定，為教學(xué)目的往往采取這種虛擬機(jī)目標(biāo)代碼形式。下面就以一種虛擬機(jī)指令系統(tǒng)來(lái)討論目標(biāo)代碼的生成。9.1.2寄存器分配9

充分利用寄存器對(duì)生成高質(zhì)量目標(biāo)代碼尤其重要。

寄存器的分配成為目標(biāo)代碼生成中的主要問(wèn)題。

寄存器的分配策略與目標(biāo)機(jī)的資源密切相關(guān)。

有些機(jī)器中的寄存器分為變址器和數(shù)據(jù)寄存器，還有些機(jī)器的寄存器可以通用。按用途不同，寄存器可分為作為變址器使用、專供操作系統(tǒng)使用、用于目標(biāo)代碼中存放引用次數(shù)最多的變量三類。9.1.2寄存器分配操作碼操作數(shù)1操作數(shù)2執(zhí)行代價(jià)OP寄存器寄存器1寄存器內(nèi)存單元2寄存器寄存器間接地址2寄存器內(nèi)存間接地址3根據(jù)訪問(wèn)內(nèi)存數(shù)來(lái)定義每條指令的執(zhí)行代價(jià)，則對(duì)于以下的一些操作有其相應(yīng)的執(zhí)行代價(jià)：

9.2一個(gè)計(jì)算機(jī)模型——虛擬機(jī)11

為了使下面的討論比較簡(jiǎn)明和具有一般性，出于教學(xué)的目的，比較合適的是采取虛擬機(jī)目標(biāo)代碼形式，假設(shè)在某臺(tái)虛擬的計(jì)算機(jī)上分析。9.2.1虛擬機(jī)9.2.1虛擬機(jī)虛擬機(jī)不是一臺(tái)實(shí)際的機(jī)器，而是便于討論的一臺(tái)假想和抽象的計(jì)算機(jī)。假設(shè)這臺(tái)虛擬機(jī)有如下特性：該虛擬機(jī)是一臺(tái)地址單累加器的計(jì)算機(jī)，用“AC”表示該累加器；設(shè)OP為操作碼，d為地址，則指令：

0Pd表示ACOPd=>AC9.2.1虛擬機(jī)9.2.2虛擬機(jī)的匯編指令1．填地址指令設(shè)有一維數(shù)組a：array[m..n]ofinteger；其元素有a[m],a[m+1],…,a[i],…,a[n]，一共需要n-m+1個(gè)存儲(chǔ)單元：<a[m]>，<a[m+1]>，…，<a[i]>，…，<a[n]>一般有存儲(chǔ)單元：<a[i]>=<a[m]>+i-m由于<a[0]>=<a[m]-m，所以有<a[m]>=<a[0]>+m。從而對(duì)于一維數(shù)組的存儲(chǔ)單元，有公式：<a[i]>=<a[0]>+i其中<a[0]>稱為數(shù)組的假頭，<a[m]>稱為數(shù)組的真頭。9.2.2虛擬機(jī)的匯編指令2．按真轉(zhuǎn)編寫程序9.2.2虛擬機(jī)的匯編指令3．按假轉(zhuǎn)編寫程序9.3.1從逆波蘭表生成目標(biāo)代碼例如，對(duì)于逆波蘭表達(dá)式：ab*cd+e/-具體生成目標(biāo)代碼處理過(guò)程如表9.2所示。9.3.1從逆波蘭表生成目標(biāo)代碼上面首先把簡(jiǎn)單表達(dá)式改造成中間語(yǔ)言的逆波蘭形式，然后由逆波蘭表達(dá)式生成目標(biāo)代碼。實(shí)際中也常把兩步合為一步，根據(jù)運(yùn)算符優(yōu)先數(shù)的大小關(guān)系，直接對(duì)簡(jiǎn)單表達(dá)式進(jìn)行語(yǔ)法語(yǔ)義分析。為了處理簡(jiǎn)單起見，規(guī)定被處理的簡(jiǎn)單表達(dá)式的前后都有特殊符號(hào)“#”，即呈下列形式：

#<簡(jiǎn)單表達(dá)式>#并把“#”視為優(yōu)先數(shù)為0的運(yùn)算符。同時(shí)引進(jìn)運(yùn)算符棧(棧)與運(yùn)算分量棧(棧)，相應(yīng)算法如下。9.3.1從逆波蘭表生成目標(biāo)代碼9.3.2從四元式序列生成目標(biāo)代碼例如，對(duì)于中綴表達(dá)式“#a+(b-c)/d#”運(yùn)用以上算法直接生成目標(biāo)代碼處理過(guò)程如表9.4所示。9.4目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)管理21

編譯程序目的是將源程序翻譯成等價(jià)的目標(biāo)程序，為此編譯程序在工作過(guò)程中，必須為源程序中所出現(xiàn)的一些標(biāo)識(shí)符(如常量、變量及數(shù)組等)分配運(yùn)行時(shí)的存儲(chǔ)空間。

在程序的執(zhí)行過(guò)程中，程序中數(shù)據(jù)的存取就是通過(guò)對(duì)應(yīng)的存儲(chǔ)單元進(jìn)行的。

對(duì)編譯程序來(lái)說(shuō)，存儲(chǔ)的組織與分配是一個(gè)既復(fù)雜又十分重要的問(wèn)題。

9.4.1程序運(yùn)行時(shí)的存儲(chǔ)組織

程序在運(yùn)行時(shí)，系統(tǒng)將為其分配一塊存儲(chǔ)空間，該空間需容納程序生成的目標(biāo)代碼以及目標(biāo)代碼運(yùn)行時(shí)的各種數(shù)據(jù)。從用途上來(lái)看，存儲(chǔ)空間可以劃分為幾個(gè)部分(如圖所示)。①目標(biāo)程序區(qū)，用來(lái)存放目標(biāo)代碼。②靜態(tài)數(shù)據(jù)區(qū)，用來(lái)存放編譯時(shí)就能確定存儲(chǔ)空間的數(shù)據(jù)。③運(yùn)行棧區(qū)，用來(lái)存放運(yùn)行時(shí)才能確定存儲(chǔ)空間的數(shù)據(jù)。④運(yùn)行堆區(qū)，用來(lái)存放運(yùn)行時(shí)用戶動(dòng)態(tài)申請(qǐng)存儲(chǔ)空間的數(shù)據(jù)。9.4.1程序運(yùn)行時(shí)的存儲(chǔ)組織如果一個(gè)程序設(shè)計(jì)語(yǔ)言允許使用遞歸過(guò)程、可變數(shù)組或可變數(shù)據(jù)結(jié)構(gòu)，那么就需要采用棧式、堆式的動(dòng)態(tài)存儲(chǔ)管理技術(shù)，程序運(yùn)行時(shí)堆、棧的大小可隨程序的運(yùn)行而改變。圖9.2所示為堆、棧共用一空白存儲(chǔ)區(qū)，并使它們各自的增長(zhǎng)方向相對(duì)，這樣可以充分利用存儲(chǔ)空間。編譯程序所生成的目標(biāo)代碼的大小在編譯時(shí)(最遲在連接之后)就可確定，因此編譯程序可以把它放在一個(gè)靜態(tài)確定的區(qū)域——目標(biāo)程序區(qū)。9.4.2靜態(tài)存儲(chǔ)分配靜態(tài)存儲(chǔ)分配是一種最簡(jiǎn)單的分配方式。許多早期的程序語(yǔ)言，如Fortran、BASIC和COBOL等，都采用這種靜態(tài)分配方式。所謂靜態(tài)存儲(chǔ)分配就是在編譯時(shí)對(duì)所有的數(shù)據(jù)項(xiàng)分配固定的存儲(chǔ)單元，且在運(yùn)行時(shí)始終保持不變。具體地說(shuō)，適用于靜態(tài)存儲(chǔ)分配的程序設(shè)計(jì)語(yǔ)言必須滿足下列條件：不允許過(guò)程的遞歸調(diào)用；不允許含可變大小的數(shù)據(jù)(如數(shù)組的上下界必須是常數(shù))；不允許用戶動(dòng)態(tài)地建立數(shù)據(jù)實(shí)體(如不允許那些需在運(yùn)行時(shí)動(dòng)態(tài)確定的數(shù)據(jù)項(xiàng))。9.4.3棧式動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序設(shè)計(jì)語(yǔ)言允許使用遞歸過(guò)程、可變數(shù)組或可變數(shù)據(jù)結(jié)構(gòu)，則無(wú)法采用靜態(tài)存儲(chǔ)管理方法。因?yàn)閷?duì)于這樣的語(yǔ)言來(lái)說(shuō)，程序在編譯時(shí)無(wú)法確定它在運(yùn)行時(shí)所需存儲(chǔ)空間的大小，所以在程序運(yùn)行時(shí)只能采用動(dòng)態(tài)存儲(chǔ)管理的方式，在程序運(yùn)行時(shí)對(duì)存儲(chǔ)空間進(jìn)行動(dòng)態(tài)分配。動(dòng)態(tài)存儲(chǔ)分配方式有兩種，首先介紹棧式動(dòng)態(tài)存儲(chǔ)分配。棧式存儲(chǔ)分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧，每當(dāng)程序調(diào)用一個(gè)過(guò)程時(shí)，就在棧頂為其分配數(shù)據(jù)空間，當(dāng)調(diào)用結(jié)束時(shí)，就釋放這部分空間。這種方式適用于C、Pascal、ALOGOL、PL/1語(yǔ)言。9.4.3棧式動(dòng)態(tài)存儲(chǔ)分配在C、Pascal等語(yǔ)言的實(shí)現(xiàn)系統(tǒng)中，使用棧的方式來(lái)管理整個(gè)過(guò)程的活動(dòng)，為了管理一個(gè)過(guò)程在一次執(zhí)行時(shí)所需要的信息，常使用一段連續(xù)的存貯區(qū)，這個(gè)存貯區(qū)稱為活動(dòng)記錄(ActivationRecord，AR)，其結(jié)構(gòu)如圖9.5。圖9.5活動(dòng)記錄的結(jié)構(gòu)9.4.3棧式動(dòng)態(tài)存儲(chǔ)分配1．簡(jiǎn)單的棧式存儲(chǔ)分配有一些語(yǔ)言雖然允許過(guò)程遞歸調(diào)用，但是不允許過(guò)程嵌套定義，也沒(méi)有分程序結(jié)構(gòu)，這些語(yǔ)言可以采用一種比較簡(jiǎn)單的棧式存儲(chǔ)分配方式。例如，C語(yǔ)言就是這樣一種語(yǔ)言。9.4.3棧式動(dòng)態(tài)存儲(chǔ)分配在上述C程序中，若主程序調(diào)用了過(guò)程P1，P1又調(diào)用了P2，那么在P2進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖9.6(a)所示；若主程序調(diào)用了過(guò)程P2，P2又遞歸調(diào)用自己，在P2過(guò)程第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖9.6(b)所示。圖9.6C程序的棧式存儲(chǔ)分配

在簡(jiǎn)單棧式存儲(chǔ)分配方法中，常用到兩個(gè)指示器(SP和TOP)指向棧最頂端的數(shù)據(jù)區(qū)，其中SP指向最新的過(guò)程活動(dòng)記錄的起點(diǎn)，TOP則指向當(dāng)前棧的棧頂單元。9.4.3棧式動(dòng)態(tài)存儲(chǔ)分配2．嵌套過(guò)程語(yǔ)言的棧式存儲(chǔ)分配

Pascal等語(yǔ)言的程序結(jié)構(gòu)中允許過(guò)程嵌套定義，因此這類語(yǔ)言的存儲(chǔ)分配不能運(yùn)用簡(jiǎn)單的棧式辦法來(lái)實(shí)現(xiàn)。為了便于討論，對(duì)Pascal語(yǔ)言中的一些數(shù)據(jù)類型(如“文件”和“指針”等)不予考慮，這樣仍然可以采用棧式動(dòng)態(tài)分配策略，只是在過(guò)程活動(dòng)記錄中需增加一些內(nèi)容，用以解決對(duì)全局變量的引用問(wèn)題。首先來(lái)看一個(gè)省略的Pascal程序，其中包含了該程序中各過(guò)程之間的嵌套關(guān)系以及各變量的作用域。9.4.3棧式動(dòng)態(tài)存儲(chǔ)分配9.4.3棧式動(dòng)態(tài)存儲(chǔ)分配討論兩種方法，一種是在過(guò)程活動(dòng)記錄中增設(shè)存取鏈(也稱靜態(tài)鏈)，指向包含該過(guò)程的直接外層過(guò)程的最新活動(dòng)記錄的地址，其過(guò)程活動(dòng)記錄的內(nèi)容如圖9.7所示。

另一種是在建立過(guò)程活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表display圖9.7過(guò)程活動(dòng)記錄的結(jié)構(gòu)(嵌套定義過(guò)程)圖9.9display表和運(yùn)行棧9.4.4堆式動(dòng)態(tài)存儲(chǔ)分配堆式存儲(chǔ)分配在運(yùn)行時(shí)動(dòng)態(tài)地進(jìn)行，它是最靈活也是最昂貴的一種存儲(chǔ)分配方式。假設(shè)程序運(yùn)行時(shí)有一個(gè)大的存儲(chǔ)空間，每當(dāng)需要時(shí)就從這片空間中申請(qǐng)一塊，不用時(shí)再釋放給它。由于塊可以按任意順序釋放，經(jīng)過(guò)一段運(yùn)行時(shí)間后，堆將被劃分成若干塊，這些塊有些正在使用，是有用塊，而有一些塊是空閑的，是無(wú)用塊，如圖9.10所示。圖9.10堆式存儲(chǔ)分配過(guò)程中的內(nèi)存狀態(tài)9.4.4堆式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)管理可以采取多種策略進(jìn)行。介紹一種使用可利用空間表進(jìn)行動(dòng)態(tài)分配的方法。可利用空間表是指將所有空閑塊用一張表記錄下來(lái)，表的結(jié)構(gòu)可以是目錄表，也可以是鏈表，如圖9.11所示。圖9.11內(nèi)存狀態(tài)和可利用空間表9.5本章小結(jié)341．目標(biāo)代碼生成程序的輸入是由先行端產(chǎn)生的源程序的中間代碼表示，輸出是目標(biāo)代碼2．按用途不同寄存器可以分為三類：寄存器作為變址器使有、專供操作系統(tǒng)使