編譯原理第九章-運(yùn)行時(shí)存儲(chǔ)空間組織

1、第九章 運(yùn)行時(shí)存儲(chǔ)空間組織第一頁(yè)，共四十一頁(yè)。目標(biāo)程序運(yùn)行時(shí)的活動(dòng)過(guò)程的活動(dòng) 一個(gè)過(guò)程的活動(dòng)指該過(guò)程的一次執(zhí)行。參數(shù)傳遞 1. 參數(shù) 形參：過(guò)程定義時(shí)出現(xiàn) 實(shí)參：過(guò)程調(diào)用時(shí)出現(xiàn) 2. 參數(shù)傳遞的途徑： 傳地址(call by reference) 傳值 (call by value) 傳名(換名)(call by name)第二頁(yè)，共四十一頁(yè)。參數(shù)傳遞途徑傳地址把實(shí)參的地址傳遞給相應(yīng)的形參。過(guò)程段中每個(gè)形參都有相應(yīng)單元，稱為形式單元，用來(lái)存放相應(yīng)實(shí)參的地址。若實(shí)參是變量則直接傳遞地址，若實(shí)參是常數(shù)或表達(dá)式，則先計(jì)算其值并存放于某一臨時(shí)單元，再傳遞臨時(shí)單元的地址。傳結(jié)果(call by refe

2、rence)與傳地址相似，其實(shí)質(zhì)：每個(gè)形參對(duì)應(yīng)兩個(gè)單元，第一個(gè)單元存放實(shí)參地址，第二個(gè)存放實(shí)參的值。過(guò)程體中對(duì)形參的動(dòng)作均看成對(duì)第二個(gè)單元的直接訪問(wèn)，在過(guò)程完成返回前必須把第二個(gè)單元的內(nèi)容存放到第一個(gè)單元所指的實(shí)參單元中。第三頁(yè)，共四十一頁(yè)。Procedure s); var j:real; begin j:=n; n:=m; m:=j; end傳地址過(guò)程調(diào)用s(i)的過(guò)程：(1)將i，k(i)地址傳遞到已知單元J1和J2中(2) n:=J1; m:=J2;(3) j:=n;(4) n:=m;(5) m:=j;第四頁(yè)，共四十一頁(yè)。參數(shù)傳遞途徑傳值Procedure s); var j:real

3、; begin j:=n; n:=m; m:=j; end傳值過(guò)程a:=1;b:=2;調(diào)用s)執(zhí)行過(guò)程：n:=am:=bj:=nn:=mm:=j局部變量m,n,j的值改變，但不影響a，b的值第五頁(yè)，共四十一頁(yè)。參數(shù)傳遞途徑傳名把被調(diào)用段的過(guò)程體抄到調(diào)用出現(xiàn)的位置，并將形參替換成相應(yīng)實(shí)參（文字替換）。Procedure s); var j:real; begin j:=n; n:=m; m:=j; end傳名過(guò)程調(diào)用s(i)的過(guò)程： j:=i; i:=k(i); k(i):=j;第六頁(yè)，共四十一頁(yè)。對(duì)于下面程序： Procedure p (x,y,z) ; begin y:=y+1; z:=z+

4、x; end; p begin a:=2; b:=3; p (a+b , a , a) print a end. 若參數(shù)傳遞的方法分別為 （1）傳名（2）傳地址 （3）傳結(jié)果 （4）傳值。 執(zhí)行時(shí)所輸出的a分別是什么？第七頁(yè)，共四十一頁(yè)。參數(shù)傳遞方式為“傳名”P(pán)rocedure p (a+b,a,a) ; begin a:=a+1; a:=a+a+b; end; p此時(shí)調(diào)用者數(shù)據(jù)區(qū)為(a):執(zhí)行a:=a+1后數(shù)據(jù)區(qū)為(b):執(zhí)行a:=a+a+b后數(shù)據(jù)區(qū)為(c):32b：a：(a)33b：a：(b)39b：a：(c)程序輸出結(jié)果a為9第八頁(yè)，共四十一頁(yè)。參數(shù)傳遞方式為“傳地址”32&b：&a：調(diào)

5、用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)據(jù)區(qū)&a z：執(zhí)行語(yǔ)句y:=y+1后33&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)據(jù)區(qū)&a z：第九頁(yè)，共四十一頁(yè)。參數(shù)傳遞方式為“傳地址”執(zhí)行語(yǔ)句z:=z+x后38&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)據(jù)區(qū)&a z：程序輸出結(jié)果a為8第十頁(yè)，共四十一頁(yè)。參數(shù)傳遞方式為“傳結(jié)果”32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)執(zhí)行語(yǔ)句y:=y+1后32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)5T x_val ：x_add：被調(diào)用者數(shù)據(jù)區(qū)&a&

6、a32y_val ：y_add ：z_val ：z_add ：5T x_val ：x_add：被調(diào)用者數(shù)據(jù)區(qū)&a&a22y_val ：y_add ：z_val ：z_add ：第十一頁(yè)，共四十一頁(yè)。參數(shù)傳遞方式為“傳結(jié)果”執(zhí)行語(yǔ)句z:=z+x后32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)程序輸出結(jié)果a為75T x_val ：x_add：被調(diào)用者數(shù)據(jù)區(qū)&a&a37y_val ：y_add ：z_val ：z_add ：程序結(jié)束，調(diào)用返回后：37&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)第十二頁(yè)，共四十一頁(yè)。參數(shù)傳遞方式為“傳值”32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a

7、+b的值)25y：x：被調(diào)用者數(shù)據(jù)區(qū)2 z：執(zhí)行語(yǔ)句y:=y+1后32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)35y：x：被調(diào)用者數(shù)據(jù)區(qū)2 z：第十三頁(yè)，共四十一頁(yè)。參數(shù)傳遞方式為“傳值”執(zhí)行語(yǔ)句z:=z+x后32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時(shí)單元T：(a+b的值)37y：x：被調(diào)用者數(shù)據(jù)區(qū)2 z：程序輸出結(jié)果a為2第十四頁(yè)，共四十一頁(yè)。運(yùn)行時(shí)存儲(chǔ)器的劃分程序區(qū)棧區(qū)靜態(tài)區(qū)目標(biāo)區(qū)堆區(qū)可變數(shù)組，函數(shù)活動(dòng)記錄 目標(biāo)代碼區(qū) 靜態(tài)數(shù)據(jù)區(qū) Stack heap第十五頁(yè)，共四十一頁(yè)。靜態(tài)：如果一個(gè)名字的性質(zhì)通過(guò)說(shuō)明語(yǔ)句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。動(dòng)態(tài)：如果名字的性質(zhì)只有在程

8、序運(yùn)行時(shí)才能知道，則稱這種性質(zhì)為“動(dòng)態(tài)”確定的?？勺?(動(dòng)態(tài))數(shù)組： 若一個(gè)數(shù)組所需的存儲(chǔ)空間的大小在編譯時(shí)就已知道，則稱它為確定數(shù)組，否則稱為可變(動(dòng)態(tài))數(shù)組。第十六頁(yè)，共四十一頁(yè)。數(shù)據(jù)區(qū)管理方法靜態(tài)存儲(chǔ)方法動(dòng)態(tài)存儲(chǔ)方法 棧式：函數(shù)遞歸定義、調(diào)用 堆式：動(dòng)態(tài)申請(qǐng)、釋放、new、delete活動(dòng)記錄連接數(shù)據(jù) 返回地址 靜態(tài)鏈：指向調(diào)用該過(guò)程前的最新活動(dòng)記錄地址的指針 動(dòng)態(tài)鏈：指向靜態(tài)直接外層最新活動(dòng)記錄地址的指針形式單元局部數(shù)據(jù)區(qū)：局部變量、內(nèi)情向量、臨時(shí)工作單元第十七頁(yè)，共四十一頁(yè)。靜態(tài)存儲(chǔ)分配靜態(tài)分配：若在編譯時(shí)就能確定程序在運(yùn)行時(shí)所需存儲(chǔ)空間的大小，則在編譯時(shí)就能夠安排好目標(biāo)程序運(yùn)行時(shí)的

9、全部數(shù)據(jù)空間，并能確定每個(gè)數(shù)據(jù)項(xiàng)的單元地址。 Fortran語(yǔ)言就采用了靜態(tài)存儲(chǔ)分配的策略。數(shù)據(jù)區(qū) 第十八頁(yè)，共四十一頁(yè)。簡(jiǎn)單的棧式存儲(chǔ)分配main( ) Q( ); P( ) Q( ) P( ); 1010SPTOP老SP 1010TOP+1=SP2010返回地址TOPSP2010TOPP的活動(dòng)記錄Q的活動(dòng)記錄主函數(shù)的活動(dòng)記錄第十九頁(yè)，共四十一頁(yè)。C語(yǔ)言活動(dòng)記錄的內(nèi)容連接數(shù)據(jù)參數(shù)個(gè)數(shù)形式單元函數(shù)的局部變量、數(shù)組內(nèi)情向量、臨時(shí)單元老SP返回地址參數(shù)個(gè)數(shù)形式單元簡(jiǎn)單變量?jī)?nèi)情向量臨時(shí)單元sp第二十頁(yè)，共四十一頁(yè)。嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)主要特點(diǎn)： （語(yǔ)言）一個(gè)過(guò)程可以引用包圍它的任一外層過(guò)程所定義的

10、標(biāo)識(shí)符（如變量，數(shù)組或過(guò)程等）。 （實(shí)現(xiàn)）一個(gè)過(guò)程可以引用它的任一外層過(guò)程的最新活動(dòng)記錄中的某些數(shù)據(jù)。第二十一頁(yè)，共四十一頁(yè)。嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)關(guān)鍵技術(shù)：解決對(duì)非局部量的引用（存?。?。設(shè)法跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄AR的位置。跟蹤辦法： 1. 用靜態(tài)鏈。 2. 用DISPLAY表。第二十二頁(yè)，共四十一頁(yè)。每個(gè)過(guò)程的AR有3個(gè)聯(lián)系單元：SL： 靜態(tài)鏈，指向定義該過(guò)程的直接外過(guò)程 （或主程序）運(yùn)行時(shí)最新數(shù)據(jù)段的基地址。DL： 動(dòng)態(tài)鏈，指向調(diào)用該過(guò)程前正在運(yùn)行過(guò)程的數(shù)據(jù)段基地址。RA： 返回地址，記錄調(diào)用該過(guò)程時(shí)目標(biāo)程序的斷點(diǎn)，即調(diào)用過(guò)程指令的下一條指令的地址。第二十三頁(yè)，共四十一頁(yè)。pro

11、gram P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112第二十四頁(yè)，共四十一頁(yè)。program P; var a,x:integer; pr

12、ocedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112ic0(形參個(gè)數(shù))0返回地址x0a0返回地址0過(guò)程P中調(diào)用S時(shí)的活動(dòng)記錄012345678910SPTOP動(dòng)態(tài)鏈靜態(tài)鏈第二十五頁(yè)，共四十一

13、頁(yè)。program P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112ic0返回地址x0a0過(guò)程S中調(diào)用Q時(shí)的活動(dòng)記錄012345678910S

14、PTOP動(dòng)態(tài)鏈靜態(tài)鏈返回地址00 (形參個(gè)數(shù))511返回地址120131(形參個(gè)數(shù))14b(形參)15i16第二十六頁(yè)，共四十一頁(yè)。program P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c)

15、; endbegin a:=0; S; end0112過(guò)程Q中調(diào)用R時(shí)的活動(dòng)記錄ic0返回地址x0a0012345678910SPTOP動(dòng)態(tài)鏈靜態(tài)鏈返回地址00 (形參個(gè)數(shù))511返回地址120131(形參個(gè)數(shù))14b(形參)15i161117返回地址1811192 (形參個(gè)數(shù))20u (形參)21v (形參)22c23d24第二十七頁(yè)，共四十一頁(yè)。Display表和活動(dòng)記錄Display表-嵌套層次顯示表 當(dāng)前激活過(guò)程的層次為K，它的Display表含有K+1個(gè)單元，依次存放著現(xiàn)行層，直接外層直至最外層的每一過(guò)程的最新活動(dòng)記錄的基地址。第二十八頁(yè)，共四十一頁(yè)。第二十九頁(yè)，共四十一頁(yè)。用Dis

16、play表的方案(1)主程序-(2)P-(3)Q-(4)R主程序的活動(dòng)記錄 d0spdisplaytop（1） P 的活動(dòng)記錄主程序的活動(dòng)記錄 d1d0displaysptop（2）第三十頁(yè)，共四十一頁(yè)。用Display表的方案(1)主程序-(2)P-(3)Q-(4)RQ 的活動(dòng)記錄 P 的活動(dòng)記錄主程序的活動(dòng)記錄 displayd2d1d0sptop（3）R 的活動(dòng)記錄 Q 的活動(dòng)記錄 P 的活動(dòng)記錄主程序的活動(dòng)記錄 d1d0 displaytopsp（4）第三十一頁(yè)，共四十一頁(yè)。 當(dāng)過(guò)程的層次為n，它的 display為n+1個(gè)值。 一個(gè)過(guò)程被調(diào)用時(shí)，從調(diào)用過(guò)程的DISPLAY表中自下向上

17、抄錄n個(gè)SP值，再加上本層的SP值。全局DISPLAY地址DISPLAY表的維護(hù)和建立0老SP1返回地址2全局DISPLAY地址3參數(shù)個(gè)數(shù)4形式單元dDISPLAY.簡(jiǎn)單變量數(shù)組內(nèi)情向量臨時(shí)變量第三十二頁(yè)，共四十一頁(yè)。program P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q pro

18、cedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112第三十三頁(yè)，共四十一頁(yè)。program P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer;

19、begin a:=1; Q(c); endbegin a:=0; S; end0112500(形參個(gè)數(shù))2(全局display)返回地址x0a0(display)返回地址0過(guò)程P中調(diào)用S時(shí)的display表012345678910SPTOPc11i12display第三十四頁(yè)，共四十一頁(yè)。program P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*

20、(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112502返回地址x0a0過(guò)程S中調(diào)用Q時(shí)的display012345678910SPTOP返回地址00 (形參個(gè)數(shù))c11i12513返回地址149(display)151(形參個(gè)數(shù))16b(形參)170181319displaydisplay第三十五頁(yè)，共四十一頁(yè)。program P; var a,x:integer; procedure Q(b:integer); var i:int

21、eger; procedure R(u:integer; v:integer); var c,d:integer; begin if u=1 then R(u+1,v) v:=(a+c)*(b-d); end R begin R(1,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); endbegin a:=0; S; end0112過(guò)程Q中調(diào)用R時(shí)的display502返回地址x0a0012345678910SPTOP返回地址00c11i12513返回地址14915116b1701813191320返回地址2118(全局display)222(形參個(gè)數(shù))23U(形參)24v(形參)2502613272028c