編譯原理第六章符號表組織

1、內容提要內容提要: : - - 語義分析之一語義分析之一6.1 6.1 符號表的地位和作用符號表的地位和作用6.2 6.2 符號表的組織與管理符號表的組織與管理6.3 6.3 符號表的結構設計符號表的結構設計6.4 6.4 符號表的構造過程示例符號表的構造過程示例 6.5 6.5 運行時刻存儲分配運行時刻存儲分配 符號表是符號表是標識符標識符的的動態(tài)語義詞典動態(tài)語義詞典，屬于，屬于編譯中語義分析的知識庫；主要內容：編譯中語義分析的知識庫；主要內容： 名字名字 標識符源碼，用作查詢關鍵字；標識符源碼，用作查詢關鍵字； 類型類型 - - 該標識符的數據類型及其相關信息；該標識符的數據類型及其相關信

2、息； 種類種類 - - 該標識符在源程序中的語義角色；該標識符在源程序中的語義角色； 地址地址 - - 與值單元相關的一些信息；與值單元相關的一些信息； 定義和重定義檢查；定義和重定義檢查； 類型匹配校驗；類型匹配校驗； 數據的越界和溢出檢查；數據的越界和溢出檢查； 值單元存儲分配信息；值單元存儲分配信息； 函數、過程的參數傳遞與校驗；函數、過程的參數傳遞與校驗； 符號表符號表的功能的功能標識符標識符四種語四種語義信息義信息6.2.1 6.2.1 符號表的工作原理符號表的工作原理 遇遇 定義性標識符定義性標識符( (在說明中在說明中)- )- 把語義信把語義信息息填填入表中，并修改其入表中，并

3、修改其TOKENTOKEN的指針，使其指向相的指針，使其指向相應的表項：應的表項：（i , )i , )該該標識符標識符符號表項符號表項 遇遇 應用性標識符應用性標識符( (在語句中在語句中)- )- 查查符號表符號表的相應項，查到后修改其的相應項，查到后修改其TOKENTOKEN的指針，使其指向的指針，使其指向相應的表項：相應的表項：6.2.2 6.2.2 符號表的查詢、訪問方式符號表的查詢、訪問方式線性表、順序表、索引表和散列表，皆可以采用。線性表、順序表、索引表和散列表，皆可以采用。（i , )i , )該該標識符標識符符號表項符號表項6.2.3 6.2.3 符號表的維護、管理方式符號表

4、的維護、管理方式 一個源文件有若干個函數組成，通常，一個源文件有若干個函數組成，通常，每個函數對每個函數對應一個符號表應一個符號表，此外，還是有一個，此外，還是有一個公用符號表公用符號表； 符號表如何管理？往往取決于所屬語言的程序結符號表如何管理？往往取決于所屬語言的程序結構，就構，就 C C語言來說，可以在內存設置一定長度的語言來說，可以在內存設置一定長度的符號符號表區(qū)表區(qū)，并建立適當的，并建立適當的索引機制索引機制，訪問相應的符號表：，訪問相應的符號表：公用公用符號表符號表FUNCTION 2 符號表符號表 FUNCTION 1 符號表符號表現行現行函數符號表函數符號表全局全局 符號表區(qū)符

5、號表區(qū)局部局部 符號表區(qū)符號表區(qū) 索引索引機制機制FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;FUNCTION exp(x:REAL;VAR y:INTEGER):REAL; CONST pai CONST pai=3.14;=3.14; TYPE arr TYPE arr=ARRAY1.5,1.10 OF INTEGER;=ARRAY1.5,1.10 OF INTEGER; VAR a:arr VAR a:arr; b,a:real; b,a:real; BEGIN BEGIN ; a2,5:=100; b:=z+6; ; a2,5:=100; b:=z+

6、6; END; END;【例【例6.16.1】有下列函數過程：】有下列函數過程： 需要進符號表的標識符：需要進符號表的標識符： exp(exp(函數函數, ,附帶信息附帶信息: :類型、參數情況和入口地址類型、參數情況和入口地址),),paipai( (常量常量),),arrarr( (類型類型),),a(a(下標變量下標變量) )，b b( (簡單變簡單變量量) )， 怎樣檢查出：怎樣檢查出：a a 重定義、重定義、z z 無定義以及下表變量無定義以及下表變量a2,5a2,5的值地址在何處？的值地址在何處？ 由于標識符的種類不同，導致語義屬性也不盡相同；由于標識符的種類不同，導致語義屬性也不

7、盡相同；怎樣組織符號表？下面提供一個符號表的怎樣組織符號表？下面提供一個符號表的體系結構體系結構： SYNBL SYNBL（符號表）（符號表） NAME TYPE CAT ADDRNAME TYPE CAT ADDR PFINFL(PFINFL(函數表函數表) )CONSL(CONSL(常量表常量表) ) AINFL( AINFL(數組表數組表) )RINFL(RINFL(結構表結構表) )VALL(VALL(活動紀錄活動紀錄) )LENL(LENL(長度表長度表) )TYPELTYPEL（類型表）（類型表） TVAL TPOINTTVAL TPOINT名字名字 類型類型 種類種類 地址地址

8、tokentoken i i 6.3.1 6.3.1 符號表總表符號表總表(SYNBL)(SYNBL)NAMENAMETYPTYPCATCATADDRADDR 結構：結構：NEME(NEME(名字名字) ) 標識符源碼標識符源碼( (或內部碼或內部碼) )TYP(TYP(類型類型) ) 指針，指向類型表相應項；指針，指向類型表相應項；CAT(CAT(種類種類) ) 種類編碼：種類編碼： f(f(函數函數) )，c(c(常量常量) )，t(t(類型類型) )，d(d(域名域名) )， v,vn,vfv,vn,vf( (變量，換名形參，賦值形參變量，換名形參，賦值形參) )；ADDR(ADDR(地

9、址地址) ) 指針，根據標識符的指針，根據標識符的種類種類不同，分不同，分別指向：別指向：PFINFL,CONSL,LENL,VALL,PFINFL,CONSL,LENL,VALL,6.3.2 6.3.2 類型表類型表(TAPEL)(TAPEL) 結構：結構：TVALTVALTPOINTTPOINTTVAL(TVAL(類碼類碼) ) 類型代碼：類型代碼： i i( (整型整型) )，r r( (實型實型) )，c c( (字符型字符型) )，b b( (布爾型布爾型) )， a a( (數組型數組型) )，d d( (結構型結構型) )，TPOINT(TPOINT(指針指針) ) 根據數據類型

10、不同，指向不同的根據數據類型不同，指向不同的信息表項：信息表項： 基本數據類型基本數據類型( (i i, ,r r, ,c c, ,b b) nul) nul( (空指針空指針) )； 數組類型數組類型( (a a) ) 指向數組表；指向數組表； 結構類型結構類型( (d d) ) 指向結構表指向結構表; ; 6.3.3 6.3.3 數組表數組表(AINFL)(AINFL) 結構：結構：LOWLOWUPUPCTPCTPCLENCLEN每維占表中一個紀錄每維占表中一個紀錄 LOW( LOW(數組的下界數組的下界)-)-（C C語言自動設為：語言自動設為：0 0）; ; UP( UP(數組的上界數

11、組的上界) ) CTP( CTP(成分類型指針成分類型指針) ) 指針，指向該維數組成分類指針，指向該維數組成分類型型( (在類型表中的信息在類型表中的信息);); CLEN( CLEN(成分類型的長度成分類型的長度) ) 成分類型的數據所占成分類型的數據所占值單值單元的個數元的個數； 這里假定：這里假定：值單元個數值單元個數依依字長字長為單位計算。為單位計算。6.3.4 6.3.4 結構表結構表(RINFL)(RINFL) 結構：結構：每個域占表中一個紀錄每個域占表中一個紀錄 ID( ID(結構的域名結構的域名) ) OFF( OFF(區(qū)距區(qū)距) )是是ididk k的值單元首址相對于所在記

12、錄值區(qū)的值單元首址相對于所在記錄值區(qū)區(qū)頭位置；區(qū)頭位置；約定：約定：offoff1 1=0=0， offoff2 2= off= off1 1+LEN(tp+LEN(tp1 1), ), off offn n= off= offn-1n-1+ +LEN(tpLEN(tpn-1n-1) )。 ididn-1n-1的長度的長度 TP(TP(域成分類型指針域成分類型指針) ) 指針，指向指針，指向ididk k域域成分類型成分類型( (在類型表中的信息在類型表中的信息);); IDID OFFOFF TPTP6.3.5 6.3.5 函數表函數表(PFINFL)(PFINFL) 結構：結構：LEVEL

13、LEVEL OFF OFF FN FNENTRYENTRY PARAMPARAM LEVEL( LEVEL(層次號層次號) ) 該過函靜態(tài)層次嵌套號該過函靜態(tài)層次嵌套號, , OFF( OFF(區(qū)距區(qū)距) ) 該過函自身數據區(qū)起始單元相對該該過函自身數據區(qū)起始單元相對該過函值區(qū)區(qū)頭位置過函值區(qū)區(qū)頭位置 ； FN(FN(參數個數參數個數) ) 該過函的形式參數的個數；該過函的形式參數的個數； PARAM(PARAM(參數表參數表) ) 指針，指向形參表；指針，指向形參表； ENTRY(ENTRY(入口地址入口地址) ) 該函數目標程序首地址該函數目標程序首地址( (運運行時填寫行時填寫) )；

14、- 過程過程或或函數函數語義信息語義信息6.3.6 6.3.6 其他表其他表( () ) 常量表常量表(CONSL)- (CONSL)- 存放相應常量的初值；存放相應常量的初值； 長度表長度表(LENL) (LENL) 存放相應數據類型所占值單元存放相應數據類型所占值單元個數；個數； 活動紀錄表活動紀錄表(VALL) (VALL) 一個函數一個函數( (或過程或過程) )虛擬虛擬的值單元存儲分配表；此分配表在運行調用時才可的值單元存儲分配表；此分配表在運行調用時才可用，故稱用，故稱活動紀錄活動紀錄。 結構：結構： 結構：結構： 結構結構： ENTENT 2 2 ? ? v3 v3 vn vni

15、tpitp y y v2 v2 vf vfrtprtp x x臨時變量值區(qū)臨時變量值區(qū) b值 y值 數組a值區(qū) 管理區(qū) exp值 x值 鏈接表3.143.14 50 50 1 1itpitp10101 110105 51 1 a a a ac,i,r,bc,i,r,bv1v1v2v2v3v3v4v4v5v5 t t arrarr v4 v4 v v a a c crtprtppaipai v5 v5 v vrtprtp b b v3 v3vnvnitpitp y y v2 v2 vf vfrtprtp x x f frtprtpexpexpSYNBLSYNBLPFINFLPFINFLVALLV

16、ALLCONSLCONSLLENLLENLAINFLAINFLTYPELTYPEL【例【例6.26.2】有類型說明有類型說明: : TYPE arrTYPE arr = ARRAY 1.10 OF ARRAY 1.5 OF INTEGER; = ARRAY 1.10 OF ARRAY 1.5 OF INTEGER; 試填寫符號表。試填寫符號表。 SYNBLSYNBLTYPELTYPEL i r c bAINFLAINFLarra110a15itp設：實型占設：實型占8 8個存儲單元，整型占個存儲單元，整型占4 4個單元，布爾型和字符型占個單元，布爾型和字符型占1 1個單元。個單元。 420tL

17、ENLLENL200【例【例6.36.3】有類型說明有類型說明: :試填寫符號表。試填寫符號表。 SYNBLSYNBLTYPELTYPELAINFLAINFLrecd110dbtp設：實型占設：實型占8 8個存儲單元，整型占個存儲單元，整型占4 4個單元，布爾型和字符型占個單元，布爾型和字符型占1 1個單元。個單元。 1 tLENLLENLTYPE rec = RECORD u: INTEGER; v: ARRAY 1.10 OF BOOLEAN; r: RECORD x, y : REAL END END; i,r,c,bi,r,c,bRINFLRINFLu0itpuitpd4v4avd10

18、r14x0rtprtprrtpdxdd8y8yrtp81630【例【例6.46.4】試填寫符號表。試填寫符號表。 SYNBLSYNBLTYPELTYPELvf?rtp設：實型占設：實型占8 8個存儲單元，整型占個存儲單元，整型占4 4個單元，布爾型和字符型占個單元，布爾型和字符型占1 1個單元。個單元。 ? PROCEDURE P1(VAR x: REAL; y: INTEGER); BEGIN END; i i r r c c b bPFINFLPFINFLrtpP1rtppxvny2yrtp有過程說明有過程說明: :設設P1P1所在層所在層LEVEL=1LEVEL=1，即所定義的層，即所定

19、義的層LEVEL=2,LEVEL=2,1P122?Entryxvn? vf? 注注： ？ 該標識符的值單元首址，該標識符的值單元首址， 為相對地址（為相對地址（LEVEL, offsetLEVEL, offset） LEVEL LEVEL 該標識符該標識符所在層次號，所在層次號， offset offset 區(qū)距，區(qū)距，存儲分配時可定存儲分配時可定。解決的問題：解決的問題：標識符標識符變量的變量的地址分配地址分配與對它們的訪問。與對它們的訪問。 6.5.1 6.5.1 標識符值單元分配標識符值單元分配 值單元分配分兩類：值單元分配分兩類： 在在編譯階段編譯階段即可完成真實的地址分配。在編譯時即

20、可完成真實的地址分配。在編譯時對所有數據對象分配固定的存儲單元，且在運行是始對所有數據對象分配固定的存儲單元，且在運行是始終保持不變。終保持不變。1.1.靜態(tài)分配靜態(tài)分配2.2.動態(tài)分配動態(tài)分配 指在運行時刻進行的值單元分配，在編譯時只能進指在運行時刻進行的值單元分配，在編譯時只能進行相對地址分配。行相對地址分配。 棧式動態(tài)分配；棧式動態(tài)分配； 堆式動態(tài)分配。堆式動態(tài)分配。 值單元分配是以過程函數為單位的。值單元分配是以過程函數為單位的。 注：注：6.5.2 6.5.2 活動記錄活動記錄 1.三個概念三個概念過程：過程：一個可執(zhí)行模塊，過程或函數，通常完成特一個可執(zhí)行模塊，過程或函數，通常完成

21、特定的功能。定的功能。活動：活動： 過函的一次執(zhí)行。每執(zhí)行一次過程體，則產過函的一次執(zhí)行。每執(zhí)行一次過程體，則產生該過函的一個活動。生該過函的一個活動?；顒佑涗洠夯顒佑涗洠?一個有一個有結構結構的連續(xù)存儲塊。用來存儲過的連續(xù)存儲塊。用來存儲過函一次執(zhí)行中所需要的信息。函一次執(zhí)行中所需要的信息。 如果不支持可變數據結構，活動記錄的體積是如果不支持可變數據結構，活動記錄的體積是可以在編譯時確定的。可以在編譯時確定的。 活動記錄僅是一種活動記錄僅是一種存儲映像存儲映像，編譯程序所進行，編譯程序所進行的運行時刻存儲分配是在符號表中進行的。的運行時刻存儲分配是在符號表中進行的。 6.5.2 6.5.2

22、活動記錄（續(xù)）活動記錄（續(xù)） 2.2.活動記錄的結構活動記錄的結構 臨時單元臨時單元 內情向量內情向量 局部變量局部變量 形式單元形式單元 靜態(tài)鏈靜態(tài)鏈 動態(tài)鏈動態(tài)鏈 返回地址返回地址VALLVALLTOPTOPSPSP連接數據連接數據局部數據局部數據（1 1）連接數據區(qū)）連接數據區(qū)返回地址返回地址： 動態(tài)鏈動態(tài)鏈： 指向調用該過程的主調程序的指向調用該過程的主調程序的活動記錄的指針；活動記錄的指針； 靜態(tài)鏈靜態(tài)鏈： 指向靜態(tài)直接外層活動記錄的指針。指向靜態(tài)直接外層活動記錄的指針。 （2 2）形式單元）形式單元用來存放實參的值或地址。用來存放實參的值或地址。 （3 3）局部數據區(qū)）局部數據區(qū)

23、用來存放局部變量、內情向量、用來存放局部變量、內情向量、臨時單元。臨時單元。 （4 4）棧指針）棧指針SPSP 指向現行過程活動記指向現行過程活動記錄的起點，即第一個單元；錄的起點，即第一個單元； TOPTOP 指向（已占用）棧頂指向（已占用）棧頂單元，即活動記錄的最后一單元，即活動記錄的最后一個單元。個單元。 6.5.3 6.5.3 簡單的棧式存儲分配簡單的棧式存儲分配 沒有分程序結構，過程定義不允許嵌套，沒有分程序結構，過程定義不允許嵌套，但允許過程的遞歸調用。但允許過程的遞歸調用。 以以C C語言為例語言為例: :1 1C C語言程序的存儲組織語言程序的存儲組織 【例【例6.56.5】

24、C C語言過程調用關系：語言過程調用關系：Main( )Main( ) Q( )Q( ) R( ) R( ) 則，活動記錄棧狀態(tài)為：則，活動記錄棧狀態(tài)為： R R的活動記錄的活動記錄 Q Q的活動記錄的活動記錄MainMain的活動記錄的活動記錄 全局數據區(qū)全局數據區(qū)TOPTOPSPSP2 2C C的活動記錄的活動記錄 臨時單元臨時單元 內情向量內情向量 局部變量局部變量 形式單元形式單元 參數個數參數個數 返回地址返回地址 Old SPOld SPOld SPOld SP值，即前一活動記錄的地址；值，即前一活動記錄的地址； 其中：其中：SPSPTOPTOP6.5.3 6.5.3 簡單的棧式存

25、儲分配（續(xù)）簡單的棧式存儲分配（續(xù)） 3 3C C語言的過程調用與返回語言的過程調用與返回 （1 1）過程調用）過程調用 過程調用的四元式序列：過程調用的四元式序列：(param, entry(t1), _, _)(param, entry(t1), _, _) (param, entry(tn(param, entry(tn), _, _), _, _)(call, entry(P(call, entry(P), n, _), n, _) 對應的目標指令：對應的目標指令： (i+3)TOP := entry(ti).Addr (i+3)TOP := entry(ti).Addr /將將tit

26、i地址填到活動記錄的形參區(qū)去地址填到活動記錄的形參區(qū)去 (param, (param, entry(tientry(ti) ), _, _), _, _)對應的指令：對應的指令：(call, entry(P(call, entry(P), n,), n, _)_)對應的指令：對應的指令：1TOP := SP 1TOP := SP /保護現行保護現行SPSP3TOP := n 3TOP := n /傳遞參數個數傳遞參數個數JSP P JSP P 第第n n個實參地址個實參地址 過程過程P P的入口地址的入口地址 參數個數參數個數 SPSPTOPTOP主調過程活動記錄 子過程P的活動記錄 Old

27、SPOld SP返回地址返回地址參數個數參數個數形參區(qū)t t1 1 t t1 1 主調過程活動記錄 SPSPTOPTOP子過程P的活動記錄 SPSPn n 子過程子過程P P需完成的工作：定義自需完成的工作：定義自己的活動記錄；己的活動記錄； SP := TOP+1 /SP := TOP+1 /定義過程定義過程P P的的SP SP 1SP := 1SP := 返回地址返回地址 /保護返回地址保護返回地址TOP := TOP+TOP := TOP+L L / /定義新定義新TOPTOPL LSPSPSPSP返回地址TOPTOPSPSPTOPTOP6.5.3 6.5.3 簡單的棧式存儲分配（續(xù)）簡

28、單的棧式存儲分配（續(xù)） 3 3C C語言的過程調用與返回語言的過程調用與返回 （2 2）過程返回）過程返回 過程返回的四元式：過程返回的四元式：(ret, _, _, _)(ret, _, _, _) 對應的目標指令：對應的目標指令：TOP := SP-1 /TOP := SP-1 /恢復恢復TOPTOPSP := 0SP /SP := 0SP /恢復恢復SPSPX := 2TOP X := 2TOP / /取返回地址，取返回地址，X X為某一變址器為某一變址器UJ 0XUJ 0X / /按按X X中的返回地址實行變址轉移中的返回地址實行變址轉移 t t1 1 n SP SP 主調過程活動記錄

29、 子過程P的活動記錄 L LSPSPTOPTOPTOPTOPTOPTOPSPSPSPSPX X返回地址返回地址返回地址返回地址X X6.5.4 6.5.4 嵌套過程語言的棧式存儲分配嵌套過程語言的棧式存儲分配 過程嵌套的一個關鍵問題：過程嵌套的一個關鍵問題：標識符的作用域問題標識符的作用域問題 。 標識符的作用范圍往往與它所處的過程相關，也就標識符的作用范圍往往與它所處的過程相關，也就是說，同一個標識符，在不同的程序段里，代表不同的是說，同一個標識符，在不同的程序段里，代表不同的對象，具有不同的性質，因此要分配不同的存儲空間。對象，具有不同的性質，因此要分配不同的存儲空間。 標識符的有效范圍：

30、標識符的有效范圍：（1 1）在外層未定義，而在內層定義的，服從內層定義；）在外層未定義，而在內層定義的，服從內層定義；（2 2）在外層已定義，而在內層未定義的，服從全范圍；）在外層已定義，而在內層未定義的，服從全范圍；（3 3）在外層已定義，而在內層也定義的，在外層服從）在外層已定義，而在內層也定義的，在外層服從外層定義，在內層服從內層定義。外層定義，在內層服從內層定義。服從最小作用域原理服從最小作用域原理；1.1.標識符的作用域標識符的作用域2.2.活動記錄活動記錄6.5.4 6.5.4 嵌套過程語言的棧式存儲分配（續(xù)）嵌套過程語言的棧式存儲分配（續(xù)） 問題的提出：問題的提出： 過程過程Q

31、Q可能會引用到它的可能會引用到它的任意外層過程任意外層過程的最新活動記的最新活動記錄中的某些數據。錄中的某些數據。 為了在活動記錄中查找這些為了在活動記錄中查找這些非局部名字所對應的存儲空間，非局部名字所對應的存儲空間，過程過程Q Q運行時必須設法跟蹤它的運行時必須設法跟蹤它的所所有外層過程有外層過程的最新活動記錄的地的最新活動記錄的地址。址。 解決問題的思想：解決問題的思想：解決方案：解決方案： 活動記錄中增加活動記錄中增加靜態(tài)鏈靜態(tài)鏈！使！使其其指向直接外層指向直接外層的的最新活動記錄最新活動記錄的的首地址首地址； 臨時單元臨時單元 內情向量內情向量 局部變量局部變量 形式單元形式單元 參

32、數個數參數個數 靜態(tài)鏈靜態(tài)鏈 返回地址返回地址 Old SP Old SPSPSPTOPTOP連接數據連接數據3.3.嵌套層次顯示表嵌套層次顯示表(display)(display)和活動記錄結構和活動記錄結構(1)(1)連接數據區(qū)：連接數據區(qū)：用于訪問外層的變量用于訪問外層的變量 Old SPOld SP返回地址返回地址全局全局DisplayDisplay地址地址參數個數參數個數 形式單元形式單元 顯示區(qū)表顯示區(qū)表(Display)(Display) 局部變量局部變量 內情向量內情向量 臨時單元臨時單元SPSPTOPTOP0 01 12 20 02 2；連接數據 全局全局displaydis

33、play地址地址 主調過程的顯示區(qū)表首址；主調過程的顯示區(qū)表首址；老老SP SP 主調過程的活動記錄首址；主調過程的活動記錄首址；(2)(2)參數個數：參數個數：3 3；3 3(3)(3)形參值單元區(qū)：形參值單元區(qū)：4 4入口為入口為4 4；換名形參（換名形參（vnvn） 分配分配2 2個單元（地址傳遞）；個單元（地址傳遞）；賦值形參（賦值形參（vfvf） 按相應類型長度分配；按相應類型長度分配； l l為層次號，包含為層次號，包含直接外層直接外層嵌套的嵌套的l l個過個過程的活動記錄的首址，再加上本過程的活程的活動記錄的首址，再加上本過程的活動記錄首址；動記錄首址；(4)(4)顯示區(qū)表顯示區(qū)

34、表(display)(display)： 占占l+1l+1個單元個單元；l+1l+1類型標識符、常量標識符等不分配值單元；類型標識符、常量標識符等不分配值單元；(5)(5)局部變量區(qū)：局部變量區(qū)：入口為入口為off + l + 2off + l + 2；offoff為形參區(qū)最后一個值單元地址；為形參區(qū)最后一個值單元地址；局部變量值單元按相應類型長度分配地址；局部變量值單元按相應類型長度分配地址；編譯系統定義的變量，按局部變量值單元分配原則分配地址；編譯系統定義的變量，按局部變量值單元分配原則分配地址； (6)(6)臨時變量區(qū)：臨時變量區(qū)：4. Display4. Display表的建立表的建立

35、 則則Q Q與與R R的的displaydisplay表的關系如下表的關系如下: : 設過程調用關系為設過程調用關系為Q( )Q( ) R( )R( )，且，且R( )R( )的層次號為的層次號為l l，Old SPOld SP返回地址返回地址全局全局DisplayDisplay地址地址參數個數參數個數 形式單元形式單元 顯示區(qū)表顯示區(qū)表(Display)(Display) 局部變量局部變量 內情向量內情向量 臨時單元臨時單元SPSPTOPTOPOld SPOld SP返回地址返回地址全局全局DisplayDisplay地址地址參數個數參數個數 形式單元形式單元 顯示區(qū)表顯示區(qū)表(Displa

36、y)(Display) 局部變量局部變量 內情向量內情向量 臨時單元臨時單元Q Q的活動記錄的活動記錄 R R的活動記錄的活動記錄 拷貝拷貝l個單元個單元 拷貝自身的拷貝自身的SPSPl+1l+1個單元個單元【例【例6.66.6】0 0 program P; program P; var var a, x: integer; a, x: integer; 1 1 procedure Q(b procedure Q(b: integer);: integer); var var i: integer; i: integer; 2 2 procedure R(u: integer; var pro

37、cedure R(u: integer; var v: integer); v: integer); var var c, d: integer; c, d: integer; begin begin if u=1 then u=u+1; if u=1 then u=u+1; u,vu,v c,dc,d v:= (a+c)+(b-d v:= (a+c)+(b-d);); b,ib,i end R end R begin begin R(1, x); R(1, x); a,xa,x end Q end Q 1 1 procedure S; procedure S; var var c, i: i

38、nteger; c, i: integer; begin begin a:=1; a:=1; c,ic,i Q(c Q(c);); end S end S begin begin a:=0; a:=0; S; S; end. end.層次：層次：設有設有Pascal程序片段如下：程序片段如下：變量作用域：變量作用域：過程調用關系為：過程調用關系為：P PS SQ QR R 試給出程序運行時的活動記錄關系。試給出程序運行時的活動記錄關系。 【例【例6.66.6】局部變量局部變量DisplayDisplay表表參數個數參數個數全局全局Display返回地址返回地址Old SPOld SPP P的活

39、動記錄的活動記錄(0(0層層) )0 00 00 01 12 23 30 04 40 05-85-8a a9-129-12x x局部變量局部變量DisplayDisplay表表參數個數參數個數全局全局Display返回地址返回地址Old SPOld SP局部變量局部變量DisplayDisplay表表形式單元形式單元參數個數參數個數全局全局Display返回地址返回地址Old SPOld SP局部變量局部變量DisplayDisplay表表形式單元形式單元參數個數參數個數全局全局Display返回地址返回地址Old SPOld SPS S的活動記錄的活動記錄(1(1層層) )0 04 40 0

40、0 01313c ci i13131414151516161717181819-2219-2223-2623-26Q Q的活動記錄的活動記錄(1(1層層) )131317172727282829291 13030b b31-3431-340 0353536362727i i37-4037-40R R的活動記錄的活動記錄(2(2層層) )272741414242353543432 24444u u45-4845-48v v49-5049-500 027274141515152525353c cd d54-5754-5758-6158-61 R R活動記錄活動記錄 Q Q活動記錄活動記錄 S S活

41、動記錄活動記錄 P P活動記錄活動記錄活動記錄?；顒佑涗洍-(0,5)x-(0,9)c-(1,6)i-(1,10)b-(1,4)i-(1,10)u-(2,4)v-(2,8)c-(2,15)d-(2,19)5.5.值單元的地址分配值單元的地址分配 值單元分配是依據活動記錄的結構，在符號表中進行的。值單元分配是依據活動記錄的結構，在符號表中進行的。 設有設有PascalPascal程序片段如下，程序片段如下，P1P1所在層所在層level=2level=2；【例【例6.76.7】PROCEDURE P1( x: REAL; VAR y: BOOLEAN );PROCEDURE P1( x: RE

42、AL; VAR y: BOOLEAN ); CONST pai CONST pai=3.14;=3.14; TYPE arr TYPE arr=ARRAY 1.10 OF INTEGER;=ARRAY 1.10 OF INTEGER; VAR m: INTEGER; VAR m: INTEGER; a: arr a: arr; ; l: REAL; l: REAL; FUNCTION F1( z: REAL; k: INTEGER ): REAL; FUNCTION F1( z: REAL; k: INTEGER ): REAL; BEGIN BEGIN END; END; ; ; BEGIN

43、 BEGIN ; ; END; END; 試給出符號表組織及值單元分配情況。試給出符號表組織及值單元分配情況。 設：設：(1)(1)實型占實型占8 8個存儲單元，整型占個存儲單元，整型占4 4個單元，布爾型和字符型占個單元，布爾型和字符型占1 1個單元。個單元。 (2)(2)換名形參換名形參vn分配分配2個單元，賦值形參個單元，賦值形參vf按相應類型長度分配；按相應類型長度分配；接上頁：接上頁：SYNBLSYNBLi,r,c,bi,r,c,bTYPELTYPELPFINFLPFINFLP1P1的的VALLVALLCONSLCONSLLENLLENLAINFLAINFL局部變量局部變量DisplayDisplay表表形式單元形式單元參數個數參數個數全局全局DisplayDisplay返回地