【文章內(nèi)容簡(jiǎn)介】 終指向已占用的棧頂單元。這種語言若含有可變數(shù)組。這里把控制鏈也稱作老SP，即調(diào)用該過程的那個(gè)過程的最新活動(dòng)記錄的起點(diǎn)?！　。╝）中現(xiàn)行過程R的活動(dòng)記錄，SP為此過程活動(dòng)記錄的起點(diǎn)，TOP指向?yàn)榇诉^程創(chuàng)設(shè)的活動(dòng)記錄的頂端，并假定R含有可變數(shù)組，則在分配了數(shù)組區(qū)之后TOP就指向數(shù)組區(qū)（整個(gè)運(yùn)行棧）的頂端。，（a）對(duì)照?！　≡谶^程段中對(duì)任何局部變量x的引用可表示為變址訪問x[SP]，此處x代表變量x的相對(duì)數(shù)，也就是相對(duì)于活動(dòng)記錄起點(diǎn)的地址。這個(gè)相對(duì)數(shù)在編譯時(shí)可完全確定下來。過程的局部數(shù)組的內(nèi)情向量的相對(duì)地址在編譯時(shí)也同樣可確定下來。數(shù)組空間分配之后，對(duì)數(shù)組元素的引用也就容易用變址訪問的方式來實(shí)現(xiàn)。 嵌套過程語言的棧式實(shí)現(xiàn)　　我們所熟悉的PASCAL語言程序結(jié)構(gòu)的特點(diǎn)是允許過程嵌套定義，一個(gè)過程可以引用包圍它的任一外層過程所定義的標(biāo)識(shí)（如變量，數(shù)組或過程等）。若不考慮它的文件和指針類型，它的存儲(chǔ)分配也是采用棧式動(dòng)態(tài)分配策略，只是它的過程活動(dòng)記錄中應(yīng)增設(shè)一些內(nèi)容，用以解決對(duì)非局部變量的引用問題?！　　　?1) program sort(input, output)。 //sort的過程頭　　(2)　　var a: array [0..10] of integer?！　?3)　　x: integer?！　?4)　　procedure readarray。 //sort內(nèi)嵌套定義的readarray的過程頭　　(5)　　　var i: integer?！　?6)　　　begin…a…end{readarray}。 //readarray的過程體　　(7)　　procedure exchange(i,j: integer)。　　　　　　　　　　//sort內(nèi)嵌套定義的exchange的過程頭　　(8)　　　begin　　(9) 　　 x∶=a[i]。 a[i]∶=a[j]。 a[j]∶=x。 //exchange的過程體　　(10)　　 end{exchange}。　　(11)　 procedure quicksort(m,n: integer)。　　　　　　　　　　//sort內(nèi)嵌套定義的quicksort的過程頭　　(12) 　　var k,v: integer。 　　(13)　　 function partition(y,z:integer):integer?！　　　　　　　　　?/quicksort內(nèi)嵌套定義的partition的函數(shù)頭　　(14)　　　　var :integer?！　?15)　　　　begin …a… //partition的函數(shù)體　　(16)　　　　…v…　　(17) 　　　 …exchange(i,j)。…　　(18) 　　　 end{partition}。　　(19) 　　begin…end{quicksort}。 //quicksort的過程體　　(20) begin…end{sort}. //sort的例程體：　　sort　　　readarray　　　exchange　　　quicksort　　　　partition　　這里不妨將整個(gè)程序sort看成最外層的過程。過程readarray,exchange和partition中引用的a均不是它們的局部變量，而是過程sort的局部變量。假如過程sort激活(調(diào)用)了過程quicksort,，其中在quicksort過程活動(dòng)記錄中有一(或一些)存儲(chǔ)單元(用斜線描繪)用以記錄過程quicksort可以引用sort中定義的變量a和x。也就是說，為了解決對(duì)非局部量的存取問題，必須設(shè)法跟蹤每個(gè)外層過程的最新活動(dòng)記錄的位置。圖 實(shí)現(xiàn)對(duì)非局部量的存取的方法跟蹤每個(gè)外層過程的最新活動(dòng)記錄AR的位置?！　「欈k法：　?、?用靜態(tài)鏈（如PL/0的SL）?！　、?用DISPLAY表。跟蹤的辦法很多，我們介紹兩種，一種是在過程活動(dòng)記錄中增設(shè)存取鏈，指向包含該過程的直接外層過程的最新活動(dòng)記錄的起始位置。（a）所示。（b）說明。圖 嵌套定義過程的活動(dòng)記錄和存儲(chǔ)棧回顧PL/0編譯程序，其假想機(jī)匯編解釋程序的環(huán)境之一是數(shù)據(jù)棧stack，它的存儲(chǔ)分配策略便是棧式動(dòng)態(tài)分配的，因?yàn)镻L/0是PASCAL的一個(gè)子集，它的過程允許嵌套定義，它的過程活動(dòng)記錄中便有存取鏈，在PL/0編譯程序中我們稱作靜態(tài)鏈。因?yàn)镻L/0的過程是無參過程，PL/0也無動(dòng)態(tài)數(shù)組。圖 PL/0編譯程序的過程活動(dòng)記錄。如果該程序的某次執(zhí)行順序?yàn)椋骸　ort→quicksort→quicksort→partition→exchange…　　即主程序(最外層過程)sort開始執(zhí)行,繼而進(jìn)入過程quicksort，而又一次進(jìn)入過程quicksort，接著進(jìn)入過程partition，進(jìn)入過程exchange…?！　?，我們僅把存取鏈和控制鏈的值標(biāo)明。圖 運(yùn)行?？梢钥闯?，過程exchange由過程（函數(shù)）partition調(diào)用，但exchange的直接外層過程是sort，所以過程exchange的活動(dòng)記錄的存取鏈指向sort的活動(dòng)記錄的始址。 　　另外，過程partition中引用了第(2)行說明的變量a，而partition的直接外層是quicksort，quicksort的直接外層過程是sort，partition對(duì)非局部量a的引用通過兩次拉鏈實(shí)現(xiàn)。另外一種存取非局部變量的辦法，也是常用的有效辦法。即每進(jìn)入一個(gè)過程后，在建立它的活動(dòng)記錄的同時(shí)建立一張嵌套層次顯示表display?！　∵@里所提到的嵌套層次，是指過程定義的層數(shù)，始終假定主程序的層數(shù)為0，因此主程序稱為0層過程。如某過程p是在層次為i的過程q內(nèi)定義的，并且q是包圍p的直接外層，那么p的過程層數(shù)為i+1。一般編譯程序處理過程說明時(shí)，將把過程層數(shù)作為重要的屬性登記在符號(hào)表中。計(jì)數(shù)過程的層數(shù)很容易實(shí)現(xiàn)，用一個(gè)計(jì)數(shù)器Level，初值為0，每遇到過程說明則增1，過程說明結(jié)束則減1，PL/0編譯程序就是這樣處理的。display是一個(gè)指針數(shù)組d，也可看做是一個(gè)小棧，自頂向下每個(gè)單元依次存放著現(xiàn)行層，直接外層，……直至最外層（0層，主程序?qū)樱┑让恳粚舆^程的最新活動(dòng)記錄的地址。也即，嵌套層次i的過程的局部變量a是在由display元素d[i]所指的那個(gè)活動(dòng)記錄中存放的。也就是說，嵌套層次i+1過程中的非局部變量可能在i,i1,…,0層，對(duì)它的存取是通過display元素d[i],d[i],…,d[0]而獲得的。　　假定現(xiàn)在進(jìn)入的過程的層數(shù)為i，則它的display表含有i+1個(gè)元素，依次指向現(xiàn)行層、直接外層……直至最外層（0層）等每一層過程的最新活動(dòng)記錄的地址。，假定有如下四種調(diào)用情況：(a)sort→quicksort…。(b)sort→quicksort→quicksort…。(c)sort→quicksort→quicksort→partition…。(d)sort→quicksort→quicksort→partition→exchange…。（a），（b），（c），（d）分別說明了上述四種情形的運(yùn)行棧和display。確實(shí)看出，display顯示了存取鏈的信息。圖 display表display本身的體積在編譯時(shí)可確定。至于display本身作為單獨(dú)的表分配存儲(chǔ)，還是作為活動(dòng)記錄的一部分，比如置于實(shí)參（形式單元）的上端（），則取決于編譯程序的設(shè)計(jì)者?！　〖俣▽isplay作為活動(dòng)記錄的一部分，由于每個(gè)過程的形式單元數(shù)目在編譯時(shí)是知道的，那么display的相對(duì)地址d（相對(duì)于活動(dòng)記錄起點(diǎn)）在編譯時(shí)也是完全確定的。因此，若現(xiàn)行過程中引用了某一外層過程的變量，則很容易生成相應(yīng)的存取指令?，F(xiàn)在我們要討論，當(dāng)過程P1調(diào)用過程P2而進(jìn)入P2后，P2應(yīng)如何建立起自己的display。為了建立自己的display，P2必須知道它的直接外層過程(記為P0)的display。這意味著，當(dāng)P1調(diào)用P2時(shí)必須把P0的display地址作為連接數(shù)據(jù)之一傳給P2。圖 display作為活動(dòng)記錄的一部分圖 P1調(diào)用P2的兩種不同嵌套圖 (a)　調(diào)用情形一 　　　圖 (b)　調(diào)用情形二如果P2是一個(gè)真實(shí)過程(P2不是形式參數(shù))，那么，P0或者就是P1自身或者既是P1又是P2的直接外層((a)、(b)兩種情形)。不論哪一種情形，只要在進(jìn)入P2后能夠知道P1的display就能知道P0的display，從而可直接構(gòu)造出P2的display?！　∈聦?shí)上，只需從P1的di