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

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

expressionVariable

procedureFunction

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

bytes

wordsRegistersStack

addressRoutine(sub

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

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

and

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

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

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

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

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

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

名字/名稱type

類型location

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

byteintegers:

2

or

4

bytesfloats:

4

to

16

bytesbooleans:

1

bit

(but

usually

1

byte)valuecomponent

成分指針：unsigned

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

簡(jiǎn)單的棧式分配方案4

嵌套過(guò)程的棧式分配方案4

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

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

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

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

A(m,n:integer);begin

real

z;array

B[m:n];begin·

·

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

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

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

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

形參（形式單元）l

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

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

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

M調(diào)用過(guò)程Pz

RAz

DLz

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

R……end

R;proc

Q……end

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

end

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

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

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

program

sort(input,

output);//sort的過(guò)程頭procedure

readarray;

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

var

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

//readarray的過(guò)程體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的過(guò)程體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的過(guò)程體//sort的例程體例子1（簡(jiǎn)略圖）//sort的例程體的簡(jiǎn)略視圖begin………readarray{

var

i:

integer;…對(duì)a的訪問(wèn)…}exchange{

…對(duì)a的訪問(wèn)…}quicksort{

var

k,v:

integer;partition{

var

i.j:integer;…對(duì)a的訪問(wèn)…}}end只要一個(gè)函數(shù)在調(diào)用點(diǎn)前出現(xiàn)過(guò)，則可以對(duì)該函數(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，因?yàn)樗莙私有的。因此一個(gè)函數(shù)被激活的時(shí)候，它的外層都處于激活狀態(tài)，也就是說(shuō)在棧中有活動(dòng)記錄。因此不會(huì)出現(xiàn)p被調(diào)用時(shí)，找不到quicksort的活動(dòng)記錄。（p只可能在q中被調(diào)用）例子1（問(wèn)題）過(guò)程readarray,exchange和partition中引用的a均不是它們的局部變量，而是過(guò)程sort的局部變量。假如過(guò)程sort激活(調(diào)用)了過(guò)程quicksort,這時(shí)存儲(chǔ)棧中的情形示意如圖，其中在quicksort過(guò)程活動(dòng)記錄中有一(或一些)存儲(chǔ)單元(用斜線描繪)用以記錄過(guò)程

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

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

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

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

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

(d)sort→quicksort→quicksort→partition→exchange例子2：用Display表解決對(duì)非局部量的引用程序結(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表解決對(duì)非局部量的引用(1)main--->(2)P--->(3)Q--->(4)R（3）（4）主程序的活動(dòng)記錄d[0]spdisplaytop（1）P

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

的活動(dòng)記錄P

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

的活動(dòng)記錄Q

的活動(dòng)記錄P

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