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

1、第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 第六章第六章 運(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地址第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 (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)做的工作有 。

2、a. 保護(hù)SP b. 恢復(fù)SP c. 保護(hù)TOP d. 恢復(fù)TOP第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 (5) 如果活動(dòng)記錄中沒有DISPLAY表，則說明 。a. 程序中不允許有遞歸定義的過程 b. 程序中不允許有嵌套定義的過程c. 程序中既不允許有嵌套定義的過程，也不允許有遞歸定義的過程d. 程序中允許有遞歸定義的過程，也允許有嵌套定義的過程【解答】 (1) b (2) a (3) d (4) b (5) b第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 6.2 何謂嵌套過程語(yǔ)言運(yùn)行時(shí)的DISPLAY表？它的作用是什么？【解答】 當(dāng)過程定義允許嵌套時(shí)，一個(gè)過程在運(yùn)行中應(yīng)能夠

3、引用在靜態(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嵌套層次顯示表。第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 也即，每當(dāng)進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄區(qū)的同時(shí)也建立一張DISPLAY表，它自頂而下每個(gè)單元依次存放著現(xiàn)行層、直接外層等，直至最外層

4、(主程序?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)方法。假定語(yǔ)言中過程參數(shù)只有傳值和傳地址兩種形式，為便于理解，舉下例說明這種特殊的函數(shù)調(diào)用： 第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 int gcd (int p,int q) if (p % q =0) return q; else return gcd (q, p % q) 【解答】 (1) 一般遞歸過程的

5、活動(dòng)記錄如圖6-1所示。第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 TOP SP臨時(shí)單元內(nèi)情向量局部變量形式單元參數(shù)個(gè)數(shù)老SPDISPLAY表TOPd個(gè)單元全局DISPLAY地址返回地址L圖6-1 遞歸過程的活動(dòng)記錄 第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 過程調(diào)用指令為 (i+4)TOP=Ti 或 (i+4)TOP=addr Ti 1TOP=SP 3TOP=SP+d 4TOP=n JSR P第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 過程進(jìn)入指令為 SP=TOP+1 1SP=返回地址 TOP=TOP+L 建立DISPLAY P； /*執(zhí)行P過程*/返回指令為 TO

6、P=SP-1 SP=0SP X=2TOP UJ 0X第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 (2) 對(duì)于return后的直接遞歸情況，可簡(jiǎn)化為 (i+3)SP=Ti 或 (i+3)SP=addr Ti UJ P6.4 有一程序如下：program ex; a: integer; procedure PP(x: integer); begin: x:=5; x:=a+1第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 end; begin a:= 2; PP(a); write(a) end.試用圖表示ex調(diào)用PP(a)前后活動(dòng)記錄的過程。 【解答】 按照嵌套過程語(yǔ)言棧式實(shí)現(xiàn)方法，

7、ex調(diào)用PP(a)前后活動(dòng)記錄的過程如圖6-2所示。第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 PP_SPex_SPDISPLAY表形式參數(shù)X參數(shù)個(gè)數(shù)：1全局DISPLAY地址返回地址ex_SPaDISPLAY表ex_SP參數(shù)個(gè)數(shù)：0全局DISPLAY地址返回地址ex_SPPP_TOPPP_SPex_TOPex_SPPP的活動(dòng)記錄(調(diào)用PP(a)之后)ex的活動(dòng)記錄(調(diào)用PP(a)之前)圖6-2 ex調(diào)用PP(a)前后的活動(dòng)記錄第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 6.5 類PASCAL結(jié)構(gòu)(嵌套過程)的程序如下，該語(yǔ)言的編譯器采用棧式動(dòng)態(tài)存儲(chǔ)分配策略管理目標(biāo)程序數(shù)據(jù)空間

8、。program Demo procedure A;procedure B; begin(*B*) 第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 if d then B else A; end;(*B*)begin(*A*) Bend;(*A*) begin(*Demo*)A end.第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 (1) 若過程調(diào)用序列為 DemoA； DemoAB； DemoABB； DemoABBA請(qǐng)分別給出這四個(gè)時(shí)刻運(yùn)行棧的布局和使用的DISPLAY表；(2) 若該語(yǔ)言允許動(dòng)態(tài)數(shù)組，編譯程序應(yīng)如何處置？如過程B有動(dòng)態(tài)局部數(shù)組Rm:n，請(qǐng)給出B第一次激活時(shí)相應(yīng)的

9、數(shù)據(jù)空間的情況?！窘獯稹?(1) 運(yùn)行棧及使用的DISPLAY表如圖6-3所示。 第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 Demo_spA_spB_spDemo_spA_spDemo_spA_spA的活動(dòng)記錄Demo的活動(dòng)記錄DISPLAY表B_spA_spDemo_spA_spDemo_spDISPLAY表DISPLAY表B的活動(dòng)記錄A的活動(dòng)記錄Demo的活動(dòng)記錄(1) DemoA(2) DemoABDemo_spDemo_spDISPLAY 表DISPLAY表A2_spB2_spA_spDemo_spA_spDemo_spA_spDemo_spDISPLAY表(3) DemoA

10、B1B2Demo_spDemo_spDemo_spDemo_spDISPLAY表DISPLAY表A2的活動(dòng)記錄A1的活動(dòng)記錄Demo的活動(dòng)記錄(4) DemoA1B1B2A2B2的活動(dòng)記錄B1的活動(dòng)記錄B2_spB1_spA1_spB2_spDISPLAY表DISPLAY表B1_spA_spB1的活動(dòng)記錄B2的活動(dòng)記錄A的活動(dòng)記錄Demo的活動(dòng)記錄B1_spB2_spB1_spA1_spA1_spA2_spA1_sp圖6-3 運(yùn)行棧及DISPLAY表示意圖 第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 (2) 由于一個(gè)過程在運(yùn)行時(shí)所需的實(shí)際數(shù)據(jù)空間的大小，除可變數(shù)據(jù)結(jié)構(gòu)(可變數(shù)組)那些部

11、分外，其余部分在編譯時(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所示。第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 B的活動(dòng)記錄A_sp數(shù)組R的內(nèi)情向量B_spA_spDemo_spA_spDemo_spA的活動(dòng)記錄Demo的活動(dòng)記錄DISPLAY表B_spDemo_sp數(shù)組R數(shù)

12、組R的內(nèi)情向量B_spA_spDemo_spA_spDemo_spB的活動(dòng)記錄A的活動(dòng)記錄Demo的活動(dòng)記錄A_spB_spDemo_spB的可變輔助空間(a)(b) DISPLAY表DISPLAY表 圖6-4 帶動(dòng)態(tài)數(shù)組的運(yùn)行棧示意(a) 動(dòng)態(tài)數(shù)組R空間分配之前；(b) 動(dòng)態(tài)數(shù)組R空間分配之后第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 6.6 下面程序的結(jié)果是120。但是如果把第5行的abs(1)改成1的話，則程序結(jié)果為1。試分析為什么會(huì)有這種不同的結(jié)果。int fact( )static int i=5;if (i=0) return(1); else i=i-1; return(

13、i+abs(1)*fact( );第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 main( )printf (factor or 5=%dn,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。第六章第六章 運(yùn)行時(shí)存儲(chǔ)空間組織運(yùn)行時(shí)存儲(chǔ)空間組織 將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(