編譯原理第5版-課件 第8章 目標(biāo)程序運行時的存儲組織

編譯程序需進(jìn)行目標(biāo)程序運行環(huán)境的設(shè)計和數(shù)據(jù)空間的分配。本章主要介紹：靜態(tài)存儲分配策略動態(tài)存儲分配策略第8章目標(biāo)程序運行時的存儲組織18.1概述編譯程序的最終目的是將源程序翻譯成等價的目標(biāo)程序，為了達(dá)到此目的，編譯程序除了對源程序進(jìn)行詞法分析、語法分析和語義分析外，在生成目標(biāo)代碼之前，還必需進(jìn)行目標(biāo)程序運行環(huán)境的設(shè)計和數(shù)據(jù)空間的分配。2運行時的環(huán)境：是指目標(biāo)計算機(jī)的寄存器和存儲器的結(jié)構(gòu)，以及用來管理存儲器并保存指導(dǎo)執(zhí)行過程所需要的信息。如編譯程序從操作系統(tǒng)中得到一塊存儲區(qū)，以使目標(biāo)程序在其上運行，該存儲區(qū)需容納生成的目標(biāo)代碼和目標(biāo)代碼運行時的數(shù)據(jù)空間。8.1概述3數(shù)據(jù)空間：包括用戶定義的各種類型的數(shù)據(jù)對象所需的存儲空間、調(diào)用過程所需的連接單元和組織輸入/輸出所需的緩沖區(qū)及保留中間結(jié)果和傳遞參數(shù)所需的臨時單元等。運行時的存儲空間通常被劃分成：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如下圖所示。8.1概述48.1概述其中，目標(biāo)代碼區(qū)用于存放生成的目標(biāo)代碼，它的長度是固定的，即能在編譯時確定，靜態(tài)數(shù)據(jù)區(qū)用于存放編譯時所能確定占用空間大小的數(shù)據(jù)，堆、棧區(qū)用于存放可變數(shù)據(jù)以及管理過程活動的控制信息。運行時存儲空間的劃分目標(biāo)代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)棧自由空間堆5程序設(shè)計語言關(guān)于名字的作用域和生成期的定義規(guī)則決定了分配目標(biāo)程序數(shù)據(jù)空間的基本策略。在大部分現(xiàn)有編譯中目標(biāo)程序數(shù)據(jù)空間的分配策略有：8.1概述靜態(tài)存儲分配策略分配策略動態(tài)存儲分配策略棧式動態(tài)存儲分配堆式動態(tài)存儲分配6靜態(tài)存儲分配策略編譯時對源程序中各數(shù)據(jù)項分配固定的存儲空間，運行時始終不變。動態(tài)存儲分配策略運行階段動態(tài)地為源程序中的數(shù)據(jù)項分配存儲空間。8.1概述7(1)棧式動態(tài)存儲分配用一個棧作為動態(tài)分配的存儲空間。運行時，每當(dāng)調(diào)用一個子程序(過程)，所需存儲空間就動態(tài)地分配于棧頂，退出時釋放所占用的空間。(2)堆式動態(tài)存儲分配運行時把存儲區(qū)組織成堆，以便用戶動態(tài)地申請或釋放存儲空間。8.1概述88.2靜態(tài)存儲分配靜態(tài)存儲分配編譯階段對源程序中各數(shù)據(jù)項分配固定的存儲空間，運行時始終不變。如果在編譯時能確定目標(biāo)程序運行中所需要的全部數(shù)據(jù)空間的大小，編譯時安排好目標(biāo)程序運行時的全部數(shù)據(jù)空間，并確定每個數(shù)據(jù)項的存儲位置（單元地址），則稱這種分配策略為靜態(tài)存儲分配。98.2靜態(tài)存儲分配對語言要求（1）程序中每一個數(shù)據(jù)對象的大小在編譯階段能夠確定即不允許有可變體積的數(shù)據(jù)如可變數(shù)組等；（2）程序運行過程中的給定時刻，每一個數(shù)據(jù)對象只允許存在一個實例即不允許有遞歸等；108.2靜態(tài)存儲分配（3）所有數(shù)據(jù)的性質(zhì)是完全確定（即不允許有須在運行時動態(tài)確定性質(zhì)的名字）。例如FORTRAN77是滿足上述特點的語言。11 FORTRAN77采用的是靜態(tài)存儲分配，它的程序是段結(jié)構(gòu)的，整個程序由主程序段和若干個子程序段組成，各程序段中定義的名字一般彼此獨立，它的每個數(shù)據(jù)名所需的存儲空間大小都是常量，并且不允許遞歸調(diào)用。這樣，整個程序所需數(shù)據(jù)空間的總量在編譯時就能完全確定，從而每個數(shù)據(jù)名的地址就可靜態(tài)進(jìn)行分配。8.2靜態(tài)存儲分配128.2靜態(tài)存儲分配下面給出一個FORTRAN77的程序例子(1)PROGRAMCNSUME(2)CHARACTER*50BUF(3)INTEGERNEXT(4)CHARACTERC,PRDUCE(5)DATANEXT/1/,BUF/‘‘/(6)6C=PRDUCE()(7)BUF(NEXT:NEXT)=C(8)NEXT=NEXT+1(9)IF(C.EN.‘‘)GOTO6(10)WRITE(*,‘(A)’)BUF(11)END (12)CHARACTERFUNCTIONPRDUCE() (13)CHARACTER*80BUFFER(14)INTEGERNEXT (15)SAVEBUFFER,NEXT (16)DATANEXT/81/ (17)IF(NEXT.GT.80)THEN (18)READ(*,‘(A)’)BUFFER(19)NEXT=1(20)ENDIF(21)PRDUCE=BUFFER(NEXT:NEXT)(22)NEXT=NEXT+1(23)END13CNSUME的代碼PRDUCE的代碼CHARACTER*50BUFINTEGERNEXTCHARACTERCCHARACTER*80BUFFERINTEGERNEXT該圖描述了程序中局部變量的靜態(tài)存儲位置。代碼靜態(tài)數(shù)據(jù)8.2靜態(tài)存儲分配14動態(tài)存儲分配策略運行階段動態(tài)地為源程序中的數(shù)據(jù)項分配存儲空間。(1)棧式動態(tài)存儲分配用一個棧作為動態(tài)分配的存儲空間。運行時，每當(dāng)調(diào)用一個子程序(過程)，所需存儲空間就動態(tài)地分配于棧頂，退出時釋放所占用的空間。8.2靜態(tài)存儲分配158.3動態(tài)存儲分配(2)堆式動態(tài)存儲分配運行時把存儲區(qū)組織成堆，以便用戶動態(tài)地申請或釋放存儲空間。16如果一個程序設(shè)計語言允許遞歸調(diào)用、可變數(shù)組或每次調(diào)用都要重新分配局部變量，那么，就需要采用動態(tài)存儲分配策略。因為對于這種情況，編譯程序無法知道它在運行時需要多大的存儲空間，它所需要的存儲空間的大小需待運行時動態(tài)地確定。8.3動態(tài)存儲分配17為討論方便，引入術(shù)語—活動記錄。過程的活動記錄是一段連續(xù)的存儲區(qū)，用以存放過程的一次執(zhí)行所需要的信息。8.3動態(tài)存儲分配18臨時變量內(nèi)情向量局部變量形式單元靜態(tài)鏈動態(tài)鏈返回地址1.返回地址保存該被調(diào)過程返回后的地址。2.動態(tài)鏈指向調(diào)用該過程前的最新活動記錄地址(即前一個活動記錄的地址)。SPTOP8.3動態(tài)存儲分配活動記錄至少應(yīng)該包括以下幾個部分193.靜態(tài)鏈指向靜態(tài)直接外層最新活動記錄地址的指針，用來訪問非局部數(shù)據(jù)。8.3動態(tài)存儲分配臨時變量內(nèi)情向量局部變量形式單元靜態(tài)鏈動態(tài)鏈返回地址SPTOP204.形式單元存放相應(yīng)的實在參數(shù)的地址或值。5.局部變量一個子程序(過程)的局部變量。臨時變量內(nèi)情向量局部變量形式單元靜態(tài)鏈動態(tài)鏈返回地址SPTOP8.3動態(tài)存儲分配216.臨時變量比如計算表達(dá)式過程中需存放中間結(jié)果用的臨時值單元。臨時變量內(nèi)情向量局部變量形式單元靜態(tài)鏈動態(tài)鏈返回地址SPTOP連接數(shù)據(jù)8.3動態(tài)存儲分配22SP總是指向現(xiàn)行過程活動記錄的起始地址TOP則始終指向已占用的棧頂單元。臨時變量內(nèi)情向量局部變量形式單元靜態(tài)鏈動態(tài)鏈返回地址SPTOP8.3動態(tài)存儲分配23簡單棧式存儲分配對于沒有分程序結(jié)構(gòu)，過程定義不允許嵌套但允許過程遞歸調(diào)用的語言，我們可以采用一種簡單的棧式存儲分配策略。C語言就是滿足上述特點的一種語言。8.3.1簡單棧式存儲分配24C語言其過程的活動記錄一般采用如圖所示結(jié)構(gòu)。圖中使用兩個指針(SP和TOP)指示棧最頂端的數(shù)據(jù)區(qū)，SP總是指向現(xiàn)行過程活動記錄的起點臨時工作單元局部數(shù)組的內(nèi)情向量局部簡單變量實參(形式單元)參數(shù)個數(shù)返回地址動態(tài)(控制)鏈(老SP)（前一活動記錄的地址）SPTOP8.3.1簡單棧式存儲分配25TOP則始終指向已占用的棧頂單元。臨時工作單元局部數(shù)組的內(nèi)情向量局部簡單變量實參(形式單元)參數(shù)個數(shù)返回地址控制鏈(老SP)（前一活動記錄的地址）SPTOP8.3.1簡單棧式存儲分配26由圖可知，過程的每一個局部變量或形參在活動記錄中的相對地址是確定的，因此可以知道程序運行時，變量和形參在棧上的絕對地址是：絕對地址＝活動記錄基地址(SP)＋相對地址臨時工作單元局部數(shù)組的內(nèi)情向量局部簡單變量實參(形式單元)參數(shù)個數(shù)返回地址控制鏈(老SP)(前一活動記錄的地址)SPTOP8.3.1簡單棧式存儲分配27相對地址：相對于活動記錄起點的地址，它在編譯時可完全確定。對任何局部變量x的引用可表示為變址訪問x[sp],此處x為變量x的相對地址。x[sp]表示地址為x+sp即x所在地址)臨時工作單元局部數(shù)組的內(nèi)情向量局部簡單變量實參(形式單元)參數(shù)個數(shù)返回地址控制鏈(老SP)(前一活動記錄的地址)SPTOP8.3.1簡單棧式存儲分配28voidp(intm){ …… if(m>1) {q(m-1);x--;p(m-1);}……}main(){p(x);}考慮下面的一種簡單的C程序結(jié)構(gòu)：intx=2;voidp(int);voidq(intn){ …… p(n); ……}8.3.1簡單棧式存儲分配29main(){p(x);}（ｃ）第三次對p進(jìn)行調(diào)用時的環(huán)境自由空間p的活動記錄main的活動記錄全局/靜態(tài)數(shù)據(jù)區(qū)SPTOP主函數(shù)main第一次調(diào)用p的情況8.3.1簡單棧式存儲分配30在主函數(shù)調(diào)用p，在p中調(diào)用函數(shù)q,函數(shù)q再調(diào)用函數(shù)p的情況（ａ）SPTOP自由空間p的活動記錄q的活動記錄p的活動記錄main的活動記錄全局/靜態(tài)數(shù)據(jù)區(qū)8.3.1簡單棧式存儲分配31voidp(intm){ …… if(m>1) {q(m-1);x--;p(m-1);}……}main(){p(x);}intx=2;voidp(int);voidq(intn){ …… p(n); ……}（ａ）8.3.1簡單棧式存儲分配32函數(shù)q執(zhí)行完畢后，函數(shù)p對自己調(diào)用的情況注意：在函數(shù)中定義的靜態(tài)變量必須存放在全局／靜態(tài)區(qū)中，不能在函數(shù)的活動記錄中分配。（ａ）SPTOP自由空間p的活動記錄p的活動記錄main的活動記錄全局/靜態(tài)數(shù)據(jù)區(qū)8.3.1簡單棧式存儲分配33如果在語言中允許過程嵌套定義(如Pascal語言)，因為沒有提供非局部變量的引用，所以前面所說的兩種存儲分配策略都不能使用了。這時我們需要設(shè)計一種新的存儲分配策略。8.3.2嵌套過程語言的棧式存儲分配34現(xiàn)在我們分析的對象是允許過程嵌套定義的語言，因此會常常用到過程定義的層數(shù)，我們始終假定主程序的層數(shù)為，因此主程序為第０層過程。如過程Ｑ是在層數(shù)為i的過程Ｐ內(nèi)定義，并且Ｐ是包圍Ｑ的最小過程，那么Ｑ的層數(shù)就為i+1。這時我們把Ｐ稱為Ｑ的直接外層過程，而Ｑ稱為Ｐ的內(nèi)層過程。8.3.2嵌套過程語言的棧式存儲分配35由于過程的定義是嵌套的，一個過程可以引用包圍它的任一外層過程所定義的變量，又由于過程允許遞歸調(diào)用，因此一個過程在引用非局部變量時必須清楚地知道它的每個外層過程的最新活動記錄的位置。8.3.2嵌套過程語言的棧式存儲分配368.3.2嵌套過程語言的棧式存儲分配跟蹤外層活動記錄的方法有很多，這里我們介紹一種常用的辦法：通過嵌套層次顯示表進(jìn)行跟蹤。嵌套層次顯示表(Display)實質(zhì)上是一個指針數(shù)組，也可以看作是一個小棧，自頂向下依次存放著現(xiàn)行層、直接外層、……、第０層的最新活動記錄的基地址，它是建立過程的活動記錄的同時建立起來的。378.3.2嵌套過程語言的棧式存儲分配例如，令過程R的外層為Q,Q的外層為主程序P，則在過程R運行時的Display表的內(nèi)容為：R的現(xiàn)行活動記錄始址(SP的現(xiàn)行值)Q的最新活動記錄的地址P的活動記錄的地址210388.3.2嵌套過程語言的棧式存儲分配由于過程的層數(shù)也可以靜態(tài)確定，因此每個過程的Display表的大小在編譯時就可以確定。這樣，由一個非局部變量說明所在的靜態(tài)層數(shù)和相對于活動記錄的相對地址，就可以得到絕對地址＝Display[靜態(tài)層數(shù)]＋相對地址398.3.2嵌套過程語言的棧式存儲分配為了便于組織存取和簡化處理手續(xù)，通常把Display表作為活動記錄的一部分置于形式單元的上端。見下圖臨時單元內(nèi)情向量簡單變量Display形式單元參數(shù)個數(shù)全局Display地址返回地址老SPd3210第K層SP…最外層過程SP主程序SPd+01kSpTop40programP; vara,b:integer;

procedureQ(x:integer) vari:integer; procedureR(y:integer) varc,d:integer; begin: …… ify>0thenR(y-1); c=d+y; …… end {R} begin …… ifb>0thenR(b)elseQ(b); …… end{Q}8.3.2嵌套過程語言的棧式存儲分配procedureS; vari,c,d:integer; begin c:=a+i+d; Q(c); …… end{S}begin …… a:=0; b:=2; S; ……end {P}418.3.2嵌套過程語言的棧式存儲分配對于這個程序，下面給出PSQR其運行時的Display的活動情況：自由空間R的活動記錄Q的活動記錄S的活動記錄P的活動記錄d[3]d[2]d[1]d[0]Display428.3.2嵌套過程語言的棧式存儲分配對于這個程序，下面給出PSQQR其運行時的Display的活動情況：Display表依次指向現(xiàn)行層、直接外層、……、第０層的最新活動記錄的基地址。d[3]d[2]d[1]d[0]Display自由空間R的活動記錄Q的活動記錄Q的活動記錄S的活動記錄P的活動記錄438.3.2嵌套過程語言的棧式存儲分配對于這個程序，下面給出PSQRR其運行時的Display的活動情況：Display表依次指向現(xiàn)行層、直接外層、……、第０層的最新活動記錄的基地址。d[3]d[2]d[1]d