編譯原理簡明教程（第3版）-課件 第9、10章 目標代碼的生成、符號表和出錯處理

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

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

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

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

軟件構(gòu)造22024/11/63學習目標了解和掌握目標代碼生成程序中的有關(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è)定，為教學目的往往采取這種虛擬機目標代碼形式。下面就以一種虛擬機指令系統(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í)行代價，則對于以下的一些操作有其相應的執(zhí)行代價：

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

為了使下面的討論比較簡明和具有一般性，出于教學的目的，比較合適的是采取虛擬機目標代碼形式，假設(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的運算符。同時引進運算符棧(棧)與運算分量棧(棧)，相應算法如下。9.3.1從逆波蘭表生成目標代碼9.3.2從四元式序列生成目標代碼例如，對于中綴表達式“#a+(b-c)/d#”運用以上算法直接生成目標代碼處理過程如表9.4所示。9.4目標程序運行時的存儲管理21

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

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

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

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è)計為一個棧，每當程序調(diào)用一個過程時，就在棧頂為其分配數(shù)據(jù)空間，當調(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則指向當前棧的棧頂單元。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è)程序運行時有一個大的存儲空間，每當需要時就從這片空間中申請一塊，不用時再釋放給它。由于塊可以按任意順序釋放，經(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)使用、用于目標代碼中存放引用次數(shù)最多的變量三類3．討論了一個計算機模型—虛擬機，并在此基礎(chǔ)上討論了從逆波蘭表示生成目標代碼及從四元式序列生成目標代碼4．存儲分配是在目標程序運行階段進行的5.存儲的組織與分配的方式有：靜態(tài)存儲分配、棧式動態(tài)存儲分配、堆式動態(tài)存儲分配。35總結(jié)

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

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

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

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

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

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

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

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

符號表是一個包含程序中的變量、子程序、常量、過程定義、數(shù)組信息等內(nèi)容的數(shù)據(jù)庫。

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

名字域

—存放符號或其內(nèi)部碼每個表項

屬性域

—存放屬性和特征例如：

名字域?qū)傩杂蛎?屬性1......名字n屬性n10.1符號表的結(jié)構(gòu)和存放符號表的組織方式簡單方式：固定名字域和屬性域的長度。

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

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

靜態(tài)表（編譯前事先構(gòu)造好）：保留字表、標符號表

準函數(shù)名表等。

動態(tài)表（編譯過程中根據(jù)需要構(gòu)造的表）：變量名表數(shù)組信息表、過程信息表等。10.1.1符號表的組織和內(nèi)容變量表

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

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

但填入表時會增加移動開銷。10.1.3有序符號表項數(shù)名字域?qū)傩杂?a……2ave……3b1……4sum……………

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

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

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

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

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

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

·對已查到的符號，查詢有關(guān)信息

·對已查到的符號，增加或更新有關(guān)信息

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

1、隱式說明語言的符號表查填如FORTRAN“I–N”規(guī)則。語句中每出現(xiàn)一個符號均需查表，當?shù)谝淮纬霈F(xiàn)時填表。502、顯式說明語言的符號表查填如Pascal、C語言

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

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

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

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

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

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