編譯原理存儲(chǔ)組織演示文稿當(dāng)前第1頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)編譯原理第章存儲(chǔ)組織當(dāng)前第2頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)第十章目標(biāo)程序運(yùn)行時(shí)的存儲(chǔ)組織概述數(shù)據(jù)空間的使用方法和管理方法棧式存儲(chǔ)分配的實(shí)現(xiàn)參數(shù)傳遞過(guò)程操作練習(xí)當(dāng)前第3頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)概述一般來(lái)講，假如編譯程序從操作系統(tǒng)中得到一塊存儲(chǔ)區(qū)以位目標(biāo)程序在其上運(yùn)行，該存儲(chǔ)區(qū)需容納生成的目標(biāo)代碼和目標(biāo)代碼運(yùn)行時(shí)的數(shù)據(jù)空間。數(shù)據(jù)空間應(yīng)包括：用戶定義的各種類型的數(shù)據(jù)對(duì)象(變量和常數(shù))所需的存儲(chǔ)空間、作為保留中間結(jié)果和傳遞參數(shù)的臨時(shí)工作單元，調(diào)用過(guò)程時(shí)所需的連接單元、以及組織輸入/輸出所需的緩沖區(qū)。運(yùn)行時(shí)的存儲(chǔ)區(qū)常常劃分成：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)。運(yùn)行時(shí)存儲(chǔ)區(qū)的典型劃分編譯程序?qū)?shù)據(jù)空間的分配當(dāng)前第4頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)運(yùn)行時(shí)存儲(chǔ)區(qū)的典型劃分代碼(code)區(qū)用以存放目標(biāo)代碼，這是固定長(zhǎng)度的，即編譯時(shí)能確定的。靜態(tài)數(shù)據(jù)區(qū)(staticdata)用以存放編譯時(shí)能確定所占用空間的數(shù)據(jù)。堆棧區(qū)(stackandheap)用于可變數(shù)據(jù)以及管理過(guò)程活動(dòng)的控制信息。目標(biāo)程序運(yùn)行時(shí)存儲(chǔ)區(qū)的典型劃分當(dāng)前第5頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)編譯程序?qū)?shù)據(jù)空間的分配基本原則是程序語(yǔ)言設(shè)計(jì)時(shí)對(duì)程序運(yùn)行中存儲(chǔ)空間的使用和管理辦法的規(guī)定。數(shù)據(jù)空間的分配：本質(zhì)上看是將程序中的每個(gè)名字與一個(gè)存儲(chǔ)位置關(guān)聯(lián)起來(lái)，該存儲(chǔ)位置用以容納名字的值。在程序設(shè)計(jì)語(yǔ)言語(yǔ)義學(xué)中，使用術(shù)語(yǔ)environment表示將一個(gè)名字映射到一個(gè)存儲(chǔ)位置的函數(shù)，術(shù)語(yǔ)state表示存儲(chǔ)位置到值的映射。名字到存儲(chǔ)、到值的映射當(dāng)前第6頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)數(shù)據(jù)空間的使用方法和管理方法術(shù)語(yǔ)：靜態(tài)：如果一個(gè)名字的性質(zhì)通過(guò)說(shuō)明語(yǔ)句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。動(dòng)態(tài)：如果名字的性質(zhì)只有在程序運(yùn)行時(shí)才能知道，則稱這種性質(zhì)為“動(dòng)態(tài)”確定的。靜態(tài)存儲(chǔ)分配動(dòng)態(tài)存儲(chǔ)分配當(dāng)前第7頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)靜態(tài)存儲(chǔ)分配如果在編譯時(shí)能確定目標(biāo)程序運(yùn)行中所需的全部數(shù)據(jù)空間的大小，編譯時(shí)安排好目標(biāo)程序運(yùn)行時(shí)的全部數(shù)據(jù)空間，確定每個(gè)數(shù)據(jù)對(duì)象的存儲(chǔ)位置，那么則稱這種分配策略為靜態(tài)存儲(chǔ)分配。示例FORTRAN77的示例程序該程序中局部變量的靜態(tài)存儲(chǔ)位置當(dāng)前第8頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)FORTRAN77的程序當(dāng)前第9頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)局部變量的靜態(tài)存儲(chǔ)位置當(dāng)前第10頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序設(shè)計(jì)語(yǔ)言允許遞歸過(guò)程、可變數(shù)組或可變數(shù)據(jù)結(jié)構(gòu)，那么，就需要采用動(dòng)態(tài)存儲(chǔ)管理技術(shù)。因?yàn)閷?duì)于這種程序在編譯時(shí)無(wú)法知道它在運(yùn)行時(shí)需要多大的存儲(chǔ)空間，它所需要的數(shù)據(jù)空間的大小需待程序運(yùn)行時(shí)動(dòng)態(tài)地確定。分類：棧式動(dòng)態(tài)存儲(chǔ)分配堆式動(dòng)態(tài)存儲(chǔ)分配當(dāng)前第11頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)棧式動(dòng)態(tài)存儲(chǔ)分配這種分配策略是將整個(gè)程序的數(shù)據(jù)空間設(shè)計(jì)為一個(gè)棧。它適用于Pascal，C，ALGOL之類的語(yǔ)言的實(shí)現(xiàn)，每當(dāng)調(diào)用一個(gè)過(guò)程時(shí)，它所需的數(shù)據(jù)空間就分配在棧頂，每當(dāng)過(guò)程工作結(jié)束時(shí)就釋放這部分空間。過(guò)程所需的數(shù)據(jù)空間包括兩部分：一部分是生存期在本過(guò)程這次活動(dòng)中的數(shù)據(jù)對(duì)象，如局部變量、參數(shù)單元、臨時(shí)變量等等；另一部分則是用以管理過(guò)程活動(dòng)的記錄信息，即當(dāng)一次過(guò)程調(diào)用出現(xiàn)時(shí)，調(diào)用該過(guò)程的那個(gè)過(guò)程的活動(dòng)即被中斷，當(dāng)前機(jī)器的狀態(tài)信息，諸如程序計(jì)數(shù)器(返回地址)、寄存器的值等等，也都必須保留在棧中。當(dāng)控制從調(diào)用返回時(shí)，便根據(jù)棧中記錄的信息恢復(fù)機(jī)器狀態(tài)，使該過(guò)程的活動(dòng)重新開(kāi)始。當(dāng)前第12頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)堆式動(dòng)態(tài)存儲(chǔ)分配如果一個(gè)程序語(yǔ)言提供用戶自由地申請(qǐng)數(shù)據(jù)空間和退還數(shù)據(jù)空間的機(jī)制(如C++中的new，delete．Pascal的new，便是這種機(jī)制)，或者不僅有過(guò)程而且有進(jìn)程的程序結(jié)構(gòu)，即空間的使用未必服從“先申請(qǐng)后釋放，后申請(qǐng)先釋放”的原則，那么棧式的動(dòng)態(tài)分配方案就不適用了。這種情況下通常使用一種稱為堆式的動(dòng)態(tài)存儲(chǔ)分配方案。假設(shè)程序運(yùn)行時(shí)有一個(gè)大的存儲(chǔ)空間，每當(dāng)需要時(shí)就從這片空間中借用一塊，不用時(shí)再退還，由于借還的時(shí)間先后不一，經(jīng)一段運(yùn)行之后，程序運(yùn)行空間將被分劃成許多塊塊，有些占用，有些空閑。那么當(dāng)運(yùn)行程序要求一塊體積為N的空間時(shí)，需要決定應(yīng)該從哪個(gè)空閑塊得到這個(gè)空間。理論上講，應(yīng)該從比N稍大一些的空間塊中取出N個(gè)單元，以便位大的空閑塊派更大的用場(chǎng)，但實(shí)現(xiàn)難度很大，實(shí)際中常常采用的辦法是：先遇到哪塊比N大就從其中取出N個(gè)單元。即使這樣，也會(huì)發(fā)生找不到一塊比N大的空閑塊，但所有空閑塊的總和比N大得多的情況，這時(shí)，有的分配管理系統(tǒng)采用廢品回收的辦法來(lái)應(yīng)付。當(dāng)前第13頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)棧式存儲(chǔ)分配的實(shí)現(xiàn)過(guò)程的活動(dòng)記錄簡(jiǎn)單的棧式動(dòng)態(tài)分配實(shí)現(xiàn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)分程序結(jié)構(gòu)的存儲(chǔ)管理當(dāng)前第14頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)過(guò)程的活動(dòng)記錄過(guò)程的活動(dòng)記錄是一段連續(xù)的存儲(chǔ)區(qū)．用以存放過(guò)程的一次執(zhí)行所需要的信息。簡(jiǎn)單描述當(dāng)前第15頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)簡(jiǎn)單描述1．臨時(shí)工作單元，比如計(jì)算表達(dá)式過(guò)程中需存放中間結(jié)果用的臨時(shí)值單元。2．局部變量，一個(gè)過(guò)程的局部變量。3．保存機(jī)器狀態(tài)，容納該過(guò)程執(zhí)行前關(guān)于機(jī)器狀態(tài)信息，諸如程序計(jì)數(shù)器、寄存器的值，這些值都需要在控制從該過(guò)程返回時(shí)給予恢復(fù)。4．存取鏈，用以存取非局部變量，這些變量存放于其它過(guò)程活動(dòng)記錄中。并不是所有語(yǔ)言需要該信息。5．控制鏈，指向調(diào)用該過(guò)程的那個(gè)過(guò)程的活動(dòng)記錄，這也不是所有語(yǔ)言都需要的。6．實(shí)參，也稱形式單元，由調(diào)用過(guò)程向該被說(shuō)過(guò)程提供實(shí)參的值(或地址)。當(dāng)然在實(shí)際編譯程序中，也常常使用機(jī)器寄存器傳遞實(shí)參。7．返回地址，保存該被調(diào)過(guò)程返回后的地址。當(dāng)前第16頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)簡(jiǎn)單的棧式動(dòng)態(tài)分配實(shí)現(xiàn)要求：沒(méi)有分程序結(jié)構(gòu)過(guò)程定義不嵌套允許過(guò)程遞歸調(diào)用示例：程序結(jié)構(gòu)分配策略存儲(chǔ)分配結(jié)構(gòu)圖活動(dòng)記錄內(nèi)容運(yùn)行棧當(dāng)前第17頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)程序結(jié)構(gòu)當(dāng)前第18頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)分配策略運(yùn)行時(shí)，每當(dāng)進(jìn)入一個(gè)過(guò)程，則為該過(guò)程分配一段存儲(chǔ)區(qū)。當(dāng)一個(gè)過(guò)程工作完畢返回時(shí)，它所占用的存儲(chǔ)區(qū)則可釋放。程序運(yùn)行時(shí)的存儲(chǔ)空間，(棧)中在某一時(shí)刻可能會(huì)包含某個(gè)過(guò)程的幾個(gè)活動(dòng)記錄(某個(gè)過(guò)程遞歸調(diào)用的情況)；另外，同樣的一個(gè)存儲(chǔ)位置，可能不同運(yùn)行時(shí)刻分配給不同的數(shù)據(jù)對(duì)象。當(dāng)前第19頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)存儲(chǔ)分配結(jié)構(gòu)圖若主程序調(diào)用了過(guò)程Q，Q又調(diào)用了R，在R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖(a)所示。若主程序調(diào)用了過(guò)程Q，Q遞歸調(diào)用自己，在Q過(guò)程第二次進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)如圖(b)所示。若主程序先調(diào)用過(guò)程Q，然后主程序接著調(diào)用R，且Q過(guò)程不調(diào)用Q和R，這時(shí)Q和R進(jìn)入運(yùn)行后的存儲(chǔ)結(jié)構(gòu)分別如圖(c)和(d)所示。當(dāng)前第20頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)活動(dòng)記錄內(nèi)容SP總是指向現(xiàn)行過(guò)程活動(dòng)記錄的起點(diǎn)。TOP則始終指向已占用的棧頂單元。當(dāng)前第21頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)運(yùn)行棧當(dāng)前第22頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)嵌套過(guò)程語(yǔ)言的棧式實(shí)現(xiàn)具有嵌套過(guò)程的Pascal程序程序中過(guò)程定義的嵌套情況存儲(chǔ)棧的布局活動(dòng)記錄情況在過(guò)程活動(dòng)記錄中增設(shè)存儲(chǔ)鏈在過(guò)程活動(dòng)記錄中存取非局部變量當(dāng)前第23頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)具有嵌套過(guò)程的Pascal程序當(dāng)前第24頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)程序中過(guò)程定義的嵌套情況sortreadarrayexchangequicksonpartition可將整個(gè)程序sort看成最外層的過(guò)程，readarray、exchange、quickson、partition中引用的a均不是它們的局部變量，而是過(guò)程sort的局部變量。當(dāng)前第25頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)存儲(chǔ)棧的布局假如過(guò)程sort激活(調(diào)用)了過(guò)程quicksort，這時(shí)存儲(chǔ)棧小的情形示意如下圖所示，其中在quicksort過(guò)程活動(dòng)記錄中有一(或一些)存儲(chǔ)單元(用斜線描繪)用以記錄過(guò)程quicksort以引用sort中定義的變量a和x。當(dāng)前第26頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)增設(shè)存儲(chǔ)鏈在活動(dòng)記錄過(guò)程中增設(shè)存取鏈，指向包含該過(guò)程的直接外層過(guò)程的最新活動(dòng)記錄的起始位置。示例：過(guò)程活動(dòng)記錄的內(nèi)容圖過(guò)程sort調(diào)用過(guò)程quicksort的存儲(chǔ)棧圖如果某次執(zhí)行的順序?yàn)?sort→quicksort→quicksort→partition→exchange→?進(jìn)入過(guò)程exchange之后的運(yùn)行棧圖。當(dāng)前第27頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)過(guò)程活動(dòng)記錄的內(nèi)容圖當(dāng)前第28頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)過(guò)程sort調(diào)用過(guò)程quicksort的存儲(chǔ)棧圖當(dāng)前第29頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)進(jìn)入過(guò)程exchange之后的運(yùn)行棧圖當(dāng)前第30頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)存取非局部變量存取非局部變量的辦法是常用的有效辦法。即每進(jìn)入一個(gè)過(guò)程后，在建立它的活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表display。display是一個(gè)指針數(shù)組d，也可看作是一個(gè)小棧，自頂向下每個(gè)單元依次存放著現(xiàn)行層，直接外層，……直至最外層(0層，主程序?qū)?等每一層過(guò)程的最新活動(dòng)記錄的地址。示例：1)sort→quicksort?；2)sort→quicksort→quicksort?；3)sort→quicksort→quicksort→partition?；4)sort→quicksort→quicksort→partition→exchange?

過(guò)程調(diào)用時(shí)display的建立當(dāng)前第31頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)1的運(yùn)行棧和display當(dāng)前第32頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)2的運(yùn)行棧和display當(dāng)前第33頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)3的運(yùn)行棧和display當(dāng)前第34頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)4的運(yùn)行棧和display當(dāng)前第35頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)過(guò)程調(diào)用時(shí)display的建立當(dāng)過(guò)程P1調(diào)用過(guò)程P2而進(jìn)入P2后，P2為了建立自己的display，P2必須知道它的直接外層過(guò)程(記為P0)的display。這意味著,當(dāng)P1調(diào)用P2時(shí)必須把P0的display地址作為連接數(shù)據(jù)之一傳給P2。display的構(gòu)造P2是真實(shí)過(guò)程時(shí)的構(gòu)造P2是形式參數(shù)時(shí)的構(gòu)造當(dāng)前第36頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)真實(shí)過(guò)程時(shí)的構(gòu)造P0或者就是P1自身或者既是P1又是P2的直接外層(示意圖)。不論哪一種情形，只要在進(jìn)入P2后能夠知道P1的display就能知道P0的display，從而可直接構(gòu)造出P2的display。事實(shí)上，只需從P1的display中自底而上地取過(guò)l2個(gè)單元(l2為P2的層數(shù))再添上進(jìn)入P2后新建立的SP值就構(gòu)成了P2的display。也就是說(shuō)，在這種情況下，只需把P1的display地址作為連接數(shù)據(jù)之一傳送給P2就能夠建立P2的display。當(dāng)前第37頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)P1調(diào)用P2的兩種不同嵌套示意圖當(dāng)前第38頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)形式參數(shù)時(shí)的構(gòu)造調(diào)用P2意味著調(diào)用P2當(dāng)前相應(yīng)的實(shí)在過(guò)程。此時(shí)的P0應(yīng)是這個(gè)實(shí)在過(guò)程的直接外層過(guò)程。假定P0的display地址可從形式單元P2所指示的地方獲得。為了能在P2中獲得P0的display地址，必須在P1調(diào)用P2時(shí)設(shè)法把P1的display地址作為連接數(shù)據(jù)之一(稱為“全局display地址”)傳送給P2。于是連接數(shù)據(jù)變?yōu)槿?xiàng)：(1)老SP值；(2)返回地址；(3)全局display地址。當(dāng)前第39頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)分程序結(jié)構(gòu)的存儲(chǔ)管理概述聲明作用域遵循的原則——最近嵌套原則分程序結(jié)構(gòu)的存儲(chǔ)管理分程序結(jié)構(gòu)的存儲(chǔ)實(shí)現(xiàn)方法視分程序?yàn)椤盁o(wú)參過(guò)程”視分程序?yàn)橥暾倪^(guò)程體活動(dòng)記錄的內(nèi)容分程序的進(jìn)入和退出時(shí)活動(dòng)記錄的情況當(dāng)前第40頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)概述一個(gè)分程序是一個(gè)含有它自己的局部數(shù)據(jù)(變量)聲明的語(yǔ)句。示例：C語(yǔ)言，一個(gè)分程序的語(yǔ)法形式是：{聲明語(yǔ)句}C語(yǔ)言的一個(gè)分程序分程序的特征是它們的嵌套結(jié)構(gòu)，使用界符標(biāo)明分程序的開(kāi)始和結(jié)束。界符保證一個(gè)分程序要么與別的分程序無(wú)關(guān)，要么是嵌在別的分程序中，這種嵌套性有時(shí)稱作“分程序結(jié)構(gòu)”當(dāng)前第41頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)C語(yǔ)言的一個(gè)分程序當(dāng)前第42頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)最近嵌套原則1、一個(gè)分程序B中的一個(gè)聲明的作用域包含在B中。2、如果某個(gè)名字x未在分程序B中聲明。那么，若B中出現(xiàn)的x的聲明的作用域是在B的包含層B’中，則應(yīng)該：(1)B’中有x的聲明；(2)B’與任何別的包含有x聲明的分程序相比，它是最近包圍B的分程序。當(dāng)前第43頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)分程序結(jié)構(gòu)的存儲(chǔ)管理分程序結(jié)構(gòu)用棧式存儲(chǔ)分配實(shí)現(xiàn)，是因?yàn)橐粋€(gè)聲明的作用域不會(huì)落在它出現(xiàn)的分程序之外，該聲明的空間可以在分程序進(jìn)入時(shí)分配。當(dāng)前第44頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)無(wú)參過(guò)程把分程序看成一個(gè)“無(wú)參過(guò)程”，只不過(guò)是在該分程序前調(diào)用，分程序之后返回，分程序在哪里定義就在哪里被調(diào)用。效率低下的原因解決效率低的辦法當(dāng)前第45頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)效率低下的原因第一分程序不存在被調(diào)用的問(wèn)題，不必要在進(jìn)入一個(gè)分程序時(shí)，將連接數(shù)據(jù)(如動(dòng)態(tài)鏈、返回地址等)和display都放進(jìn)活動(dòng)記錄中；第二，當(dāng)從內(nèi)層分程序向外轉(zhuǎn)移時(shí)可能同時(shí)要結(jié)束若干個(gè)分程序，恢復(fù)所要到達(dá)的那個(gè)分程序的數(shù)據(jù)區(qū)需要順序退出，浪費(fèi)時(shí)間，降低效率。當(dāng)前第46頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)解決效率低的辦法首先，代替原來(lái)的那個(gè)統(tǒng)一的棧頂指示器，讓每個(gè)過(guò)程和分程序都有自己的棧頂指示器TOP，它的值保存在各自的活動(dòng)記錄中。這樣上述第二個(gè)問(wèn)題即可解決；其次，不把分程序看作“無(wú)參過(guò)程”，而讓每個(gè)分程序享用包圍它的那個(gè)最小過(guò)程的display。每個(gè)分程序都隸屬于某個(gè)確定的過(guò)程，分程序的層次是相對(duì)于它所屬的那個(gè)過(guò)程進(jìn)行編號(hào)的。每個(gè)過(guò)程被當(dāng)作0層分程序，而過(guò)程體分程序(假定是一個(gè)分程序)當(dāng)作是它所管轄的第一層分程序。當(dāng)前第47頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)完整過(guò)程體每次為一個(gè)完整的過(guò)程體分配存儲(chǔ)，即把一個(gè)過(guò)程體中的所有分程序所需的存儲(chǔ)一次分配好。當(dāng)前第48頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)活動(dòng)記錄的內(nèi)容內(nèi)容：1．過(guò)程的TOP單元，指向活動(dòng)記錄的棧頂位置；2．連接數(shù)據(jù)，共4項(xiàng)：(1)老SP值；(2)返回地址；(3)全局display地址；(4)調(diào)用時(shí)的棧頂單元地址，稱作老TOP。3．參數(shù)個(gè)數(shù)和形式單元。4．display表。5．過(guò)程所管轄的各分程序的局部數(shù)據(jù)單元對(duì)每個(gè)分程序來(lái)說(shuō)，它們包括：(1)一個(gè)名為TOP的單元，當(dāng)進(jìn)入時(shí)它含現(xiàn)行棧頂?shù)刂?，以后用?lái)存放棧的新高度；(2)分程序的局部變量、數(shù)組內(nèi)情向量和臨時(shí)工作單元。示例：程序活動(dòng)記錄當(dāng)前第49頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)ALGOL的一個(gè)程序當(dāng)前第50頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)ALGOL的活動(dòng)記錄當(dāng)前第51頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)活動(dòng)記錄的情況分程序進(jìn)入時(shí)分程序退出時(shí)分程序結(jié)構(gòu)數(shù)據(jù)區(qū)變化圖當(dāng)前第52頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)分程序進(jìn)入時(shí)的活動(dòng)記錄每個(gè)分程序在進(jìn)入時(shí)，都有它自己的一個(gè)TOP單元，剛進(jìn)入時(shí)，它的TOP值是由其直接外層分程序的TOP單元的內(nèi)容所賦予的。一旦定義了TOP值后，就對(duì)該分程序的所有局部數(shù)組進(jìn)行地址分配。每分配一個(gè)數(shù)組區(qū)后，TOP的值隨即調(diào)整指向新的棧頂位置。過(guò)程看成0層分程序、它是通過(guò)調(diào)用而進(jìn)入的，它的TOP值是調(diào)用時(shí)的棧頂?shù)刂芳由纤幕顒?dòng)記錄的長(zhǎng)度L，L是在編譯時(shí)靜態(tài)計(jì)算出來(lái)的。運(yùn)行中每逢進(jìn)入分程序(除0層分程序外)，即執(zhí)行分程序的begin語(yǔ)句時(shí)，只需把直接外層分程序的TOP值抄進(jìn)自己的TOP單元中。由于分程序的數(shù)據(jù)區(qū)起點(diǎn)(分程序TOP單元所在處)可在編譯時(shí)靜態(tài)地確定，因此，這個(gè)抄送動(dòng)作只需用兩條指令就可完成。所以，進(jìn)入分程序所要做的工作是非常簡(jiǎn)單的。在進(jìn)入分程序建立TOP單元的值之后，執(zhí)行第一個(gè)執(zhí)行句之前，如果有數(shù)組說(shuō)明則應(yīng)對(duì)所定義的數(shù)組分配存儲(chǔ)空間。數(shù)組空間分配之后，TOP調(diào)整為指向新的棧頂(新分配的數(shù)組區(qū)的頂端)。當(dāng)前第53頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)分程序退出時(shí)的活動(dòng)記錄在分程序工作完畢正常退出時(shí)，即到達(dá)分程序的end語(yǔ)句時(shí)，無(wú)需進(jìn)行任何退棧的工作。換句話說(shuō)，分程序的正常出口不需要執(zhí)行任何指令。當(dāng)前第54頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)分程序結(jié)構(gòu)數(shù)據(jù)區(qū)變化圖當(dāng)前第55頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)參數(shù)傳遞傳值傳地址傳結(jié)果傳名字過(guò)程參數(shù)當(dāng)前第56頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳值傳值，即call-by-value，也稱值調(diào)用，是最簡(jiǎn)單的參數(shù)傳遞方法。即將實(shí)參計(jì)算出它的值．然后把它傳給被調(diào)過(guò)程。參數(shù)傳遞方法的不同主要基于實(shí)在參數(shù)是表達(dá)一個(gè)右值，一個(gè)左值，還是實(shí)在參數(shù)本身的文本(字)?！白蟆焙汀坝摇眮?lái)自賦值語(yǔ)句的“左”端和“右”端。左值：(l-value)指表達(dá)式代表的存儲(chǔ)。右值：(r-value)指該存儲(chǔ)位置中含有的值。傳值的具體內(nèi)容傳值的特點(diǎn)傳值的示例當(dāng)前第57頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳值的具體內(nèi)容1、形式參數(shù)當(dāng)作過(guò)程的局部變量處理，即在被調(diào)過(guò)程的活動(dòng)記錄中開(kāi)辟了形參的存儲(chǔ)空間，這些存儲(chǔ)位置即是實(shí)參或形式單元。2、調(diào)用過(guò)程計(jì)算實(shí)參的值，并將它們的右值(r-value)放在為形式單元開(kāi)辟的空間中。3、被調(diào)用過(guò)程執(zhí)行時(shí)，就像使用局部變量一樣使用這些形式單元。當(dāng)前第58頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳值的特點(diǎn)傳值或值調(diào)用的重要特點(diǎn)是對(duì)形式參數(shù)的任何運(yùn)算不影響調(diào)用過(guò)程的活動(dòng)記錄中實(shí)參的值。當(dāng)前第59頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳值的示例該程序的輸出是：a＝2，b＝l如果將第3行的關(guān)鍵字var去掉，則是以傳值方式將x和y傳遞給過(guò)程swap，第12行swap(a，b)調(diào)用過(guò)程將不會(huì)影響a和b的值，則該程序的輸出是：a＝1，b＝2。當(dāng)前第60頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳地址當(dāng)參數(shù)通過(guò)引用傳遞時(shí)，稱作傳地址，或引用調(diào)用(call-by-reference)。調(diào)用過(guò)程傳給被調(diào)過(guò)程的是指針，指向?qū)崊⒋鎯?chǔ)位置的指針。1、如實(shí)參是一個(gè)名字或是具有左值的表達(dá)式，則左值本身傳遞過(guò)去。2、如實(shí)參是一表達(dá)式，比方a+b或2，而沒(méi)有左值，則表達(dá)式先求值，并存入某一位置，然后該位置的地址傳遞過(guò)去。3、被調(diào)過(guò)程中對(duì)形式參數(shù)的任何引用和賦值都通過(guò)傳遞到被調(diào)過(guò)程的指針被處理成間接訪問(wèn)。示例

當(dāng)前第61頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳地址示例若用實(shí)參i和a[i]對(duì)過(guò)程swap進(jìn)行調(diào)用，即swap(i，a[i])，其效果如下步驟所述：1、將i和a[i]的地址(左值)拷貝到被調(diào)過(guò)程的活動(dòng)記錄中，比如說(shuō)分別對(duì)應(yīng)形參x和y的單元arg1和arg2。2、將局部變量temp設(shè)為由arg1所指單元的內(nèi)容(即令temp等于I0，其中I0是i的初值)，這一步對(duì)應(yīng)于swap定義中的第6行語(yǔ)句temp＝x。3、將arg1所指單元的內(nèi)容設(shè)為arg2所指單元的值，即i:＝a[I0]，這一步對(duì)應(yīng)于swap定義中第7行的x:＝y(tǒng)。4、將arg2所指單元的內(nèi)容設(shè)為等于temp的值，即，設(shè)a[I0]＝i，這一步對(duì)應(yīng)y:＝temp。當(dāng)前第62頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳結(jié)果傳結(jié)果(call-by-value-result)：處理的每一形參，需分配兩個(gè)形式單元，分別稱為該形參的第一形式單元和第二形式單元，其中第二形式單元被視為過(guò)程體的局部單元。實(shí)現(xiàn)這種傳遞的方法是：在進(jìn)行入過(guò)程時(shí)，將實(shí)參的地址送入相應(yīng)形參的第一形式單元，將實(shí)參之值送入第二形式單元。在退出過(guò)程時(shí)，再將第二形式單元中形參的終值再按第一形式單元中的實(shí)參地址賦給相應(yīng)的實(shí)參，所以有時(shí)又將這種參數(shù)傳遞稱為復(fù)寫存貯連接。當(dāng)前第63頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)傳名字傳名字(call-by-name)。這種數(shù)據(jù)傳遞方式是：將實(shí)在參數(shù)的名字傳給過(guò)程中相應(yīng)的形式參數(shù)，也就是，過(guò)程體中的形式參數(shù)都要用相應(yīng)的實(shí)在參數(shù)的名字進(jìn)行替換。這種名字替換的實(shí)質(zhì)是：在過(guò)程說(shuō)明的目標(biāo)程序中，在形式參數(shù)出現(xiàn)的地方都要使用相應(yīng)實(shí)在參數(shù)當(dāng)時(shí)的值或地址。當(dāng)前第64頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)過(guò)程參數(shù)一個(gè)嵌套過(guò)程(函數(shù))可以作為參數(shù)傳遞。示例：嵌套過(guò)程代碼過(guò)程參數(shù)傳遞情況當(dāng)前第65頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)嵌套過(guò)程程序代碼(1)programparam(input,ouput);(2)procedureb(fuctionh(n:integer):integer);(3)beginwriteln(h(2))end;(4)procedurec;(5)varm；integer;(6)functionf(n:integer):integer;(7)beginf:=m+nend{f};(8)beginm:=0;b(f)end{c};(9)begin(10)c(11)end當(dāng)前第66頁(yè)\共有73頁(yè)\編于星期六\9點(diǎn)過(guò)程參數(shù)傳遞情況過(guò)程c把f作為參數(shù)傳遞給b，而b通過(guò)引用形參h調(diào)用f。要注意的是：函數(shù)f有一非局部量m。但m的作用域并不包括b的過(guò)程體。b中的語(yǔ)句writeln(h(2))激活f，是