• /  86
  • 下載費用: 24.9積分  

東北大學秦皇島分校編譯原理課件 第十章.ppt

'東北大學秦皇島分校編譯原理課件 第十章.ppt'
第十章 目標程序運行時的組織 10.1 概述2數據表示10.3目標程序運行時的棧式存儲組織10.4 參數傳遞10.5堆式存儲組織的討論概述代碼生成前如何安排目標機資源運行時組織的幾個問題數據表示-如何在目標機中表示每個源語言類型的值表達式求值-如何組織表達式的計算存儲分配-如何組織不同作用域變量的存儲過程實現-如何以例程實現過程,函數,參數傳遞 概述 任務:編譯程序對目標程序運行時的組織(設計運行環境和分配存儲) 如 通常存儲區布局可為: 目標代碼區 靜態數據區 Stack heap 決定運行管理復雜程度的因素——源語言本身1. 允許的數據類型的多少2.語言中允許的數據項是 靜態確定 動態確定3.程序結構 決定名字的作用域的規則和結構A. 段結構B. 過程定義不嵌套,只允許過程遞歸調用C. 分程序結構分程序嵌套過程定義嵌套 4存儲類別的多少GlobalStaticLocaldynamic術語靜態:如果一個名字的性質通過說明語句或隱或顯規則而定義,則稱這種性質是“靜態”確定的。動態:如果名字的性質只有在程序運行時才能知道,則稱這種性質為“動態”確定的。數據表示各種數據對象的存儲分配數據對象的屬性 name 名字,名稱 type 類型 location 內存地址 value 值 component 成分 數據表示(固定長度,直接或間接表示)簡單變量: char: 1 byteintegers: 2 or 4 bytesfloats: 4 to 16 bytesbooleans: 1 bit (but usually 1 byte)指針:unsigned integers一維數組:一塊連續的存儲區多維數組:一塊連續的存儲區,按行存放結構(記錄):把所有域(field)存放在一塊連續的存儲區對象:類的實例變量象結構的域一樣存放在一塊連續的存儲區, 但方法(成員函數)不存在該對象里指令:l 可變 (動態)數組: 若一個數組所需的存儲空間的大小在編譯時就已知道,則稱它為確定數組,否則稱為可變(動態)數組。數組內情向量:: 編譯將數組的有關信息記錄在一些單元中,稱為數組的“內情向量”A[l 1:u 1,l 2:u 2, ,ln : un] l1 u1 l2 u2 : : type a(首地址) n C目標程序運行時的存儲組織存儲分配策略:簡單的棧式分配方案 嵌套過程的棧式分配方案 分程序結構的存儲分配方案靜態存儲分配動態存儲分配——棧式堆式l 術語-過程活動記錄AR:為說明方便,假定程序是由過程組成,過程區分為源文本,運行時稱作過程的激活。一個過程的一次執行所需要的信息使用一個連續的存儲區來管理,這個區 (塊)叫做一個活動記錄或frame(幀)一般這個段要記錄:l 臨時值,如計算表達式時的中間工作單元。l 局部變量(數據)l 保存運行過程前的狀態(返回地址,寄存器值……)l 存取鏈(可選) 對于非局部量的引用。l 控制鏈(可選) 指向調用者的活動記錄,釋放棧。l 實參(形式單元)l 返回值(對函數)(有時可使用寄存器存放返回值) 簡單的棧式分配方案 程序結構特點:過程定義不嵌套,過程可遞歸調用,含可變數組; 例: main 全局變量的說明proc R……end R;proc Q…… end Q;主程序執行語句 end main 嵌套過程語言的棧式 分配方案 主要特點:(語言)一個過程可以引用包圍它的任一外層過程所定義的標識符(如變量,數組或過程等)。(實現)一個過程可以引用它的任一外層過程的最新活動記錄中的某些數據。 關鍵技術:解決對非局部量的引用(存?。?。設法跟蹤每個外層過程的最新活動記錄AR的位置。跟蹤辦法: 1. 用靜態鏈(如PL/0的SL)。 2. 用DISPLAY表。const a=10; var b,c; procedure p; begin c:=b+a; end; begin read(b); while b#0 do begin call p; write(2*c); read(b); end end. ( 0) jmp 0 8 轉向主程序入口( 1) jmp 0 2 轉向過程p入口( 2) int 0 3 過程p入口,為過程p開辟空間( 3) lod 1 3 取變量b的值到棧頂( 4) lit 0 10 取常數10到棧頂( 5) opr 0 2 次棧頂與棧頂相加( 6) sto 1 4 棧頂值送變量c中( 7) opr 0 0 退棧并返回調用點(16)( 8) int 0 5 主程序入口開辟5個??臻g( 9) opr 0 16 從命令行讀入值置于棧頂(10) sto 0 3 將棧頂值存入變量b中(11) lod 0 3 將變量b的值取至棧頂(12) lit 0 0 將常數值0進棧(13) opr 0 9 次棧頂與棧頂是否不等(14) jpc 0 24 等時轉(24)(條件不滿足轉)(15) cal 0 2 調用過程p(16) lit 0 2 常數值2進棧(17) lod 0 4 將變量c的值取至棧頂(18) opr 0 4 次棧頂與棧頂相乘(2*c)(19) opr 0 14 棧頂值輸出至屏幕(20) opr 0 15 換行(21) opr 0 16 從命令行讀取值到棧頂(22) sto 0 3 棧頂值送變量b中(23) jmp 0 11 無條件轉到循環入口(11)(24) opr 0 0 結束退棧目標代碼解釋執行時數據棧的布局(運行棧的存儲分配)每個過程的AR有3個聯系單元:SL: 靜態鏈,指向定義該過程的直接外過程 (或主程序)運行時最新數據段的基地址。。省略部分。小從大到小排序。只需從鏈表中刪除第一個結點,并將其中一部分分配給用戶,而其它部分作為一個新的結點插入到空閑塊表的適當置上去。 減少碎片的技術1分配時,找最小的足夠大的塊---需保持空閑塊的大小排序2 釋放時,合并任何相鄰的塊---搜索全部空閑塊表,或其它算法3 將堆變量緊縮在一起空間的釋放1顯式釋放2隱式(自動)釋放顯式釋放程序設計語言提供機制 如:pascal 的 dispose C 的free程序員必須編寫分配和釋放存儲的明確的調用注意的問題 1 堆變量是不可訪問的(垃圾) 2 懸掛(不安全)指針堆式分配和釋放的C語言描述#define NULL 0# define MEMSIZE 8096 /* change for different sizes */typedef fdouble Align;typedef union header {struct {union header *next; unsigned usedsize; unsigned freesize;}s;Align a;}Header;//數據類型Header保存每個存儲塊的簿記信息 static Header mem [MEMSIZE];static Header *memptr= NULL;void *malloc (unsigned nbytes){Header *p, *newp;unsigned nunits;nunits= (nbytes+sizeof (Header)-1/ sizeof (Header)+1;if (memptr == NULL){memptr->s. next = memptr = mem;memptr->s. usedsize = 1;memptr->s. freesize = MEMSIZE-1;}for (p=memptr;(p->s. next!= memptr) &&(p->s. freesize s. next);if (p->s. freesize nunits) return NULL;/* no block big enough */newp = p+p->s. usedsize;newp->s. usedsize= nunits;newp->s. freesize = p->s. freesize-nunits;newp->s.next = p->s. next;p->s. freesize=0;p->s. next= newp;memptr=newp;return (void *)(newp+1);}void free (void *ap){Header * bp, *p, *prev;bp= (Header *) ap –1;for (prev= memptr, p=memptr->s. next;(p!=bp) &&(p!= memptr); prev=p, p=p->s. next);if (p!=bp) return;/* corrupted list, do nothing */prev->s. freesize += p->s. usedsize + p->s. freesize;prev->s. next = p->s. next;memptr = prev;}堆的自動管理-----隱式存儲回收在一種需要完全動態的運行時環境的語言(OO語言,函數式語言Lisp,ML)中,堆也必須類似地自動管理。自動存儲器管理涉及到了前面分配的但不再使用的存儲器的回收,可能是在它被分配的很久以后,而沒有明確的對free的調用。這個過程稱作垃圾回收(grabage collection)。 垃圾回收垃圾回收程序---尋找可被引用的所有存儲器并釋所有未引用的存儲器。在存儲塊不再引用時,無論是直接還是通過指針間接的引用,識別這些存儲塊是一項比維護堆存儲 的列表復雜得多的任務。方法---對malloc的調用失敗,激活垃圾回收程序垃圾回收算法 mark and sweep隱式存儲回收—mark and sweep算法 隱式存儲回收要求用戶程序和支持運行的回收子程序并行工作,因為回收程序需要知道分配給用戶程序的存儲塊何時不再使用。為了實現并行工作,在存儲塊中要設置回收子程序訪問的信息。 存儲塊格式: 塊長度訪問計數標記指針用戶使用空間回收過程分為兩個階段。 (1)第一個階段為標記階段,對已分配的塊跟蹤程序中各指針的訪問路徑。如果某個塊被訪問過,就給這個塊加一個標記。(2)第二個階段為回收階段,所有未加標記的存儲塊回收到一起,并插入空閑塊鏈表中,然后消除在存儲塊中所加的全部標記。面向對象的語言中的動態存儲器面向對象的語言在運行時環境中要求特殊的機制以完成其增添的特性:對象、方法、繼承以及動態聯編。面向對象語言在對運行時方面的要求差異很大。Smalltalk要求與LISP相似的完全動態環境C++則保持C的基于棧的環境實現對象實現對象的一個簡單機制是,初始化代碼將所有當前的繼承特征(和方法)直接地復制到記錄結構中(將方法當作代碼指針)。但這樣做極浪費空間。另外一種方法是在執行時將類結構的一個完整的描述保存在每個點的存儲器中,并由超類指針維護繼承性(有時這也稱作繼承圖(inheritance graph))。接著同用于它的實例變量的域一起,每個對象保持一個指向其定義類的指針,通過這個類就可找到所有(局部和繼承的)的方法。此時,只記錄一次方法指針(在類結構中),而且對于每個對象并不將其復制到存儲器中。由于是通過類繼承的搜索來找到這個機制的,所以該機制還實現繼承性與動態聯編。其缺 在于:雖然實例變量具有可預測的偏移量(正如在標準環境中的局部變量一樣),方法卻沒有,而且它們必須由帶有查詢功能的符號表結構中的名字維護。這是對于諸如Smalltalk的高度動態語言的合理的結構,因為類結構可以在執行中改變。C++中選擇的方法將整個類結構保存在環境中,計算出每個類的可用方法的代碼指針列表,并將其作為一個虛擬函數表(virtual function table)而存放在(靜態)存儲器。它的優點在于:可做出安排以使每個方法都有一個可預測的偏移量,而且也不再需要用一系列表查詢遍歷類的層次結構?,F在每個對象都包括了一個指向相應的虛擬函數表而不是類結構的指針(當然,這個指針的位置必須也有可預測的偏移量)。例C++類聲明:class A{public:double x,y;void f();virtual void g();};class B:public A{public:double z;void f();virtual void h();};類A的一個對象應出現在存儲器中(帶有它的虛擬函數表)  而類B的一個對象則應如下所示: xyvtpA::gB::hA::gXYvtpz
關 鍵 詞:
分校 秦皇島 編譯 第十 原理 東北大學
 天天文庫所有資源均是用戶自行上傳分享,僅供網友學習交流,未經上傳用戶書面授權,請勿作他用。
關于本文
本文標題:東北大學秦皇島分校編譯原理課件 第十章.ppt
鏈接地址: http://www.476824.live/p-51497199.html
關于我們 - 網站聲明 - 網站地圖 - 資源地圖 - 友情鏈接 - 網站客服點擊這里,給天天文庫發消息,QQ:1290478887 - 聯系我們

本站為“文檔C2C交易模式”,即用戶上傳的文檔直接賣給(下載)用戶,本站只是中間服務平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有【成交的100%(原創)】。本站是網絡服務平臺方,若您的權利被侵害,侵權客服QQ:1290478887 歡迎舉報。

[email protected] 2017-2027 http://www.476824.live 網站版權所有

粵ICP備19057495號 

收起
展開
球探网即时蓝球比分 江苏体彩七位数 北京11选五开奖走势图 湖南幸运赛车开奖结果 山西新11选5走势图表i 湖北11选5任二最大遗漏 山东体彩快乐扑克开奖结果走势图 河南11选5 七乐彩2020010期开奖结果 广东快乐10分稳赢 2020股票分析报告