6章符號表組織ppt課件

1、內(nèi)容提要:第 6 章 符號表組織 - 語義分析之一6.1 符號表的位置和作用6.2 符號表的組織與管理6.3 符號表的構(gòu)造設(shè)計6.4 符號表的構(gòu)造過程例如 6.5 運轉(zhuǎn)時辰存儲分配6.1 符號表的位置和功能 符號表是標(biāo)識符的動態(tài)語義詞典，屬于編譯中語義分析的知識庫；主要內(nèi)容： 名字 標(biāo)識符源碼，用作查詢關(guān)鍵字； 類型 - 該標(biāo)識符的數(shù)據(jù)類型及其相關(guān)信息； 種類 - 該標(biāo)識符在源程序中的語義角色； 地址 - 與值單元相關(guān)的一些信息； 定義和重定義檢查； 類型匹配校驗； 數(shù)據(jù)的越界和溢出檢查； 值單元存儲分配信息； 函數(shù)、過程的參數(shù)傳送與校驗； 符號表的功能標(biāo)識符四種語義信息6.2 符號表的組織與

2、管理6.2.1 符號表的任務(wù)原理 遇 定義性標(biāo)識符(在闡明中)- 把語義信息填入表中，并修正其TOKEN的指針，使其指向相應(yīng)的表項：i , )該標(biāo)識符符號表項 遇 運用性標(biāo)識符(在語句中)- 查符號表的相應(yīng)項，查到后修正其TOKEN的指針，使其指向相應(yīng)的表項：6.2.2 符號表的查詢、訪問方式線性表、順序表、索引表和散列表，皆可以采用。i , )該標(biāo)識符符號表項6.2.3 符號表的維護、管理方式 一個源文件有假設(shè)干個函數(shù)組成，通常，每個函數(shù)對應(yīng)一個符號表，此外，還是有一個公用符號表； 符號表如何管理？往往取決于所屬言語的程序構(gòu)造，就 C言語來說，可以在內(nèi)存設(shè)置一定長度的符號表區(qū)，并建立適當(dāng)?shù)乃?/p>

3、引機制，訪問相應(yīng)的符號表：公用符號表FUNCTION 2 符號表 FUNCTION 1 符號表現(xiàn)行函數(shù)符號表全局 符號表區(qū)部分 符號表區(qū) 索引機制FUNCTION exp(x:REAL;VAR y:INTEGER):REAL; CONST pai=3.14; TYPE arr=ARRAY1.5,1.10 OF INTEGER; VAR a:arr; b,a:real; BEGIN ; a2,5:=100; b:=z+6; END;6.3 符號表的構(gòu)造設(shè)計【例6.1】有以下函數(shù)過程： 需求進符號表的標(biāo)識符： exp(函數(shù),附帶信息:類型、參數(shù)情況和入口地址),pai(常量),arr(類型),a(

4、下標(biāo)變量)，b(簡單變量)， 怎樣檢查出：a 重定義、z 無定義以及下表變量a2,5的值地址在何處？ 符號表的體系構(gòu)造設(shè)計 由于標(biāo)識符的種類不同，導(dǎo)致語義屬性也不盡一樣；怎樣組織符號表？下面提供一個符號表的體系構(gòu)造： SYNBL符號表 NAME TYPE CAT ADDR PFINFL(函數(shù)表)CONSL(常量表) AINFL(數(shù)組表)RINFL(構(gòu)造表)VALL(活動紀(jì)錄)LENL(長度表)TYPEL類型表 TVAL TPOINT名字 類型 種類 地址 token i 6.3.1 符號表總表(SYNBL)NAMETYPCATADDR 構(gòu)造：NEME(名字) 標(biāo)識符源碼(或內(nèi)部碼)TYP(類型

5、) 指針，指向類型表相應(yīng)項；CAT(種類) 種類編碼： f(函數(shù))，c(常量)，t(類型)，d(域名)， v,vn,vf(變量，換名形參，賦值形參)；ADDR(地址) 指針，根據(jù)標(biāo)識符的種類不同，分別指向：PFINFL,CONSL,LENL,VALL,6.3.2 類型表(TAPEL) 構(gòu)造：TVALTPOINTTVAL(類碼) 類型代碼： i(整型)，r(實型)，c(字符型)，b(布爾型)， a(數(shù)組型)，d(構(gòu)外型)，TPOINT(指針) 根據(jù)數(shù)據(jù)類型不同，指向不同的信息表項： 根本數(shù)據(jù)類型(i,r,c,b) nul(空指針)； 數(shù)組類型(a) 指向數(shù)組表； 構(gòu)造類型(d) 指向構(gòu)造表; 6

6、.3.3 數(shù)組表(AINFL) 構(gòu)造：LOWUPCTPCLEN每維占表中一個紀(jì)錄 LOW(數(shù)組的下界)-C言語自動設(shè)為：0; UP(數(shù)組的上界) CTP(成分類型指針) 指針，指向該維數(shù)組成分類型(在類型表中的信息); CLEN(成分類型的長度) 成分類型的數(shù)據(jù)所占值單元的個數(shù)； 這里假定：值單元個數(shù)依字長為單位計算。6.3.4 構(gòu)造表(RINFL) 構(gòu)造：每個域占表中一個紀(jì)錄 ID(構(gòu)造的域名) OFF(區(qū)距)是idk的值單元首址相對于所在記錄值區(qū)區(qū)頭位置；商定：off1=0， off2= off1+LEN(tp1), offn= offn-1+LEN(tpn-1)。 idn-1的長度 TP

7、(域成分類型指針) 指針，指向idk域成分類型(在類型表中的信息); ID OFF TP6.3.5 函數(shù)表(PFINFL) 構(gòu)造：LEVEL OFF FNENTRYPARAM LEVEL(層次號) 該過函靜態(tài)層次嵌套號, OFF(區(qū)距) 該過函本身數(shù)據(jù)區(qū)起始單元相對該過函值區(qū)區(qū)頭位置 ； FN(參數(shù)個數(shù)) 該過函的方式參數(shù)的個數(shù)； PARAM(參數(shù)表) 指針，指向形參表； ENTRY(入口地址) 該函數(shù)目的程序首地址(運轉(zhuǎn)時填寫)； - 過程或函數(shù)語義信息6.3.6 其他表() 常量表(CONSL)- 存放相應(yīng)常量的初值； 長度表(LENL) 存放相應(yīng)數(shù)據(jù)類型所占值單元個數(shù)； 活動紀(jì)錄表(VA

8、LL) 一個函數(shù)(或過程)虛擬的值單元存儲分配表；此分配表在運轉(zhuǎn)調(diào)用時才可用，故稱活動紀(jì)錄。 構(gòu)造： 構(gòu)造： 構(gòu)造： 6.4 符號表的構(gòu)造過程例如： ENT 2 ? v3 vnitp y v2 vfrtp x暫時變量值區(qū) b值 y值 數(shù)組a值區(qū) 管理區(qū) exp值 x值 鏈接表3.14 50 1itp1011051 a ac,i,r,bv1v2v3v4v5 t arr v4 v a crtppai v5 vrtp b v3vnitp y v2 vfrtp x frtpexpSYNBLPFINFLVALLCONSLLENLAINFLTYPEL【例6.2】有類型闡明: TYPE arr = ARRA

9、Y 1.10 OF ARRAY 1.5 OF INTEGER; 試填寫符號表。 SYNBLTYPEL i r c bAINFLarra110a15itp設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。 420tLENL200【例6.3】有類型闡明:試填寫符號表。 SYNBLTYPELAINFLrecd110dbtp設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。 1 tLENLTYPE rec = RECORD u: INTEGER; v: ARRAY 1.10 OF BOOLEAN; r: RECORD x, y : REAL END END; i,r,c

10、,bRINFLu0itpuitpd4v4avd10r14x0rtprtprrtpdxdd8y8yrtp81630【例6.4】試填寫符號表。 SYNBLTYPELvf?rtp設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。 ? PROCEDURE P1(VAR x: REAL; y: INTEGER); BEGIN END; i r c bPFINFLrtpP1rtppxvny2yrtp有過程闡明:設(shè)P1所在層LEVEL=1，即所定義的層LEVEL=2,1P122?Entryxvn? vf? 注： ？ 該標(biāo)識符的值單元首址， 為相對地址LEVEL, offset LEVEL 該

11、標(biāo)識符所在層次號， offset 區(qū)距，存儲分配時可定。6.5 運轉(zhuǎn)時辰存儲分配處理的問題：標(biāo)識符變量的地址分配與對它們的訪問。 6.5.1 標(biāo)識符值單元分配 值單元分配分兩類： 在編譯階段即可完成真實的地址分配。在編譯時對一切數(shù)據(jù)對象分配固定的存儲單元，且在運轉(zhuǎn)是一直堅持不變。1.靜態(tài)分配2.動態(tài)分配 指在運轉(zhuǎn)時辰進展的值單元分配，在編譯時只能進展相對地址分配。 棧式動態(tài)分配； 堆式動態(tài)分配。 值單元分配是以過程函數(shù)為單位的。 注：6.5.2 活動記錄 1.三個概念過程：一個可執(zhí)行模塊，過程或函數(shù)，通常完成特定的功能。活動：過函的一次執(zhí)行。每執(zhí)行一次過程體，那么產(chǎn)生該過函的一個活動?；顒佑涗?/p>

12、：一個有構(gòu)造的延續(xù)存儲塊。用來存儲過函一次執(zhí)行中所需求的信息。 假設(shè)不支持可變數(shù)據(jù)構(gòu)造，活動記錄的體積是可以在編譯時確定的。 活動記錄僅是一種存儲映像，編譯程序所進展的運轉(zhuǎn)時辰存儲分配是在符號表中進展的。 6.5.2 活動記錄續(xù) 2.活動記錄的構(gòu)造 臨時單元 內(nèi)情向量 局部變量 形式單元 靜態(tài)鏈 動態(tài)鏈 返回地址VALLTOPSP銜接數(shù)據(jù)部分?jǐn)?shù)據(jù)1銜接數(shù)據(jù)區(qū)前往地址： 動態(tài)鏈： 指向調(diào)用該過程的主調(diào)程序的活動記錄的指針； 靜態(tài)鏈： 指向靜態(tài)直接外層活動記錄的指針。 2方式單元用來存放實參的值或地址。 3部分?jǐn)?shù)據(jù)區(qū) 用來存放部分變量、內(nèi)情向量、暫時單元。 4棧指針SP 指向現(xiàn)行過程活動記錄的起點

13、，即第一個單元； TOP 指向已占用棧頂單元，即活動記錄的最后一個單元。 6.5.3 簡單的棧式存儲分配 沒有分程序構(gòu)造，過程定義不允許嵌套，但允許過程的遞歸調(diào)用。 以C言語為例:1C言語程序的存儲組織 【例6.5】C言語過程調(diào)用關(guān)系：Main( ) Q( ) R( ) 那么，活動記錄棧形狀為： R的活動記錄 Q的活動記錄Main的活動記錄 全局?jǐn)?shù)據(jù)區(qū)TOPSP2C的活動記錄 臨時單元 內(nèi)情向量 局部變量 形式單元 參數(shù)個數(shù) 返回地址 Old SPOld SP值，即前一活動記錄的地址； 其中：SPTOP6.5.3 簡單的棧式存儲分配續(xù) 3C言語的過程調(diào)用與前往 1過程調(diào)用 過程調(diào)用的四元式序列

14、：(param, entry(t1), _, _) (param, entry(tn), _, _)(call, entry(P), n, _) 對應(yīng)的目的指令： (i+3)TOP := entry(ti).Addr /將ti地址填到活動記錄的形參區(qū)去 (param, entry(ti), _, _)對應(yīng)的指令：(call, entry(P), n, _)對應(yīng)的指令：1TOP := SP /維護現(xiàn)行SP3TOP := n /傳送參數(shù)個數(shù)JSP P 第n個實參地址 過程P的入口地址 參數(shù)個數(shù) SPTOP主調(diào)過程活動記錄 子過程P的活動記錄 Old SP前往地址參數(shù)個數(shù)形參區(qū)t1 t1 主調(diào)過程活

15、動記錄 SPTOP子過程P的活動記錄 SPn 子過程P需完成的任務(wù)：定義本人的活動記錄； SP := TOP+1 /定義過程P的SP 1SP := 前往地址 /維護前往地址TOP := TOP+L /定義新TOPLSPSP前往地址TOPSPTOP6.5.3 簡單的棧式存儲分配續(xù) 3C言語的過程調(diào)用與前往 2過程前往 過程前往的四元式：(ret, _, _, _) 對應(yīng)的目的指令：TOP := SP-1 /恢復(fù)TOPSP := 0SP /恢復(fù)SPX := 2TOP /取前往地址，X為某一變址器UJ 0X /按X中的前往地址實行變址轉(zhuǎn)移 t1 n SP 主調(diào)過程活動記錄 子過程P的活動記錄 LSP

16、TOPTOPTOPSPSPX前往地址前往地址X6.5.4 嵌套過程言語的棧式存儲分配 過程嵌套的一個關(guān)鍵問題：標(biāo)識符的作用域問題 。 標(biāo)識符的作用范圍往往與它所處的過程相關(guān)，也就是說，同一個標(biāo)識符，在不同的程序段里，代表不同的對象，具有不同的性質(zhì)，因此要分配不同的存儲空間。 標(biāo)識符的有效范圍：1在外層未定義，而在內(nèi)層定義的，服從內(nèi)層定義；2在外層已定義，而在內(nèi)層未定義的，服從全范圍；3在外層已定義，而在內(nèi)層也定義的，在外層服從外層定義，在內(nèi)層服從內(nèi)層定義。服從最小作用域原理；1.標(biāo)識符的作用域2.活動記錄6.5.4 嵌套過程言語的棧式存儲分配續(xù) 問題的提出： 過程Q能夠會援用到它的任不測層過程

17、的最新活動記錄中的某些數(shù)據(jù)。 為了在活動記錄中查找這些非部分名字所對應(yīng)的存儲空間，過程Q運轉(zhuǎn)時必需設(shè)法跟蹤它的一切外層過程的最新活動記錄的地址。 處理問題的思想：處理方案： 活動記錄中添加靜態(tài)鏈！使其指向直接外層的最新活動記錄的首地址； 臨時單元 內(nèi)情向量 局部變量 形式單元 參數(shù)個數(shù) 靜態(tài)鏈 返回地址 Old SPSPTOP銜接數(shù)據(jù)3.嵌套層次顯示表(display)和活動記錄構(gòu)造(1)銜接數(shù)據(jù)區(qū)：用于訪問外層的變量 Old SP前往地址全局Display地址參數(shù)個數(shù) 方式單元 顯示區(qū)表(Display) 部分變量 內(nèi)情向量 暫時單元SPTOP01202；銜接數(shù)據(jù) 全局display地址 主

18、調(diào)過程的顯示區(qū)表首址；老SP 主調(diào)過程的活動記錄首址；(2)參數(shù)個數(shù)：3；3(3)形參值單元區(qū)：4入口為4；換名形參vn 分配2個單元地址傳送；賦值形參vf 按相應(yīng)類型長度分配； l為層次號，包含直接外層嵌套的l個過程的活動記錄的首址，再加上本過程的活動記錄首址；(4)顯示區(qū)表(display)：占l+1個單元；l+1類型標(biāo)識符、常量標(biāo)識符等不分配值單元；(5)部分變量區(qū)：入口為off + l + 2；off為形參區(qū)最后一個值單元地址；部分變量值單元按相應(yīng)類型長度分配地址；編譯系統(tǒng)定義的變量，按部分變量值單元分配原那么分配地址； (6)暫時變量區(qū)：4. Display表的建立 那么Q與R的di

19、splay表的關(guān)系如下: 設(shè)過程調(diào)用關(guān)系為Q( ) R( )，且R( )的層次號為l，Old SP前往地址全局Display地址參數(shù)個數(shù) 方式單元 顯示區(qū)表(Display) 部分變量 內(nèi)情向量 暫時單元SPTOPOld SP前往地址全局Display地址參數(shù)個數(shù) 方式單元 顯示區(qū)表(Display) 部分變量 內(nèi)情向量 暫時單元Q的活動記錄 R的活動記錄 拷貝l個單元 拷貝本身的SPl+1個單元【例6.6】0 program P; var a, x: integer; 1 procedure Q(b: integer); var i: integer; 2 procedure R(u: in

20、teger; var v: integer); var c, d: integer; begin if u=1 then u=u+1; u,v c,d v:= (a+c)+(b-d); b,i end R begin R(1, x); a,x end Q 1 procedure S; var c, i: integer; begin a:=1; c,i Q(c); end S begin a:=0; S; end.層次：設(shè)有Pascal程序片段如下：變量作用域：過程調(diào)用關(guān)系為：PSQR 試給出程序運轉(zhuǎn)時的活動記錄關(guān)系。 【例6.6】局部變量Display表參數(shù)個數(shù)全局Display返回地址Ol

21、d SPP的活動記錄(0層)0001230405-8a9-12x局部變量Display表參數(shù)個數(shù)全局Display返回地址Old SP局部變量Display表形式單元參數(shù)個數(shù)全局Display返回地址Old SP局部變量Display表形式單元參數(shù)個數(shù)全局Display返回地址Old SPS的活動記錄(1層)040013ci13141516171819-2223-26Q的活動記錄(1層)1317272829130b31-340353627i37-40R的活動記錄(2層)2741423543244u45-48v49-5002741515253cd54-5758-61 R活動記錄 Q活動記錄 S活

22、動記錄 P活動記錄活動記錄棧a-(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.值單元的地址分配 值單元分配是根據(jù)活動記錄的構(gòu)造，在符號表中進展的。 設(shè)有Pascal程序片段如下，P1所在層level=2；【例6.7】PROCEDURE P1( x: REAL; VAR y: BOOLEAN ); CONST pai=3.14; TYPE arr=ARRAY 1.10 OF INTEGER; VAR m: INTEGER; a: arr; l: REAL; FUNCTION F1( z: REAL; k: INTEGER ): REAL; BEGIN END; ; BEGIN ; END; 試給出符號表組織及值單元分配情況。 設(shè)：(1)實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。 (2)換名形參vn分配2個單元，賦值形參vf按相應(yīng)類型長度分配；接上頁：SYNBLi,r,c,bTYPELPFINFLP1的VALLCON