編譯原理 第19講(第十章)- -

第十章目標(biāo)程序運行時的組織概述數(shù)據(jù)表示目標(biāo)程序運行時的棧式存儲組織參數(shù)傳遞堆式存儲概述10.1概述-代碼生成解決語義gap高級語言支持的概念Type value

expressionVariable

procedureFunction

parameters目標(biāo)機(jī)支持的概念bits

bytes

wordsRegistersStack

addressRoutine(sub

routine)概述在代碼生成前，編譯程序必須進(jìn)行目標(biāo)程序運行環(huán)境的配置和數(shù)據(jù)空間的分配。一般來講，假如從操作系統(tǒng)中得到一塊存儲區(qū)以使目標(biāo)程序在其上運行，該存儲區(qū)需容納生成的目標(biāo)代碼和目標(biāo)代碼運行時的數(shù)據(jù)空間。數(shù)據(jù)空間應(yīng)包括：用戶定義的各種類型的數(shù)據(jù)對象（變量和常數(shù)）所需的存儲空間，作為保留中間結(jié)果和傳遞參數(shù)的臨時工作單元，調(diào)用過程時所需的連接單元，以及組織輸入/輸出所需的緩沖區(qū)。目標(biāo)代碼所占用空間的大小在編譯時能確定。有些數(shù)據(jù)對象所占用的空間也能在編譯時確定，其地址可以編譯進(jìn)目標(biāo)代碼中。而有些數(shù)據(jù)對象具有可變體積和待分配性質(zhì)，無法在編譯時確定存儲空間的位置。概述運行時的存儲區(qū)常常劃分成：目標(biāo)區(qū)、靜態(tài)數(shù)據(jù)區(qū)、棧區(qū)和堆區(qū)，如下圖就是一種典型劃分，代碼(code)區(qū)用以存放目標(biāo)代碼，這是固定長度的，即編譯時能確定的；靜態(tài)數(shù)據(jù)區(qū)(static

data)用以存放編譯時能確定所占用空間的數(shù)據(jù)；堆棧區(qū)(stack

and

heap)用于可變數(shù)據(jù)以及管理過程活動的控制信息。目標(biāo)代碼區(qū)靜態(tài)數(shù)據(jù)區(qū)

Stackheap概述代碼生成前如何安排目標(biāo)機(jī)資源運行時組織的幾個問題數(shù)據(jù)表示-如何在目標(biāo)機(jī)中表示每個源語言類型的值表達(dá)式求值-如何組織表達(dá)式的計算存儲分配-如何組織不同作用域變量的存儲過程實現(xiàn)-如何以例程實現(xiàn)過程，函數(shù)，參數(shù)傳遞允許的數(shù)據(jù)類型的多少語言中允許的數(shù)據(jù)項是靜態(tài)確定動態(tài)確定3．程序結(jié)構(gòu)(決定名字的作用域的規(guī)則和結(jié)構(gòu))A

．段結(jié)構(gòu)(Fortran)B

．過程定義不嵌套，只允許過程遞歸調(diào)用C

．分程序結(jié)構(gòu)分程序嵌套過程定義嵌套4．存儲類別的多少GlobalStaticLocaldynamic決定運行管理復(fù)雜程度的因素—源語言本身靜態(tài)：如果一個名字的性質(zhì)通過說明語句或隱或顯規(guī)則而定義，則稱這種性質(zhì)是“靜態(tài)”確定的。動態(tài)：如果名字的性質(zhì)只有在程序運行時才能知道，則稱這種性質(zhì)為“動態(tài)”確定的。10.2

數(shù)據(jù)表示各種數(shù)據(jù)對象的存儲分配數(shù)據(jù)對象的屬性name

名字/名稱type

類型location

內(nèi)存地址值簡單變量：char:1

byteintegers:

2

or

4

bytesfloats:

4

to

16

bytesbooleans:

1

bit

(but

usually

1

byte)valuecomponent

成分指針：unsigned

integers一維數(shù)組：一塊連續(xù)的存儲區(qū)多維數(shù)組：一塊連續(xù)的存儲區(qū)，按行存放結(jié)構(gòu)（記錄）：把所有域（field)存放在一塊連續(xù)的存儲區(qū)對象：類的實例變量象結(jié)構(gòu)的域一樣存放在一塊連續(xù)的存儲區(qū)，但方法（成員函數(shù)）不存在該對象里指令：10.3目標(biāo)程序運行時的存儲組織存儲分配策略：靜態(tài)存儲分配動態(tài)存儲分配——棧式和堆式注：可以混合使用4

簡單的棧式分配方案4

嵌套過程的棧式分配方案4

分程序結(jié)構(gòu)的存儲分配方案4

堆式存儲靜態(tài)存儲分配這種存儲分配非常簡單，如果在編譯時能確定目標(biāo)程序運行中所需的全部數(shù)據(jù)空間的大小，編譯時安排好目標(biāo)程序運行時的全部數(shù)據(jù)空間，確定每個數(shù)據(jù)對象的存儲位置，稱這種分配策略為靜態(tài)存儲分配。靜態(tài)存儲分配舉例FORTRAN語言由主程序段和若干子程序段組成。各程序

段中定義的名字一般是彼此獨立的，也即各段的數(shù)據(jù)對象名的作用域在各段中，同一個名字在不同的程序段表示不同的存儲單元，不會在不同段間互相引用、賦值。另外它的每個數(shù)據(jù)名所需的存儲空間大小都是常量（即不許含可變體積的數(shù)據(jù)，如可變數(shù)組)。這樣，整個程序所需數(shù)據(jù)空間的總量在編譯時完全確定，從而每個數(shù)據(jù)名的地址就可靜態(tài)進(jìn)行分配。靜態(tài)存儲分配舉例PROGRAM

CNSUMECHARACTER

*

50

BUFINTEGER

NEXT//程序體所擁有的靜態(tài)量BUF//程序體所擁有的靜態(tài)量NEXTCHARACTER

C,PRDUCE//程序體所擁有的靜態(tài)量CDATA

NEXT

/1/,

BUF

/

‘

’

/6

C=PRDUCE()BUF(NEXT:NEXT)=CNEXT=NEXT+1IF(C

.EN.

‘

’

)GOTO

6(10)WRITE

(

*

,‘

(A)’

)BUFENDCHARACTER

FUNCTION

PRDUCE()(13)(14)(15)CHARACTER

*

80

BUFFERINTEGER

NEXTSAVE

BUFFER,

NEXT//PRDUCE函數(shù)體所擁有的靜態(tài)量BUFFER,NEXTDATA

NEXT

/81/IF

(NEXT

.GT.80)THEN,‘

(A)’

)BUFFERREAD

(

*NEXT=1END

IF(16)(17)(18)(19)(20)(21)(22)PRDUCE=BUFFER(NEXT:NEXT)NEXT=NEXT+1(23)

END在Fortran

90之前的Fortran

版本都沒有遞歸.有遞歸則不能進(jìn)行靜態(tài)存儲分配動態(tài)存儲分配如果一個程序設(shè)計語言允許遞歸過程、可變數(shù)組或允許用戶自由申請和釋放空間，那么，就需要采用動態(tài)存儲管理技術(shù)。因為對于這種程序在編譯時無法知道它在運行時需要多大的存儲空間，它所需要的數(shù)據(jù)空間的大小需待程序運行時動態(tài)地確定。動態(tài)存儲分配舉例若一個數(shù)組所需的存儲空間的大小在編譯時就已知道，則稱它為確定數(shù)組，否則稱為可變數(shù)組。procedure

A(m,n:integer);begin

real

z;array

B[m:n];begin·

·

·end;end;B[m:n]為可變數(shù)組，B的上下界是過程A的實參，A被調(diào)用時才能確定。使用malloc為說明方便，假定源程序是由過程組成，運行時稱作過程的激活。一個過程的一次執(zhí)行所需要的信息，使用一個連續(xù)的存儲區(qū)來管理這個區(qū)（塊），叫做一個活動記錄AR或frame幀一般這個區(qū)AR要記錄：（運行棧的存儲分配）l

臨時值（如計算表達(dá)式時的中間工作單元。）l

局部變量（數(shù)據(jù)）l

保存運行過程前的狀態(tài)（返回地址，寄存器值……）l

形參（形式單元）l

返回值（RA對函數(shù)，有時可使用寄存器存放返回值）l

存取鏈（SL可選，對于非局部量的引用。）l

控制鏈（DL可選，指向調(diào)用者的活動記錄，釋放棧。）術(shù)語--過程活動記錄AR目標(biāo)代碼的解釋執(zhí)行(運行棧S)4

M調(diào)用過程Pz

RAz

DLz

SLz.z.ztzbztzPzMzb10.3.1簡單的棧式分配方案4程序結(jié)構(gòu)特點:過程定義不嵌套，過程可遞歸調(diào)用，含可變數(shù)組;例:main4全局變量的說明proc

R……end

R;proc

Q……end

Q;主程序執(zhí)行語句4

end

main演示函數(shù)調(diào)用退出時sp和top的變化Main---->Q---R->

Main--->Q---->QTOSPTOP---->臨時工作單元局部簡單變量局部數(shù)組的內(nèi)情向量保存運行過程前的狀態(tài)（返回地址，寄存器值……）實參（形式單元）和參數(shù)個數(shù)SP----->控制鏈（老SP）P

----->R的數(shù)組區(qū)R的活動記錄>Q的數(shù)組區(qū)Q的活動記錄主程序全局?jǐn)?shù)據(jù)區(qū)Q的數(shù)組區(qū)Q的活動記錄Q的數(shù)組區(qū)Q的活動記錄主程序全局?jǐn)?shù)據(jù)區(qū)10.3.2嵌套過程語言的棧式分配方案主要特點：4（語言）一個過程可以引用包圍它的任一外層過程所定義的標(biāo)識符（如變量，數(shù)組或過程等）。4（實現(xiàn)）一個過程執(zhí)行時可以引用它的任一外層過程的最新活動記錄中的某些數(shù)據(jù)。我們所熟悉的PASCAL語言程序結(jié)構(gòu)的特點是允許過程嵌套定義，一個過程可以引用包圍它的任一外層過程所定義的標(biāo)識（如變量，數(shù)組或過程等）。它的存儲分配也看成是采用棧式動態(tài)分配策略，只是它的過程活動記錄中應(yīng)增設(shè)一些內(nèi)容，用以解決對非局部變量的引用問題。（回憶簡單棧式存儲分配：局部量＋全局量）例子1(1)

program

sort(input,

output);//sort的過程頭procedure

readarray;

//sort內(nèi)嵌套定義的readarray的過

var

i:integer;begin…a…end{readarray};

//readarray的過程體procedure

exchange(i,j:integer);//sort內(nèi)嵌套定義的exchangevar

a:

array

[0..10]

of

integer;x:

integer;(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)beginx∶=a[i];a[i]∶=a[j];a[j]∶=x;//exchange的過程體end{exchange};procedurequicksort(m,n:integer);//sort內(nèi)嵌套定義的quicksvar

k,v:integer;function

partition(y,z:integer):integer;//quicksort內(nèi)嵌套定義的partition的函var

i.j:integer;//partition的函數(shù)體begin…a……v…exchange(i,j);end{partition};(14)(15)(16)(17)(18)(19)(20)begin…end{quicksort};(21)

begin…end{sort}//quicksort的過程體//sort的例程體例子1（簡略圖）//sort的例程體的簡略視圖begin………readarray{

var

i:

integer;…對a的訪問…}exchange{

…對a的訪問…}quicksort{

var

k,v:

integer;partition{

var

i.j:integer;…對a的訪問…}}end只要一個函數(shù)在調(diào)用點前出現(xiàn)過，則可以對該函數(shù)進(jìn)行var

a:array[0..10]of

integer;x:in調(diào)te用ge。r;sort可以調(diào)用r,e,q（在哪里？）quicksort中可以調(diào)用partition（在哪里？）partition中可以調(diào)r，e，q但是在s,r,e中都不能調(diào)用p，因為它是q私有的。因此一個函數(shù)被激活的時候，它的外層都處于激活狀態(tài)，也就是說在棧中有活動記錄。因此不會出現(xiàn)p被調(diào)用時，找不到quicksort的活動記錄。（p只可能在q中被調(diào)用）例子1（問題）過程readarray,exchange和partition中引用的a均不是它們的局部變量，而是過程sort的局部變量。假如過程sort激活(調(diào)用)了過程quicksort,這時存儲棧中的情形示意如圖，其中在quicksort過程活動記錄中有一(或一些)存儲單元(用斜線描繪)用以記錄過程

quicksort可以引用sort中定義的變量a和x。也就是說，為了解決對非局部量的存取問題，必須設(shè)法跟蹤每個外層過程的最新活動記錄的位置。關(guān)鍵技術(shù)：解決對非局部量的引用（存?。┰O(shè)法跟蹤每個外層過程的最新活動記錄AR的位置。跟蹤辦法：用靜態(tài)鏈（如SL）。用嵌套層次顯示表DISPLAY。用靜態(tài)鏈解決對非局部量的引用（存取）(參見簡略圖)過程exchange由過

程（函數(shù)）partition調(diào)用，但exchange的直接外層過程是sort，所以過程exchange的活動記錄的存取鏈指向sort的活動記錄的始址。如果該程序的某次執(zhí)行順序為(調(diào)用次序)：

sort→quicksort→quicksort→partition→exchange…過程partition中引用了sort中說明的變量a，而partition的直接外層是quicksort，

quicksort的直接外層過程是sort，partitio對非局部量a的引用通過兩次拉鏈實現(xiàn)。存取鏈就是靜態(tài)鏈，控制鏈就是動態(tài)鏈用Display表解決對非局部量的引用（存?。┝硗庖环N存取非局部變量的辦法，也是常用的有效辦法。即每進(jìn)入一個過程后，在建立它的活動記錄的同時建立一張嵌套層次顯示表Display。這里所提到的“嵌套層次”，是指過程定義的層數(shù)，始終假定主程序的層數(shù)為0，因此主程序稱為0層過程。如某過程p是在層次為i的過程q內(nèi)定義的，并且q是包圍p的直接外層，那么p的過程層數(shù)為i+1。一般編譯程序處理過程說明時，將把過程層數(shù)作為重要的屬性登記在符號表中。計數(shù)過程的層數(shù)很容易實現(xiàn)，用一個計數(shù)器Level，初值為0，每遇到過程說明則增1，過程說明結(jié)束則減1.Display是一個指針數(shù)組d，也可看做是一個小棧，自頂向下每個單元依次存放著現(xiàn)行層，直接外層，……直至最外層（0層，主程序?qū)樱┑让恳粚舆^程的最新活動記錄的地址。也即，嵌套層次i的過程的局部變量a是在由Display元素d[i]所指的那個活動記錄中存放的。也就是說，嵌套層次i+1過程中的非局部變量可能在i,i-1,…,0層，對它的存取是通過display元素

d[i],d[i-],…,d[0]而獲得的。例子2假定現(xiàn)在進(jìn)入的過程的層數(shù)為i，則它的display表含有i+1個元素，依次指向現(xiàn)行層、直接外層……直至最外層（0層）等每一層過程的最新活動記錄的地址。假定有如下四種調(diào)用情況：(a)sort→quicksort…;(b)sort→quicksort→quicksort…;(c)sort→quicksort→quicksort→partition…;

(d)sort→quicksort→quicksort→partition→exchange例子2：用Display表解決對非局部量的引用程序結(jié)構(gòu)圖program

main(i,0);……proc

R(c,d);……Rend

/*R*/主proc P

(a);……proc

Q

(b);PQ

callRcall

Qcall

Pcall

R……R(x,y);end

/*Q*/……Q(z);end

/*P*/……P（W

）；……R

（U

，V

）；……end

/*main*/例子3例子3：用Display表解決對非局部量的引用(1)main--->(2)P--->(3)Q--->(4)R（3）（4）主程序的活動記錄d[0]spdisplaytop（1）P

的活動記錄主程序的活動記錄d[1]d[0]displaytopsp（2）Q

的活動記錄P

的活動記錄主程序的活動記錄displayd[2]d[1]d[0]sptopR

的活動記錄Q

的活動記錄P

的活動記錄主程序的活動記錄displayd[1]d[0]topsp例子4現(xiàn)在我們要討論，當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display。為了建立自己的display，P2必須知道它的直接外層過程(記為P的display。這意味著：當(dāng)P1調(diào)用P2時必須把P0的display地址作為連接數(shù)據(jù)一傳給P2。第一個激活的總是主程序，它的display表很簡單，就只有一項，該指向自身的活動記錄的起始地址。（有了初值，有了遞推規(guī)則，那么每個動記錄的display都能構(gòu)造出來。）一般，P0或者就是P1自身或者既是P1又是P2的直接外層(見上圖的(a)、(b)兩種情形)。不論哪一種情形，只要在進(jìn)入P2后能夠知道P1的display就能知道P0的display，從而可直接構(gòu)造出P2的display。事實上，只需從P1的display中自底而上地取過l2個單元(l2為P2的層數(shù))再添上進(jìn)入