編譯原理 第九章——運行時存儲空間組織ppt課件

1、第九章 運轉(zhuǎn)時存儲空間組織目的程序運轉(zhuǎn)時的活動過程的活動 一個過程的活動指該過程的一次執(zhí)行。參數(shù)傳送 1. 參數(shù) 形參：過程定義時出現(xiàn) 實參：過程調(diào)用時出現(xiàn) 2. 參數(shù)傳送的途徑： 傳地址(call by reference) 傳值 (call by value) 傳名(換名)(call by name)參數(shù)傳送途徑傳地址把實參的地址傳送給相應(yīng)的形參。過程段中每個形參都有相應(yīng)單元，稱為方式單元，用來存放相應(yīng)實參的地址。假設(shè)實參是變量那么直接傳送地址，假設(shè)實參是常數(shù)或表達式，那么先計算其值并存放于某一暫時單元，再傳送暫時單元的地址。傳結(jié)果(call by reference)與傳地址類似，其本質(zhì)

2、：每個形參對應(yīng)兩個單元，第一個單元存放實參地址，第二個存放實參的值。過程體中對形參的動作均看成對第二個單元的直接訪問，在過程完成前往前必需把第二個單元的內(nèi)容存放到第一個單元所指的實參單元中。Procedure swap(n,m:real); var j:real; begin j:=n; n:=m; m:=j; end傳地址過程調(diào)用swap(i,k(i)的過程：(1)將i，k(i)地址傳送到知單元J1和J2中(2) n:=J1; m:=J2;(3) j:=n;(4) n:=m;(5) m:=j;參數(shù)傳送途徑傳值Procedure swap(n,m:real); var j:real; begi

3、n j:=n; n:=m; m:=j; end傳值過程a:=1;b:=2;調(diào)用swap(a,b)執(zhí)行過程：n:=am:=bj:=nn:=mm:=j部分變量m,n,j的值改動，但不影響a，b的值參數(shù)傳送途徑傳名把被調(diào)用段的過程體抄到調(diào)用出現(xiàn)的位置，并將形參交換成相應(yīng)實參文字交換。Procedure swap(n,m:real); var j:real; begin j:=n; n:=m; m:=j; end傳名過程調(diào)用swap(i,k(i)的過程： j:=i; i:=k(i); k(i):=j;對于下面程序： Procedure p (x,y,z) ; begin y:=y+1; z:=z+x;

4、 end; p begin a:=2; b:=3; p (a+b , a , a) print a end. 假設(shè)參數(shù)傳送的方法分別為 1傳名2傳地址 3傳結(jié)果 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)程序輸出結(jié)果a為9參數(shù)傳送方式為“傳地址32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5暫時單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)

5、據(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：程序輸出結(jié)果a為8參數(shù)傳送方式為“傳結(jié)果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&a32y_val ：y_add ：z_val ：z_add ：5T x_val ：x_add：被調(diào)用者數(shù)據(jù)

6、區(qū)&a&a22y_val ：y_add ：z_val ：z_add ：參數(shù)傳送方式為“傳結(jié)果執(zhí)行語句z:=z+x后32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5暫時單元T：(a+b的值)程序輸出結(jié)果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+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

7、：參數(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：程序輸出結(jié)果a為2運轉(zhuǎn)時存儲器的劃分程序區(qū)棧區(qū)靜態(tài)區(qū)目的區(qū)堆區(qū)可變數(shù)組，函數(shù)活動記錄 目的代碼區(qū) 靜態(tài)數(shù)據(jù)區(qū) Stack heap靜態(tài)：假設(shè)一個名字的性質(zhì)經(jīng)過闡明語句或隱或顯規(guī)那么而定義，那么稱這種性質(zhì)是“靜態(tài)確定的。動態(tài)：假設(shè)名字的性質(zhì)只需在程序運轉(zhuǎn)時才干知道，那么稱這種性質(zhì)為“動態(tài)確定的?？勺?(動態(tài))數(shù)組： 假設(shè)一個數(shù)組所需的存儲空間的大小在編譯時就知道，那么稱它為確定數(shù)組，否那么稱為可變(動態(tài))數(shù)組。數(shù)據(jù)區(qū)管理方法靜態(tài)存儲方法動態(tài)存儲方法 棧式：函數(shù)遞歸

8、定義、調(diào)用 堆式：動態(tài)懇求、釋放、new、delete活動記錄銜接數(shù)據(jù) 前往地址 靜態(tài)鏈：指向調(diào)用該過程前的最新活動記錄地址的指針 動態(tài)鏈：指向靜態(tài)直接外層最新活動記錄地址的指針方式單元部分數(shù)據(jù)區(qū)：部分變量、內(nèi)情向量、暫時任務(wù)單元靜態(tài)存儲分配靜態(tài)分配：假設(shè)在編譯時就能確定程序在運轉(zhuǎn)時所需存儲空間的大小，那么在編譯時就可以安排好目的程序運轉(zhuǎn)時的全部數(shù)據(jù)空間，并能確定每個數(shù)據(jù)項的單元地址。 Fortran言語就采用了靜態(tài)存儲分配的戰(zhàn)略。數(shù)據(jù)區(qū) 簡單的棧式存儲分配main( ) Q( ); P( ) Q( ) P( ); 1010SPTOP老SP 1010TOP+1=SP2021前往地址TOPSP2

9、021TOPP的活動記錄Q的活動記錄主函數(shù)的活動記錄C言語活動記錄的內(nèi)容銜接數(shù)據(jù)參數(shù)個數(shù)方式單元函數(shù)的部分變量、數(shù)組內(nèi)情向量、暫時單元老SP前往地址參數(shù)個數(shù)方式單元簡單變量內(nèi)情向量暫時單元sp嵌套過程言語的棧式實現(xiàn)主要特點： 言語一個過程可以援用包圍它的任一外層過程所定義的標識符如變量，數(shù)組或過程等。 實現(xiàn)一個過程可以援用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。嵌套過程言語的棧式實現(xiàn)關(guān)鍵技術(shù)：處理對非部分量的援用存取。設(shè)法跟蹤每個外層過程的最新活動記錄AR的位置。跟蹤方法： 1. 用靜態(tài)鏈。 2. 用DISPLAY表。每個過程的AR有3個聯(lián)絡(luò)單元：SL： 靜態(tài)鏈，指向定義該過程的直接外過程

10、 或主程序運轉(zhuǎn)時最新數(shù)據(jù)段的基地址。DL： 動態(tài)鏈，指向調(diào)用該過程前正在運轉(zhuǎn)過程的數(shù)據(jù)段基地址。RA： 前往地址，記錄調(diào)用該過程時目的程序的斷點，即調(diào)用過程指令的下一條指令的地址。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:i

11、nteger; begin a:=1; Q(c); endbegin a:=0; S; end0112program 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

12、; S; end0112ic0(形參個數(shù))0前往地址x0a0前往地址0過程P中調(diào)用S時的活動記錄012345678910SPTOP動態(tài)鏈靜態(tà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 procedure S; var c,i:integer; begin a:=1;

13、 Q(c); endbegin a:=0; S; end0112ic0前往地址x0a0過程S中調(diào)用Q時的活動記錄012345678910SPTOP動態(tài)鏈靜態(tài)鏈前往地址00 (形參個數(shù))511前往地址120131(形參個數(shù))14b(形參)15i16program 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

14、,x); end Q procedure S; var c,i:integer; begin a:=1; Q(c); 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 (形參)22c23d24Display表和活動記錄Display表-嵌套層次顯示表 當前激活過程的層次為K，它的Display表含有K+1個單元，依次存放著現(xiàn)行層，直接外層直至最外層

15、的每一過程的最新活動記錄的基地址。用Display表的方案(1)主程序-(2)P-(3)Q-(4)R主程序的活動記錄 d0spdisplaytop1 P 的活動記錄主程序的活動記錄 d1d0displaysptop2用Display表的方案(1)主程序-(2)P-(3)Q-(4)RQ 的活動記錄 P 的活動記錄主程序的活動記錄 displayd2d1d0sptop3R 的活動記錄 Q 的活動記錄 P 的活動記錄主程序的活動記錄 d1d0 displaytopsp4 當過程的層次為n，它的 display為n+1個值。 一個過程被調(diào)用時，從調(diào)用過程的DISPLAY表中自下向上抄錄n個SP值，再加

16、上本層的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 procedure S; var c,i:inte

17、ger; begin a:=1; Q(c); endbegin a:=0; S; end0112program 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

18、; end0112500(形參個數(shù))2(全局display)前往地址x0a0(display)前往地址0過程P中調(diào)用S時的display表012345678910SPTOPc11i12displayprogram 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; end0112502前往地址x0a0過程S中調(diào)用Q時的display012345678910SPTOP前往地址00 (形參個數(shù))c11i12513前往地址149(display)151(形參個數(shù))16b(形參)170181319displaydisplayprogram P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer