編譯原理課后答案-第六章-運(yùn)行時(shí)存儲(chǔ)空間組織課件

第六章

運(yùn)行時(shí)存儲(chǔ)空間組織

6.1完成下列選擇題： (1)過程的DISPLAY表中記錄了

。 a.過程的連接數(shù)據(jù)b.過程的嵌套層次 c.過程的返回地址d.過程的入口地址 (2)過程P1調(diào)用P2時(shí)，連接數(shù)據(jù)不包含

。 a.嵌套層次顯示表b.老SP c.返回地址d.全局DISPLAY地址 (3)堆式動(dòng)態(tài)分配申請(qǐng)和釋放存儲(chǔ)空間遵守

原則。 a.先請(qǐng)先放b.先請(qǐng)后放

c.后請(qǐng)先放d.任意 (4)棧式動(dòng)態(tài)分配與管理在過程返回時(shí)應(yīng)做的工作有

。 a.保護(hù)SPb.恢復(fù)SP c.保護(hù)TOPd.恢復(fù)TOP (5)如果活動(dòng)記錄中沒有DISPLAY表，則說明

。 a.程序中不允許有遞歸定義的過程

b.程序中不允許有嵌套定義的過程 c.程序中既不允許有嵌套定義的過程，也不允許有遞歸定義的過程 d.程序中允許有遞歸定義的過程，也允許有嵌套定義的過程 【解答】

(1)b(2)a(3)d(4)b(5)b

6.2何謂嵌套過程語言運(yùn)行時(shí)的DISPLAY表？它的作用是什么？ 【解答】

當(dāng)過程定義允許嵌套時(shí)，一個(gè)過程在運(yùn)行中應(yīng)能夠引用在靜態(tài)定義時(shí)包圍它的任一外層過程所定義的變量或數(shù)組。也就是說，在棧式動(dòng)態(tài)存儲(chǔ)分配方式下的運(yùn)行中，一個(gè)過程Q可能引用它的任一外層過程P的最新活動(dòng)記錄中的某些數(shù)據(jù)。因此，過程Q運(yùn)行時(shí)必須知道它的所有(靜態(tài))外層過程的最新活動(dòng)記錄的地址。由于允許遞歸和可變數(shù)組，這些外層過程的活動(dòng)記錄的位置也往往是變遷的。因此，必須設(shè)法跟蹤每個(gè)(靜態(tài))外層的最新活動(dòng)記錄的位置，而完成這一功能的就是DISPLAY嵌套層次顯示表。

也即，每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)也建立一張DISPLAY表，它自頂而下每個(gè)單元依次存放著現(xiàn)行層、直接外層等，直至最外層(主程序?qū)?等每一層過程的最新活動(dòng)記錄的起始地址。 6.3(1)寫出實(shí)現(xiàn)一般遞歸過程的活動(dòng)記錄結(jié)構(gòu)以及過程調(diào)用、過程進(jìn)入與過程返回的指令； (2)對(duì)以return(表達(dá)式)形式(這個(gè)表達(dá)式本身是一個(gè)遞歸調(diào)用)返回函數(shù)值的特殊函數(shù)過程，給出不增加時(shí)間開銷但能節(jié)省存儲(chǔ)空間的實(shí)現(xiàn)方法。假定語言中過程參數(shù)只有傳值和傳地址兩種形式，為便于理解，舉下例說明這種特殊的函數(shù)調(diào)用：

intgcd(intp,intq) { if(p%q==0)returnq; elsereturngcd(q,p%q) } 【解答】

(1)一般遞歸過程的活動(dòng)記錄如圖6-1所示。圖6-1遞歸過程的活動(dòng)記錄

過程調(diào)用指令為 (i+4)[TOP]=Ti

或(i+4)[TOP]=addr[Ti]1[TOP]=SP3[TOP]=SP+d4[TOP]=nJSRP

過程進(jìn)入指令為 SP=TOP+1 1[SP]=返回地址 TOP=TOP+L

建立DISPLAY P；/*執(zhí)行P過程*/ 返回指令為 TOP=SP-1 SP=0[SP] X=2[TOP] UJ0[X] (2)對(duì)于return后的直接遞歸情況，可簡(jiǎn)化為 (i+3)[SP]=Ti

或(i+3)[SP]=addr[Ti]UJP 6.4有一程序如下： programex; a:integer; procedurePP(x:integer); begin: x:=5;x:=a+1 end;

begin

a:=2;

PP(a);

write(a)

end. 試用圖表示ex調(diào)用PP(a)前后活動(dòng)記錄的過程。

【解答】

按照嵌套過程語言棧式實(shí)現(xiàn)方法，ex調(diào)用PP(a)前后活動(dòng)記錄的過程如圖6-2所示。圖6-2ex調(diào)用PP(a)前后的活動(dòng)記錄 6.5類PASCAL結(jié)構(gòu)(嵌套過程)的程序如下，該語言的編譯器采用棧式動(dòng)態(tài)存儲(chǔ)分配策略管理目標(biāo)程序數(shù)據(jù)空間。 programDemo procedureA; procedureB; begin(*B*)

… ifdthenBelseA;

… end;(*B*) begin(*A*) B end;(*A*) begin(*Demo*) A end. (1)若過程調(diào)用序列為 ①Demo→A；②Demo→A→B；③Demo→A→B→B；④Demo→A→B→B→A 請(qǐng)分別給出這四個(gè)時(shí)刻運(yùn)行棧的布局和使用的DISPLAY表； (2)若該語言允許動(dòng)態(tài)數(shù)組，編譯程序應(yīng)如何處置？如過程B有動(dòng)態(tài)局部數(shù)組R[m:n]，請(qǐng)給出B第一次激活時(shí)相應(yīng)的數(shù)據(jù)空間的情況。 【解答】(1)運(yùn)行棧及使用的DISPLAY表如圖6-3所示。

圖6-3運(yùn)行棧及DISPLAY表示意圖

(2)由于一個(gè)過程在運(yùn)行時(shí)所需的實(shí)際數(shù)據(jù)空間的大小，除可變數(shù)據(jù)結(jié)構(gòu)(可變數(shù)組)那些部分外，其余部分在編譯時(shí)是完全可以知道的。編譯程序處理時(shí)將過程運(yùn)行時(shí)所需的數(shù)據(jù)空間分為兩部分：一部分在編譯時(shí)可確定其體積，稱為該過程的活動(dòng)記錄；另一部分(動(dòng)態(tài)數(shù)組)的體積需在運(yùn)行時(shí)動(dòng)態(tài)確定，稱為該過程的可變輔助空間。當(dāng)一個(gè)過程開始工作時(shí)，首先在運(yùn)行棧頂部建立它的活動(dòng)記錄，然后再在這個(gè)記錄之頂確定它所需的輔助空間。含有動(dòng)態(tài)數(shù)組R的過程B在第一次激活時(shí)，相應(yīng)的數(shù)據(jù)空間情況如圖6-4所示。圖6-4帶動(dòng)態(tài)數(shù)組的運(yùn)行棧示意(a)動(dòng)態(tài)數(shù)組R空間分配之前；(b)動(dòng)態(tài)數(shù)組R空間分配之后

6.6下面程序的結(jié)果是120。但是如果把第5行的abs(1)改成1的話，則程序結(jié)果為1。試分析為什么會(huì)有這種不同的結(jié)果。 intfact() { staticinti=5; if(i==0){return(1);} else{i=i-1;return((i+abs(1))*fact());} }

main() { printf("factoror5=%d\n",fact()); } 解答】

i是靜態(tài)變量，所有對(duì)i的操作實(shí)際上都是對(duì)i所對(duì)應(yīng)的存儲(chǔ)單元進(jìn)行操作，每次遞歸進(jìn)入下一層fact函數(shù)后，上一層對(duì)i的賦值仍然有效。需要注意的是，每次遞歸調(diào)用時(shí)，(i+abs(1))*fact()中的(i+abs(1))的值都先于fact算出。因此，第一次遞歸調(diào)用所求得的值為5*fact，第二次遞歸調(diào)用所求得的值為4*fact，…，一直到第五次遞歸調(diào)用所求得的值為1*fact，而此時(shí)fact為1。也即實(shí)際上是求一個(gè)5*4*3*2*1的階乘，由此得到結(jié)果為120。

將abs(1)改為1后，輸出結(jié)果為1而不是120，這主要是與編譯的代碼生成策略有關(guān)。對(duì)表達(dá)式(i+abs(1))*fact()，因?yàn)閮蓚€(gè)子表達(dá)式(i+abs(1))和fact()都有函數(shù)調(diào)用，而編譯器的編譯則是先產(chǎn)生左子表達(dá)式的代碼，后產(chǎn)生右子表達(dá)式的代碼。也即，每次遞歸調(diào)用時(shí)，(i+abs(1))*fact()中的(i+abs(1))的值都先于fact算出。但是，當(dāng)abs(1)改為1后，左子表達(dá)式就沒有函數(shù)調(diào)用了，于是編譯器就先產(chǎn)生右子表達(dá)式的代碼。每次遞歸調(diào)用時(shí)，