新工科建設·計算機類系列教材

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

面向對象語言的編譯第十二章

并行編譯技術第十三章

軟件構造22024/11/63學習目標了解和掌握目標代碼生成程序中的有關問題了解和掌握虛擬機了解和掌握從中間代碼生成目標代碼9目標代碼的生成重點：虛擬機、目標代碼生成難點：從中間代碼生成目標代碼

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

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

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

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

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

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

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

寄存器的分配策略與目標機的資源密切相關。

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

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

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

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

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

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

在程序的執行過程中，程序中數據的存取就是通過對應的存儲單元進行的。

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

9.4.1程序運行時的存儲組織

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

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

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

另一種是在建立過程活動記錄的同時建立一張嵌套層次顯示表display圖9.7過程活動記錄的結構(嵌套定義過程)圖9.9display表和運行棧9.4.4堆式動態存儲分配堆式存儲分配在運行時動態地進行，它是最靈活也是最昂貴的一種存儲分配方式。假設程序運行時有一個大的存儲空間，每當需要時就從這片空間中申請一塊，不用時再釋放給它。由于塊可以按任意順序釋放，經過一段運行時間后，堆將被劃分成若干塊，這些塊有些正在使用，是有用塊，而有一些塊是空閑的，是無用塊，如圖9.10所示。圖9.10堆式存儲分配過程中的內存狀態9.4.4堆式動態存儲分配堆式動態存儲管理可以采取多種策略進行。介紹一種使用可利用空間表進行動態分配的方法。可利用空間表是指將所有空閑塊用一張表記錄下來，表的結構可以是目錄表，也可以是鏈表，如圖9.11所示。圖9.11內存狀態和可利用空間表9.5本章小結341．目標代碼生成程序的輸入是由先行端產生的源程序的中間代碼表示，輸出是目標代碼2．按用途不同寄存器可以分為三類：寄存器作為變址器使有、專供操作系統使用、用于目標代碼中存放引用次數最多的變量三類3．討論了一個計算機模型—虛擬機，并在此基礎上討論了從逆波蘭表示生成目標代碼及從四元式序列生成目標代碼4．存儲分配是在目標程序運行階段進行的5.存儲的組織與分配的方式有：靜態存儲分配、棧式動態存儲分配、堆式動態存儲分配。35總結

本章我們學習了什么是目標代碼的生成、一種計算機模型——虛擬機、從中間代碼生成目標代碼、目標程序運行時的存儲管理等內容。

下一章將學習符號表和出錯處理。THANKS36THANKS新工科建設·計算機類系列教材

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

面向對象語言的編譯第十二章

并行編譯技術第十三章

軟件構造382024/11/639學習目標10符號表和出錯處理

符號表在整個編譯期間的作用主要有兩條：一是輔助語義的（即上下文有關的）正確性檢查；二是輔助代碼生成。著重需要掌握以下內容符號表的作用符號表中的內容嵌套結構語言的棧式符號表

目錄10.1符號表的結構與存放10.2符號表的建立10.3程序的錯誤10.4出錯處理10.5本章小結40

符號表是一個包含程序中的變量、子程序、常量、過程定義、數組信息等內容的數據庫。

一般地，符號表由一些表項組成二維表格。

名字域

—存放符號或其內部碼每個表項

屬性域

—存放屬性和特征例如：

名字域屬性域名字1屬性1......名字n屬性n10.1符號表的結構和存放符號表的組織方式簡單方式：固定名字域和屬性域的長度。

有的語言標識符長度不超過6個字符，可定為6位。間接方式：在符號表的名字域中存放一個指針或一個指針和一個整數，把標識符存放到一個字符串數組中。見圖10.210.1.1符號表的組織和內容符號表的內容

屬性域的內容因符號表名字域內容不同而不同。例如數組：維數、下標界偶、存儲區域等信息數組信息向量表。如圖10.3。

靜態表（編譯前事先構造好）：保留字表、標符號表

準函數名表等。

動態表（編譯過程中根據需要構造的表）：變量名表數組信息表、過程信息表等。10.1.1符號表的組織和內容變量表

如圖10.4線性表(無序符號表):按程序中符號出現的先后次序建立的表。如圖10.5查找方式:只能線性查找，(查找效率低)，結構簡單，節省空間，適合于比較小的表。10.1.2線性符號表名字類型地址SUM實型100AVER實型102COUNT整型104項數名字域屬性域1a……2ave……3b1……4sum……………

有序符號表：按一定順序(如字典順序)排列符號。如圖10.6、10.7查找:折半查找法,查找效率較高。

但填入表時會增加移動開銷。10.1.3有序符號表項數名字域屬性域1a……2ave……3b1……4sum……………

散列符號表（哈希符號表）：利用哈希函數值確定符號在表中的位置。hash函數性質：·函數值只依賴于對應符號·函數計算簡單、高效·函數值能較均勻分布如:除法散列函數、乘法散列函數、多項式除法散列函數、平方取中散列函數等。“質數除余法”見圖10.8查詢效率較高，但要解決散列沖突問題。10.1.4散列符號表（哈希符號表）設計一個棧，新符號出現從棧頂壓入。查找時從棧頂→棧底例

PASCAL語言分程序嵌套結構例10-1程序的棧式符號表如圖10.9、10.10、10.11查找時，最新加入的符號總是最先查找。

適合嵌套結構的程序設計語言，但表太大時，查找速度較慢。10.1.5棧式符號表10.2.1符號表的建立48一、符號表的初始化漸增符號表。如線性符號表和有序符號表

定長符號表。如散列符號表在初始狀態時，表的內容都應該為空。一般符號表在詞法分析時創建，其它階段都可能要填表。如圖10.12、10.1310.2.2符號表的查填一、對符號表的操作

·對給定符號，查看是否是在表中

·對沒查到的符號，向表中填入

·對已查到的符號，查詢有關信息

·對已查到的符號，增加或更新有關信息

·刪除一個或一組無用表項二、查填符號表的形式可分為兩種情況：

1、隱式說明語言的符號表查填如FORTRAN“I–N”規則。語句中每出現一個符號均需查表，當第一次出現時填表。502、顯式說明語言的符號表查填如Pascal、C語言

說明部分：出現的符號，先查表，若沒有，則填表。語句部分：出現的符號，先查表，若查不到，到外層

查(對于分程序結構)，最后仍未查到，說明該符號未

定義，輸出出錯信息。10.2.2符號表的查填通常用程序設計語言編寫的源程序往往包含一些錯誤，很少能一次在機器上通過，并算出預期結果，需要反復修改和調試。所以，人們希望編譯程序能有較強的錯誤處理能力，能檢查出程序中的各種錯誤，并準確無誤地報告出這些錯誤的性質和位置。5110.3程序的錯誤

編譯程序用來對源程序進行編譯，當程序在語法(包括詞法)上正確時，可以得到相應的等價的目標代碼。當程序在語義上正確時，以正確的輸入數據運行目標代碼可以得到預期的輸出結果。然而，一個程序，尤其是大型軟件的程序，其中難免包含錯誤。5210.3.1錯誤存在的必然性5310.3.2錯誤的種類①詞法錯誤。②語法錯誤。③語義錯誤。④違反環境限制的錯誤。程序錯誤的種類

在編譯的過程中，發現源程序的錯誤時采取一定的措施，使得能繼續編譯下去，這稱為錯誤復原。如果把所給不正確程序變換成正確的程序，則稱之為錯誤校正。在錯誤復原時，應重視以下兩個方面： 1.株連信息的遏止。 2.重復信息的遏止。5410.3.3錯誤復原詞法的錯誤：詞法分析時發現的詞法錯誤大多是單詞拼寫錯誤語法的錯誤:不同的語法分析技術發現錯誤的手段和方式是不同的語義的錯誤:一般分為兩類，一類是在編譯時可以發現的靜態語義錯誤，另一類是在運行時才能發現的動態語義錯誤。5510.4出錯處理5610.4.1詞法錯誤的處理

詞法分析時發現的詞法錯誤大多是單詞拼寫錯誤，這或者是因為書寫錯誤，或者是因為輸入錯誤假定不會有連續幾個字符的錯誤，可以假定有如下幾類詞法錯誤：拼錯一個字符，如RECORD錯寫成RCCORD。遺漏一個字符，如RE