編譯原理—存儲分配

1、運(yùn)行時存儲空間的組織第六章 1本章要求主要內(nèi)容：程序的靜態(tài)文本與它運(yùn)行時的活動之間的關(guān)系，源程序運(yùn)行時各種對象的存儲空間主要有三種方式分配方式：靜態(tài)存儲分配、棧式存儲分配和堆式存儲分配重點掌握：源程序運(yùn)行時的活動，參數(shù)傳遞方式，程序中名字的作用域，局部數(shù)據(jù)區(qū)的內(nèi)容，存儲空間的分配方式 26.1 程序執(zhí)行時的活動靜態(tài)和動態(tài)的聯(lián)系名字和數(shù)據(jù)對象數(shù)據(jù)對象的動態(tài)表示名字的作用域數(shù)據(jù)對象的存儲分配過程和活動參數(shù)處理運(yùn)行時支撐程序包3過程相關(guān)的幾個概念過程定義是一個聲明，它的最簡單的形式是把一個標(biāo)識符（過程的名字）和一段語句聯(lián)系起來。 當(dāng)過程名出現(xiàn)在可執(zhí)行語句中時，則稱過程在該點被調(diào)用 出現(xiàn)在過程定義中的

2、標(biāo)識符稱為形式參數(shù)（或形參） 出現(xiàn)在過程調(diào)用中的標(biāo)識符或常數(shù)稱為實在參數(shù)（或?qū)崊ⅲ?4一個過程的一次執(zhí)行指的是從過程體的起點開始，最后退出該過程，將控制返回到該過程被調(diào)用之后的位置。一個過程的活動指的是該過程的一次執(zhí)行。就是說，每次執(zhí)行一個過程體就產(chǎn)生該過程的一個活動。從執(zhí)行該過程體的第一步操作到最后一步操作之間的操作序列所花的時間稱為該過程的一個活動的生存期 5聲明的作用域語言中名字的聲明是把信息與名字聯(lián)系起來的語法結(jié)構(gòu)。區(qū)分同名程序聲明：最接近的嵌套規(guī)則int a , b;int *p;int foo( int a )int b, c;char *p;p = malloc( sizeof(

3、 char ) );b = foo( 1 ); 6作用域：一個聲明起作用的程序部分稱為該聲明的作用域局部和非局部：過程中名字的出現(xiàn)，如果是在該過程的一個聲明的作用域內(nèi)，則這個出現(xiàn)稱為局部于該過程7參數(shù)的傳遞 傳地址（常用）：把實在參數(shù)的地址傳遞給相應(yīng)的形式參數(shù) 傳值（常用）：調(diào)用段把實在參數(shù)的值傳給被調(diào)用段。被調(diào)用段把實參值抄進(jìn)形式單元中，再使用。 得結(jié)果：形式參數(shù)對應(yīng)有兩個單元，第一個單元放實參的地址，第二個單元放實參的值。對形式參數(shù)的任何引用或賦值都看成是對第二個單元的直接訪問，過程返回前必須把第二個單元的內(nèi)容存放到第一個單元所指的那個實參單元之中 傳名：(ALGOL60 )過程調(diào)用相當(dāng)于

4、把被調(diào)過程的過程體抄到調(diào)用出現(xiàn)的位置，把其中任一出現(xiàn)的形式參數(shù)都替換成相應(yīng)的實在參數(shù)（文字替換） 8名字的綁定 靜態(tài)概念動態(tài)概念過程的定義名字的聲明聲明的作用域過程的活動名字的綁定綁定的生命期程序中聲明的名字和動態(tài)數(shù)據(jù)對象的關(guān)系數(shù)據(jù)對象是保存值的存儲單元一個名字可能代表不同的數(shù)據(jù)對象環(huán)境：表示將名字映射到存儲單元（即名字的左值）的函數(shù)狀態(tài)：表示將存儲單元映射到它所保存的值（即名字的右值）的函數(shù)賦值操作只改變狀態(tài)，但不改變環(huán)境結(jié)合：如果環(huán)境把存儲單元s聯(lián)系到名字x，則稱x綁定到s，這個聯(lián)系本身稱為x的綁定9名字綁定要考慮的問題過程是否遞歸當(dāng)控制從過程的活動返回時，局部名字的值是否要保留過程能否引

5、用非局部的名字過程調(diào)用時參數(shù)是如何傳遞的過程是否可以作為參數(shù)被傳遞過程能否作為結(jié)果值返回存儲區(qū)能否在程序控制下動態(tài)地分配存儲區(qū)是否必須顯式地釋放106.2 運(yùn)行時內(nèi)存的劃分程序運(yùn)行時如何使用內(nèi)存：目標(biāo)代碼的存放目標(biāo)代碼可以存放在靜態(tài)確定的區(qū)域，其長度在編譯時即可確定數(shù)據(jù)對象可靜態(tài)分配的數(shù)據(jù)對象，其地址可以編譯到目標(biāo)代碼中動態(tài)分配控制棧：記錄過程活動堆：可以存放動態(tài)分配的數(shù)據(jù)等，但開銷要比棧大過程1的目標(biāo)代碼代碼區(qū)過程2的目標(biāo)代碼過程n的目標(biāo)代碼全局變量和靜態(tài)變量靜態(tài)數(shù)據(jù)棧自由空間堆動態(tài)數(shù)據(jù)11局部數(shù)據(jù)區(qū)的內(nèi)容 活動記錄：過程的依次執(zhí)行所需要的信息用一塊連續(xù)的存儲區(qū)來管理，這塊存儲區(qū)叫做活動記錄

6、或幀并不是所有的語言或編譯器都是如此寄存器的使用活動記錄的操作：過程被調(diào)用時入棧過程返回時出棧12活動記錄的各個域的作用臨時數(shù)據(jù)：臨時變量的存儲等局部數(shù)據(jù)：局部于過程執(zhí)行的數(shù)據(jù)機(jī)器狀態(tài)：保存過程調(diào)用前的機(jī)器狀態(tài)信息返回地址可選的訪問鏈：用于非局部數(shù)據(jù)的訪問可選的控制鏈：指向調(diào)用者的活動記錄實在參數(shù)域：參數(shù)個數(shù)較少時，可以考慮用寄存器傳遞，效率高；參數(shù)多時用用這個域傳遞返回值域：用于存放被調(diào)用過程返回給調(diào)用過程的值，也可以用寄存器返回（效率高，但形式受限制）136.3 存儲分配策略靜態(tài)存儲分配棧式存儲分配堆式存儲分配 14靜態(tài)存儲分配策略名字的綁定：編譯時實現(xiàn)，不需要運(yùn)行時支撐程序名字和存儲的綁

7、定是固定的允許名字的值在過程停止活動后保持根據(jù)名字的類型，編譯器可以在靜態(tài)時刻確定該名字所需的存儲空間，效率局限：數(shù)據(jù)對象的長度和它在內(nèi)存中位置的限制必須在編譯時知道不允許遞歸過程不允許有動態(tài)數(shù)據(jù)結(jié)構(gòu)在FORTRAN77中，靜態(tài)存儲分配策略，每個過程的活動記錄可以與它的代碼放在一起15靜態(tài)存儲分配策略（2）PROGRAM CNSUMECHARACTER * 50BUFINTEGERNEXTCHARACTERC , PRDUCEDATA NEXT / 1 /, BUF / /6C = PRDUCE( )BUF( NEXT , NEXT ) = CNEXT = NEXT + 1IF ( C .NE

8、. ) GOTO 6WRITE( * , ( A ) ) BUFENDCHARACTER FUNCTION PRDUCE( )CHARACTER * 80BUFFERINTEGERNEXTSAVE BUFFER , NEXTDATA NEXT / 81 /IF ( NEXT .GT. 80 ) THENREAD(* , ( A ) ) BUFFERNEXT = 1END IFPRDUCE = BUFFER( NEXT , NEXT )NEXT = NEXT + 1END16棧式存儲分配策略遞歸過程要求棧分配允許動態(tài)數(shù)據(jù)對象的存在滿足先進(jìn)后出的次序控制棧：活動記錄和棧的關(guān)系局部量的存儲空間包含在

9、對應(yīng)調(diào)用的活動記錄中局部量的值回隨著過程調(diào)用結(jié)束而丟失控制棧top的變化和活動記錄的長度相關(guān)通常，局部量相對于活動記錄開始點的偏移量可以記錄在符號表中17棧式存儲分配策略（2）例：例6.1的快速排序程序的活動記錄在棧中的分配Program s； a:的數(shù)據(jù)說明； procedure r; function p； procedure q begin patition; q(m,i-1); q(i+1,n); end;begin r(); q(1,9);18堆式存儲分配策略棧分配的局限不能使得活動停止時，局部名字的值保持被調(diào)用者的活動不能比調(diào)用者的活動活得更長，只能滿足先入后出的次序堆分配把連續(xù)存儲區(qū)域分成塊需要時分配（活動記錄或其它對象）釋放次序任意堆可以與棧分配結(jié)合起來C+語言中，基本保持棧的