編譯原理課程設(shè)計之第七章 運行時環(huán)境

1、mcy1w課程內(nèi)容課程內(nèi)容第一章第一章 概論概論第二章第二章 詞法分析詞法分析第三章第三章上下文無關(guān)文法及分析上下文無關(guān)文法及分析第四章第四章自上而下的語法分析自上而下的語法分析第五章第五章自下而上的語法分析自下而上的語法分析第六章第六章語義分析語義分析第七章第七章運行時環(huán)境運行時環(huán)境第八章第八章代碼生成代碼生成mcy2第第7 7章章 運行時環(huán)境運行時環(huán)境( (存儲空間存儲空間) )l當(dāng)源程序的目標(biāo)代碼被運行時，在內(nèi)存中不當(dāng)源程序的目標(biāo)代碼被運行時，在內(nèi)存中不僅有目標(biāo)代碼，而且還要保存各種信息，如僅有目標(biāo)代碼，而且還要保存各種信息，如必須為源程序中所出現(xiàn)的一些量（常量、變必須為源程序中所出現(xiàn)的

2、一些量（常量、變量及某些數(shù)組等）分配運行時的存儲空間。量及某些數(shù)組等）分配運行時的存儲空間。即編譯器要從操作系統(tǒng)得到一塊存儲區(qū)，用即編譯器要從操作系統(tǒng)得到一塊存儲區(qū)，用于被編譯過的目標(biāo)程序的運行。于被編譯過的目標(biāo)程序的運行。mcy3w存儲分配是在運行階段進行的，但存儲分配是在運行階段進行的，但編譯程序編譯程序在編譯階段要為其設(shè)計好存儲組織形式，并在編譯階段要為其設(shè)計好存儲組織形式，并將這種組織形式通過生成的目標(biāo)代碼體現(xiàn)出將這種組織形式通過生成的目標(biāo)代碼體現(xiàn)出來。來。( (舉例說明：舉例說明：函數(shù)調(diào)用分析函數(shù)調(diào)用分析. .txttxt) )w目標(biāo)代碼運行時，目標(biāo)代碼運行時，存儲空間的組織存儲空間

3、的組織稱為目標(biāo)稱為目標(biāo)代碼的代碼的運行時環(huán)境運行時環(huán)境。mcy4w運行時環(huán)境有三個類型：完全靜態(tài)環(huán)境運行時環(huán)境有三個類型：完全靜態(tài)環(huán)境(fully static environment)、基于棧的環(huán)境、基于棧的環(huán)境(stack-based environment)，以及完全動態(tài)環(huán)境以及完全動態(tài)環(huán)境(fully dynamic environment)。這這3種類型種類型的混合形式也是可能的。的混合形式也是可能的。mcy57.1 7.1 程序執(zhí)行時的存儲器組織程序執(zhí)行時的存儲器組織7.2 7.2 完全靜態(tài)的運行時環(huán)境完全靜態(tài)的運行時環(huán)境7.3 7.3 基于棧的運行時環(huán)境基于棧的運行時環(huán)境7.4

4、7.4 動態(tài)存儲器動態(tài)存儲器7.5 7.5 參數(shù)存儲機制參數(shù)存儲機制mcy67.17.1程序執(zhí)行時的存儲器組織程序執(zhí)行時的存儲器組織目標(biāo)代碼運行時目標(biāo)代碼運行時, ,操作系統(tǒng)為目標(biāo)代碼的運行分配操作系統(tǒng)為目標(biāo)代碼的運行分配的存儲空間按用途可劃分為下面幾個部分的存儲空間按用途可劃分為下面幾個部分: :mcy7 代碼區(qū)域：目標(biāo)代碼的存儲區(qū)域，由于代碼區(qū)在執(zhí)行之前是代碼區(qū)域：目標(biāo)代碼的存儲區(qū)域，由于代碼區(qū)在執(zhí)行之前是固定的，所以在編譯時所有目標(biāo)代碼的地址都是可計算的；固定的，所以在編譯時所有目標(biāo)代碼的地址都是可計算的； 全程全程/ /靜態(tài)區(qū)域：靜態(tài)數(shù)據(jù)區(qū)用來存放那些具有絕對地址的靜態(tài)區(qū)域：靜態(tài)數(shù)據(jù)區(qū)

5、用來存放那些具有絕對地址的數(shù)據(jù)和變量數(shù)據(jù)和變量( (如靜態(tài)變量和全程變量如靜態(tài)變量和全程變量) )；編譯器可以確定其所編譯器可以確定其所占用存儲空間的大??；占用存儲空間的大小； 棧區(qū)：在運行時分配存儲空間的數(shù)據(jù)就分配在棧區(qū)；編譯器棧區(qū)：在運行時分配存儲空間的數(shù)據(jù)就分配在棧區(qū)；編譯器知道存在棧中的具體數(shù)據(jù)大小和存活時間；知道存在棧中的具體數(shù)據(jù)大小和存活時間； 堆區(qū)：供用戶動態(tài)申請存儲空間，編譯器不需要知道究竟得堆區(qū)：供用戶動態(tài)申請存儲空間，編譯器不需要知道究竟得從從heapheap中分配多少空間，也不需要知道從中分配多少空間，也不需要知道從heapheap上分配的空間上分配的空間究竟需要存在多久

6、。究竟需要存在多久。 由于棧區(qū)和堆區(qū)的長度會隨著目標(biāo)代碼的運行而變化，因此把它們由于棧區(qū)和堆區(qū)的長度會隨著目標(biāo)代碼的運行而變化，因此把它們分配在數(shù)據(jù)區(qū)的兩端。一般情況下，棧向下長，堆向上長，可以使分配在數(shù)據(jù)區(qū)的兩端。一般情況下，棧向下長，堆向上長，可以使棧和堆共用一空白存儲空間。棧和堆共用一空白存儲空間。mcy8 在在語言中語言中, ,通常采用以過程為單位的動態(tài)存通常采用以過程為單位的動態(tài)存儲分配方案：儲分配方案：當(dāng)一過程當(dāng)一過程( (函數(shù)函數(shù)) )被調(diào)用時，就在棧頂為該過程分配所需的被調(diào)用時，就在棧頂為該過程分配所需的數(shù)據(jù)空間數(shù)據(jù)空間( (過程活動記錄過程活動記錄) )，當(dāng)一個過程工作完畢返

7、回時，當(dāng)一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)空間它在棧頂?shù)臄?shù)據(jù)空間( (過程活動記錄過程活動記錄)也即釋放。也即釋放。 過程的活動記錄過程的活動記錄( (activation record,AR) )是一段連續(xù)的存是一段連續(xù)的存儲區(qū)，用于存放過程的一次執(zhí)行所需要的信息，當(dāng)調(diào)儲區(qū)，用于存放過程的一次執(zhí)行所需要的信息，當(dāng)調(diào)用或激活過程或函數(shù)時，必須為被調(diào)用過程的活動記用或激活過程或函數(shù)時，必須為被調(diào)用過程的活動記錄分配空間。錄分配空間。 活動記錄存放的信息至少應(yīng)包括以下幾個部分：活動記錄存放的信息至少應(yīng)包括以下幾個部分：mcy9存放主調(diào)過程為被調(diào)過程存放主調(diào)過程為被調(diào)過程提供的實參信息提供的實參

8、信息;存放目標(biāo)程序臨時變存放目標(biāo)程序臨時變量的值量的值;存放本次執(zhí)行中的局部數(shù)據(jù)存放本次執(zhí)行中的局部數(shù)據(jù)用于指向主調(diào)過程的活動記用于指向主調(diào)過程的活動記錄的控制鏈和返回地址錄的控制鏈和返回地址;mcy10b:2a:1該函數(shù)調(diào)用結(jié)束該函數(shù)調(diào)用結(jié)束時的返回地址時的返回地址(00401353)主調(diào)函數(shù)的控主調(diào)函數(shù)的控制鏈制鏈語言所調(diào)用函語言所調(diào)用函數(shù)的活動記錄數(shù)的活動記錄示例示例( (函數(shù)調(diào)用函數(shù)調(diào)用分析中的舉例分析中的舉例) )c:3棧底棧底棧頂棧頂mcy11第第7 7章章 運行時環(huán)境運行時環(huán)境7.1 7.1 程序執(zhí)行時的存儲器組織程序執(zhí)行時的存儲器組織7.2 7.2 完全靜態(tài)的運行時環(huán)境完全靜態(tài)

9、的運行時環(huán)境7.3 7.3 基于棧的運行時環(huán)境基于棧的運行時環(huán)境7.4 7.4 動態(tài)存儲器動態(tài)存儲器7.5 7.5 參數(shù)存儲機制參數(shù)存儲機制mcy127.2 7.2 完全靜態(tài)的運行時環(huán)境完全靜態(tài)的運行時環(huán)境 在完全靜態(tài)環(huán)境中，不僅全局變量，所有的變量都在完全靜態(tài)環(huán)境中，不僅全局變量，所有的變量都是靜態(tài)分配，即是靜態(tài)分配，即整個程序所需數(shù)據(jù)空間的總量在編整個程序所需數(shù)據(jù)空間的總量在編譯時是完全確定的譯時是完全確定的，從而每個數(shù)據(jù)名的地址就可靜，從而每個數(shù)據(jù)名的地址就可靜態(tài)地進行分配，適于靜態(tài)分配的語言，要求滿足的態(tài)地進行分配，適于靜態(tài)分配的語言，要求滿足的條件是：條件是： 每個數(shù)據(jù)名所需的存儲空

10、間的大小都是常量每個數(shù)據(jù)名所需的存儲空間的大小都是常量 不允許采用動態(tài)的數(shù)據(jù)結(jié)構(gòu)，即在程序運行過程不允許采用動態(tài)的數(shù)據(jù)結(jié)構(gòu)，即在程序運行過程中申請或釋放的數(shù)據(jù)結(jié)構(gòu)中申請或釋放的數(shù)據(jù)結(jié)構(gòu) 過程不可遞歸調(diào)用過程不可遞歸調(diào)用mcy13整個程序存儲器如下所示：整個程序存儲器如下所示：mcy14w程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為_管理技術(shù)。a.靜態(tài)存儲b.動態(tài)存儲c.棧式存儲d.堆式存儲mcy15u靜態(tài)存儲分配允許程序出現(xiàn)_。a.遞歸過程b.可變體積的數(shù)據(jù)項目c.靜態(tài)變量d.待定性質(zhì)的名字mcy16第第7 7章章 運行時環(huán)境運行時環(huán)境7.1 7.1 程序執(zhí)行時的存儲器組織程序執(zhí)行時的存儲器組

11、織7.2 7.2 完全靜態(tài)的運行時環(huán)境完全靜態(tài)的運行時環(huán)境7.3 7.3 基于棧的運行時環(huán)境基于棧的運行時環(huán)境7.4 7.4 動態(tài)存儲器動態(tài)存儲器7.5 7.5 參數(shù)存儲機制參數(shù)存儲機制mcy177.3 7.3 基于棧的運行時環(huán)境基于棧的運行時環(huán)境7.3.1沒有局部過程的基于棧的環(huán)境沒有局部過程的基于棧的環(huán)境 在一個在一個所有過程都是全局的所有過程都是全局的、過程定義不允許嵌套過程定義不允許嵌套，但允許過程的遞歸調(diào)用的程序設(shè)計語言但允許過程的遞歸調(diào)用的程序設(shè)計語言( (例如例如C C語言語言) )中，基于棧的動態(tài)運行時環(huán)境有兩個指針中，基于棧的動態(tài)運行時環(huán)境有兩個指針：sp:棧頂部棧頂部( (

12、top of stack) )指針；對于指針；對于x86x86系統(tǒng)來說，系統(tǒng)來說，它采用它采用spsp或或espesp寄存器存儲棧頂部的地址；寄存器存儲棧頂部的地址；mcy18fp(frame point)指向當(dāng)前活動記錄的控制鏈的指向當(dāng)前活動記錄的控制鏈的指針指針，對于對于x86系統(tǒng)，它采用系統(tǒng)，它采用bp或或ebp寄存器寄存器存存儲儲當(dāng)前活動記錄的控制鏈的地址，其作用如下：當(dāng)前活動記錄的控制鏈的地址，其作用如下：1.1.通過該指針可以訪問當(dāng)前執(zhí)行函數(shù)的局部變量；通過該指針可以訪問當(dāng)前執(zhí)行函數(shù)的局部變量；2.2.通過該指針可以訪問主調(diào)程序的活動記錄；通過該指針可以訪問主調(diào)程序的活動記錄；3.

13、3.允許在當(dāng)前的被調(diào)函數(shù)執(zhí)行完畢時，用它來恢復(fù)允許在當(dāng)前的被調(diào)函數(shù)執(zhí)行完畢時，用它來恢復(fù)主調(diào)函數(shù)的活動記錄。主調(diào)函數(shù)的活動記錄。mcy19b:2a:1該函數(shù)調(diào)用結(jié)束該函數(shù)調(diào)用結(jié)束時的返回地址時的返回地址(cs:eip) 00401353主調(diào)函數(shù)的控主調(diào)函數(shù)的控制鏈制鏈(main.fp)語言當(dāng)前執(zhí)行語言當(dāng)前執(zhí)行函數(shù)的活動記錄函數(shù)的活動記錄示例示例( (函數(shù)調(diào)用函數(shù)調(diào)用分析中的舉例分析中的舉例) )c:3spfp棧底棧底棧頂棧頂mcy20當(dāng)一個過程被調(diào)用時，當(dāng)一個過程被調(diào)用時，在棧頂為該過程分配所在棧頂為該過程分配所需的數(shù)據(jù)空間需的數(shù)據(jù)空間( (過程活動記錄過程活動記錄) )如下：如下：1)1)

14、將將實參實參的值壓入在該函數(shù)對應(yīng)的的值壓入在該函數(shù)對應(yīng)的新活動記錄新活動記錄中。中。2)2) 將被調(diào)函數(shù)執(zhí)行完畢后的將被調(diào)函數(shù)執(zhí)行完畢后的返回地址返回地址壓入在壓入在新的活動記錄新的活動記錄中。中。3)3) 完成到被調(diào)用的過程的代碼一個轉(zhuǎn)移。完成到被調(diào)用的過程的代碼一個轉(zhuǎn)移。4)4) 將主調(diào)函數(shù)的將主調(diào)函數(shù)的fpfp作為作為控制鏈壓入到新的活動記錄控制鏈壓入到新的活動記錄中。中。5)5) 改變改變fpfp以使其以使其指向新的活動記錄指向新的活動記錄( (將將spsp復(fù)制到該復(fù)制到該fpfp中中) )6)6) 將該函數(shù)的將該函數(shù)的局部變量局部變量和和局部臨時變量局部臨時變量壓入到新的活動記錄中。

15、壓入到新的活動記錄中。mcy21b:2a:1該函數(shù)調(diào)用結(jié)束該函數(shù)調(diào)用結(jié)束時的返回地址時的返回地址(cs:eip) 00401353主調(diào)函數(shù)的控主調(diào)函數(shù)的控制鏈制鏈(main.fp)語言當(dāng)前執(zhí)語言當(dāng)前執(zhí)行函數(shù)的活動行函數(shù)的活動記錄示例：記錄示例：c:3sp棧底棧底棧頂棧頂fpmcy22當(dāng)被調(diào)函數(shù)執(zhí)行完畢返回時，其對應(yīng)當(dāng)被調(diào)函數(shù)執(zhí)行完畢返回時，其對應(yīng)的活動記錄從棧中彈出的過程：的活動記錄從棧中彈出的過程： 將將fpfp復(fù)制到復(fù)制到spsp中。中。 將控制鏈裝載到將控制鏈裝載到fpfp中。中。 完成到返回地址主調(diào)函數(shù)的一個轉(zhuǎn)移。完成到返回地址主調(diào)函數(shù)的一個轉(zhuǎn)移。 改變改變spsp以彈出實參。以彈出實

16、參。mcy23例：計算兩個非負(fù)整數(shù)的最大公約數(shù)的例：計算兩個非負(fù)整數(shù)的最大公約數(shù)的c c代碼如下：代碼如下：#include int x,y;int gcd(int u,int v) if(v= =0) return u; else return gcd(v,u%v)main() scanf(“%d%d”,&x,&y); printf(“%dn”,gcd(x,y); return 0;mcy24x:15x:15y:10y:10全局全局/ /靜態(tài)區(qū)域靜態(tài)區(qū)域mainmain的活動記錄的活動記錄sp,fpsp,fpv:10v:10u:15u:15返回地址返回地址mainmain的的

17、fpfp第一次調(diào)用第一次調(diào)用gcdgcd時的活動記錄時的活動記錄sp,fpsp,fp第二次調(diào)用第二次調(diào)用gcdgcd時的活動記錄時的活動記錄v:5v:5u:10u:10返回地址返回地址第一次調(diào)用第一次調(diào)用gcdgcd時的時的fpfp第三次調(diào)用第三次調(diào)用gcdgcd時的活動記錄時的活動記錄v:0v:0u:5u:5返回地址返回地址第二次調(diào)用第二次調(diào)用gcdgcd時的時的fpfpsp,fpsp,fpsp,fpsp,fp棧生長方向棧生長方向自由空間自由空間mcy25例：考慮下列程序清單的例：考慮下列程序清單的c c代碼。代碼。int x=2;void g(int);void f(int n)stati

18、c int x=1; g(n); x- -;void g(int m)int y=m-1;if (y0) f(y); x- -; g(y); main()g(x); return 0;畫出第二次對畫出第二次對g調(diào)用時，程調(diào)用時，程序的運行時環(huán)境：序的運行時環(huán)境：mcy26x:2x:2x x（from ffrom f）:1:1全局全局/ /靜態(tài)區(qū)域靜態(tài)區(qū)域mainmain的活動記錄的活動記錄sp,fpsp,fpm:2m:2返回地址返回地址mainmain的的fpfp y:1y:1第一次調(diào)用第一次調(diào)用g g時時的活動記錄的活動記錄fpfpspsp第一次調(diào)用第一次調(diào)用f f時時的活動記錄的活動記錄n

19、:1n:1 返回地址返回地址第一次調(diào)用第一次調(diào)用g g時的時的fpfpsp,fpsp,fp第二次調(diào)用第二次調(diào)用g g時的時的活動記錄活動記錄m:1m:1 返回地址返回地址第一次調(diào)用第一次調(diào)用f f時的時的fpfp y:0y:0fpfpspsp棧生長方向棧生長方向自由空間自由空間mcy27w目標(biāo)代碼的生成必須支持變量和臨時變量的目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的實際定位，并增加支持運行時環(huán)境所必需的代碼代碼。對名字的訪問對名字的訪問如何處理可變長度的問題如何處理可變長度的問題局部臨時變量局部臨時變量嵌套聲明嵌套聲明mcy28對名字的訪問：對名字的訪問：w

20、在沒有局部過程的基于棧的運行時環(huán)境中，所有的在沒有局部過程的基于棧的運行時環(huán)境中，所有的非局部的名字都是全局的非局部的名字都是全局的，因此也就是靜態(tài)的，都，因此也就是靜態(tài)的，都具有一個固定的靜態(tài)地址，可以被直接訪問。具有一個固定的靜態(tài)地址，可以被直接訪問。w對函數(shù)參數(shù)和局部變量而言，在大多數(shù)的語言中，對函數(shù)參數(shù)和局部變量而言，在大多數(shù)的語言中，每個局部聲明的偏移量仍是可有編譯程序靜態(tài)地計每個局部聲明的偏移量仍是可有編譯程序靜態(tài)地計算出來算出來，因為過程的聲明在編譯時是固定的，而且，因為過程的聲明在編譯時是固定的，而且為每個聲明分配的存儲器大小也根據(jù)其數(shù)據(jù)類型而為每個聲明分配的存儲器大小也根據(jù)其

21、數(shù)據(jù)類型而固定。固定。mcy29m:2 m:2 返回地址返回地址控制鏈控制鏈 y:1y:1fpfpmOffsetmOffsetyOffsetyOffsetmOffsetmOffset=+8=+8yOffsetyOffset=-4=-4高端地址高端地址低端地址低端地址mcy30例：考慮下面的例：考慮下面的C C過程過程ViodViod f(intf(int x,char c) x,char c) intint a10; a10; double y; double y; 對對f f調(diào)用的活動記錄為：調(diào)用的活動記錄為：c cx x 返回地址返回地址控制鏈控制鏈a9a9a1a1a0a0y yfpfpx

22、OffsetxOffsetaOffsetaOffsetcOffsetcOffsetyOffsetyOffsetxOffsetxOffset=+8=+8cOffsetcOffset=+12=+12aOffsetaOffset=-40=-40yOffsetyOffset=-48=-48現(xiàn)在對現(xiàn)在對aiai訪問，要求計算地址：訪問，要求計算地址：(-40+4(-40+4* *i)(fpi)(fp) )mcy31w目標(biāo)代碼的生成必須支持變量和臨時變量的目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的實際定位，并增加支持運行時環(huán)境所必需的代碼代碼。對名字的訪問對名字的訪問如何

23、處理可變長度的問題如何處理可變長度的問題局部臨時變量局部臨時變量嵌套聲明嵌套聲明mcy32處理可變長度的數(shù)據(jù)處理可變長度的數(shù)據(jù)有時編譯程序必須處理數(shù)據(jù)變化的可能性，表現(xiàn)在數(shù)據(jù)有時編譯程序必須處理數(shù)據(jù)變化的可能性，表現(xiàn)在數(shù)據(jù)對象的數(shù)量和每個對象的大小上。發(fā)生在支持基于棧的對象的數(shù)量和每個對象的大小上。發(fā)生在支持基于棧的環(huán)境的語言中的兩種情況如下：環(huán)境的語言中的兩種情況如下： 調(diào)用中的自變量的數(shù)量可根據(jù)調(diào)用的不同而不同。調(diào)用中的自變量的數(shù)量可根據(jù)調(diào)用的不同而不同。 數(shù)組參數(shù)或局部數(shù)組變量的大小可根據(jù)調(diào)用的不同數(shù)組參數(shù)或局部數(shù)組變量的大小可根據(jù)調(diào)用的不同而不同。而不同。printf(%d%s%cpr

24、intf(%d%s%c, n, prompt, , n, prompt, chch););printf(Helloprintf(Hello, worldn);, worldn);通常，通常，C C編譯程序一般通過把調(diào)用的自變量按相反順序編譯程序一般通過把調(diào)用的自變量按相反順序( (in reverse order)in reverse order)壓入到運行時棧來處理這一點。壓入到運行時棧來處理這一點。mcy33w目標(biāo)代碼的生成必須支持變量和臨時變量的目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的實際定位，并增加支持運行時環(huán)境所必需的代碼代碼。對名字的訪問對名字的

25、訪問如何處理可變長度的問題如何處理可變長度的問題局部臨時變量局部臨時變量嵌套聲明嵌套聲明mcy34局部臨時變量：局部臨時變量： 考慮考慮C C表達式：表達式： xi=(i+j) xi=(i+j)* *(i/k+f(j)(i/k+f(j) 在這個表達式從左到右的求值計算中，在對在這個表達式從左到右的求值計算中，在對f f的調(diào)的調(diào)用過程中需要保存中間結(jié)果：用過程中需要保存中間結(jié)果： xixi的地址、的地址、i+ji+j的的和、和、i/ki/k的商。的商。 這些中間值可計算到寄存器中，根據(jù)寄存器進行保這些中間值可計算到寄存器中，根據(jù)寄存器進行保存和恢復(fù)；或者存和恢復(fù)；或者可將它們作為臨時變量存儲在對

26、可將它們作為臨時變量存儲在對f f調(diào)用之前的運行時棧中調(diào)用之前的運行時棧中。如下所示：。如下所示：mcy35 返回地址返回地址控制鏈控制鏈xixi的地址的地址i+ji+j的結(jié)果的結(jié)果i/ji/j的結(jié)果的結(jié)果fpfp( (棧的其余部分棧的其余部分) )spsp臨時棧臨時棧調(diào)用調(diào)用f f（將要創(chuàng)建的）時的將要創(chuàng)建的）時的新活動記錄新活動記錄包含表達式過程的活動記錄包含表達式過程的活動記錄自由空間自由空間mcy36w目標(biāo)代碼的生成必須支持變量和臨時變量的目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的實際定位，并增加支持運行時環(huán)境所必需的代碼代碼。對名字的訪問對名字的訪問

27、如何處理可變長度的問題如何處理可變長度的問題局部臨時變量局部臨時變量嵌套聲明嵌套聲明mcy37嵌套聲明：嵌套聲明：嵌套聲明也出現(xiàn)了與局部臨時變量同樣的問題?？紤]以下的嵌套聲明也出現(xiàn)了與局部臨時變量同樣的問題?？紤]以下的C C代碼：代碼：Void Void p(intp(int x,double y) x,double y) char a; char a; intint i; i; A:double x; A:double x; intint j; j; B:char B:char * *a;a; intint k; k; mcy38一個簡單的處理辦法是按照與臨時表達式相類似的辦法一個簡單的處理

28、辦法是按照與臨時表達式相類似的辦法在嵌套的塊中處理聲明，并在進入塊時在棧中分配它們。在嵌套的塊中處理聲明，并在進入塊時在棧中分配它們。x:x:y:y: 返回地址返回地址 控制鏈控制鏈a:a:i:i:x x: :j j: :fpfp( (棧的其余部分棧的其余部分) )spsp塊塊A A的分配區(qū)的分配區(qū)調(diào)用調(diào)用p p時的活動記錄時的活動記錄自由空間自由空間當(dāng)進入塊當(dāng)進入塊A A后，運行時棧如下所示：后，運行時棧如下所示：mcy39x:x:y:y: 返回地址返回地址控制鏈控制鏈a:a:i:i:a a: :k k: :fpfp( (棧的其余部分棧的其余部分) )spsp塊塊B B的分配區(qū)的分配區(qū)調(diào)用調(diào)

29、用p p時的活動記錄時的活動記錄自由空間自由空間當(dāng)進入塊當(dāng)進入塊B B后，運行時棧如下所示：后，運行時棧如下所示：mcy40第第7 7章章 運行時環(huán)境運行時環(huán)境7.1 7.1 程序執(zhí)行時的存儲器組織程序執(zhí)行時的存儲器組織7.2 7.2 完全靜態(tài)的運行時環(huán)境完全靜態(tài)的運行時環(huán)境7.3 7.3 基于棧的運行時環(huán)境基于棧的運行時環(huán)境7.4 7.4 動態(tài)存儲器動態(tài)存儲器7.5 7.5 參數(shù)存儲機制參數(shù)存儲機制mcy417.4.1對象類型對象類型在大多數(shù)面向?qū)ο蟮恼Z言中，對象都有構(gòu)造函數(shù)和在大多數(shù)面向?qū)ο蟮恼Z言中，對象都有構(gòu)造函數(shù)和析構(gòu)函數(shù)，它們分別在創(chuàng)建對象和釋放對象時被調(diào)析構(gòu)函數(shù)，它們分別在創(chuàng)建對象

30、和釋放對象時被調(diào)用。如果這就是全部內(nèi)容的話，那么對象的實現(xiàn)將用。如果這就是全部內(nèi)容的話，那么對象的實現(xiàn)將非常簡單。假定我們有一對象類非常簡單。假定我們有一對象類A A，它有方法它有方法m1,m2m1,m2以及字段以及字段a1a1和和a2a2。那么類那么類A A對象的運行時表示有包含對象的運行時表示有包含字段字段a1a1和和a2a2記錄組成：記錄組成：a1a1a2a2m1_Am1_Am2_Am2_A另外，編譯程序維護著一張類另外，編譯程序維護著一張類A A的編譯時方法表：的編譯時方法表：7.4 7.4 動態(tài)存儲器動態(tài)存儲器mcy42在上述簡單的模塊中，字段選擇可以像記錄字段選擇一樣在上述簡單的模

31、塊中，字段選擇可以像記錄字段選擇一樣實現(xiàn)，方法選擇由編譯程序內(nèi)的識別過程來實現(xiàn)。即通過實現(xiàn)，方法選擇由編譯程序內(nèi)的識別過程來實現(xiàn)。即通過一個指向?qū)ο蟮闹羔?，方法可以像函?shù)一樣實現(xiàn)。因此方一個指向?qū)ο蟮闹羔槪椒梢韵窈瘮?shù)一樣實現(xiàn)。因此方法法m2_Am2_A可以翻譯為可以翻譯為c c語言中的函數(shù)。語言中的函數(shù)。 void m2_A(class_A void m2_A(class_A * *this,intthis,int i) i) 方法方法m2_Am2_A的程序體，通過的程序體，通過this-xthis-x訪問任一對象字段訪問任一對象字段x x 方法的調(diào)用方法的調(diào)用a .m2(3)a .m2(

32、3)可以翻譯成可以翻譯成m2_A(&a,3)m2_A(&a,3)mcy43繼承特性繼承特性現(xiàn)在假定類現(xiàn)在假定類B B通過增添方法通過增添方法m3m3和字段和字段b1b1來擴展類來擴展類A,A,那么類那么類B B的運行時表示如下：的運行時表示如下：a1a1a2a2m1_Am1_Am2_Am2_Ab1b1另外類另外類B B的方法編譯時表如下：的方法編譯時表如下：m3_Bm3_Bmcy44方法重載方法重載假定上例中類假定上例中類B B重新定義了方法重新定義了方法m2m2，那么那么A A中方法中方法m2m2的定義既是它唯一的聲明也是它的第一次定義，而的定義既是它唯一的聲明也是它的第一次

33、定義，而它在類它在類B B中的定義為重定義。為使名字既可以反映聲中的定義為重定義。為使名字既可以反映聲明它的類，也可以反映定義它的類。方法的名字可明它的類，也可以反映定義它的類。方法的名字可有三部分組成：方法名、聲明方法的類名、定義方有三部分組成：方法名、聲明方法的類名、定義方法類名。各部分之間用下劃線（法類名。各部分之間用下劃線（）分開。因此在）分開。因此在類類A A中聲明在類中聲明在類B B中定義的方法中定義的方法m2m2其名字記為其名字記為m2_A_Bm2_A_B。方法重載影響方法的編譯時表，現(xiàn)在類方法重載影響方法的編譯時表，現(xiàn)在類A A的方法的編的方法的編譯時表如下：譯時表如下：m1_

34、A_Am1_A_Am2_A_Am2_A_Am1_A_Am1_A_Am2_A_Bm2_A_Bm3_B_Bm3_B_B類類B B的方法的的方法的編譯時表如右：編譯時表如右：mcy45現(xiàn)在假定現(xiàn)在假定a a是類是類A A的一個對象，而的一個對象，而b b是類是類B B的一個對的一個對象。方法調(diào)用象。方法調(diào)用a.m2(a.m2() )將翻譯成對將翻譯成對m2_A_Am2_A_A的調(diào)用，的調(diào)用，而方法調(diào)用而方法調(diào)用b.m2(b.m2() )將翻譯成對將翻譯成對m2_A_Bm2_A_B的調(diào)用。的調(diào)用。m2_A_Am2_A_A在類在類A A中聲明和定義。中聲明和定義。m2_A_Bm2_A_B在類在類A A中

35、生明，中生明，在類在類B B中定義。如果繼承是語言中唯一的面向?qū)ο笾卸x。如果繼承是語言中唯一的面向?qū)ο蟮奶卣?，那么的特征，那么m2_A_Am2_A_A翻譯形式為：翻譯形式為：void m2_A_A(Class_A void m2_A_A(Class_A * *this,intthis,int i); i);而而m2_A_Bm2_A_B的翻譯形式為：的翻譯形式為：void m2_A_B(Class_B void m2_A_B(Class_B * *this,intthis,int i); i);mcy46多態(tài)性多態(tài)性當(dāng)類當(dāng)類B B繼承類繼承類A A并且該語言允許并且該語言允許“類類B B的指針

36、的指針”類型的指針類型的指針能夠賦給一個能夠賦給一個“類類A A的指針的指針”類型的變量時，那么該語言類型的變量時，那么該語言支持多態(tài)型。例如：支持多態(tài)型。例如：Class B Class B * *b=b=; ;Class A Class A * *a=b;a=b;則第二行被翻譯成：則第二行被翻譯成：class A class A * *a=a=convert_ptr_to_B_to_ptr_to_A(bconvert_ptr_to_B_to_ptr_to_A(b););現(xiàn)在，過程現(xiàn)在，過程convert_ptr_to_B_to_ptr_to_Aconvert_ptr_to_B_to_ptr

37、_to_A()()為一編譯為一編譯時類型的操作時類型的操作, ,它將指向子類它將指向子類B B的一個對象指針轉(zhuǎn)換為指的一個對象指針轉(zhuǎn)換為指向其父類向其父類A A對象的指針。因為類對象的指針。因為類B B的對象也是從類的對象也是從類A A的字的字段開始，因而指針的值并不需要改變，唯一影響的是改段開始，因而指針的值并不需要改變，唯一影響的是改變了指針的類型：變了指針的類型：mcy47a1a1a2a2b1b1指向指向B B的指針的指針指向指向B B中中A A的指針的指針但要注意，現(xiàn)在同一指針指向了不同類的對象但要注意，現(xiàn)在同一指針指向了不同類的對象mcy48動態(tài)綁定：動態(tài)綁定：因為類型因為類型cla

38、ss Aclass A* *的指針的指針p p可能實際上引用了類可能實際上引用了類B B的一的一個對象，動態(tài)綁定認(rèn)為如果實際上為類個對象，動態(tài)綁定認(rèn)為如果實際上為類B B的對象，那就的對象，那就應(yīng)該調(diào)用應(yīng)該調(diào)用m2_A_B,m2_A_B,如果實際為如果實際為A A的對象，那么就應(yīng)該調(diào)的對象，那么就應(yīng)該調(diào)用用m2_A_A.m2_A_A.對于方法調(diào)用對于方法調(diào)用P-m2(3),pP-m2(3),p是一指向類是一指向類A A對象對象指針，可以被翻譯成如下形式：指針，可以被翻譯成如下形式：switch(dynamic_type_of(p)switch(dynamic_type_of(p) case D

39、ynamic_class_A:m2_A_A(p,3);break; case Dynamic_class_A:m2_A_A(p,3);break; case Dynamic_class_B: case Dynamic_class_B: m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);break; m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);break; 當(dāng)當(dāng)p p為一指向類為一指向類B B對象指針時，可以立即將對象指針時，可以立即將p-m2(3)p-m2(3)調(diào)用翻調(diào)用翻譯為：譯為：m2_A_B(p,3);m2_A_B

40、(p,3);mcy49動態(tài)綁定對于方法動態(tài)綁定對于方法P-m2(3)P-m2(3)的更好翻譯方法為：的更好翻譯方法為：如果如果p p是一指向類是一指向類A A對象指針，則進行如下處理有：對象指針，則進行如下處理有：1.1. ( (dynamic_type_of(p)= =Dynamic_Class_A ? m2_A_A:m2_A_B)(p,3);dynamic_type_of(p)= =Dynamic_Class_A ? m2_A_A:m2_A_B)(p,3);如果指針如果指針p p實際上引用了類實際上引用了類B B的一個對象，則執(zhí)行步驟的一個對象，則執(zhí)行步驟2 2中的方法。中的方法。2.2.

41、 void m2_A_B(Class_A void m2_A_B(Class_A * *this_A,intthis_A,int i) i)Class_B Class_B * *this=this=convert_ptr_to_A_to_ptr_to_B(this_Aconvert_ptr_to_A_to_ptr_to_B(this_A););方法方法m2_A_Bm2_A_B的程序體，通過的程序體，通過this-xthis-x訪問任一對象字段訪問任一對象字段x x 如果如果p p是一指向類是一指向類B B對象指針，則進行如下處理有：對象指針，則進行如下處理有：1.1. m2_A_B(conve

42、rt_ptr_to_B_to_ptr_to_A(p),3);m2_A_B(convert_ptr_to_B_to_ptr_to_A(p),3);2.2. 執(zhí)行的方法同上述的步驟執(zhí)行的方法同上述的步驟2 2；mcy50對于上述的翻譯方法，每一個對象的類型信息實現(xiàn)為一個對于上述的翻譯方法，每一個對象的類型信息實現(xiàn)為一個指向分派表的指針，如下圖所示指向分派表的指針，如下圖所示( (分派表是存儲方法地址分派表是存儲方法地址的記錄，下圖分派表存儲的是方法的記錄，下圖分派表存儲的是方法m1_A_Am1_A_A， m2_A_B m2_A_B和和 m1_B_Bm1_B_B的地址的地址) )a1a1a2a2b1

43、b1指向指向B B的指針的指針指向指向B B中中A A的指針的指針m1_A_Am1_A_Am2_A_Bm2_A_Bm3_B_Bm3_B_B類類B B對象的表示對象的表示分派表分派表B-objectB-objectB-classB-classmcy517.4.2 堆管理堆管理對于允許程序為變量在運行時動態(tài)申請和釋對于允許程序為變量在運行時動態(tài)申請和釋放存儲空間的語言放存儲空間的語言, ,采用堆式分配是最有效的解采用堆式分配是最有效的解決方案決方案. .堆式分配的基本思想是堆式分配的基本思想是, ,為運行的程序劃出適為運行的程序劃出適當(dāng)大的空間當(dāng)大的空間( (稱為堆稱為堆Heap),Heap),每

44、當(dāng)程序申請空間時每當(dāng)程序申請空間時, ,就從堆的空閑區(qū)找出一塊空間分配給程序就從堆的空閑區(qū)找出一塊空間分配給程序, ,每當(dāng)每當(dāng)釋放時則回收之釋放時則回收之. .mcy52在在C C中處理鏈表等結(jié)構(gòu)時中處理鏈表等結(jié)構(gòu)時, ,常常隨機地插入或刪除一些結(jié)點常常隨機地插入或刪除一些結(jié)點, ,利用利用指針變量和結(jié)構(gòu)類型指針變量和結(jié)構(gòu)類型, ,可動態(tài)地生成新結(jié)點可動態(tài)地生成新結(jié)點( (使用使用mallocmalloc()()函數(shù)函數(shù)), ), 或刪除之或刪除之( (使用使用free()free()函數(shù)函數(shù)).).例如例如 structstruct node char data; node char dat

45、a; structstruct node node * *next;next;定義了定義了鏈表的結(jié)點鏈表的結(jié)點, ,下面函數(shù)可在表的尾部添加新結(jié)點下面函數(shù)可在表的尾部添加新結(jié)點: : void void Append(structAppend(struct node node * *head,char head,char chch) ) structstruct node node * *p=head;p=head; while( while(* *p) p=p-next; p-next=p) p=p-next; p-next=malloc(sizeof(structmalloc(sizeof

46、(struct node);node); p-next-data= p-next-data=chch; p-next-next=NULL; p-next-next=NULL;還可用下面的函數(shù)在表頭刪除一結(jié)點還可用下面的函數(shù)在表頭刪除一結(jié)點: :void void Delete(structDelete(struct node node * *head) head) structstruct node node * *p=head; p=head; if( if(* *p) head =head-next; free(p); p) head =head-next; free(p); 堆分配的必要

47、性堆分配的必要性mcy53將存儲空間劃分為若干存儲塊將存儲空間劃分為若干存儲塊; ;用戶可隨機地申請或用戶可隨機地申請或釋放一個或多個塊釋放一個或多個塊; ;在存儲空間中建立兩個隊列在存儲空間中建立兩個隊列: :空閑隊列和忙隊列空閑隊列和忙隊列, ,空閑空閑隊列拉成鏈隊列拉成鏈, ,鏈?zhǔn)子面準(zhǔn)子肍REEFREE指針指明指針指明, ,忙隊列用一忙隊列用一( (已占已占塊塊) )記錄表記錄各占用塊的首址及大小信息記錄表記錄各占用塊的首址及大小信息( (也可用鏈也可用鏈進行記錄進行記錄).).申請時可按需要找到合適的塊分配之申請時可按需要找到合適的塊分配之( (分配策略有最分配策略有最佳分配或隨機分

48、配等佳分配或隨機分配等););釋放時將該塊插入到空閑隊列釋放時將該塊插入到空閑隊列( (能合并時可合并能合并時可合并),),并并從占用記錄表中刪除相應(yīng)的項從占用記錄表中刪除相應(yīng)的項. .堆存儲管理的實現(xiàn)堆存儲管理的實現(xiàn)mcy54第第7 7章章 運行時環(huán)境運行時環(huán)境7.1 7.1 程序執(zhí)行時的存儲器組織程序執(zhí)行時的存儲器組織7.2 7.2 完全靜態(tài)的運行時環(huán)境完全靜態(tài)的運行時環(huán)境7.3 7.3 基于棧的運行時環(huán)境基于棧的運行時環(huán)境7.4 7.4 動態(tài)存儲器動態(tài)存儲器7.5 7.5 參數(shù)存儲機制參數(shù)存儲機制mcy557.5 7.5 參數(shù)傳遞機制參數(shù)傳遞機制值傳遞值傳遞值傳遞的處理方法是：進入過程時

49、值傳遞的處理方法是：進入過程時, ,送入形參對應(yīng)的形式單元的是送入形參對應(yīng)的形式單元的是相應(yīng)實參的值相應(yīng)實參的值; ;過程體中對形參的任何賦值都按對形式單元的直接過程體中對形參的任何賦值都按對形式單元的直接訪問來產(chǎn)生代碼。訪問來產(chǎn)生代碼。因此因此, ,一旦把實參之值送入對應(yīng)形式單元之后一旦把實參之值送入對應(yīng)形式單元之后, ,在執(zhí)行過程體期間在執(zhí)行過程體期間, ,除了以實參值作為形參的初值進行運算之外除了以實參值作為形參的初值進行運算之外, ,將將不再與實參發(fā)生任不再與實參發(fā)生任何聯(lián)系。由此可見何聯(lián)系。由此可見, ,過程執(zhí)行的結(jié)果決不會改變實參之值。過程執(zhí)行的結(jié)果決不會改變實參之值。void i

50、nc2( int x)/* incorrect! */ +x;+x; void inc2( int* x)/* now ok */ +(*x);+(*x); mcy56引用傳遞引用傳遞控制轉(zhuǎn)入被調(diào)過程后控制轉(zhuǎn)入被調(diào)過程后,由被調(diào)過程將實參的地址寫入由被調(diào)過程將實參的地址寫入相應(yīng)的形式單元。過程體中對形式參數(shù)的任何引用相應(yīng)的形式單元。過程體中對形式參數(shù)的任何引用或賦值或賦值,都按對相應(yīng)形式單元間接訪問的尋址方式為都按對相應(yīng)形式單元間接訪問的尋址方式為其產(chǎn)生代碼其產(chǎn)生代碼。顯然。顯然,執(zhí)行過程時執(zhí)行過程時,型參就變成了實參的型參就變成了實參的別名，別名，對形參的賦值將會影響相應(yīng)實參之值。對形參的賦值將會影響相應(yīng)實參之值。在在C+中中，是通過在參數(shù)說明中使用特殊字符是通過在參數(shù)說明中使用特殊字符& &來得來得到引用傳遞：到引用傳遞：void inc2( int &x)/* C+ reference parameter */ +x;+x; mcy57引用傳遞不要求復(fù)制被傳遞的值，這與值傳遞不同。引用傳遞不要求復(fù)制被傳遞的值，這與值傳遞不同。當(dāng)要當(dāng)要復(fù)制的值是一個較