編譯原理課件

1、第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理 編譯程序在完成詞法、語法和語義分析后，在生成目標(biāo)代碼之前，需要把程序的靜態(tài)正文和實(shí)現(xiàn)這個(gè)程序的運(yùn)行時(shí)的活動(dòng)聯(lián)系起來弄清楚將來在代碼運(yùn)行時(shí)刻，源代碼中的各種變量、常量等用戶定義的量是如何存放的，如何去訪問它們。 在程序的執(zhí)行過程中，程序中數(shù)據(jù)的存取是通過與之對(duì)應(yīng)的存儲(chǔ)單元來進(jìn)行的。在程序語言中，程序使用的存儲(chǔ)單元都是由標(biāo)識(shí)符來表示的。它們對(duì)應(yīng)的內(nèi)存地址都是由編譯程序在編譯時(shí)或由其生成的目標(biāo)程序運(yùn)行時(shí)進(jìn)行分配。所以對(duì)于編譯程序來說存儲(chǔ)組織與管理是一個(gè)復(fù)雜而又十分重要的問題。1第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理 過程的活動(dòng)過程的一次執(zhí)行稱為過程的一次活動(dòng)活動(dòng)記錄過

2、程的活動(dòng)需要可執(zhí)行代碼和存放所需信息的存儲(chǔ)空間,后者稱為活動(dòng)記錄本章內(nèi)容討論一個(gè)活動(dòng)記錄中的數(shù)據(jù)安排程序執(zhí)行過程中，所有活動(dòng)記錄的組織方式 2第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理過程P一次活動(dòng)的生存期，指的是從執(zhí)行該過程體第一步操作到最后一步操作之間的操作時(shí)間，包括執(zhí)行P時(shí)調(diào)用其它過程花費(fèi)的時(shí)間。過程可以是遞歸的一個(gè)過程可對(duì)應(yīng)多個(gè)活動(dòng)3第六章 運(yùn)行時(shí)存儲(chǔ)空間的組織和管理影響存儲(chǔ)分配策略的語言特征 過程能否遞歸當(dāng)控制從過程的活動(dòng)返回時(shí)，局部變量的值是否要保留過程能否訪問非局部變量過程調(diào)用的參數(shù)傳遞方式過程能否作為參數(shù)被傳遞過程能否作為結(jié)果值傳遞存儲(chǔ)塊能否在程序控制下動(dòng)態(tài)地分配存儲(chǔ)塊是否必須顯式地釋

3、放本章在邏輯地址空間討論46.1 (過程內(nèi)部)局部存儲(chǔ)分配策略6.1.1 過程過程定義、過程調(diào)用、形式參數(shù)、實(shí)在參數(shù)、活動(dòng)的生存期Procedure f(a:int, b:bool)int c;過程定義void main()f(3,true);過程調(diào)用56.1 局部存儲(chǔ)分配策略6.1.2 名字的作用域和綁定名字的作用域一個(gè)聲明起作用的程序部分稱為該聲明的作用域。int a;Function f(int b)int c;void main()a = 0;c = 0;f(3);正確，在a的作用域內(nèi)錯(cuò)誤，超出了c的作用域66.1 局部存儲(chǔ)分配策略6.1.2 名字的作用域和綁定名字的作用域即使一個(gè)名字

4、在程序中只聲明一次，該名字在程序運(yùn)行時(shí)也可能表示不同的數(shù)據(jù)對(duì)象。int a;Function f(int b)int c;void main()a = 0;f(3);f(5);兩次調(diào)用，函數(shù)f中變量c對(duì)應(yīng)不同的數(shù)據(jù)對(duì)象保存值的存儲(chǔ)單元76.1 局部存儲(chǔ)分配策略名字到存儲(chǔ)單元的綁定環(huán)境把名字映射到左值（存儲(chǔ)單元），而狀態(tài)把左值映射到右值（值）。賦值改變狀態(tài)，但不改變環(huán)境。 如果環(huán)境將名字x映射到存儲(chǔ)單元s，我們就說x被綁定到s。名字存儲(chǔ)單元狀態(tài)值環(huán)境6.1.2 名字（變量）的作用域和綁定A = b5A4bA586.1 局部存儲(chǔ)分配策略靜態(tài)概念和動(dòng)態(tài)概念的對(duì)應(yīng)靜 態(tài) 概 念 動(dòng) 態(tài) 對(duì) 應(yīng) 過程的

5、定義 過程的活動(dòng) 名字的聲明 名字的綁定 聲明的作用域 綁定的生存期 96.1 局部存儲(chǔ)分配策略6.1.3 活動(dòng)記錄編譯之后的程序每次運(yùn)行時(shí)，從操作系統(tǒng)（OS）獲得一塊存儲(chǔ)區(qū)（內(nèi)存）。其內(nèi)容包括：編譯后的目標(biāo)代碼 (可執(zhí)行程序 .exe)數(shù)據(jù)對(duì)象 (各種靜態(tài)變量和動(dòng)態(tài)變量)用于管理過程活動(dòng)的控制棧 (活動(dòng)記錄)過程的活動(dòng)中用于存放所需信息的存儲(chǔ)空間, 稱為活動(dòng)記錄或幀106.1 局部存儲(chǔ)分配策略6.1.3 活動(dòng)記錄目標(biāo)程序每次運(yùn)行時(shí)，編譯器從操作系統(tǒng)（OS）獲得一塊存儲(chǔ)區(qū)（內(nèi)存）。其空間安排：代 碼靜 態(tài) 數(shù) 據(jù)堆棧目標(biāo)代碼（.exe）靜態(tài)變量和外部變量活動(dòng)記錄活動(dòng)記錄及動(dòng)態(tài)變量116.1 局

6、部存儲(chǔ)分配策略6.1.3 活動(dòng)記錄例子void p() void main() ; p(); .; 代 碼靜 態(tài) 數(shù) 據(jù)main的活動(dòng)記錄堆p的活動(dòng)記錄棧126.1 局部存儲(chǔ)分配策略6.1.3 活動(dòng)記錄一般的活動(dòng)記錄的布局返 回 值臨 時(shí) 數(shù) 據(jù)實(shí) 在 參 數(shù)控 制 鏈訪 問 鏈機(jī) 器 狀 態(tài)局 部 數(shù) 據(jù)本過程返回給調(diào)用過程的值調(diào)用過程傳遞給本過程的參數(shù)指向調(diào)用過程的指針用于引用存于其他活動(dòng)記錄的非局部數(shù)據(jù)用于保存本過程調(diào)用前的機(jī)器狀態(tài)本過程內(nèi)部定義的局部變量臨時(shí)變量，中間結(jié)果136.1 局部存儲(chǔ)分配策略6.1.4 局部數(shù)據(jù)的安排字節(jié)是可編址內(nèi)存的最小單位。一個(gè)過程所聲明的局部變量，按這些變

7、量聲明時(shí)出現(xiàn)的次序，在活動(dòng)記錄的局部數(shù)據(jù)區(qū)中依次分配空間。 局部數(shù)據(jù)的地址可以用相對(duì)于某個(gè)位置（本過程對(duì)應(yīng)的活動(dòng)記錄的起始位置）的偏移來表示。數(shù)據(jù)對(duì)象的存儲(chǔ)安排深受目標(biāo)機(jī)器尋址方式的影響，存在對(duì)齊問題。例如，要求整數(shù)（int，long）的相對(duì)地址可以被4整除。由于對(duì)齊而引起的無用空間稱為襯墊空白區(qū)。14例題在X86/Linux工作站上，以下兩個(gè)結(jié)構(gòu)的size分別是20和16，為什么不一樣？typedef struct _atypedef struct _bchar c1; char c1;long i; char c2;charc2; long i;double f; double f;a;

8、b;第一部分 存儲(chǔ)區(qū)（內(nèi)存）的劃分15例題解答：typedef struct _achar c1;long i;charc2; double f;a;04812c1ic2f20襯墊空白區(qū)襯墊空白區(qū)19第一部分 存儲(chǔ)區(qū)（內(nèi)存）的劃分16例題解答：typedef struct _bchar c1;char c2;longi; double f;b;0c14816ic2f襯墊空白區(qū)12第一部分 存儲(chǔ)區(qū)（內(nèi)存）的劃分176.1 局部存儲(chǔ)分配策略6.1.5 程序塊語法如聲明 語句本身含有局部變量聲明的語句，可以嵌套最接近的嵌套作用域規(guī)則程序塊B中聲明的作用域包括B如果名字x沒有在B中聲明，那么B中x的出

9、現(xiàn)是在外圍程序塊B的x聲明的作用域中，且滿足B有x的聲明B比其他任何包含x聲明的程序塊更接近被嵌套的B并列程序塊不會(huì)同時(shí)活躍并列程序塊的變量可以重疊分配 int a; .int b; a = 3; .int a BB1B2可以把程序塊看成是不帶參數(shù)和返回值的函數(shù)186.1 局部存儲(chǔ)分配策略main() / begin of B0 /int a = 0;int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / end

10、 of B1 / end of B0 /196.1 局部存儲(chǔ)分配策略main() / begin of B0 /int a = 0;int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / end of B1 / end of B0 /聲 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 206.

11、1 局部存儲(chǔ)分配策略main() / begin of B0 /int a = 0;int b = 0; / begin of B1 / int b = 1; / begin of B2 / int a = 2; / end of B2 / / begin of B3 / int b = 3; / end of B3 / end of B1 / end of B0 /聲 明 作 用 域 int a = 0; B0 B2 int b = 0; B0 B1 int b = 1; B1 B3 int a = 2;B2int b = 3; B3 a0b0b1a2, b3重疊分配存儲(chǔ)單元 216.2 全

12、局存儲(chǔ)分配策略介紹程序運(yùn)行時(shí)所需的各個(gè)活動(dòng)記錄在存儲(chǔ)空間的分配策略描述過程的目標(biāo)代碼怎樣訪問綁定到局部名字的存儲(chǔ)單元介紹三種分配策略靜態(tài)分配策略堆式分配策略棧式分配策略代 碼靜 態(tài) 數(shù) 據(jù)堆棧226.2 全局存儲(chǔ)分配策略6.2.1 運(yùn)行時(shí)內(nèi)存的劃分代 碼靜 態(tài) 數(shù) 據(jù)堆棧236.2 全局存儲(chǔ)分配策略6.2.2 靜態(tài)分配名字在程序被編譯時(shí)綁定到存儲(chǔ)單元，不需要運(yùn)行時(shí)的任何支持。綁定的生存期是程序的整個(gè)運(yùn)行時(shí)間?？刂圃俅芜M(jìn)入該過程時(shí)，局部變量的值和控制上一次離開時(shí)的一樣。每個(gè)活動(dòng)記錄的大小是固定的。過程調(diào)用時(shí)保存信息的地址在編譯時(shí)也是已知的。246.2 全局存儲(chǔ)分配策略靜態(tài)分配的應(yīng)用：Fortra

13、n語言被設(shè)計(jì)成允許靜態(tài)存儲(chǔ)分配C語言程序的外部變量和程序中出現(xiàn)的常量都可以靜態(tài)分配。聲明在函數(shù)外面外部變量聲明在函數(shù)里面靜態(tài)局部變量常量25 像FORTRAN這樣的語言，其程序是段結(jié)構(gòu)的，即由主程序段和若干子程序段組成。 各程序段中定義的名字一般是彼此獨(dú)立的，也即各段的數(shù)據(jù)對(duì)象名的作用域在各段中，同一個(gè)名字在不同的程序段表示不同的存儲(chǔ)單元，不會(huì)在不同段間互相引用、賦值。 另外它的每個(gè)數(shù)據(jù)名所需的存儲(chǔ)空間大小都是常量（即不許含可變體積的數(shù)據(jù)，如可變數(shù)組），且所有數(shù)據(jù)名的性質(zhì)是完全確定的。 這樣，整個(gè)程序所需數(shù)據(jù)空間的總量在編譯時(shí)完全確定，換句話說，一旦存儲(chǔ)空間的某個(gè)位置分配給了某個(gè)數(shù)據(jù)名（關(guān)聯(lián)起

14、來）之后，在目標(biāo)程序的整個(gè)運(yùn)行過程中，此位置（地址）就屬于該數(shù)據(jù)名了。 266.2 全局存儲(chǔ)分配策略靜態(tài)分配給語言帶來限制遞歸過程不被允許數(shù)據(jù)對(duì)象的長度和它在內(nèi)存中位置，必須是在編譯時(shí)可以知道的數(shù)據(jù)結(jié)構(gòu)不能動(dòng)態(tài)建立276.2 全局存儲(chǔ)分配策略6.2.3 棧式分配棧式分配主要用于管理過程的活動(dòng)記錄。局部變量的生存期是過程活動(dòng)的時(shí)間?？刂七M(jìn)入該過程時(shí)，局部變量綁定到存儲(chǔ)單元，過程活動(dòng)結(jié)束后，局部變量的空間釋放。286.2 全局存儲(chǔ)分配策略6.2.3 棧式分配活動(dòng)樹:用樹來描繪控制進(jìn)入和離開活動(dòng)的方式srq(2,3)q(2,1)q(3,3)p(2,3) 活動(dòng)樹的特點(diǎn)每個(gè)結(jié)點(diǎn)代表某過程的一個(gè)活動(dòng)根結(jié)點(diǎn)

15、代表主程序的活動(dòng)結(jié)點(diǎn)a是結(jié)點(diǎn)b的父結(jié)點(diǎn)，當(dāng)且僅當(dāng)控制流從a的活動(dòng)進(jìn)入b的活動(dòng)結(jié)點(diǎn)a 處于結(jié)點(diǎn)b 的左邊，當(dāng)且僅當(dāng)a的生存期先于b的生存期活動(dòng)執(zhí)行的順序？深度優(yōu)先搜索296.2 全局存儲(chǔ)分配策略當(dāng)前活躍著的過程活動(dòng)可以保存在一個(gè)棧中控制棧的內(nèi)容：s, q (2, 3), p(2, 3) srq(2,3)q(2,1)q(3,3)p(2,3)306.2 全局存儲(chǔ)分配策略運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） sa : arrays316.2 全局存儲(chǔ)分配策略運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） si: integerra :

16、arraysr326.2 全局存儲(chǔ)分配策略運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） sk: integerq (2, 3)a : arraysq(2,3)r336.2 全局存儲(chǔ)分配策略運(yùn)行棧：把控制棧中的信息拓廣到包括過程活動(dòng)所需的所有局部信息（即活動(dòng)記錄） sk: integerq (2, 3)a : arrayp(2, 3)k: integersq(2,3)rp(2,3)34/48346.2 全局存儲(chǔ)分配策略運(yùn)行棧的管理:過程調(diào)用和過程返回都需要執(zhí)行一些代碼來管理活動(dòng)記錄棧，保存或恢復(fù)機(jī)器狀態(tài)等過程調(diào)用序列過程調(diào)用時(shí)執(zhí)行的分配活動(dòng)記錄，把信息填入它的域中的

17、代碼過程返回序列過程返回時(shí)執(zhí)行的恢復(fù)機(jī)器狀態(tài)，釋放活動(dòng)記錄，使調(diào)用過程能夠繼續(xù)執(zhí)行的代碼調(diào)用序列和返回序列都分常常分成兩部分，分處于調(diào)用過程和被調(diào)用過程中356.2 全局存儲(chǔ)分配策略即使是同一種語言，過程調(diào)用序列、返回序列和活動(dòng)記錄中各域的排放次序，也會(huì)因?qū)崿F(xiàn)而異設(shè)計(jì)這些序列和活動(dòng)記錄的一些原則是把參數(shù)域和可能有的返回值域放在緊靠調(diào)用者活動(dòng)記錄的地方以活動(dòng)記錄中間的某個(gè)位置作為基地址長度能較早確定的域放在活動(dòng)記錄的中間一般把臨時(shí)數(shù)據(jù)域放在局部數(shù)據(jù)域的后面用同樣的代碼來執(zhí)行各個(gè)活動(dòng)的保存和恢復(fù)366.2 全局存儲(chǔ)分配策略調(diào)用者和被調(diào)用者之間的任務(wù)劃分被調(diào)用者的責(zé)任調(diào)用者的責(zé)任調(diào)用者的活動(dòng)記錄被調(diào)

18、用者的活動(dòng)記錄過程p調(diào)用過程q局部數(shù)據(jù)臨時(shí)數(shù)據(jù)控制鏈訪問鏈和機(jī)器狀態(tài)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù) 控制鏈訪問鏈和機(jī)器狀態(tài)top_sp base_sp 棧qP376.2 全局存儲(chǔ)分配策略過程p調(diào)用過程q的調(diào)用序列p在棧上留出放返回值的空間，并計(jì)算實(shí)參，依次放入棧頂，同時(shí)改變top_sp的值。p把返回地址存入q的活動(dòng)記錄中，建立q的訪問鏈q保存寄存器的值和其它機(jī)器狀態(tài)信息，將base_sp的值壓棧,并將當(dāng)前的top_sp作為自己的base_sp 。q根據(jù)局部數(shù)據(jù)域和臨時(shí)數(shù)據(jù)域的大小減小top_sp的值，初始化它的局部數(shù)據(jù)，并開始執(zhí)行過程體。局部數(shù)據(jù)臨時(shí)數(shù)據(jù)控制鏈訪問鏈和機(jī)器狀態(tài)返回值和

19、參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù) 控制鏈訪問鏈和機(jī)器狀態(tài)top_sp base_sp 棧qP386.2 全局存儲(chǔ)分配策略過程p調(diào)用過程q的返回序列q把返回值置入鄰近p的活動(dòng)記錄的地方q增加top_sp的值 q恢復(fù)寄存器（包括base_sp）和機(jī)器狀態(tài)，返回pp根據(jù)參數(shù)個(gè)數(shù)與類型和返回值類型調(diào)整top_sp，然后取出返回值39/48局部數(shù)據(jù)臨時(shí)數(shù)據(jù)控制鏈訪問鏈和機(jī)器狀態(tài)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù) 控制鏈訪問鏈和機(jī)器狀態(tài)top_sp base_sp 棧qP396.2 全局存儲(chǔ)分配策略過程的參數(shù)個(gè)數(shù)可變的情況函數(shù)返回值改成用寄存器傳遞編譯器產(chǎn)生將這些參數(shù)逆序進(jìn)棧的代碼被調(diào)用函數(shù)能準(zhǔn)確地知道第一個(gè)參數(shù)的位置被調(diào)用函數(shù)根據(jù)第一個(gè)參數(shù)到棧中取第二、第三個(gè)參數(shù)等等局部數(shù)據(jù)臨時(shí)數(shù)據(jù)控制鏈訪問鏈和機(jī)器狀態(tài)返回值和參數(shù)局部數(shù)據(jù)臨時(shí)數(shù)據(jù)返回值和參數(shù) 控制鏈訪問鏈和機(jī)器狀態(tài)top_sp base_sp 棧qP406.2 全局存儲(chǔ)分配策略活動(dòng)記錄的長度在編譯時(shí)不能確定的情況局部數(shù)組的大小要等到過程激活時(shí)才能確定在活動(dòng)記錄中為這樣的數(shù)組分別存放數(shù)組指針的單元運(yùn)行時(shí)，這些指針指向分配在棧頂?shù)拇鎯?chǔ)空間訪問動(dòng)態(tài)分配的數(shù)組q的數(shù)組q的活動(dòng)記錄p的數(shù)組