編譯原理簡明教程（第3版）-課件 第9章 目標代碼的生成

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

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

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

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

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

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

生成的目標代碼盡可能地短，

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

②待裝配的機器語言模塊。需要執(zhí)行時，由連接裝配程序把它們和某些運行程序連接起來，裝配成可以執(zhí)行的機器語言代碼。即可浮動的機器語言代碼。

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

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

寄存器的分配成為目標代碼生成中的主要問題。

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

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

9.2一個計算機模型——虛擬機11

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

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

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

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

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

對編譯程序來說，存儲的組織與分配是一個既復(fù)雜又十分重要的問題。

9.4.1程序運行時的存儲組織

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

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

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

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