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

會計學(xué)1編譯原理課程設(shè)計之運行時環(huán)境mcy2第7章運行時環(huán)境(存儲空間)當(dāng)源程序的目標(biāo)代碼被運行時，在內(nèi)存中不僅有目標(biāo)代碼，而且還要保存各種信息，如必須為源程序中所出現(xiàn)的一些量（常量、變量及某些數(shù)組等）分配運行時的存儲空間。即編譯器要從操作系統(tǒng)得到一塊存儲區(qū)，用于被編譯過的目標(biāo)程序的運行。第1頁/共62頁mcy3存儲分配是在運行階段進(jìn)行的，但編譯程序在編譯階段要為其設(shè)計好存儲組織形式，并將這種組織形式通過生成的目標(biāo)代碼體現(xiàn)出來。(舉例說明：函數(shù)調(diào)用分析.txt)目標(biāo)代碼運行時，存儲空間的組織稱為目標(biāo)代碼的運行時環(huán)境。第2頁/共62頁mcy4運行時環(huán)境有三個類型：完全靜態(tài)環(huán)境(fullystaticenvironment)、基于棧的環(huán)境(stack-basedenvironment)，以及完全動態(tài)環(huán)境(fullydynamicenvironment)。這3種類型的混合形式也是可能的。第3頁/共62頁mcy57.1程序執(zhí)行時的存儲器組織7.2完全靜態(tài)的運行時環(huán)境7.3基于棧的運行時環(huán)境7.4動態(tài)存儲器7.5參數(shù)存儲機制第4頁/共62頁mcy67.1程序執(zhí)行時的存儲器組織目標(biāo)代碼運行時,操作系統(tǒng)為目標(biāo)代碼的運行分配的存儲空間按用途可劃分為下面幾個部分:第5頁/共62頁mcy7代碼區(qū)域：目標(biāo)代碼的存儲區(qū)域，由于代碼區(qū)在執(zhí)行之前是固定的，所以在編譯時所有目標(biāo)代碼的地址都是可計算的；全程/靜態(tài)區(qū)域：靜態(tài)數(shù)據(jù)區(qū)用來存放那些具有絕對地址的數(shù)據(jù)和變量(如靜態(tài)變量和全程變量)；編譯器可以確定其所占用存儲空間的大小；棧區(qū)：在運行時分配存儲空間的數(shù)據(jù)就分配在棧區(qū)；編譯器知道存在棧中的具體數(shù)據(jù)大小和存活時間；堆區(qū)：供用戶動態(tài)申請存儲空間，編譯器不需要知道究竟得從heap中分配多少空間，也不需要知道從heap上分配的空間究竟需要存在多久。由于棧區(qū)和堆區(qū)的長度會隨著目標(biāo)代碼的運行而變化，因此把它們分配在數(shù)據(jù)區(qū)的兩端。一般情況下，棧向下長，堆向上長，可以使棧和堆共用一空白存儲空間。第6頁/共62頁mcy8在PASCAL，C語言中,通常采用以過程為單位的動態(tài)存儲分配方案：當(dāng)一過程(函數(shù))被調(diào)用時，就在棧頂為該過程分配所需的數(shù)據(jù)空間(過程活動記錄)，當(dāng)一個過程工作完畢返回時，它在棧頂?shù)臄?shù)據(jù)空間(過程活動記錄)也即釋放。過程的活動記錄(activationrecord,AR)是一段連續(xù)的存儲區(qū)，用于存放過程的一次執(zhí)行所需要的信息，當(dāng)調(diào)用或激活過程或函數(shù)時，必須為被調(diào)用過程的活動記錄分配空間。活動記錄存放的信息至少應(yīng)包括以下幾個部分：第7頁/共62頁mcy9存放主調(diào)過程為被調(diào)過程提供的實參信息;存放目標(biāo)程序臨時變量的值;存放本次執(zhí)行中的局部數(shù)據(jù)用于指向主調(diào)過程的活動記錄的控制鏈和返回地址;第8頁/共62頁mcy10b:2a:1該函數(shù)調(diào)用結(jié)束時的返回地址(00401353)主調(diào)函數(shù)的控制鏈C語言所調(diào)用函數(shù)的活動記錄示例(函數(shù)調(diào)用分析中的舉例)c:3棧底棧頂?shù)?頁/共62頁mcy11第7章運行時環(huán)境7.1程序執(zhí)行時的存儲器組織7.2完全靜態(tài)的運行時環(huán)境7.3基于棧的運行時環(huán)境7.4動態(tài)存儲器7.5參數(shù)存儲機制第10頁/共62頁mcy127.2完全靜態(tài)的運行時環(huán)境在完全靜態(tài)環(huán)境中，不僅全局變量，所有的變量都是靜態(tài)分配，即整個程序所需數(shù)據(jù)空間的總量在編譯時是完全確定的，從而每個數(shù)據(jù)名的地址就可靜態(tài)地進(jìn)行分配，適于靜態(tài)分配的語言，要求滿足的條件是：每個數(shù)據(jù)名所需的存儲空間的大小都是常量不允許采用動態(tài)的數(shù)據(jù)結(jié)構(gòu)，即在程序運行過程中申請或釋放的數(shù)據(jù)結(jié)構(gòu)過程不可遞歸調(diào)用第11頁/共62頁mcy13整個程序存儲器如下所示：第12頁/共62頁mcy14程序所需的數(shù)據(jù)空間在程序運行前就可確定，稱為_______管理技術(shù)。靜態(tài)存儲動態(tài)存儲棧式存儲堆式存儲第13頁/共62頁mcy15靜態(tài)存儲分配允許程序出現(xiàn)_______。遞歸過程可變體積的數(shù)據(jù)項目靜態(tài)變量待定性質(zhì)的名字第14頁/共62頁mcy16第7章運行時環(huán)境7.1程序執(zhí)行時的存儲器組織7.2完全靜態(tài)的運行時環(huán)境7.3基于棧的運行時環(huán)境7.4動態(tài)存儲器7.5參數(shù)存儲機制第15頁/共62頁mcy177.3基于棧的運行時環(huán)境7.3.1沒有局部過程的基于棧的環(huán)境在一個所有過程都是全局的、過程定義不允許嵌套，但允許過程的遞歸調(diào)用的程序設(shè)計語言(例如C語言)中，基于棧的動態(tài)運行時環(huán)境有兩個指針：sp:棧頂部(topofstack)指針；對于x86系統(tǒng)來說，它采用sp或esp寄存器存儲棧頂部的地址；第16頁/共62頁mcy18fp(framepoint)指向當(dāng)前活動記錄的控制鏈的指針，對于x86系統(tǒng)，它采用bp或ebp寄存器存儲當(dāng)前活動記錄的控制鏈的地址，其作用如下：1.通過該指針可以訪問當(dāng)前執(zhí)行函數(shù)的局部變量；2.通過該指針可以訪問主調(diào)程序的活動記錄；3.允許在當(dāng)前的被調(diào)函數(shù)執(zhí)行完畢時，用它來恢復(fù)主調(diào)函數(shù)的活動記錄。第17頁/共62頁mcy19b:2a:1該函數(shù)調(diào)用結(jié)束時的返回地址(cs:eip)00401353主調(diào)函數(shù)的控制鏈(main.fp)C語言當(dāng)前執(zhí)行函數(shù)的活動記錄示例(函數(shù)調(diào)用分析中的舉例)c:3spfp棧底棧頂?shù)?8頁/共62頁mcy20當(dāng)一個過程被調(diào)用時，在棧頂為該過程分配所需的數(shù)據(jù)空間(過程活動記錄)如下：將實參的值壓入在該函數(shù)對應(yīng)的新活動記錄中。將被調(diào)函數(shù)執(zhí)行完畢后的返回地址壓入在新的活動記錄中。完成到被調(diào)用的過程的代碼一個轉(zhuǎn)移。將主調(diào)函數(shù)的fp作為控制鏈壓入到新的活動記錄中。改變fp以使其指向新的活動記錄(將sp復(fù)制到該fp中)將該函數(shù)的局部變量和局部臨時變量壓入到新的活動記錄中。第19頁/共62頁mcy21b:2a:1該函數(shù)調(diào)用結(jié)束時的返回地址(cs:eip)00401353主調(diào)函數(shù)的控制鏈(main.fp)C語言當(dāng)前執(zhí)行函數(shù)的活動記錄示例：c:3sp棧底棧頂fp第20頁/共62頁mcy22當(dāng)被調(diào)函數(shù)執(zhí)行完畢返回時，其對應(yīng)的活動記錄從棧中彈出的過程：①將fp復(fù)制到sp中。②將控制鏈裝載到fp中。③完成到返回地址主調(diào)函數(shù)的一個轉(zhuǎn)移。④改變sp以彈出實參。第21頁/共62頁mcy23例：計算兩個非負(fù)整數(shù)的最大公約數(shù)的c代碼如下：#include<studio.h>intx,y;intgcd(intu,intv){if(v==0)returnu;elsereturngcd(v,u%v)}main(){scanf(“%d%d”,&x,&y);printf(“%d\n”,gcd(x,y));return0;}第22頁/共62頁mcy24x:15y:10全局/靜態(tài)區(qū)域main的活動記錄sp,fpv:10u:15返回地址main的fp第一次調(diào)用gcd時的活動記錄sp,fp第二次調(diào)用gcd時的活動記錄v:5u:10返回地址第一次調(diào)用gcd時的fp第三次調(diào)用gcd時的活動記錄v:0u:5返回地址第二次調(diào)用gcd時的fpsp,fpsp,fp棧生長方向自由空間第23頁/共62頁mcy25例：考慮下列程序清單的c代碼。intx=2;voidg(int);voidf(intn){staticintx=1;g(n);x--;}voidg(intm){inty=m-1;if(y>0){f(y);x--;g(y);}}main(){g(x);return0;}畫出第二次對g調(diào)用時，程序的運行時環(huán)境：第24頁/共62頁mcy26x:2x（fromf）:1全局/靜態(tài)區(qū)域main的活動記錄sp,fpm:2返回地址main的fpy:1第一次調(diào)用g時的活動記錄fpsp第一次調(diào)用f時的活動記錄n:1

返回地址第一次調(diào)用g時的fpsp,fp第二次調(diào)用g時的活動記錄m:1返回地址第一次調(diào)用f時的fpy:0fpsp棧生長方向自由空間第25頁/共62頁mcy27目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的代碼。對名字的訪問如何處理可變長度的問題局部臨時變量嵌套聲明第26頁/共62頁mcy28對名字的訪問：在沒有局部過程的基于棧的運行時環(huán)境中，所有的非局部的名字都是全局的，因此也就是靜態(tài)的，都具有一個固定的靜態(tài)地址，可以被直接訪問。對函數(shù)參數(shù)和局部變量而言，在大多數(shù)的語言中，每個局部聲明的偏移量仍是可有編譯程序靜態(tài)地計算出來，因為過程的聲明在編譯時是固定的，而且為每個聲明分配的存儲器大小也根據(jù)其數(shù)據(jù)類型而固定。第27頁/共62頁mcy29m:2返回地址控制鏈

y:1fpmOffsetyOffsetmOffset=+8yOffset=-4高端地址低端地址第28頁/共62頁mcy30例：考慮下面的C過程Viodf(intx,charc){inta[10];doubley;

……}對f調(diào)用的活動記錄為：cx

返回地址控制鏈a[9]…a[1]a[0]yfpxOffsetaOffsetcOffsetyOffsetxOffset=+8cOffset=+12aOffset=-40yOffset=-48現(xiàn)在對a[i]訪問，要求計算地址：(-40+4*i)(fp)第29頁/共62頁mcy31目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的代碼。對名字的訪問如何處理可變長度的問題局部臨時變量嵌套聲明第30頁/共62頁mcy32處理可變長度的數(shù)據(jù)有時編譯程序必須處理數(shù)據(jù)變化的可能性，表現(xiàn)在數(shù)據(jù)對象的數(shù)量和每個對象的大小上。發(fā)生在支持基于棧的環(huán)境的語言中的兩種情況如下：①調(diào)用中的自變量的數(shù)量可根據(jù)調(diào)用的不同而不同。②數(shù)組參數(shù)或局部數(shù)組變量的大小可根據(jù)調(diào)用的不同而不同。printf("%d%s%c",n,prompt,ch);printf("Hello,world\n");通常，C編譯程序一般通過把調(diào)用的自變量按相反順序(inreverseorder)壓入到運行時棧來處理這一點。第31頁/共62頁mcy33目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的代碼。對名字的訪問如何處理可變長度的問題局部臨時變量嵌套聲明第32頁/共62頁mcy34局部臨時變量：考慮C表達(dá)式：x[i]=(i+j)*(i/k+f(j))在這個表達(dá)式從左到右的求值計算中，在對f的調(diào)用過程中需要保存中間結(jié)果：x[i]的地址、i+j的和、i/k的商。這些中間值可計算到寄存器中，根據(jù)寄存器進(jìn)行保存和恢復(fù)；或者可將它們作為臨時變量存儲在對f調(diào)用之前的運行時棧中。如下所示：第33頁/共62頁mcy35…

返回地址控制鏈…x[i]的地址i+j的結(jié)果i/j的結(jié)果fp(棧的其余部分)sp臨時棧調(diào)用f（將要創(chuàng)建的）時的新活動記錄包含表達(dá)式過程的活動記錄自由空間第34頁/共62頁mcy36目標(biāo)代碼的生成必須支持變量和臨時變量的實際定位，并增加支持運行時環(huán)境所必需的代碼。對名字的訪問如何處理可變長度的問題局部臨時變量嵌套聲明第35頁/共62頁mcy37嵌套聲明：嵌套聲明也出現(xiàn)了與局部臨時變量同樣的問題?？紤]以下的C代碼：Voidp(intx,doubley){chara;inti;

…A:{doublex;intj;

…}

…B:{char*a;intk;

…}

…}第36頁/共62頁mcy38一個簡單的處理辦法是按照與臨時表達(dá)式相類似的辦法在嵌套的塊中處理聲明，并在進(jìn)入塊時在棧中分配它們。x:y:

返回地址控制鏈a:i:x:j:fp(棧的其余部分)sp塊A的分配區(qū)調(diào)用p時的活動記錄自由空間當(dāng)進(jìn)入塊A后，運行時棧如下所示：第37頁/共62頁mcy39x:y:

返回地址控制鏈a:i:a:k:fp(棧的其余部分)sp塊B的分配區(qū)調(diào)用p時的活動記錄自由空間當(dāng)進(jìn)入塊B后，運行時棧如下所示：第38頁/共62頁mcy40第7章運行時環(huán)境7.1程序執(zhí)行時的存儲器組織7.2完全靜態(tài)的運行時環(huán)境7.3基于棧的運行時環(huán)境7.4動態(tài)存儲器7.5參數(shù)存儲機制第39頁/共62頁mcy417.4.1對象類型在大多數(shù)面向?qū)ο蟮恼Z言中，對象都有構(gòu)造函數(shù)和析構(gòu)函數(shù)，它們分別在創(chuàng)建對象和釋放對象時被調(diào)用。如果這就是全部內(nèi)容的話，那么對象的實現(xiàn)將非常簡單。假定我們有一對象類A，它有方法m1,m2以及字段a1和a2。那么類A對象的運行時表示有包含字段a1和a2記錄組成：a1a2m1_Am2_A另外，編譯程序維護(hù)著一張類A的編譯時方法表：7.4動態(tài)存儲器第40頁/共62頁mcy42在上述簡單的模塊中，字段選擇可以像記錄字段選擇一樣實現(xiàn)，方法選擇由編譯程序內(nèi)的識別過程來實現(xiàn)。即通過一個指向?qū)ο蟮闹羔?，方法可以像函?shù)一樣實現(xiàn)。因此方法m2_A可以翻譯為c語言中的函數(shù)。

voidm2_A(class_A*this,inti){

方法m2_A的程序體，通過this->x訪問任一對象字段x}方法的調(diào)用a.m2(3)可以翻譯成m2_A(&a,3)第41頁/共62頁mcy43繼承特性現(xiàn)在假定類B通過增添方法m3和字段b1來擴(kuò)展類A,那么類B的運行時表示如下：a1a2m1_Am2_Ab1另外類B的方法編譯時表如下：m3_B第42頁/共62頁mcy44方法重載假定上例中類B重新定義了方法m2，那么A中方法m2的定義既是它唯一的聲明也是它的第一次定義，而它在類B中的定義為重定義。為使名字既可以反映聲明它的類，也可以反映定義它的類。方法的名字可有三部分組成：方法名、聲明方法的類名、定義方法類名。各部分之間用下劃線（—）分開。因此在類A中聲明在類B中定義的方法m2其名字記為m2_A_B。方法重載影響方法的編譯時表，現(xiàn)在類A的方法的編譯時表如下：m1_A_Am2_A_Am1_A_Am2_A_Bm3_B_B類B的方法的編譯時表如右：第43頁/共62頁mcy45現(xiàn)在假定a是類A的一個對象，而b是類B的一個對象。方法調(diào)用a.m2(…)將翻譯成對m2_A_A的調(diào)用，而方法調(diào)用b.m2(…)將翻譯成對m2_A_B的調(diào)用。m2_A_A在類A中聲明和定義。m2_A_B在類A中生明，在類B中定義。如果繼承是語言中唯一的面向?qū)ο蟮奶卣鳎敲磎2_A_A翻譯形式為：voidm2_A_A(Class_A*this,inti);而m2_A_B的翻譯形式為：voidm2_A_B(Class_B*this,inti);第44頁/共62頁mcy46多態(tài)性當(dāng)類B繼承類A并且該語言允許“類B的指針”類型的指針能夠賦給一個“類A的指針”類型的變量時，那么該語言支持多態(tài)型。例如：ClassB*b=…;ClassA*a=b;則第二行被翻譯成：classA*a=convert_ptr_to_B_to_ptr_to_A(b);現(xiàn)在，過程convert_ptr_to_B_to_ptr_to_A()為一編譯時類型的操作,它將指向子類B的一個對象指針轉(zhuǎn)換為指向其父類A對象的指針。因為類B的對象也是從類A的字段開始，因而指針的值并不需要改變，唯一影響的是改變了指針的類型：第45頁/共62頁mcy47a1a2b1指向B的指針指向B中A的指針但要注意，現(xiàn)在同一指針指向了不同類的對象第46頁/共62頁mcy48動態(tài)綁定：因為類型classA*的指針p可能實際上引用了類B的一個對象，動態(tài)綁定認(rèn)為如果實際上為類B的對象，那就應(yīng)該調(diào)用m2_A_B,如果實際為A的對象，那么就應(yīng)該調(diào)用m2_A_A.對于方法調(diào)用P->m2(3),p是一指向類A對象指針，可以被翻譯成如下形式：switch(dynamic_type_of(p)){caseDynamic_class_A:m2_A_A(p,3);break;caseDynamic_class_B:m2_A_B(convert_ptr_to_A_to_ptr_to_B(p),3);break;}當(dāng)p為一指向類B對象指針時，可以立即將p->m2(3)調(diào)用翻譯為：m2_A_B(p,3);第47頁/共62頁mcy49動態(tài)綁定對于方法P->m2(3)的更好翻譯方法為：如果p是一指向類A對象指針，則進(jìn)行如下處理有：(dynamic_type_of(p)==Dynamic_Class_A?m2_A_A:m2_A_B)(p,3);如果指針p實際上引用了類B的一個對象，則執(zhí)行步驟2中的方法。voidm2_A_B(Class_A*this_A,inti){Class_B*this=convert_ptr_to_A_to_ptr_to_B(this_A);方法m2_A_B的程序體，通過this->x訪問任一對象字段x}如果p是一指向類B對象指針，則進(jìn)行如下處理有：m2_A_B(convert_ptr_to_B_to_ptr_to_A(p),3);執(zhí)行的方法同上述的步驟2；第48頁/共62頁mcy50對于上述的翻譯方法，每一個對象的類型信息實現(xiàn)為一個指向分派表的指針，如下圖所示(分派表是存儲方法地址的記錄，下圖分派表存儲的是方法m1_A_A，m2_A_B和m1_B_B的地址)a1a2b1指向B的指針指向B中A的指針m1_A_Am2_A_Bm3_B_B類B對象的表示分派表B-objectB-class第49頁/共62頁mcy517.4.2堆管理對于允許程序為變量在運行時動態(tài)申請和釋放存儲空間的語言,采用堆式分配是最有效的解決方案.堆式分配的基本思想是,為運行的程序劃出適當(dāng)大的空間(稱為堆Heap),每當(dāng)程序申請空間時,就從堆的空閑區(qū)找出一塊空間分配給程序,每當(dāng)釋放時則回收之.第50頁/共62頁mcy52在C中處理鏈表等結(jié)構(gòu)時,常常隨機地插入或刪除一些結(jié)點,利用指針變量和結(jié)構(gòu)類型,可動態(tài)地生成新結(jié)點(使用malloc()函數(shù)),或刪除之(使用free()函數(shù)).例如structnode{chardata;structnode*next;}定義了鏈表的結(jié)點,下面函數(shù)可在表的尾部添加新結(jié)點:

voidAppend(structnode*head,charch){structnode*p=head;while(*p)p=p->next;p->next=malloc(sizeof(structnode));p->next->data=ch;p->next->next=NULL;}還可用下面的函數(shù)在表頭刪除一結(jié)點:voidDelete(structnode*head){structnode*p=head;if(*p){head=head->next;free(p);}}堆分配的必要性第51頁/共62頁mcy53將存儲空間劃分為若干存儲塊;用戶可隨機地申請或釋放一個或多個塊;在存儲空間中建立兩個隊列:空閑隊列和忙隊列,空閑隊列拉成鏈,鏈?zhǔn)子肍REE指針指明,忙隊列用一(已占塊)記錄表記錄各占用塊的首址及大小信息(也可用鏈進(jìn)行記錄).申請時可按需要找到合適的塊分配之(分配策略有最佳分配或隨機分配等);釋放時將該塊插入到空閑隊列(能合并時可合并),并從占用記錄表中刪除相應(yīng)的項.堆存儲管理的實現(xiàn)第52頁/共62頁mcy54第7章運行時環(huán)境7.1程序執(zhí)行時的存儲器組織7.2完全靜態(tài)的運行時環(huán)境7.3基于棧的運行時環(huán)境7.4動態(tài)存儲器7.5參數(shù)存儲機制第53頁/共62頁mcy557.5參數(shù)傳遞機制值傳遞值傳遞的處理方法是：進(jìn)入過程時,送入形參對應(yīng)的形式單元的是相應(yīng)實參的值;過程體中對形參的任何賦值都按對形式單元的直接訪問來產(chǎn)生代碼。因此,一旦把實參之值送入對應(yīng)形式單元之后,在執(zhí)行過程體期間,除了以實參值作為形參的初值進(jìn)行運算之外,將不再與實參發(fā)生任何聯(lián)系。由此可見,過程執(zhí)行的結(jié)果決不會改變實參之值。voidinc2(intx)/*incorrect!*/{++x;++x;}voidinc2(int*x)/*nowok*/{++(*x);++(*x);}第54頁/共62頁mcy56引用傳遞控制轉(zhuǎn)入被調(diào)過程后,由被調(diào)過程將實參的地址寫入相應(yīng)的形式單元。過程體中對形式參數(shù)的任何引用或賦值,都按對相應(yīng)形式單元間接訪問的尋址方式為其產(chǎn)生代碼。顯然,執(zhí)行過程時,型參就變成了實參的別名，對形參的賦值將會影響相應(yīng)實參之值。在C++中，是通過在參數(shù)說明中使用特殊字符&來得到引用傳遞：voidinc2(int&x)/*C++referenceparameter*/{++x;++x;}第55頁/共62頁mcy57引用傳遞不要求復(fù)制被傳遞的值，這與值傳遞不同。當(dāng)要復(fù)制的值是一個較大的結(jié)構(gòu)時，如果禁止自變量的值有任何變化，在這種情況下，引用傳遞能夠做到值傳遞而無需覆蓋值的拷貝。在C++中可將調(diào)用寫作：voidf(constMuchData&x)其中的MuchData是帶有大型結(jié)構(gòu)的數(shù)據(jù)類型。這仍是引用傳遞，但是編譯程序還必須執(zhí)行一個靜態(tài)檢查：x從不出現(xiàn)在一個賦值的左邊或是被改變。第56頁/共62頁mcy58已知C程序：#include<