運行環(huán)境RunTimeEnvironm.ppt

第8章 運行環(huán)境 (Run-Time Environments),主要內(nèi)容,綁定（Binding） 存儲(Storage)組織(Organization)與分配(Allocation) 參數(shù)(Parameter)傳遞(Passing) 過程說明與調(diào)用 符號表(Symbol Table)管理,8.1 綁定（Binding）,Binding的概念 將符號名和相應(yīng)目標(biāo)數(shù)據(jù)(的地址)對應(yīng)起來 標(biāo)識符與數(shù)據(jù)目標(biāo)的對應(yīng) 變量名數(shù)據(jù)存儲單元地址 過程名、函數(shù)名程序段入口地址 相關(guān)問題 變量和過程的作用域，決定綁定的有效期,分段式程序 Program layer Int a,b,c Begin Sub(a+b,b,a) End Subroutine Sub(x,y,z) Real a,b,c Begin End,嵌套式程序 Program layer Int a,b,c Procedure Sub1(x,y,z) Int x,y,z Procedure add(a,b) Real a,b Begin Real x,y,z x=a y=x*2+b z=1/y End Begin End Procedure Sub2(x,y) Begin end,綁定的時機與策略,語言定義的標(biāo)識符的生存期決定最終綁定的時機 全局變量：全程有效程序裝入時 局部變量：分段有效進(jìn)入過程或分程序時,變量名的綁定,靜態(tài)(Static)綁定：編譯時指定（相對地址） 詞法分析期間在符號表中建立變量的表項 回憶：說明語句的語義分析：字節(jié)數(shù)計算，填寫變量地址 動態(tài)(Dynamic)綁定：運行時指定（具體地址/相對地址） 如：動態(tài)數(shù)組,過程/函數(shù)名的綁定,為過程指定程序代碼段入口地址 靜態(tài)綁定：編譯時指定相對地址 （詞法分析：在符號表中建立過程的表項） 語義分析：構(gòu)造目標(biāo)代碼，填寫過程的入口地址 如：一般的函數(shù)、子例程 動態(tài)綁定 運行時指定函數(shù)名作為形式參數(shù)（formals） 如：函數(shù)指針、虛函數(shù)（C+）,8.2 存儲組織與分配(P257),運行時刻的內(nèi)存劃分(Partition) 局部數(shù)據(jù)的靜態(tài)分配(Static Allocation) 局部數(shù)據(jù)的動態(tài)分配(Dynamic Allocation) 層次單元法 棧式(Stack)存儲分配策略 堆式(Heap)存儲分配策略,運行時刻的內(nèi)存劃分,局部數(shù)據(jù)區(qū)中的一個棧單元 活動記錄(靜態(tài)/動態(tài)分配),靜態(tài)存儲分配,特點 編譯時刻確定存儲位置 訪問效率高 主要用途 子程序的目標(biāo)代碼段 全局?jǐn)?shù)據(jù)目標(biāo)（全局變量） ？用什么樣的算法實現(xiàn)靜態(tài)存儲分配,靜態(tài)存儲分配策略介紹,順序分配算法 按照程序段出現(xiàn)的先后順序逐段分配,程序段 區(qū)域 021 2236 3754 5571 7294 95104 共需要105個存儲單元,程序段之間的調(diào)用關(guān)系程序段號/所需數(shù)據(jù)空間,能用更少的空間么？,分層分配算法,允許程序段之間的覆蓋（覆蓋可能性分析）,程序段 區(qū)域 6 09 5 022 4 016 3 2340 2 1731 1 4162 共需要63個存儲單元,思考：如何設(shè)計分配算法？,7/80,靜態(tài)存儲分配無法克服的問題1,動態(tài)數(shù)組問題 層次單元法 層次單元 標(biāo)準(zhǔn)單元的使用,靜態(tài)存儲分配無法克服的問題2,遞歸調(diào)用問題 棧式存儲分配,棧（Stack）式存儲分配,用途 過程的局部環(huán)境 活動記錄 特點 嵌套調(diào)用次序 先進(jìn)后出 生存期限于本次調(diào)用 自動釋放,活動記錄,活動記錄,活動記錄,運行棧,過程數(shù)據(jù)區(qū)結(jié)構(gòu),SPn SPn-1 SP1 SP0,SP,SPn為第n層過程數(shù)據(jù)區(qū)首址,靜態(tài)存儲分配無法克服的問題3,被調(diào)用者的生存期超過調(diào)用者/局部數(shù)據(jù)需要保留（ save ） 堆式存儲分配,堆（Heap）式存儲分配,用于動態(tài)數(shù)據(jù)結(jié)構(gòu) 存儲空間的動態(tài)分配和釋放 實現(xiàn)方法： 將內(nèi)存空間分為若干塊，根據(jù)用戶要求分配 無法滿足時，調(diào)用無用單元收集程序?qū)⒈会尫诺膲K收集起來重新分配,8.3 參數(shù)傳遞,傳值調(diào)用 call-by-value 過程調(diào)用時計算實參(Actual)，將值存到活動記錄 形參(Formal)綁定于活動記錄的實參域,引用調(diào)用 Call-by-Reference/Address 如果實在參數(shù)具有左值，則存放其左值到活動記錄中；否則計算出表達(dá)式的值，將此值存入一個單元，并將該單元的地址傳給被調(diào)用者。,復(fù)制恢復(fù) Copy-Restore,將參數(shù)的左、右值同時傳給被調(diào)用者，被調(diào)用者直接使用右值，并將計算結(jié)果按照左值返回給調(diào)用者,傳名調(diào)用Call-by-Name,將被調(diào)過程的過程體復(fù)制到調(diào)用處，并將每一個形參“文字地”替換成實參 用換名子程序?qū)崿F(xiàn)Thunk 是一種早期的語言ALGOL用的一種參數(shù)傳遞方式,上次課主要內(nèi)容,回填技術(shù) S if C then S1 的翻譯 C.true := newlabel; S1.next := S.next; C.false:= S.next; S.code := C.code |gen( C.true: ) |S1.code,上次課主要內(nèi)容,S if C then S1 else S2 的翻譯 C.true := newlabel; C.false := newlabel; S1.next := S2.next := S.next; S.code := C.code | gen( C.true: )| S1.code | gen( goto S.next ) | gen( C.false: ) | S2.code,上次課主要內(nèi)容,S while C do S1翻譯 S.begin := S1.next := newlabel; C.true := S1.begin := newlabel; C.false := S.next; S.code := gen( S.begin: ) | C.code | gen( C.true: ) | S1.code | gen( gotoS.begin ),上次課主要內(nèi)容,運行環(huán)境 綁定：靜態(tài)、動態(tài) 靜態(tài)分配 動態(tài)分配 層次單元法 棧式(Stack)存儲分配策略 堆式(Heap)存儲分配策略,上次課主要內(nèi)容,參數(shù)傳遞 傳值調(diào)用 call-by-value 引用調(diào)用 Call-by-Reference/Address 復(fù)制恢復(fù) Copy-Restore 傳名調(diào)用Call-by-Name,子程序 P(X,Y,Z); Y:=Y+1; Z:=Z+X,傳值調(diào)用： 2,傳地址： X=T=5,Y=Z=A=2 A:=A+1=2+1 A:=A+T=3+5 8,換名 A:=A+1=3 A:=A+A+B=3+3+3 9,主程序 A:=2; B:=3; P(A+B, A, A); Print A,臨時單元: T:A+B=5,8.4 過程調(diào)用,過程(procedure) 子程序(subroutine)、函數(shù)(function) 過程的定義與調(diào)用 形參和實參的結(jié)合：參數(shù)計算與傳遞 調(diào)用與返回,工作方式,調(diào)用方：當(dāng)前環(huán)境的保存與恢復(fù) 被調(diào)方：構(gòu)造環(huán)境，參數(shù)綁定,過程調(diào)用實現(xiàn),簡單過程調(diào)用 實在參數(shù)的計算和保存 控制轉(zhuǎn)移、返回地址的保存 實在參數(shù)和形式參數(shù)的結(jié)合(多種結(jié)合方式) 局部變量的處理 返回值的處理 遞歸過程調(diào)用與過程參數(shù) 每層過程調(diào)用信息的保存與相應(yīng)信息的查找,活動記錄中過程所用信息,用于表達(dá)式的計算 局部數(shù)據(jù) 寄存器、程序計數(shù)器（返回地址） 保存實在參數(shù)的值或地址 存放返回值 保存調(diào)用者活動記錄地址等(SP) 用于存取嵌套外層過程中的非局部名(Display),訪問鏈,控制鏈,返回值,實在參數(shù),機器狀態(tài),局部變量,臨時變量,例子函數(shù)的活動記錄,int sub( i, p ) int i; char *p; char buf32; bufi = *(p + i); return i + 1; ,過程說明語句的翻譯,分析參數(shù)的類型、分配地址 統(tǒng)計參數(shù)和返回值的空間需求 與調(diào)用語句配合完成形/實參數(shù)的結(jié)合 符號表處理 完成過程名的屬性登記,說明語句： Procedure id(X1,X2,Xn),過程說明語句代碼結(jié)構(gòu),說明語句： Procedure id(X1,X2,Xn),代碼結(jié)構(gòu) X1.code 按參數(shù)傳遞要求實現(xiàn)參數(shù)X1的傳遞，或者完成傳遞準(zhǔn)備； X2.code 按參數(shù)傳遞要求實現(xiàn)參數(shù)X2的傳遞，或者完成傳遞準(zhǔn)備； Xn.code 按參數(shù)傳遞要求實現(xiàn)參數(shù)Xn的傳遞，或者完成傳遞準(zhǔn)備； 完成動態(tài)存儲分配相關(guān)的工作； 進(jìn)入過程體,過程調(diào)用語句的代碼結(jié)構(gòu),過程調(diào)用語句id(E1,E2, ,En),E1.code a1:=E1.place En.code an:=En.place 動態(tài)存儲分配相關(guān)工作 goto pc+n+1 param a1 param an call id.place，n,需要一個隊列存放a1, a2, , an，以生成,過程調(diào)用的實現(xiàn),1) 在過程 f 中調(diào)用過程 p 時 a. f 對實在參數(shù)求值，將結(jié)果存入 p 的活動記錄參數(shù)域 b. 在 p 的活動記錄中存放返回地址和當(dāng)前棧頂指針 c. 按照活動記錄的大小，上移棧頂指針 d. 控制轉(zhuǎn)到 p 的入口（過程體）,e. p 存放寄存器值和其它狀態(tài)信息 f. 執(zhí)行過程體 2. 從過程 p 返回：對應(yīng)return語句 a. p 在返回值域中保存返回值 b. 恢復(fù)原棧頂指針和其它寄存器 c. 按返回地址返回調(diào)用者,過程調(diào)用語句的制導(dǎo)翻譯定義,產(chǎn)生式 語義規(guī)則 S call id ( Elist ) S.code := Elist.code |gen(goto pc+Elist.num+1)| for 隊列q中的每一項 t do gen(param t ) | gen(call id.place,Elist.num) Elist E Elist.num := 1; Elist.code := E.code | t:=newtemp; gen(t:= E.place)；建立隊列q，并將t 放入q Elist Elist1,E Elist.num := Elist 1.num+1; Elist.code := Elist 1.code | E.code | t:=newtemp; gen(t:= E.place);將t 放入隊列q,生成的目標(biāo)代碼 t1 := 3 + a goto pc+3 param t1 param 6 call f, 2,函數(shù)調(diào)用 f(3+a,6)的翻譯,函數(shù)調(diào)用 f(b*c-1,x+y,x,y)的翻譯,t1:=b*c t2:=t1-1 t3:=x+y goto pc+5 param t2 param t3 param x param y call f, 4,賦值語句x:=a+b+ f(b*c-1,x+y,x,y)的翻譯,t1:=a+b t2:=b*c t3:=t1-1 t4:=x+y goto pc+5,param t3 param t4 param x param y call f.place, 4 t5:=t1+f.val x:=t5,8.4 符號表管理,種類 關(guān)鍵字表、層次表、符號表（過程表、變量表、標(biāo)號表）、常數(shù)表,關(guān)鍵字表,表項結(jié)構(gòu) 關(guān)鍵字標(biāo)識 (整數(shù)) 關(guān)鍵字名字 (字符串，如“while“，“if“) 常用的操作： int IsKeyword( char Name ),層次表,保存各級分程序、循環(huán)語句、條件語句的有關(guān)信息 如：局部名字、轉(zhuǎn)移標(biāo)號等 輔助實現(xiàn)標(biāo)識符的管理 標(biāo)識符的作用域,符號表,保存名字及其屬性 名字：變量名，過程名，標(biāo)號名和常數(shù)名 屬性：種類（Kind），類型（Type），長度，作用域，標(biāo)志（引用/定義），地址等 種類：簡單變量、數(shù)組、記錄、結(jié)構(gòu)、函數(shù)、常數(shù)、常量 類型：整、實、復(fù)、布爾、字符、指針、標(biāo)號,符號表的作用,作用 記錄源程序