第六章符號(hào)表組織ppt課件

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

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

3、引機(jī)制，訪(fǎng)問(wèn)相應(yīng)的符號(hào)表：公用符號(hào)表FUNCTION 2 符號(hào)表 FUNCTION 1 符號(hào)表現(xiàn)行函數(shù)符號(hào)表全局 符號(hào)表區(qū)部分 符號(hào)表區(qū) 索引機(jī)制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 符號(hào)表的構(gòu)造設(shè)計(jì)【例6.1】有以下函數(shù)過(guò)程： 需求進(jìn)符號(hào)表的標(biāo)識(shí)符： exp(函數(shù),附帶信息:類(lèi)型、參數(shù)情況和入口地址),pai(常量),arr(類(lèi)型),a(

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

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

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

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

8、VALL) 一個(gè)函數(shù)(或過(guò)程)虛擬的值單元存儲(chǔ)分配表；此分配表在運(yùn)轉(zhuǎn)調(diào)用時(shí)才可用，故稱(chēng)活動(dòng)紀(jì)錄。 構(gòu)造： 構(gòu)造： 構(gòu)造： 6.4 符號(hào)表的構(gòu)造過(guò)程例如： ENT 2 ? v3 vnitp y v2 vfrtp x暫時(shí)變量值區(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設(shè)：整型占1個(gè)存儲(chǔ)單元，【例6.2】有類(lèi)型闡明: T

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

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

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

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

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

14、標(biāo)識(shí)符的作用域問(wèn)題 。 標(biāo)識(shí)符的作用范圍往往與它所處的過(guò)程相關(guān)，也就是說(shuō)，同一個(gè)標(biāo)識(shí)符，在不同的程序段里，代表不同的對(duì)象，具有不同的性質(zhì)，因此要分配不同的存儲(chǔ)空間。 標(biāo)識(shí)符的有效范圍：1在外層未定義，而在內(nèi)層定義的，服從內(nèi)層定義；2在外層已定義，而在內(nèi)層未定義的，服從全范圍；3在外層已定義，而在內(nèi)層也定義的，在外層服從外層定義，在內(nèi)層服從內(nèi)層定義。服從最小作用域原理；1.標(biāo)識(shí)符的作用域2.活動(dòng)記錄6.5.4 嵌套過(guò)程言語(yǔ)的棧式存儲(chǔ)分配續(xù) 問(wèn)題的提出： 過(guò)程Q能夠會(huì)援用到它的任不測(cè)層過(guò)程的最新活動(dòng)記錄中的某些數(shù)據(jù)。 為了在活動(dòng)記錄中查找這些非部分名字所對(duì)應(yīng)的存儲(chǔ)空間，過(guò)程Q運(yùn)轉(zhuǎn)時(shí)必需設(shè)法跟蹤它的

15、一切外層過(guò)程的最新活動(dòng)記錄的地址。 處理問(wèn)題的思想：處理方案： 活動(dòng)記錄中添加靜態(tài)鏈！使其指向直接外層的最新活動(dòng)記錄的首地址； 臨時(shí)單元 內(nèi)情向量 局部變量 形式單元 參數(shù)個(gè)數(shù) 靜態(tài)鏈 返回地址 Old SPSPTOP銜接數(shù)據(jù)3.嵌套層次顯示表(display)和活動(dòng)記錄構(gòu)造(1)銜接數(shù)據(jù)區(qū)：用于訪(fǎng)問(wèn)外層的變量 Old SP前往地址全局Display地址參數(shù)個(gè)數(shù) 方式單元 顯示區(qū)表(Display) 部分變量 內(nèi)情向量 暫時(shí)單元SPTOP01202；銜接數(shù)據(jù) 全局display地址 主調(diào)過(guò)程的顯示區(qū)表首址；老SP 主調(diào)過(guò)程的活動(dòng)記錄首址；(2)參數(shù)個(gè)數(shù)：3；3(3)形參值單元區(qū)：4入口為4；換

16、名形參vn 分配2個(gè)單元地址傳送；賦值形參vf 按相應(yīng)類(lèi)型長(zhǎng)度分配； l為層次號(hào)，包含直接外層嵌套的l個(gè)過(guò)程的活動(dòng)記錄的首址，再加上本過(guò)程的活動(dòng)記錄首址；(4)顯示區(qū)表(display)：占l+1個(gè)單元；l+1類(lèi)型標(biāo)識(shí)符、常量標(biāo)識(shí)符等不分配值單元；(5)部分變量區(qū)：入口為off + l + 2；off為形參區(qū)最后一個(gè)值單元地址；部分變量值單元按相應(yīng)類(lèi)型長(zhǎng)度分配地址；編譯系統(tǒng)定義的變量，按部分變量值單元分配原那么分配地址； (6)暫時(shí)變量區(qū)：4. Display表的建立 那么Q與R的display表的關(guān)系如下: 設(shè)過(guò)程調(diào)用關(guān)系為Q( ) R( )，且R( )的層次號(hào)為l，Old SP前往地址全局

17、Display地址參數(shù)個(gè)數(shù) 方式單元 顯示區(qū)表(Display) 部分變量 內(nèi)情向量 暫時(shí)單元SPTOPOld SP前往地址全局Display地址參數(shù)個(gè)數(shù) 方式單元 顯示區(qū)表(Display) 部分變量 內(nèi)情向量 暫時(shí)單元Q的活動(dòng)記錄 R的活動(dòng)記錄 拷貝l個(gè)單元 拷貝本身的SPl+1個(gè)單元5.值單元的地址分配 值單元分配是根據(jù)活動(dòng)記錄的構(gòu)造，在符號(hào)表中進(jìn)展的。 設(shè)有Pascal程序片段如下，P1所在層level=2；【例6.6】PROCEDURE P1( x: REAL; VAR y: BOOLEAN ); CONST pai=3.14; TYPE arr=ARRAY 1.10 OF INTE

18、GER; VAR m: INTEGER; a: arr; l: REAL; FUNCTION F1( z: REAL; k: INTEGER ): REAL; BEGIN END; ; BEGIN ; END; 試給出符號(hào)表組織及值單元分配情況。 設(shè)：(1)實(shí)型占8個(gè)存儲(chǔ)單元，整型占4個(gè)單元，布爾型和字符型占1個(gè)單元。 (2)換名形參vn分配2個(gè)單元，賦值形參vf按相應(yīng)類(lèi)型長(zhǎng)度分配；接上頁(yè)：SYNBLi,r,c,bTYPELPFINFLP1的VALLCONSLLENLAINFL局部變量Display表形式單元參數(shù)個(gè)數(shù)全局Display返回地址Old SP過(guò)程P1定義的層次為l=3 01234-1112-131415161718-2122-61P1p332Entryxx2rtpvf(3,4)xrtpvf(3,4)(3,12)yybtpbtpvnvny(3,12)(4,4)pairtpc3.14arra110itp4t40mitpvm(3,18)ava(3,22)lrtpvl62-69(3,62)F1rtpf432Entryzzkkrtprtpitpitpvfvfvfvf(4,4)(4,12)(4,12)程序片段 一個(gè)