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

1、第九章 運(yùn)轉(zhuǎn)時(shí)存儲(chǔ)空間組織目的程序運(yùn)轉(zhuǎ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)參數(shù)傳送途徑傳地址把實(shí)參的地址傳送給相應(yīng)的形參。過(guò)程段中每個(gè)形參都有相應(yīng)單元，稱(chēng)為方式單元，用來(lái)存放相應(yīng)實(shí)參的地址。假設(shè)實(shí)參是變量那么直接傳送地址，假設(shè)實(shí)參是常數(shù)或表達(dá)式，那么先計(jì)算其值并存放于某一暫時(shí)單元，再傳送暫時(shí)單元的地址。傳結(jié)果(call by reference)與傳地址類(lèi)似，其本質(zhì)

2、：每個(gè)形參對(duì)應(yīng)兩個(gè)單元，第一個(gè)單元存放實(shí)參地址，第二個(gè)存放實(shí)參的值。過(guò)程體中對(duì)形參的動(dòng)作均看成對(duì)第二個(gè)單元的直接訪(fǎng)問(wèn)，在過(guò)程完成前往前必需把第二個(gè)單元的內(nèi)容存放到第一個(gè)單元所指的實(shí)參單元中。Procedure swap(n,m:real); var j:real; begin j:=n; n:=m; m:=j; end傳地址過(guò)程調(diào)用swap(i,k(i)的過(guò)程：(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傳值過(guò)程a:=1;b:=2;調(diào)用swap(a,b)執(zhí)行過(guò)程：n:=am:=bj:=nn:=mm:=j部分變量m,n,j的值改動(dòng)，但不影響a，b的值參數(shù)傳送途徑傳名把被調(diào)用段的過(guò)程體抄到調(diào)用出現(xiàn)的位置，并將形參交換成相應(yīng)實(shí)參文字交換。Procedure swap(n,m:real); var j:real; begin j:=n; n:=m; m:=j; end傳名過(guò)程調(diào)用swap(i,k(i)的過(guò)程： j:=i; i:=k(i); k(i):=j;對(duì)于下面程序： 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í)行時(shí)所輸出的a分別是什么？參數(shù)傳送方式為“傳名Procedure 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參數(shù)傳送方式為“傳地址32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5暫時(shí)單元T：(a+b的值)&aTy：x：被調(diào)用者數(shù)

5、據(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：參數(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參數(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&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í)行語(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 ：程序終了，調(diào)用前往后：37&b：&a：調(diào)用者數(shù)據(jù)區(qū)5暫時(shí)單元T：(a+b的值)參數(shù)傳送方式為“傳值32&b：&a：調(diào)用者數(shù)據(jù)區(qū)5暫時(shí)單元T：(a+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

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

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

9、021TOPP的活動(dòng)記錄Q的活動(dòng)記錄主函數(shù)的活動(dòng)記錄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嵌套過(guò)程言語(yǔ)的棧式實(shí)現(xiàn)主要特點(diǎn)： 言語(yǔ)一個(gè)過(guò)程可以援用包圍它的任一外層過(guò)程所定義的標(biāo)識(shí)符如變量，數(shù)組或過(guò)程等。 實(shí)現(xiàn)一個(gè)過(guò)程可以援用它的任一外層過(guò)程的最新活動(dòng)記錄中的某些數(shù)據(jù)。嵌套過(guò)程言語(yǔ)的棧式實(shí)現(xiàn)關(guān)鍵技術(shù)：處理對(duì)非部分量的援用存取。設(shè)法跟蹤每個(gè)外層過(guò)程的最新活動(dòng)記錄AR的位置。跟蹤方法： 1. 用靜態(tài)鏈。 2. 用DISPLAY表。每個(gè)過(guò)程的AR有3個(gè)聯(lián)絡(luò)單元：SL： 靜態(tài)鏈，指向定義該過(guò)程的直接外過(guò)程

10、 或主程序運(yùn)轉(zhuǎn)時(shí)最新數(shù)據(jù)段的基地址。DL： 動(dòng)態(tài)鏈，指向調(diào)用該過(guò)程前正在運(yùn)轉(zhuǎn)過(guò)程的數(shù)據(jù)段基地址。RA： 前往地址，記錄調(diào)用該過(guò)程時(shí)目的程序的斷點(diǎn)，即調(diào)用過(guò)程指令的下一條指令的地址。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(形參個(gè)數(shù))0前往地址x0a0前往地址0過(guò)程P中調(diào)用S時(shí)的活動(dòng)記錄012345678910SPTOP動(dòng)態(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過(guò)程S中調(diào)用Q時(shí)的活動(dòng)記錄012345678910SPTOP動(dòng)態(tài)鏈靜態(tài)鏈前往地址00 (形參個(gè)數(shù))511前往地址120131(形參個(gè)數(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過(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 (形參)22c23d24Display表和活動(dòng)記錄Display表-嵌套層次顯示表 當(dāng)前激活過(guò)程的層次為K，它的Display表含有K+1個(gè)單元，依次存放著現(xiàn)行層，直接外層直至最外層

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

16、上本層的SP值。全局DISPLAY地址DISPLAY表的維護(hù)和建立0老SP1返回地址2全局DISPLAY地址3參數(shù)個(gè)數(shù)4形式單元dDISPLAY.簡(jiǎn)單變量數(shù)組內(nèi)情向量臨時(shí)變量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(形參個(gè)數(shù))2(全局display)前往地址x0a0(display)前往地址0過(guò)程P中調(diào)用S時(shí)的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過(guò)程S中調(diào)用Q時(shí)的display012345678910SPTOP前往地址00 (形參個(gè)數(shù))c11i12513前往地址149(display)151(形參個(gè)數(shù))16b(形參)170181319displaydisplayprogram P; var a,x:integer; procedure Q(b:integer); var i:integer; procedure R(u:integer; v:integer