北航研究生課程_程序語言設計原理教程_第04章

1、第第4 4章章 存存 儲儲 存儲對象是程序對象在計算機中的實現(xiàn)存儲對象是程序對象在計算機中的實現(xiàn) 程序對象不一一對應為存儲對象程序對象不一一對應為存儲對象 x:=0; x,0是兩程序對象是兩程序對象 只有一個存儲對象只有一個存儲對象x加指令清零加指令清零 初值常量也不作為單獨存儲對象初值常量也不作為單獨存儲對象4.1 4.1 程序變量的時空特性程序變量的時空特性4.1.1 4.1.1 引用和指針引用和指針計算對象有地址非固定地址計算對象有地址非固定地址, 因時而變因時而變, 相對地址相對地址 虛存空間虛存空間P指針是地址變量指針是地址變量 *P是是P所指的內容所指的內容, 也有左值和右值也有左

2、值和右值 *P左值是左值是P所指地址值，即所指地址值，即P的值的值 *P右值是所指地址內的內容值右值是所指地址內的內容值136140144A AB BC C3 31 12 23 31 16 63 32 20 0136140144( (R RA A) )3 31 12 2( (R RB B) )3 31 16 6( (R RC C) )3 32 20 0136144( (p p1 1) )4 44 48 8( (p p2 2) )4 45 50 04274.543312.27607.01( (A A) )1 13 36 6( (B B) )1 14 40 0( (C C) )1 14 44 4引

3、用是常指針是變量的別名引用是常指針是變量的別名, 但實現(xiàn)是不一樣的但實現(xiàn)是不一樣的4.1.2 4.1.2 遞引用遞引用 dereferencedereference通過指針變量引用變量的值為遞引用通過指針變量引用變量的值為遞引用*P1右值即遞引用右值即遞引用有些語言顯式遞引用算符如有些語言顯式遞引用算符如FORTH的的1 13 1 13 VARIABLE VARIABLE xx xx ( (聲明變量聲明變量xxxx并賦初值并賦初值13)13)2 0 2 0 VARIABLE Y (VARIABLE Y (聲明變量聲明變量Y Y并賦初值并賦初值0) 0) 3 3 xxxx 2 2 * * Y !

4、 ( Y ! (相當于相當于Y=Y=xxxx* *2)2)如果只寫如果只寫xxxx 2 2 * * 則為將則為將xxxx的地址乘以的地址乘以2 2放在放在Y Y之中之中4.1.3 變量的時態(tài)變量的時態(tài) 分配分配/未分配未分配/除分配除分配 分配分配: 為程序對象創(chuàng)建為程序對象創(chuàng)建存儲對象存儲對象 編譯時分配叫靜態(tài)分配編譯時分配叫靜態(tài)分配 allocate 運行時分配叫動態(tài)分配如聲明指針運行時分配叫動態(tài)分配如聲明指針p, 執(zhí)執(zhí)new才分配才分配 未分配未分配: 聲明了未分配運行時分配聲明了未分配運行時分配 除分配除分配: 取消存儲對象取消存儲對象(程序對象程序對象) delete操作顯式操作顯式

5、 自動除配自動除配: 無用單元收集無用單元收集Garbage collection動態(tài)語言有，靜態(tài)可有動態(tài)語言有，靜態(tài)可有Ada可沒有可沒有C續(xù)續(xù)43? ? a b c d e f 聲明和定義：定義必然聲明；反之不然聲明和定義：定義必然聲明；反之不然 聲明的兩個作用聲明的兩個作用 ：給出對象：給出對象, 該對象的時間有效性該對象的時間有效性 出了聲明的作用域該對象失去定義。在聲明的作用出了聲明的作用域該對象失去定義。在聲明的作用 域內顯式刪除也失去定義域內顯式刪除也失去定義定義定義/ /未定義未定義/ /失去定義失去定義 只要分配存儲對象必然有殘值只要分配存儲對象必然有殘值, 無意義即未定義無

6、意義即未定義 賦值或初值變量得以定義賦值或初值變量得以定義a,b:分配且有定義分配且有定義c,d:分配未定義或失去定義分配未定義或失去定義e,f:未分配或除配未分配或除配4.2 存儲模型 基元類型值基元類型值 僅除數(shù)組僅除數(shù)組 記錄、構造、表記錄、構造、表 不可更新其中一元素不可更新其中一元素 函數(shù)抽象函數(shù)抽象, ML重過程重過程 變量引用變量引用可存儲值可存儲值StorableStorable：指最小的可直接訪問的可存儲單元中的值指最小的可直接訪問的可存儲單元中的值Pascal可存儲值可存儲值:集合不選擇更新某一元素是可存儲值，集合不選擇更新某一元素是可存儲值，Pascal, C ，Ada數(shù)

7、組可選擇更新數(shù)組可選擇更新, 不是可存儲值。不是可存儲值。引用非可存儲引用非可存儲(C+可存儲可存儲), 過程和函數(shù)名也非可存儲過程和函數(shù)名也非可存儲ML幾乎都是可存儲值幾乎都是可存儲值, 也帶來毛?。好看胃陆Y構數(shù)據(jù)都要重也帶來毛?。好看胃陆Y構數(shù)據(jù)都要重來。它們是：來。它們是：( if exp then sin else cos ) (x) 得得sin(x)cos(x)可存儲值可存儲值 4.2.1存儲對象的生存期存儲對象的生存期 全局變量全局變量 和引用程序壽命一樣長和引用程序壽命一樣長 局部變量局部變量 和程序中的一個模塊壽命一樣長和程序中的一個模塊壽命一樣長 持久變量持久變量 比程序壽

8、命長除非顯式撤銷比程序壽命長除非顯式撤銷 文件變量文件變量 瞬間變量（瞬間變量（transient)持久變量的逆持久變量的逆每個存儲對象都有創(chuàng)建每個存儲對象都有創(chuàng)建(生生), 可用可用(活著活著)，撤銷，撤銷(死死)的的生命期。按生命期長短分：生命期。按生命期長短分：4.2.2 4.2.2 靜態(tài)存儲對象靜態(tài)存儲對象 編譯時分配存儲對象編譯時分配存儲對象, 近代語言類屬對象直到裝入后近代語言類屬對象直到裝入后確立確立(elaboration)之時才定下存儲對象叫靜態(tài)分配之時才定下存儲對象叫靜態(tài)分配 一旦執(zhí)行不再改動其存儲，直至所在存儲單元無效一旦執(zhí)行不再改動其存儲，直至所在存儲單元無效叫靜態(tài)叫靜

9、態(tài)(Static)存儲對象存儲對象 全局變量均為隱式的靜態(tài)對象全局變量均為隱式的靜態(tài)對象, COBOL,BASIC全全靜態(tài)，靜態(tài)，ALGOL，C是顯示聲明靜態(tài)，是顯示聲明靜態(tài)，Pascal除全局，除全局，Ada 不能。不能。 C語言的靜態(tài)變量是既私有又不隨所在聲明塊中消逝語言的靜態(tài)變量是既私有又不隨所在聲明塊中消逝, 全局于所在文件。全局于所在文件。auto是靜態(tài)分配動態(tài)裝入不叫靜態(tài)對是靜態(tài)分配動態(tài)裝入不叫靜態(tài)對象。象。Extern是靜態(tài)對象。是靜態(tài)對象。externstaticauto4.2.3動態(tài)存儲對象動態(tài)存儲對象 把壽命特長的（如文件，全局量）排出來歸到棧底的某一組，把壽命特短的（如循

10、環(huán)控制變量）另立嵌套組，這個問題也就解決。塊5塊66塊1塊2塊3塊45466546壽壽命命4.2.4 4.2.4 動態(tài)存儲對象動態(tài)存儲對象XX 二叉樹其大小由輸入值定在運行中確立。內存開二叉樹其大小由輸入值定在運行中確立。內存開辟堆（辟堆（heap)隨生成隨堆放動態(tài)存儲對象。指針（即隨生成隨堆放動態(tài)存儲對象。指針（即堆變量）所指程序對象用堆存放堆變量）所指程序對象用堆存放 問題：多次重分，內存成了小洞問題：多次重分，內存成了小洞 解決辦法：按壽命分組壽命最長的放在較低（按解決辦法：按壽命分組壽命最長的放在較低（按其所在塊生命期）。其所在塊生命期）。重復使用重復使用無法再分無法再分4.2.5 4

11、.2.5 堆棧幀管理堆棧幀管理 由動態(tài)堆棧聯(lián)想到一般嵌套式語言可按動態(tài)堆棧式管由動態(tài)堆棧聯(lián)想到一般嵌套式語言可按動態(tài)堆棧式管理理, 多數(shù)變量和所在塊壽命一樣長多數(shù)變量和所在塊壽命一樣長(語言稱之為自動變量語言稱之為自動變量) 動態(tài)堆棧式存儲動態(tài)堆棧式存儲 按程序動態(tài)執(zhí)行按程序動態(tài)執(zhí)行, 以動態(tài)堆棧管理局部數(shù)據(jù)和動態(tài)生以動態(tài)堆棧管理局部數(shù)據(jù)和動態(tài)生成數(shù)據(jù)成數(shù)據(jù) 運行時堆棧運行時堆棧Run-time stack其底壓入程序代碼和全局，其底壓入程序代碼和全局，靜態(tài)量。每執(zhí)行到調用時生成一個堆棧幀靜態(tài)量。每執(zhí)行到調用時生成一個堆棧幀(frame)記錄該記錄該塊數(shù)據(jù)信息塊數(shù)據(jù)信息, 每當返回則局部量自動

12、撤銷對于遞歸塊的每當返回則局部量自動撤銷對于遞歸塊的局部量可多次生成多次消除。局部量可多次生成多次消除。 動態(tài)鏈描述調用父輩地址動態(tài)鏈描述調用父輩地址, 返回地址是繼續(xù)執(zhí)行的下返回地址是繼續(xù)執(zhí)行的下一地址。一地址。 靜態(tài)鏈描述詞法父輩靜態(tài)鏈描述詞法父輩lexical parent塊地址塊地址, 按該塊復制按該塊復制局部變量。局部變量。參數(shù)參數(shù) 返回地址返回地址動態(tài)鏈動態(tài)鏈靜態(tài)鏈靜態(tài)鏈返回值返回值局部變量局部變量程序代碼程序代碼全局靜態(tài)存儲全局靜態(tài)存儲首先調用塊首先調用塊堆棧幀堆棧幀第二調用塊第二調用塊堆棧幀堆棧幀最新最新調用塊調用塊堆棧幀堆棧幀臨時變量空間臨時變量空間棧頂棧頂堆棧幀堆棧幀組織組

13、織運行時堆棧運行時堆棧續(xù)續(xù)調調用用塊塊首首地地址址本本幀幀詞詞法法父父輩輩 舉例舉例 求整數(shù)連乘積之遞歸程序求整數(shù)連乘積之遞歸程序: function product (jj： Integer)： Integer； var kk： Integer; begin if jj = 0 then product:=1 else begin readln (kk)； product:=kk * product(jj-1) end end； Product函數(shù)函數(shù)目標代碼目標代碼jj:2return :?kk:25jj:1return :?kk:7jj:0return :?kk:?臨時存儲臨時存儲DLS

14、L:SL:靜態(tài)鏈靜態(tài)鏈DL:DL:靜態(tài)鏈靜態(tài)鏈最初調用時堆棧幀最初調用時堆棧幀第一次調用時堆棧幀第一次調用時堆棧幀第一次調用時堆棧幀第一次調用時堆棧幀 棧頂棧頂SL4.2.6 動態(tài)堆存儲動態(tài)堆存儲 忽略死對象忽略死對象 不超過一頁浪費不超過一頁浪費, 若壽命差不多浪費不大若壽命差不多浪費不大 保持一個自由表保持一個自由表(鏈表鏈表)8個字節(jié)頭說明數(shù)據(jù)個字節(jié)頭說明數(shù)據(jù) 按類型長度保持多個表減少識別域開銷按類型長度保持多個表減少識別域開銷(Ada) 動態(tài)堆棧缺點：開始幀不知有多大動態(tài)堆棧缺點：開始幀不知有多大,要求存儲對象要求存儲對象比創(chuàng)建它的塊壽命長。比創(chuàng)建它的塊壽命長。 指針和顯式動態(tài)分配依然

15、不少了堆。按幀也設指針和顯式動態(tài)分配依然不少了堆。按幀也設heap 各種語言堆分配各種語言堆分配 FORTH LISP C Pascal FORTH LISP C Pascal AdaAda分配分配 Here cons Here cons malloc malloc new new new new除配除配 無回收無回收 有回收有回收 顯式除顯式除 顯式除顯式除 有回收有回收 死堆對象處理死堆對象處理 死堆對象也叫無用單元死堆對象也叫無用單元garbage。(垃圾）垃圾）4.3 4.3 懸掛引用懸掛引用Dangling ReferenceDangling Reference 當堆式管理同時提供顯

16、式除配命令當堆式管理同時提供顯式除配命令KILL時；堆棧式時；堆棧式管理外塊指針指向內塊對象時管理外塊指針指向內塊對象時; 函數(shù)抽象作為第一類值函數(shù)抽象作為第一類值時時,都會產(chǎn)生都會產(chǎn)生懸掛引用懸掛引用 解決辦法解決辦法 Pascal把指針限制為堆對象且不用把指針限制為堆對象且不用dispose，不提供地不提供地址運算。操作數(shù)組不能按指針尋址址運算。操作數(shù)組不能按指針尋址, 快速索引快速索引 C語言比較自由，懸掛引用留給程序員語言比較自由，懸掛引用留給程序員 局部函數(shù)作為返回值產(chǎn)生的懸掛指針。局部函數(shù)作為返回值產(chǎn)生的懸掛指針。 ML, Mirada完全作為堆變量且無完全作為堆變量且無KILL。

17、Algol 68是引用（常指針是引用（常指針）, 不賦比局部量壽命更長的值不賦比局部量壽命更長的值例例 懸掛引用懸掛引用( (C)C)intint * * dangle ( dangle (int int * * * ppp ppp) /) /參數(shù)是指針的指針參數(shù)是指針的指針 intint p=5 p=5； intint m=21 m=21； * *pppppp=&p=&p； /傳回的指向傳回的指向p p的指針的指針 return & mreturn & m； / /返回返回m m的地址的地址main( ) main( ) int int k =17 k =17

18、； intint * * pm pm， * *pkpk=&k=&k； /pkpk指向指向k k pm pm = dangle (& = dangle (&pkpk) )； /返回時返回時pmpm，PkPk均指向已均指向已 /失去定義的指針函數(shù)的失去定義的指針函數(shù)的 / /局部量，即局部量，即p p和和m m4.4 4.4 變量更新變量更新更新途徑：賦值更新途徑：賦值 動態(tài)賦值動態(tài)賦值 初始化初始化 靜態(tài)賦值靜態(tài)賦值4.4.1 4.4.1 變量初始化變量初始化 分配了自動賦初值分配了自動賦初值, 有多種不便有多種不便 顯式賦初值顯式賦初值 FORTRAN和和C的例

19、子的例子static char end_of_file_flag = “no ”static char end_of_file_flag = “no ”； int isumint isum=0=0； static float a8 = 8.2static float a8 = 8.2，2.62.6，3.13.1，17.017.0；CHARACTER CHARACTER * * 3 EOFLAG 3 EOFLAGDIMENSION A(8)DIMENSION A(8)DATA EOFLAGDATA EOFLAG，ISUM/NO ISUM/NO ，0/(A(I)0/(A(I)，I=1I=1， 8)

20、/8.28)/8.2， 2.62.6，3.13.1，17.017.0，4 4* * 0.0/ 0.0/簡單賦值與聚集簡單賦值與聚集 近代語言擴充動態(tài)聚集值強行賦值或近代語言擴充動態(tài)聚集值強行賦值或RAED調用調用 typedef struct typedef struct intint age age，weightweight；char sexchar sex；personperson； person aperson a，b = 10b = 10，7070，MM；/b/b有初值，有初值，a a沒有。沒有。 a = ba = b； /動態(tài)聚集賦值，動態(tài)聚集賦值，a a也有了。也有了。 函數(shù)賦值函

21、數(shù)賦值 沒有簡單賦值采用統(tǒng)一的函數(shù)返回值。沒有簡單賦值采用統(tǒng)一的函數(shù)返回值。LISP, C, APL 函數(shù)賦值是表達式計算后有一中間值函數(shù)賦值是表達式計算后有一中間值, 被賦給變量。被賦給變量。故賦值命令可作為表達式故賦值命令可作為表達式, 且支持多重賦值。且支持多重賦值。 # #define MAXLENGTH 100define MAXLENGTH 100 float float ararMAXLENGTHMAXLENGTH； intint high_sub high_sub， numnum_elements_elements； high_sub=(high_sub=(numnum_elements=MAXLENGTH)-1_elements=MAXLENGTH)-1；4.4.2 4.4.2 動態(tài)更新動態(tài)更新續(xù)續(xù)常見語言賦值實現(xiàn)常見語言賦值實現(xiàn)語言語言 賦值號賦值號 聚集賦值聚集賦值 多重賦值多重賦值 實現(xiàn)機制實現(xiàn)機制 COBOL MOVE COBOL MOVE 可可 可可 = =（在（在COMPUTECOMPUTE語句中）語句中） 否否 可可 語語 ADD,SUBTRACT,MULTIPLY ADD,SUBTRACT,MULTIPLY 否否 可可 句句 DIVIDE DIVIDE FORTRAN = FORTRAN = 否否