《編譯原理(10)》由會員分享，可在線閱讀，更多相關(guān)《編譯原理(10)（28頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、單擊此處編輯母版標(biāo)題樣式,單擊此處編輯母版文本樣式,第二級,第三級,第四級,第五級,*,*,*,（,）,1,第十章 目標(biāo)程序運(yùn)行時的存貯組織,讀入整數(shù)并排序的,Pascal,程序,Program sort(,input,output,);,var,a:array0.10 of integer;,Procedure,readarray,;,Var,i:integer,;,Begin,For i:=1 to 9 do,read(ai,),End;,Function,partition(y,z:integer):integer,;,var,i,j,x,v:integer,;,Begin,End;,P

2、rocedure,quicksort(m,n:integer,);,Var,i:integer,;,Begin,If(n,m)then begin,i:=,partition(m,n,);,Quicksort(m,i-1);,Quicksort(i+1,n);,end;,End;,Begin,a0:=-9999;,a10:=9999;,readarray,;,quicksort(1,9),End.,2,關(guān)于源程序的一些問題,我們編寫的這些源程序?qū)嶋H上是靜態(tài)的程序文本；,它們的目的是要在計算機(jī)上正確的運(yùn)行；,在運(yùn)行過程中，這些靜態(tài)程序文本必須于程序運(yùn)行時的活動狀態(tài)聯(lián)系在一起，才能實(shí)現(xiàn)程序的目的；

3、,那么，程序運(yùn)行時，源程序文本中的標(biāo)示符對應(yīng)運(yùn)行時的不同數(shù)據(jù)對象；,數(shù)據(jù)對象的空間分配和釋放需要管理策略，這些策略由運(yùn)行的支撐程序包運(yùn)行管理。,這就是編譯程序要完成的運(yùn)行環(huán)境和存貯管理。,3,關(guān)于源程序的一些問題,源程序可以由不同的過程組成；,在執(zhí)行過程中，,過程,的每次執(zhí)行稱為過程的一個,活動,。,如果這個過程設(shè)計為遞歸調(diào)用過程，那么，則會在某一個時刻可能有它的幾個活動都活躍著；,過程的每一次調(diào)用，都會引起一個活動，這個活動就會調(diào)用編譯軟件的存貯管理的軟件包給活動的數(shù)據(jù)對象分配相應(yīng)的數(shù)據(jù)空間；,4,關(guān)于源程序的一些問題,過程,過程定義,是一個聲明，它的最簡單形式是把一個標(biāo)識符和一個語句聯(lián)系起

4、來；,標(biāo)識符是過程名；,語句是過程體；,過程調(diào)用,表現(xiàn)為過程名出現(xiàn)在執(zhí)行語句中；,如果過程調(diào)用出現(xiàn)在,表達(dá)式,中，則這個過程就是函數(shù)，這個調(diào)用就是,函數(shù)調(diào)用,；,函數(shù),是特殊的過程，它是具有一個返回值的過程；,其實(shí)一個完整的,程序,就是一個過程；,過程參數(shù),形式參數(shù),：過程定義中表明的標(biāo)識符；,實(shí)在參數(shù),：過程調(diào)用中表明的標(biāo)識符；,在過程調(diào)用中，實(shí)在參數(shù)要取代形式參數(shù)；,這需要編譯程序的運(yùn)行環(huán)境存貯空間管理；,5,關(guān)于源程序的一些問題,活動樹,每次過程的調(diào)用都會產(chǎn)生一個活動；,過程的調(diào)用可能會嵌套或者遞歸，這時可能會有多個活動同時活躍，活動樹產(chǎn)生了！,控制流,程序執(zhí)行時過程的調(diào)用是按照一定的步

5、驟和順序?qū)嵤┑模@就是所謂的控制流；,控制流是連續(xù)的。程序的執(zhí)行由一些連續(xù)的步驟組成的，在任何一步，控制都處于程序中的某點(diǎn)；,過程的每次執(zhí)行都從過程體的起點(diǎn)開始，最后控制返回到直接跟隨本次調(diào)用點(diǎn)的位置；,過程間控制流的特點(diǎn)為活動樹產(chǎn)生和應(yīng)用提供了條件；,活動的生存期：,是過程執(zhí)行的第一步和最后一步之間的步序列，包括消耗在執(zhí)行被這個過程所調(diào)用的其他過程所用的時間，以及再由那些被調(diào)用過程又調(diào)用別的過程所用的時間，以此類推。,不同過程的活動生存期可能重疊，這時就出現(xiàn)了所謂的遞歸和嵌套等。,6,關(guān)于源程序的一些問題,遞歸,如果一個過程的前一個活動結(jié)束前，它的一個新的活動又開始，則這樣的過程是遞歸的；,

6、遞歸過程不必直接調(diào)用自己，過程,p,可以調(diào)用另一個過程,q,，然后,q,通過一系列過程調(diào)用之后再調(diào)用了,p,，這也是遞歸調(diào)用；,活動樹,描述控制進(jìn)入和離開活動的方式可以用一棵的方式，這就是活動樹；,活動樹的每一個結(jié)點(diǎn)代表了過程的一個活動；,根結(jié)點(diǎn)代表主程序的活動；,結(jié)點(diǎn),a,是結(jié)點(diǎn),b,的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從,a,的活動進(jìn)入,b,；,a,結(jié)點(diǎn)處于,b,結(jié)點(diǎn)的左邊，當(dāng)且僅當(dāng),a,的生存期先于,b,的生存期；,結(jié)點(diǎn)和活動是一一對應(yīng)的，所以控制結(jié)點(diǎn)就是控制活動。,7,關(guān)于源程序的一些問題,s,r,q(1,9),q(5,9),p(1,9),q(1,3),q(2,3),P(1,3),q(1,0),q

7、(3,3),P(2,3),q(2,1),q(7,9),p(5,9),q(5,5),q(9,9),q(7,7),p(7,9),活動樹,8,9,10.0,概述,在代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運(yùn)行環(huán)境的設(shè)計和數(shù)據(jù)空間的分配。,編譯程序需要一定的存貯空間以使目標(biāo)程序在其上運(yùn)行，該存貯空間需容納生成的目標(biāo)代碼和目標(biāo)代碼運(yùn)行時的數(shù)據(jù)空間。,數(shù)據(jù)空間包括,：用戶定義的各種類型的數(shù)據(jù)對象（變量和常量）所需的存貯空間；作為保留中間結(jié)果和傳遞參數(shù)的臨時工作單元；調(diào)用過程時所需的連接單元；組織輸入,/,輸出所需的緩沖區(qū)。,編譯過程中，有些數(shù)據(jù)對象所占用的空間,可以確定,，有些數(shù)據(jù)對象具有可變體積和待編譯性質(zhì)

8、，,無法在編譯時確定,存貯空間的位置。,作為運(yùn)行時存貯分配的一個原則是盡可能對數(shù)據(jù)對象進(jìn)行靜態(tài)分配。,10,10.0,概述,存貯空間常常劃分為：目標(biāo)代碼區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)、堆區(qū)。,目標(biāo)代碼區(qū)用以存放目標(biāo)代碼，是固定長度，編譯時能夠確定。,靜態(tài)數(shù)據(jù)區(qū)用以存放編譯時能確定所占用空間的數(shù)據(jù)。,堆棧區(qū)用于可變數(shù)據(jù)以及管理過程活動的控制信息。,存貯組織要解決的問題是把靜態(tài)的源程序與該程序的目標(biāo)程序運(yùn)行時的動態(tài)活動聯(lián)系起來，即要搞清楚運(yùn)行中的程序信息是如何進(jìn)行存貯和訪問的。,所謂數(shù)據(jù)空間,分配,，本質(zhì)上看，是將程序中的每個名字與一個存貯位置關(guān)聯(lián)起來，該存貯位置用以容納名字的值。,源語言的結(jié)構(gòu)特點(diǎn)、源語言

9、的數(shù)據(jù)類型、源語言中決定名字作用域的規(guī)則等因素影響存貯空間的管理和組織的復(fù)雜程度，決定數(shù)據(jù)空間分配的基本策略。,code,Static data,stack,(,可變區(qū)域,),heap,名字（標(biāo)識符）,存貯位置,值,環(huán)境,狀態(tài),11,10.1,數(shù)據(jù)空間的三種不同使用方法和管理方法,數(shù)據(jù)空間的使用和管理方法從大類分為兩種：,靜態(tài)和動態(tài),。而動態(tài)又分為：,棧式和堆式兩種,。,靜態(tài)存貯分配策略,：如果在編譯時能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，編譯時安排好目標(biāo)程序運(yùn)行時的全部數(shù)據(jù)空間，確定每個數(shù)據(jù)對象的存貯位置。,動態(tài)存貯分配策略,：目標(biāo)程序在運(yùn)行時所需要的數(shù)據(jù)空間，在編譯時無法知道，它所

10、需要的數(shù)據(jù)空間的大小要待程序運(yùn)行是動態(tài)地確定。有兩種存貯分配方式：,棧式,和,堆式,。,棧式存貯,：,1,、將整個程序的數(shù)據(jù)空間設(shè)計為一個棧；,2,、每當(dāng)調(diào)用一個過程時，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過程工作結(jié)束時就釋放這部分空間；,3,、過程所需數(shù)據(jù)空間包括兩部分：一部分是本次調(diào)用中的數(shù)據(jù)對象；另一部分是用以管理過程活動的記錄信息；,4,、當(dāng)控制從調(diào)用返回時，便根據(jù)棧中記錄的信息恢復(fù)機(jī)器狀態(tài)，使該過程的活動繼續(xù)進(jìn)行。,堆式存貯,：,1,、自由地申請數(shù)據(jù)空間和退還數(shù)據(jù)空間；,2,、數(shù)據(jù)空間的利用不服從“先申請后釋放，后申請先釋放”的原則；,3,、這種存貯方式空間的利用率可能受到限制。容易產(chǎn)

11、生碎片。,12,10.2,棧式存貯分配的實(shí)現(xiàn),棧式存貯分配的基本策略是調(diào)用一個過程時在棧頂分配所需數(shù)據(jù)空間，返回時，在棧頂釋放數(shù)據(jù)空間。,過程的活動記錄,是一段連續(xù)的存貯區(qū)，用以存放過程的一次執(zhí)行所需要的信息。,信息包括：,臨時工作單元,：計算表達(dá)式過程中需要存放中間結(jié)果用的臨時值單元；,局部變量,：一個過程的局部變量；,保存機(jī)器狀態(tài),：容納該過程執(zhí)行前關(guān)于機(jī)器狀態(tài)的信息，如程序計數(shù)器、寄存器的值等；,存取鏈,：用以存取非局部變量，這些變量存放于其他過程活動記錄中。（,所謂鏈，實(shí)際上是鏈接，包含指針,）；,控制鏈,：指向調(diào)用該過程的那個過程的活動記錄；,實(shí)參,：形式單元。由調(diào)用過程向該被調(diào)用過

12、程提供實(shí)參的值；,返回地址,：保存該被調(diào)用過程返回后的地址。,臨時工作單元,局部變量,機(jī)器狀態(tài)信息,存取鏈,控制鏈,實(shí)參,返回地址,13,10.2.1,簡單的棧式存貯分配的實(shí)現(xiàn),簡單的特征是：,沒有分程序結(jié)構(gòu)，過程定義不嵌套，允許過程遞歸調(diào)用,。,存貯空間的分配策略,：運(yùn)行時，每當(dāng)進(jìn)入一個過程時，則為該過程分配一段存貯空間，當(dāng)一個過程工作完畢后返回時，它所占用的存貯區(qū)則釋放。,程序在運(yùn)行時，存貯空間（棧）中在某一個時刻可能會包含不同過程的幾個活動記錄；可能會包含某個過程的幾個活動記錄（遞歸調(diào)用）。,同一個存貯位置，不同的運(yùn)行時刻分配給不同的數(shù)據(jù)對象。,在棧的最頂端數(shù)據(jù)區(qū)有兩個指針：,SP,總是

13、指向現(xiàn)行過程活動記錄的起點(diǎn)；,TOP,總是指向占用的棧頂單元。,Program main;,全局變量或數(shù)組的說明；,proc R;,end(R,);,proc Q,end(Q,),主程序執(zhí)行語句,end.(main,),14,10.2.1,簡單的棧式存貯分配的實(shí)現(xiàn),R,的活動,記錄,Q,的活動,記錄,主程序全局,數(shù)據(jù)區(qū),Q,的活動,記錄,Q,的活動,記錄,主程序全局,數(shù)據(jù)區(qū),Q,的活動,記錄,主程序全局,數(shù)據(jù)區(qū),R,的活動,記錄,主程序全局,數(shù)據(jù)區(qū),TOP,SP,控制鏈（老,SP,）,返回地址,參數(shù)個數(shù),實(shí)參（形式單元）,局部簡單變量,局部數(shù)組的內(nèi)情向量,臨時工作單元,TOP,SP,主程序全局

14、數(shù)據(jù)區(qū),Q,的活動記錄,R,的活動記錄,R,的數(shù)組區(qū),TOP,SP,15,主要特點(diǎn),：（語言）一個過程可以引用包圍它的任一外層過程所定義的標(biāo)識符（如變量，數(shù)組或過程等）；（實(shí)現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)；必須設(shè)法跟蹤每個外層過程的最新活動記錄的位置。,關(guān)鍵技術(shù),：,嵌套過程主要解決對非局部變量的引用問題,。,跟蹤的辦法有兩種,：一種是在過程活動記錄中增設(shè)存取鏈，指向包含該過程的直接外層過程的最新活動記錄的起始位置；另一種是每進(jìn)入一個過程后，在建立它的活動記錄的同時建立一張嵌套層次顯示表,display,。,存取鏈和控制鏈分別是存取非局部變量和指定直接外部過程。

15、,嵌套層次,：指過程定義的層數(shù)。,Display,是一個數(shù)組，也可以看作為一個小棧。自頂向下每個單元依次存放著現(xiàn)行層、直接外層、,、最外層等每一層過程的最新活動記錄地址。,10.2.2,嵌套過程語言的棧式實(shí)現(xiàn),16,舉例,程序中過程定義的嵌套情況,Sort,看成整個程序的最外層。,過程,readarray,、,exchange,、,quicksort,是次外層。,過程,partition,是最內(nèi)層。,在過程,readarray,、,exchange,和,partition,中引用的,a,均不是它們的局部變量，而是過程,sort,過程的局部變量。,這就遇到了一個非局部變量的存取問題。,必須設(shè)法跟

16、蹤每個外層過程的最新活動記錄的位置。,Sort,readarray,exchange,quicksort,partition,17,舉例,過程,sort,調(diào)用過程,quicksort,。,動態(tài)棧的存貯情形如下圖,Quicksort,過程活動記錄中斜線描述的存貯單元用以記錄過程,quicksort,引用過程,sort,中的變量,a,和,x,。,如何引用呢？通過指針！,在這個單元中設(shè)置存取鏈，指向包含該過程的直接外層過程的最新活動記錄的其始地址。,局部變量,k,v,局部變量,a,x,可以引用的過程,sort,的局部變量,過程,quicksort,的活動記錄,過程,sort,的活動記錄,局部變量,.,.,存取鏈,控制鏈,TOP,SP,18,sort,quicksort,quicksort,partition exchange,變量,a,x,控制鏈,存取鏈,局部變量,k,v,控制鏈,存取鏈,局部變量,k,v,控制鏈,存取鏈,局部變量,y,z,控制鏈,存取鏈,局部變量,i,j,Exchange,的活動記錄,partition,的活動記錄,quicksort,的活動記錄,quicksort,的活動