編譯原理-課件chapter9run

1、2022/8/231Chapter9 Run-Time Environments概 述存儲分配策略 （Storage-allocation strategies）訪問非局部名字 （Access to nonlocal names）參數(shù)傳遞 （Parameter passing）2022/8/2329.1 概述在生成目標代碼之前，必須了解目標代碼執(zhí)行時的環(huán)境1、空間環(huán)境目標代碼的運行都是在操作系統(tǒng)分配的一塊存儲區(qū)內進行的這塊存儲區(qū)必須容納目標代碼和目標代碼運行時的數(shù)據空間（目標代碼中指令能訪問的空間）2022/8/2339.1 概述編譯程序分配目標程序運行時的數(shù)據空間的基本依據是設計程序語言時對

2、程序運行中存儲空間的使用和管理辦法的規(guī)定代碼生成器在生成目標代碼時必須要體現(xiàn)該程序語言在設計時分配數(shù)據空間的規(guī)定2022/8/2349.1 概述2、寄存器環(huán)境寄存器是目標機器中的寶貴資源如何分配寄存器提高程序運行的效率是代碼生成器主要要解決的問題，（詳細內容見下一講）* 數(shù)據空間分配和寄存器分配最后都體現(xiàn)在生成的目標代碼中2022/8/2359.1 概述幾種典型程序設計語言的特點不同的語言有不同的分配數(shù)據空間的規(guī)定，有不同的組織運行時刻存儲空間的方法2022/8/2369.1 概述幾種典型程序設計語言的特點與差異：CPASCALALGOLFORTRAN過程遞歸調用過程嵌套定義動態(tài)數(shù)組動態(tài)內存申

3、請指針檢查 2022/8/2379.1 概述名字的聯(lián)編（Bindings of Names）名字的左值 (l-value) 內存地址，存儲名字的瞬時值名字的右值 (r-value) 名字的瞬時值名字的聯(lián)編 將一個內存地址與一個名字聯(lián)系起來在程序的一次運行中，一個名字右值（瞬時值）可能會經常改變，一個名字也可能被聯(lián)編到多個地址（如遞歸調用中）2022/8/2389.1 概述運行時刻內存的典型劃分操作系統(tǒng)收到運行目標程序的指令，分配一塊連續(xù)的內存空間使目標程序在其上運行P397 Fig7.7這只是一個典型的劃分，具體語言不同，該劃分也不同棧（Stack）：支持過程的遞歸調用堆（Heap）：支持動態(tài)

4、內存申請2022/8/2399.1 概述活動記錄（Activation Records）是一段連續(xù)的存儲區(qū)，用以存放過程的一次執(zhí)行所需要的信息，如局部數(shù)據活動記錄的結構 P398 Fig7.8參數(shù)域、狀態(tài)域、數(shù)據域TOP 指向棧頂，TOP-SP 指向局部數(shù)據區(qū)的開始位置 * 這只是一個一般的結構，具體語言不同，活動記錄的結構和內容也有差異2022/8/23109.1 概述過程的活動（Activation）過程的一次完整執(zhí)行（第一條語句到最后一條語句），稱為過程的一次活動過程在執(zhí)行中稱它為活著的如果允許遞歸調用，程序的一次執(zhí)行可能有同一個過程的多個實例是活著的* 本章主要討論不同語言的目標程序在

5、運行時的存儲分配策略及名字與其左值和右值的關系2022/8/23119.2 存儲分配策略靜態(tài)存儲分配（Static allocation）編譯時確定所需的全部數(shù)據空間的大小編譯時安排好每個名字的存儲位置（相對地址）采用靜態(tài)存儲分配的典型語言是 FORTRAN2022/8/23129.2 存儲分配策略FORTRAN 語言程序是段結構的，主程序段 + 若干子程序（函數(shù)）段沒有動態(tài)數(shù)據類型，每個名字所需空間是確定的沒有遞歸調用，無需棧區(qū)沒有動態(tài)數(shù)據結構（如鏈表），沒有動態(tài)內存申請，無需堆區(qū)2022/8/23139.2 存儲分配策略因此，編譯時可確定數(shù)據區(qū)大小，為每個名字分配好地址FORTRAN 程序

6、運行時內存劃分為目標代碼區(qū)和靜態(tài)數(shù)據區(qū)，沒有棧區(qū)和堆區(qū)程序例子：P 402 example 7.4Fig.7.10 Fig.7.11 Fig.7.122022/8/23149.2 存儲分配策略程序設計語言若允許遞歸調用、可變數(shù)組、可變數(shù)據結構：編譯時無法確定運行時需要的存儲空間大小動態(tài)存儲分配包括：棧式分配（Stack allocation）和堆式分配（Heap allocation）只能在運行時動態(tài)地確定，采用動態(tài)存儲分配2022/8/23159.2 存儲分配策略棧式存儲分配的思想：在運行空間中劃分一塊存儲空間作為棧區(qū)程序運行時每當調用一個過程，就將該過程的活動記錄壓入棧中，過程執(zhí)行完畢將它

7、的活動記錄從棧中彈出例子：P405 Fig.7.132022/8/23169.2 存儲分配策略棧式存儲分配的實現(xiàn)反映在目標代碼生成器的構造策略中，最終體現(xiàn)在生成的目標代碼中調用序列(Call Sequence)目標代碼中的一個指令序列，完成調用一個過程的一系列操作，包括為被調用過程分配一個活動記錄，并在相應的域中填入信息2022/8/23179.2 存儲分配策略返回序列(Return Sequence)目標代碼中的一個指令序列，完成從一個被調用過程返回到它的調用過程的一系列操作，包括釋放被調用過程的活動記錄，并復制出返回值具體內容：P407 Fig.7.142022/8/23189.2 存儲分

8、配策略有些程序設計語言允許用戶自由申請內存空間，如 C 的 malloc 和 free，PASCAL 的 new 和 dispose何時申請何時釋放由用戶決定有些程序設計語言在進行數(shù)據空間分配時不服從棧式的存儲分配原則（即“先申請后釋放、后申請先釋放”）2022/8/23199.2 存儲分配策略這時采用堆式存儲分配方案運行空間劃分一塊堆區(qū)用戶（顯式）或目標代碼需要時從這堆中借用一塊，不用時退還* 這是一種完全動態(tài)的存儲分配方案2022/8/23209.3 訪問非局部名字非局部名字相對于引用點所在的過程或分程序來說的程序執(zhí)行時引用的在當前過程（分程序）之外定義的變量稱為非局部名字* 本節(jié)主要討論

9、棧式存儲分配中如何訪問非局部名字2022/8/23219.3 訪問非局部名字最近嵌套的作用域規(guī)則 （most closely nested rule）P 412 這是大多數(shù)程序設計語言采用的作用域規(guī)則例子：P416 Fig.7.22（過程）例子：P413 Fig.7.18（塊或分程序）2022/8/23229.3 訪問非局部名字分程序（塊）結構 ALGOL 和 C分程序（塊）含有局部數(shù)據說明的語句序列有定界符號，允許嵌套例子：P413 Fig.7.182022/8/23239.3 訪問非局部名字過程（活動記錄）采用棧式存儲分配，分程序中的局部數(shù)據在活動記錄的局部數(shù)據區(qū)內也采用棧式分配并列的分程

10、序中的名字可分配同一個地址，因為它們所屬的分程序不會在同一時刻存活訪問同一過程中的局部名字可以從棧頂?shù)綏５走M行定位（同一活動記錄中）Fig.7.19* 訪問其它過程中的局部名字見下面的討論2022/8/23249.3 訪問非局部名字無過程嵌套定義 C程序中引用的名字或者在當前的過程中被定義，或者在所有過程之外被定義在所有過程之外被定義的變量，稱之為全局變量，被存放在靜態(tài)數(shù)據區(qū)，地址在編譯時刻確定（放符號表中）2022/8/23259.3 訪問非局部名字過程中的局部名字聯(lián)編到過程的活動記錄的局部數(shù)據區(qū)中訪問非局部名字可根據符號表中該變量的地址直接到全局靜態(tài)數(shù)據區(qū)中查找2022/8/23269.3

11、 訪問非局部名字有過程嵌套定義 PASCALPASCAL語言的一個例子 P416過程和函數(shù)的嵌套深度（nesting depth）訪問非局部名字的方法有兩種，一種是通過存取鏈，一種是通過 DISPLAY 表主程序為 1 2022/8/23279.3 訪問非局部名字存取鏈（access links）活動記錄中的一個區(qū)，是一個指針若過程 P 直接嵌入在過程 Q 中，則 P 的活動記錄中的存取鏈指向 Q 的最近的活動記錄中的存取鏈2022/8/23289.3 訪問非局部名字如何建立存取鏈？參見 P417 Fig. 7.23（a）（b）（c）（d）區(qū)分兩種情況： P4181、Np = Nx NpNx+

12、1 2022/8/23299.3 訪問非局部名字如何利用存取鏈訪問非局部名字？根據當前過程的嵌套深度和非局部名字所在過程的嵌套深度，可以計算出需順著存取鏈前進的步數(shù)，從而對非局部名字進行訪問 NpNa2022/8/23309.3 訪問非局部名字DISPLAY表是一個指向活動記錄的指針數(shù)組運行時刻要訪問的嵌套深度為 i 的非局部名字就在 d i 所指的活動記錄中這種方法只要一步就可到達要訪問的非局部名字的活動記錄，比存取鏈方法高效2022/8/23319.3 訪問非局部名字如何建立與維護 DISPLAY 表？DISPLAY 表的大小由程序中嵌套深度最大的過程決定參見 P421 Fig.7.26

13、（a）（b）（c）（d）2022/8/23329.3 訪問非局部名字當建立嵌套深度為 i 的過程的活動記錄時，首先在新的活動記錄中保存 d i 的值，然后置 d i 指向新的活動記錄注意考慮調用和返回兩種情況當從過程中返回時，從活動記錄中恢復老的 d i 的值2022/8/23339.4 參數(shù)傳遞傳值調用（Call-by-Value）把實在參數(shù)的右值傳遞給形式參數(shù)調用序列計算實在參數(shù)的值，并將它復制到被調用過程活動記錄的參數(shù)域中這種參數(shù)傳遞方法對調用過程的活動記錄沒有影響2022/8/23349.4 參數(shù)傳遞引用調用（Call-by-Reference）把實在參數(shù)的左值（地址）傳遞給形式參數(shù)調用序列將實在參數(shù)的左值（地址）復制到被調用過程活動記錄的參數(shù)域中被調用過程對形式參數(shù)的引用其實是對實在參數(shù)的地址（在被調用過程的活動記錄中）進行引用2022/8/23359.4 參數(shù)傳遞復制恢復（Copy-Restore）傳遞參數(shù)同傳值調用在從被調用過程返回前，