編譯原理第九章-運行時存儲空間組織

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

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

3、; begin j:=n; n:=m; m:=j; end傳值過程a:=1;b:=2;調(diào)用s)執(zhí)行過程：n:=am:=bj:=nn:=mm:=j局部變量m,n,j的值改變，但不影響a，b的值第五頁，共四十一頁。參數(shù)傳遞途徑傳名把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的位置，并將形參替換成相應實參（文字替換）。Procedure s); var j:real; begin j:=n; n:=m; m:=j; end傳名過程調(diào)用s(i)的過程： j:=i; i:=k(i); k(i):=j;第六頁，共四十一頁。對于下面程序： 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）傳結果 （4）傳值。 執(zhí)行時所輸出的a分別是什么？第七頁，共四十一頁。參數(shù)傳遞方式為“傳名”Procedure p (a+b,a,a) ; begin a:=a+1; a:=a+a+b; end; p此時調(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)程序輸出結果a為9第八頁，共四十一頁。參數(shù)傳遞方式為“傳地址”32&b：&a：調(diào)

5、用者數(shù)據(jù)區(qū)5臨時單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)據(jù)區(qū)&a z：執(zhí)行語句y:=y+1后33&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)據(jù)區(qū)&a z：第九頁，共四十一頁。參數(shù)傳遞方式為“傳地址”執(zhí)行語句z:=z+x后38&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)據(jù)區(qū)&a z：程序輸出結果a為8第十頁，共四十一頁。參數(shù)傳遞方式為“傳結果”32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時單元T：(a+b的值)執(zhí)行語句y:=y+1后32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時單元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 ：第十一頁，共四十一頁。參數(shù)傳遞方式為“傳結果”執(zhí)行語句z:=z+x后32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時單元T：(a+b的值)程序輸出結果a為75T x_val ：x_add：被調(diào)用者數(shù)據(jù)區(qū)&a&a37y_val ：y_add ：z_val ：z_add ：程序結束，調(diào)用返回后：37&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時單元T：(a+b的值)第十二頁，共四十一頁。參數(shù)傳遞方式為“傳值”32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5臨時單元T：(a

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

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

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

10、標識符（如變量，數(shù)組或過程等）。 （實現(xiàn)）一個過程可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。第二十一頁，共四十一頁。嵌套過程語言的棧式實現(xiàn)關鍵技術：解決對非局部量的引用（存取）。設法跟蹤每個外層過程的最新活動記錄AR的位置。跟蹤辦法： 1. 用靜態(tài)鏈。 2. 用DISPLAY表。第二十二頁，共四十一頁。每個過程的AR有3個聯(lián)系單元：SL： 靜態(tài)鏈，指向定義該過程的直接外過程 （或主程序）運行時最新數(shù)據(jù)段的基地址。DL： 動態(tài)鏈，指向調(diào)用該過程前正在運行過程的數(shù)據(jù)段基地址。RA： 返回地址，記錄調(diào)用該過程時目標程序的斷點，即調(diào)用過程指令的下一條指令的地址。第二十三頁，共四十一頁。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第二十四頁，共四十一頁。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(形參個數(shù))0返回地址x0a0返回地址0過程P中調(diào)用S時的活動記錄012345678910SPTOP動態(tài)鏈靜態(tài)鏈第二十五頁，共四十一

13、頁。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過程S中調(diào)用Q時的活動記錄012345678910S

14、PTOP動態(tài)鏈靜態(tài)鏈返回地址00 (形參個數(shù))511返回地址120131(形參個數(shù))14b(形參)15i16第二十六頁，共四十一頁。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過程Q中調(diào)用R時的活動記錄ic0返回地址x0a0012345678910SPTOP動態(tài)鏈靜態(tài)鏈返回地址00 (形參個數(shù))511返回地址120131(形參個數(shù))14b(形參)15i161117返回地址1811192 (形參個數(shù))20u (形參)21v (形參)22c23d24第二十七頁，共四十一頁。Display表和活動記錄Display表-嵌套層次顯示表 當前激活過程的層次為K，它的Display表含有K+1個單元，依次存放著現(xiàn)行層，直接外層直至最外層的每一過程的最新活動記錄的基地址。第二十八頁，共四十一頁。第二十九頁，共四十一頁。用Dis

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

17、抄錄n個SP值，再加上本層的SP值。全局DISPLAY地址DISPLAY表的維護和建立0老SP1返回地址2全局DISPLAY地址3參數(shù)個數(shù)4形式單元dDISPLAY.簡單變量數(shù)組內(nèi)情向量臨時變量第三十二頁，共四十一頁。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第三十三頁，共四十一頁。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(形參個數(shù))2(全局display)返回地址x0a0(display)返回地址0過程P中調(diào)用S時的display表012345678910SPTOPc11i12display第三十四頁，共四十一頁。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過程S中調(diào)用Q時的display012345678910SPTOP返回地址00 (形參個數(shù))c11i12513返回地址149(display)151(形參個數(shù))16b(形參)170181319displaydisplay第三十五頁，共四十一頁。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過程Q中調(diào)用R時的display502返回地址x0a0012345678910SPTOP返回地址00c11i12513返回地址14915116b1701813191320返回地址2118(全局display)222(形參個數(shù))23U(形參)24v(形參)2502613272028c