北大編譯原理講義chapter61

1、1 第六章 運(yùn)行時(shí)刻環(huán)境 序6.1 源語言中的一些問題6.2 存儲組織6.3 運(yùn)行時(shí)刻存儲分配策略6.4 非局部名字的訪問6.5 參數(shù)傳遞6.6 符號表2 序 計(jì)算環(huán)境 運(yùn)行時(shí)的環(huán)境 計(jì)算 目標(biāo)代碼 源程序中的名字（常量，變量）目標(biāo)機(jī)存儲空間。它受命于源程序的執(zhí)行語義。 源程序由一組過程按某種規(guī)則組成。過程的一次執(zhí)行稱作一次活動，在過程的語句序列執(zhí)行之前，過程中訪問的對象構(gòu)成此過程的運(yùn)行環(huán)境，由運(yùn)行支持程序組織好。編譯程序根據(jù)如何組織運(yùn)行環(huán)境而生成目標(biāo)代碼。映射源程序36.1有關(guān)源程序中的一些問題有關(guān)源程序中的一些問題 目的： 構(gòu)造運(yùn)行程序的策略和方法 6.1.1 過程 6.1.2 活動樹 6

2、.1.3 控制棧 6.1.4 說明的作用域 6.1.5 名字的綁定 6.1.6 構(gòu)造運(yùn)行程序和源程序有關(guān)的 一些問題46.1.1 過程 源程序由一組過程組成，不同的程序設(shè)計(jì)語言，由過程構(gòu)成源程序的方法不同。 構(gòu)成源程序的兩個(gè)過程行文，要么是嵌套的，要么是不相交的。5program sort（input，output）； var a ： array0.10 of integer； procedure readarray； var i ： integer； begin end； function partition （y ，z ： integer ）:integer； var i，j ，x，v：

3、integer； begin end; procedure quicksort（m，n ： integer）； var i ： integer； begin end end； begin end.66.1.2 活動樹活動樹 程序執(zhí)行期間的控制流： 1程序執(zhí)行的控制是順序的； 2過程的每一次執(zhí)行都是從過程體的開頭 開始，并最終把控制返回到緊接著該過 程被調(diào)用點(diǎn)的后面。 過程的一次活動: 過程體的每一次執(zhí)行。 一個(gè)過程p的一次活動的生存期:在該過程體的執(zhí)行中的第一步和最后一步之間的一序列步驟的執(zhí)行時(shí)間，其中包括執(zhí)行過程p所調(diào)用的過程的執(zhí)行時(shí)間，以及這些過程所調(diào)用的過程的執(zhí)行時(shí)間，如此等等。7 特點(diǎn)

4、： 每當(dāng)控制流從過程p的活動進(jìn)入到過程q的活動中后，它將返回到過程p的同一次活動中。 如果a和b是兩個(gè)過程活動，那么它們的生存期要么是不重疊的，要么是嵌套的。 這種活動生存期的嵌套性質(zhì)可以通過在每一個(gè)過程中插入兩個(gè)打印語句來加以說明。8執(zhí)行開始 enter readarray leave readarray enter quicksort（1，9） enter partition（1，9） leave partition（l，9） enter quicksort（1，3） . leave quicksort（1，3) enter quicksort（5，9） . leave quicksort

5、（5，9） leave quicksort（1，9） 執(zhí)行結(jié)束9 一個(gè)過程是遞歸的，如果同一過程的一次新的活動可以在前面活動結(jié)束以前開始。 用一顆樹來描繪控制進(jìn)入和離開活動的途徑。這祥的樹稱作活動樹。在一棵活動樹中： 1. 每一個(gè)結(jié)點(diǎn)代表一個(gè)過程的活動; 2. 根結(jié)點(diǎn)代表主程序的活動; 3. 代表a的結(jié)點(diǎn)是b結(jié)點(diǎn)的父結(jié)點(diǎn)當(dāng)且僅當(dāng)控 制從活動a進(jìn)入活動b; 4. 結(jié)點(diǎn)a在結(jié)點(diǎn)b的左邊當(dāng)且僅當(dāng)a的生存期 發(fā)生在b的生存期之前。 用活動樹來討論正在這個(gè)結(jié)點(diǎn)上的控制 。 10srq(1,9)p(1,9)q(1,3)p(1,3)q(1,0)q(2,3)p(2,3)q(2,1)q(3,3)q(5,9)p(

6、5,9)q(5,5)q(7,9)p(7,9)q(7,7)圖6.3 一棵活動樹11結(jié)論：一個(gè)結(jié)點(diǎn)代表一個(gè)唯一的活動， 且每 一個(gè)活動只有一個(gè)結(jié)點(diǎn)表示，當(dāng)控制進(jìn) 入某一個(gè)活動時(shí)，可以直接說，控制在 這個(gè)結(jié)點(diǎn)上。6.1.3 控制棧 程序執(zhí)行的控制流對應(yīng)于從根開始，按先根次序遍歷活動樹。因此，用一個(gè)棧保存過程活動的生存蹤跡。把它稱作控制棧。 當(dāng)一個(gè)活動開始執(zhí)行時(shí)，把代表這個(gè)活動的結(jié)點(diǎn)推進(jìn)棧；當(dāng)這個(gè)活動結(jié)束時(shí)，把代表這個(gè)活動的結(jié)點(diǎn)從棧中彈出。12例6.2 棧和活動樹的變化棧ssrs rq(1,9)s q(1.9)p(1,9)s q(1.9) p(1,9)q(1,3)s q(1.9) q(1,3)p(1,

7、3)s q(1.9) q(1,3) p(1,3)q(1,0)s q(1.9) q(1,3) q(1,0)q(2,3)s q(1.9) q(1,3) q(2,3)圖 6.413 控制棧中的活動都是活躍的，當(dāng)前控制進(jìn)入的活動在棧頂，從棧頂活動到棧底活動的活動序列是從活動樹上當(dāng)前結(jié)點(diǎn)通向根的路徑上的結(jié)點(diǎn)序列： s,q（1，9），q（l，3），q（2，3） 從棧底活動到棧頂活動的活動序列表示了活動的生存期的嵌套關(guān)系。 結(jié)論結(jié)論：擴(kuò)充控制?？捎脕韺?shí)現(xiàn)如pascal語言的棧式存儲分配，進(jìn)入一個(gè)活動，在棧頂建立這個(gè)活動所使用的存儲空間；這個(gè)活動結(jié)束，從棧頂彈出其使用的存儲空間。146.1.4 說明的作用域說

8、明的作用域 1 .說明明把名字與名字的屬性信息綁定在一起。 2 . 說明的作用域是一個(gè)說明起作用的范圍 （源程序行文）。一個(gè)名字在源程序行文中 可能有幾處說明，語言的作用域規(guī)則規(guī)定： 在語句序列中引用的一個(gè)名字是在何處說 明的名字。 3 . 編譯時(shí)，處理說明把名字及其屬性信息填 寫進(jìn)符號表(add(id.entry,id.vul); 處理引用 名字時(shí)，查找這個(gè)名字的屬性信息 （lookup(id),符號表管理程序根據(jù)語 言的 作用域規(guī)則，使 lookup(id)返回id的作作用域 中綁定的屬性信息。156.1.5名字與存儲的綁定名字與存儲的綁定 名字與存儲單元的綁定是指把源程序中的數(shù)據(jù)名字映射

9、到目標(biāo)機(jī)存儲單元的過程。 引進(jìn)兩個(gè)函數(shù)，environment和state。environment把名字映射到一個(gè)存儲單元上；state把存儲單元映射到那里所存放的值上?？梢哉f，函數(shù)environment把一個(gè)名字映射為一個(gè)l-value（左-值）,而函數(shù)state把一個(gè)l-value（左-值）映射為一個(gè)r-value（右-值）。如圖6.5所示。16名字存儲單元值存儲分配程序運(yùn)行environmentstatel-valuer-value圖6.5 從名字到值的兩個(gè)階段映射17靜態(tài)概念 動態(tài)對應(yīng)過程定義 過程活動名字說明 名字的綁定說明的作用域 活動的生存期186.1.6 提出的問題提出的問題

10、編譯程序組織存儲分配所采用策略和方法主要取決于對源程序中下面的問題的回答。 1過程可以是遞歸的嗎？ 2當(dāng)控制從過程的一次活動返回時(shí)，局部 名的值將發(fā)生什么 變化? 3一個(gè)過程可以訪問非局部名嗎？ 4當(dāng)調(diào)用過程時(shí)參數(shù)是怎樣傳遞的？ 5過程可以作為參數(shù)被傳遞嗎？ 6過程可以作為結(jié)果被返回嗎？ 7. 可以在程序控制下進(jìn)行動態(tài)存儲分配嗎？ 8. 顯式的存儲重新分配（指撤除分配后的分 配）是必須的嗎？ 19例：函數(shù)的返回值是函數(shù)。fun times x y=x*y val times=fn: int (int int) twice=times 2fun compose(f, g)=f(g(x) comp

11、ose=fn: ( ) ( )val fourtimes=compose(twice,twice)206.2 存儲組織存儲組織 6.2.1 運(yùn)行時(shí)刻內(nèi)存的劃分運(yùn)行時(shí)刻內(nèi)存的劃分 運(yùn)行時(shí)刻的存儲空間必須劃分以用來存放: 1. 生成的目標(biāo)代碼; 2. 數(shù)據(jù)目標(biāo); 3. 用于保存過程活動蹤跡的一個(gè)控制棧。 存儲空間劃分的各部分：21目標(biāo)代碼靜態(tài)數(shù)據(jù)棧堆1. 編譯后知道目標(biāo)代 碼的大小。2. pascal主程序中的 數(shù)據(jù),c,fortran3. 棧:pascal,c4. 堆: pascal,c226.2.2 活動記錄活動記錄 把過程的一個(gè)活動所需要的信息組織成一塊連續(xù)的存儲單元，稱為活動記錄。 一個(gè)活

12、動所需要的信息的每個(gè)數(shù)據(jù)項(xiàng)有相同的生存期，因此，組織成一個(gè)活動記錄是很自然的。 對于pascal語言來說，運(yùn)行過程中，當(dāng)調(diào)用一個(gè)過程時(shí)，在棧頂構(gòu)筑它的活動記錄；當(dāng)這個(gè)過程的活動執(zhí)行完后，把它從棧頂彈出。 源語言不同，實(shí)現(xiàn)方法不同，組成活動記錄的域不同。實(shí)現(xiàn)pascal語言的活動記錄如圖6.7所示。23返回值實(shí)在參數(shù)控制鏈訪問鏈保存機(jī)器狀態(tài)局部數(shù)據(jù)臨時(shí)變量控制鏈:指向調(diào)用過程活動 的活動記錄。訪問鏈：指向本活動要訪 問的非局部數(shù)據(jù)所在的 活動記錄。保存機(jī)器狀態(tài)：調(diào)用過程 活動在調(diào)用點(diǎn)的機(jī)器 狀態(tài)，包括計(jì)數(shù)器， 各種寄存器的值。局部數(shù)據(jù)：過程中定義的 局部量。臨時(shí)變量：編譯產(chǎn)生。246.2.3 編

13、譯時(shí)刻的局部數(shù)據(jù)的設(shè)計(jì)編譯時(shí)刻的局部數(shù)據(jù)的設(shè)計(jì) 局部數(shù)據(jù)域是編譯時(shí)刻在分析過程中的說 明時(shí)設(shè)計(jì)的。例如： procedure sub(x,y:real); var i ,j:integer; a:array1.5 of real; e, f : real; begin f :=e+i*j; end;25符號表名字 形 類型 偏移量活動記錄布局返回值(top-sp,0) x 形 real 1(top-sp,1) y 形 real 2(top-sp,2)(top-sp,3)(top-sp,20) i int 20(top-sp,21) j int 21(top-sp,22) a array 22(

14、top-sp,27) e real 27(top-sp,28) f real 2826中間代碼* i j t1 * (top-sp ,20) (top-sp ,21) (top-sp ,29) + e t1 t2 + (top-sp ,27) (top-sp ,29) (top-sp ,30) itor t2 t3 itor (top-sp ,30) (top-sp ,31):= t3 f := (top-sp ,31) (top-sp ,28) 編譯結(jié)束，知道每個(gè)過程的活動記錄的長度，將其填寫到相應(yīng)的過程表中，運(yùn)行時(shí)，調(diào)用哪個(gè)過程，就在運(yùn)行棧頂，推進(jìn)那個(gè)過程的活動記錄（棧箭頭加上活動記錄長度

15、）。276.3 運(yùn)行時(shí)刻存儲分配策略運(yùn)行時(shí)刻存儲分配策略 分配策略是： 1靜態(tài)分配； 2棧式分配，或稱棧式動態(tài)分配； 3堆式分配，或稱堆式動態(tài)分配。 6.3 .1 靜態(tài)存儲分配 6.3 .2 棧式存儲分配 6.3 .3 堆式存儲分配 采用哪種分配策略是由源語言的語義決定的。286.3 .1 靜態(tài)存儲分配 在編譯時(shí)刻為每個(gè)數(shù)據(jù)項(xiàng)目確定出在運(yùn)行時(shí)刻的存儲空間中的位置，且這種綁定在運(yùn)行時(shí)刻不再發(fā)生變化。 局部名字的值在過程活動停止后仍保留下來。 限制： 1.在編譯時(shí)刻知道數(shù)據(jù)目標(biāo)的大小和它們在 內(nèi)存位置上 約束； 2.不能遞歸調(diào)用過程（一個(gè)過程的兩個(gè)活動 的生存期不相交,一個(gè)過程的所有活動可以 使用

16、同一個(gè)活動記錄）； 3.不能動態(tài)地建立數(shù)據(jù)結(jié)構(gòu)。29 （1）program cnsume （2） character *50 buf （3） integer next （4 character c，prduce （5） data next1，buf/ / （6） cprduce（）。 （7） buf（next：next）c （8 nextnext1 （9） if（c.ne. )goto 6 （10） write（*，(a)）buf （11） end 30(12）character function prduce（） （13) character * 80 buffer （14） integer

17、 next （15） save buffer，next (16) data next81 （17） if(next.gt.80）then （18) read（*，（a)buffer （19） next1 （20) end if （21） prducebuffer（next：next） （22 ) nextnext1 （23 ) end 圖圖6.8 一個(gè)一個(gè)fortran 77程序程序 31cnsume目標(biāo)代碼prduce目標(biāo)代碼char *50 buf int next char cchar *80 buffer int next cnsume活動記錄prduce活動記錄目標(biāo)代碼靜態(tài)數(shù)據(jù)326

18、.3.2 棧式存儲分配棧式存儲分配 基于控制棧的原理：存儲空間被組織成棧，活動記錄的推人和彈出分別對應(yīng)于活動的開始和結(jié)束。 與靜態(tài)分配不同的是，在每次活動中把局部名字和新的存儲單元綁定，在活動結(jié)束時(shí)，活動記錄從棧中彈出，因而局部名字的存儲空間也隨之消失。 例6.5 圖6.11表明當(dāng)控制流通過圖6.3的活動樹時(shí)活動記錄被推人或彈出運(yùn)行時(shí)刻的棧中的情況，設(shè)寄存器top標(biāo)記棧頂。33ssa:arraytoprri:integertoptopq(1,9)q(1,9)i:integertopp(1,9)p(1,9)i:integertoptopq(1,3)q(1,3)i:integertop圖 6.11

19、 棧式分配活動記錄在棧中的變化34 確定活動記錄中局部數(shù)據(jù)的地址：假設(shè)top-sp標(biāo)記一個(gè)活動記錄的開始的位置， dx表示x的地址相對于top-sp的偏移量。那么， x在過程的目標(biāo)代碼中的地址可寫成 dx（top-sp）在運(yùn)行時(shí)刻，當(dāng)把x的活動記錄筑于棧頂時(shí)，寄存器top- sp被賦于實(shí)際的地址， top- sp可以是一個(gè)寄存器。調(diào)用序列和返回序列調(diào)用序列和返回序列 通過在目標(biāo)代碼中生成調(diào)用序列和返回序列實(shí)現(xiàn)過程的調(diào)用。激活一個(gè)過程的活動是執(zhí)行35過程語句的結(jié)果。過程語句 p(e1,e2,en)的目標(biāo)代碼（調(diào)用序列）完成任務(wù)： 1. 調(diào)用者對實(shí)在參數(shù)求值，并把它們傳送給 被調(diào)用過程的活動記錄的參數(shù)域。 2調(diào)用者在被調(diào)用者的活動記錄中存放返 回地址和老top-sp之值。之后調(diào)用者把 top一sp之值增加到圖6.12所示的位置。 3被調(diào)用者存放寄存器值和其它狀態(tài)信息。 4被調(diào)用者初始化其局部數(shù)據(jù)并開始執(zhí)行。36返回序列，return目標(biāo)代碼完成的任務(wù)是： 1被調(diào)用者在自己的活動記錄的返回值域 中放一個(gè)返回值。 2利用狀態(tài)域中的信息，被調(diào)用者