1、第八章哈爾濱工業(yè)大學軟件學院運行時存儲組織，重點介紹了符號表的內(nèi)容和組織、過程調(diào)用的實現(xiàn)以及靜態(tài)存儲分配和動態(tài)存儲分配的基本方法。難點：參數(shù)傳遞、過程描述語句的代碼結(jié)構(gòu)、過程調(diào)用語句的代碼結(jié)構(gòu)、過程調(diào)用語句的語法指導定義、堆棧存儲分配。2020/7/30，2，第8章，運行時的存儲組織，8.1與存儲組織相關(guān)的源語言概念和功能，8.2存儲組織，8.3靜態(tài)存儲分配，8.4堆棧存儲分配，8.5對堆棧中非本地數(shù)據(jù)的訪問，8.6堆管理，8.7本章概述，2020/7/30，3，8.1與存儲組織相關(guān)的源語言概念和功能，編譯器必須準確實現(xiàn)源程序中包含的各種抽象概念，如名稱、范圍、數(shù)據(jù)類型、運算符、過程、參數(shù)這些

2、概念反映了源語言的一些特征，它們的支持經(jīng)常影響運行時的存儲組織和分配策略。給定一個源程序，編譯器必須根據(jù)源語言的特性(規(guī)則)來決定源程序中的許多問題，包括何時以及如何為名字分配內(nèi)存地址。靜態(tài)策略：可以在編譯時決定的策略；動態(tài)策略：在程序執(zhí)行之前無法決定的策略；2020/7/30，4，8.1.1名稱及其綁定，以及“名稱”、“變量”和“標識符”之間的區(qū)別和聯(lián)系。名稱和變量表示編譯時的名稱以及運行時由名稱表示的內(nèi)存位置。標識符是指示數(shù)據(jù)對象、過程、類或?qū)ο蟮臈l目的字符串。所有標識符都是名稱，但不是所有的名稱都是標識符。名字也可以是表達。例如，名稱x.y可以表示由x表示的結(jié)構(gòu)的域y。同一個標識符可以聲

3、明多次，但是每次聲明都會引入一個新的變量。即使每個標識符只聲明一次，遞歸進程本地的標識符將在不同的運行時指向不同的內(nèi)存位置。2020/7/30，5，名稱綁定，從名稱到值的兩步映射環(huán)境將名稱映射到左值，而狀態(tài)將左值映射到右值。分配改變狀態(tài)，但不改變環(huán)境。如果環(huán)境將名字X映射到存儲單元S，我們說X綁定到由S聲明的范圍，名字，存儲位置(變量)，狀態(tài)，值，環(huán)境，2020/7/30，6，8.1.2，并且由X聲明的范圍是程序中的這樣一個區(qū)域，其中X的所有引用都指向X的這個聲明。對于某個編程語言，如果一個聲明的范圍只能通過檢查其程序來確定，則說該語言使用靜態(tài)范圍；否則，據(jù)說語言使用動態(tài)范圍。C、Java和C

4、#還通過使用公共、私有和受保護等關(guān)鍵字來提供對范圍的顯式控制。聲明的范圍通過符號表進行管理，詳見第8.4節(jié)。2020/7/30，7，1。靜態(tài)范圍。在具有塊結(jié)構(gòu)的語言中，變量聲明的靜態(tài)范圍規(guī)則如下：如果名字X的聲明D屬于塊B，那么D的范圍就是B的所有語句，除了塊B滿足以下條件：B嵌套在B中(它可以嵌套在任何深度)，B有一個新的同名聲明X.假設(shè)B1、B2、Bk是圍繞X的所有參考塊，Bk-1是Bk的直接外塊，Bk-2是Bk-1的直接外塊，依此類推。找到最大的一個屬于畢的“我”，那么這個“我”指的就是畢的這個說法。換句話說，對X的這種引用在畢的這種聲明的范圍之內(nèi)。2020/7/30，8，1。靜態(tài)范圍，

5、表8.1圖8.10所示程序中聲明的范圍，2020/7/30，9，2。顯式訪問控制、類和結(jié)構(gòu)為其成員引入了新的范圍。如果P是具有域(成員)X的類的對象，那么P.X。類似于塊結(jié)構(gòu)，類D中成員X的聲明范圍將擴展到D的任何子類D，除非D具有與X同名的局部聲明，2020/7/30，10，2。顯式訪問控制。通過使用諸如公共、私有和受保護等關(guān)鍵字，面向?qū)ο蟮腃語言或Java類提供了對超類中成員名稱的顯式訪問控制。這些關(guān)鍵字通過限制訪問來支持封裝。因此，私有名稱的范圍只包含與類及其友元相關(guān)聯(lián)的方法聲明和定義，保護名稱只對其子類可訪問，公共名稱也可從類外訪問。2020/7/30，11，3。動態(tài)范圍、相對于時間的

6、動態(tài)范圍規(guī)則和相對于空間靜態(tài)范圍規(guī)則的靜態(tài)范圍規(guī)則要求我們找出引用所指向的聲明，前提是聲明位于引用周圍的“空間最近”單元(程序塊)中。動態(tài)范圍還要求我們找出引用所指向的聲明，但前提是聲明位于引用周圍的“最近時間”單位(流程活動)。2020/7/30，12，3。動態(tài)范圍，“動態(tài)范圍”通常指以下策略名稱X的引用，該引用指向最近調(diào)用的帶有X聲明的進程中的X聲明。例如，當流程作為參數(shù)傳遞時，2020/7/30，13，8.1.3流程及其活動(將“流程、函數(shù)和方法”稱為“流程”)是一個聲明，其最簡單的形式是將標識符與語句相關(guān)聯(lián)。這個標識符是過程名，這個語句是過程體。當一個過程名出現(xiàn)在可執(zhí)行語句中時，相應的

7、過程將在該點被調(diào)用。過程調(diào)用是執(zhí)行被調(diào)用過程的過程體。請注意，過程調(diào)用也可以出現(xiàn)在表達式中。2020/7/30，14，8.1.3流程及其活動。過程定義中出現(xiàn)的一些標識符具有特殊的含義，它們被稱為過程的形式參數(shù)，簡稱為形式參數(shù)。調(diào)用過程時，表達式作為實參數(shù)(或?qū)崊?傳遞給被調(diào)用的過程，以替換過程體中出現(xiàn)的相應形式參數(shù)。第8.1.4節(jié)將討論實際參數(shù)和形式參數(shù)的組合方法。流程主體的每次執(zhí)行都被稱為流程的一個活動。進程p的活動的生命周期是從進程體執(zhí)行的第一步到最后一步，包括執(zhí)行由p調(diào)用的進程的時間，以及由這樣的進程調(diào)用其他進程所花費的時間，等等。2020/7/30，15，8.1.3流程及其活動。如果A

8、和B是進程的活動，它們的生命周期不是重疊就是嵌套。也就是說，如果b在a結(jié)束之前開始，那么b必須在a結(jié)束之前結(jié)束。如果同一個流程的新活動可以在前一個活動結(jié)束之前開始，則稱該流程是遞歸的。遞歸過程p也可以間接調(diào)用自己。如果一個過程是遞歸的，它的幾個活動可能在某個時刻同時活動，所以這些活動的存儲空間必須合理地組織。2020/7/30，16，8.1.4。當一個過程調(diào)用另一個過程時，它們之間交換信息的方法通常通過被調(diào)用過程的非本地名稱和參數(shù)來實現(xiàn)。逐值逐地址逐值逐名稱傳遞。主要區(qū)別在于參數(shù)是代表左值還是右值，還是文本本身。2020/7/30，17，1。傳遞值、計算參數(shù)以及將其正確值傳遞給被調(diào)用過程的方式

9、可以實現(xiàn)如下：被調(diào)用過程為每個形式參數(shù)打開一個稱為形式單元的存儲單元，以存儲相應參數(shù)的值。調(diào)用過程計算實際參數(shù)，并將正確的值放入相應的形式單元。，由調(diào)用者和被調(diào)用者直接使用，a，實際參數(shù)a，形式參數(shù)x，a的值，單向值傳遞，2020/7/30，18，2。地址傳遞，調(diào)用進程將實際參數(shù)的地址傳遞給被調(diào)用進程。地址傳遞的方式可以實現(xiàn)如下：如果實際參數(shù)是帶有左值的名稱或表達式，那么如果實際參數(shù)是b，則左值本身被傳遞。然后調(diào)用進程首先計算實際參數(shù)的值并將其存儲在新的存儲單元中，然后將該新單元的地址發(fā)送給被調(diào)用進程、用于地址訪問的調(diào)用方和被調(diào)用方，a、實際參數(shù)a、形式參數(shù)x、a、2020/7/30、19、3

10、的地址。在被調(diào)用的過程中，參數(shù)的正確值被用作傳遞值的方式。當控制返回到調(diào)用過程時，根據(jù)傳遞的參數(shù)的左值，將參數(shù)的當前值復制到參數(shù)存儲單元。調(diào)用者，被調(diào)用者，a，實際參數(shù)a，形式參數(shù)x，a的值，值/地址，a的地址，2020/7/30，20，4。傳遞名稱，并用實際參數(shù)表達式對形式參數(shù)進行文字替換。名稱傳遞的方法可以實現(xiàn)如下：在調(diào)用過程中，設(shè)置一個形實轉(zhuǎn)換子程序來計算參數(shù)的左值或右值。被調(diào)用的進程為每個參數(shù)打開一個存儲單元，用于存儲參數(shù)的轉(zhuǎn)換子例程的入口地址。當傳輸?shù)倪M程被執(zhí)行時，每當一個參數(shù)被賦值或取用時，對應于該參數(shù)的形式-實轉(zhuǎn)換子程序被調(diào)用以獲得該參數(shù)的相應地址或值。注意，轉(zhuǎn)換子程序的運行環(huán)境

11、是調(diào)用程序。形式到現(xiàn)實的轉(zhuǎn)換子程序也稱為重命名子程序thunk。2020/7/30，21，例如，程序交換(var x，y:整數(shù))；var temp:整數(shù)；開始呼叫交換(I，ai)溫度：=x；溫度：=i。x :=y；i :=ai:=溫度：=溫度結(jié)束，2020/7/30，22，子程序P(X，Y，Z)；Y :=Y 1；Z:=Z X，傳輸值：2，傳輸?shù)刂罚篨=T=5，Y=Z=A=2 A :=A 1=21 A :=A T=358，傳輸名稱A :=A 1=3 A 3360=A AB=3339 b :=3；(甲乙丙丁)；打印A，臨時單元： T:A B=5，2020/7/30，23，編譯器組織存儲空間時必須考

12、慮的問題，該過程可以遞歸嗎？當控制從流程活動中返回時，您是否希望保留局部變量的值？一個過程可以訪問非局部變量嗎？如何傳遞過程調(diào)用的參數(shù)？過程可以作為參數(shù)傳遞嗎？過程可以作為結(jié)果值傳遞嗎？內(nèi)存塊可以在程序控制下動態(tài)分配嗎？內(nèi)存塊必須被顯式釋放嗎？2020/7/30，24，8.2存儲組織，8.2.1運行時內(nèi)存分區(qū)8.2.2活動記錄8.2.3本地數(shù)據(jù)組織8.2.4全局存儲分配策略，2020/7/30，25，7.2.1運行時內(nèi)存分區(qū)和目標流程的每個活動所需的信息由一個連續(xù)的存儲區(qū)域管理，該區(qū)域稱為活動記錄。假設(shè)語言特性：允許過程的遞歸調(diào)用，允許過程的變量數(shù)組，并且允許/不允許過程定義的嵌套?；顒佑涗洸?/p>

13、用堆棧式存儲分配機制：在運行時，每次進入一個進程，相應的活動記錄就被推到堆棧的頂部?；顒佑涗浲ǔ０B接數(shù)據(jù)、正式單元、局部變量、局部數(shù)組的內(nèi)部向量、臨時工作單元等等。8.2.2活動記錄，2020年7月30日，對任何局部變量X的引用可以表示為索引訪問：DXSP DX3360變量X相對于活動記錄起始點的地址，該地址可以在編譯時確定。參數(shù)號，返回地址，形式單元，臨時變量，數(shù)組上下文向量，簡單變量，SP 0，1，2，舊SP，TOP，每個進程的活動記錄內(nèi)容不是嵌套語言(如C)，2020/7/30，28，連接數(shù)據(jù)返回地址動態(tài)鏈：調(diào)用進程前指向最新活動記錄地址的指針。靜態(tài)鏈：指向靜態(tài)直接外層中最新活動記錄

14、地址的指針，用于訪問非本地數(shù)據(jù)。，靜態(tài)鏈，動態(tài)鏈，形式單元，臨時變量，數(shù)組上下文向量，局部變量，SP0，1，2，返回地址，TOP，活動記錄內(nèi)容每個進程的嵌套語言(如Pascal)，2020年7月30日，29，形式單元：對應實參數(shù)的地址或值。局部數(shù)據(jù)區(qū)：局部變量、內(nèi)部信息向量和臨時工作單元(如存儲表達式的評估結(jié)果)。靜態(tài)鏈，動態(tài)鏈，形式單元，臨時變量，數(shù)組內(nèi)部向量，局部變量，SP 0，1，2，返回地址，TOP，每個進程的活動記錄內(nèi)容，組織局部數(shù)據(jù)2020年7月30日，8.2.3，字節(jié)是可尋址內(nèi)存的最小單元。變量所需的存儲空間可以根據(jù)其類型靜態(tài)確定。由進程聲明的局部變量在局部數(shù)據(jù)字段中按照聲明時出

15、現(xiàn)的順序分配空間。本地數(shù)據(jù)的地址可以用相對于某個位置的地址來表示。數(shù)據(jù)對象的存儲安排也有對齊的問題。整數(shù)必須放在內(nèi)存中的特定位置，例如可被2、4和8整除的地址，以及2020/7/30、31和8.2.3中的本地數(shù)據(jù)組織。在SPARC/Solaris工作站上，以下兩種結(jié)構(gòu)的大小分別為24和16。它們?yōu)槭裁床煌?？typedef struct _ atypedef struct _ b char C1；char c1長I；char c2charc2長I；雙倍f。雙倍f。a .b .2020/7/30，32，8.2.3本地數(shù)據(jù)的組織。在SPARC/Solaris工作站上，以下兩種結(jié)構(gòu)的大小分別為24和1

16、6。它們?yōu)槭裁床煌?？typedef struct _ atypedef struct _ b char C1；0 char c10長I；4 char c21 charc28長I；4雙f；16雙f；8a；b .2020/7/30，33，8.2.3本地數(shù)據(jù)的組織，X86/Linux機器上的結(jié)果不同于SPARC/Solaris工作站，它們是20和16。typedef struct _ atypedef struct _ b char C1；0 char c10長I；4 char c21 charc28長I；4雙f；12雙f；8a；b .2020/7/30，34，靜態(tài)存儲分配策略(FORTRAN)如果可以在編譯時確定數(shù)據(jù)空間的大小，則可以采用靜態(tài)分配方法：在編譯時運行時確定每個數(shù)據(jù)項在存儲空間中的位置。動態(tài)存儲分配策略(PASCAL)如果運行時的數(shù)據(jù)空間大小不能在編譯時確定，則必須采用動態(tài)分配方法。允許遞歸過程和動態(tài)應用以及內(nèi)存釋放。堆棧動態(tài)存儲分配堆棧動態(tài)存儲分配，8.2.4全局存儲分配策略，以及2020/7/30、35和8.3靜態(tài)存儲分配策略。如果您可以確定程序運行時所需的存儲空間大小，那么您可以在目標程序運行時安排其所有數(shù)據(jù)空間