07第7章-符號(hào)表管理技術(shù)(編輯修改稿)
2025-03-31 14:14 本頁(yè)面
【文章內(nèi)容簡(jiǎn)介】 號(hào)表，如保留字表、標(biāo)準(zhǔn)函數(shù)名表等。 ? 動(dòng)態(tài)表：在編譯過(guò)程中根據(jù)需要構(gòu)造的符號(hào)表，如變量表、數(shù)組信息表、過(guò)程信息表等 2023/4/1 23 符號(hào)表上的操作 在整個(gè)編譯期間 ， 對(duì)于符號(hào)表的操作大致可歸納為五類： ? 對(duì)給定名字 ， 查詢名字是否已在表中； ? 往表中填入一個(gè)新的名字； ? 對(duì)給定名字 ， 訪問(wèn)其某些信息； ? 對(duì)給定名字 ， 填寫(xiě)或更新其某些信息； ? 刪除一個(gè)或一組無(wú)用的項(xiàng) 。 上述五個(gè)方面只是一些基本的共同操作 。 符號(hào)表上的操作主要有插入和查找，根據(jù)聲明方式不同而不同。 2023/4/1 24 強(qiáng)類型語(yǔ)言 :所有變量都必須顯式說(shuō)明 。 (1)遇到變量聲明時(shí)，先查找符號(hào)表以確定是否重復(fù)聲明，若是則產(chǎn)生錯(cuò)誤信息，否則插入符號(hào)表。 ?有序表：先找位置再插入 ?無(wú)序表：添加表尾 (2)遇到變量引用時(shí)，查找符號(hào)表，若查到則將查到的信息用于語(yǔ)義檢查和代碼生成，否則報(bào)告錯(cuò)誤（變量未聲明） 2023/4/1 25 弱類型語(yǔ)言 :允許對(duì)變量做隱式說(shuō)明 。 ?每遇到變量出現(xiàn)時(shí)需要插入和查詢； ?任一變量引用都處理成首次引用，先查符號(hào)表，如查到則直接獲取變量的全部屬性，否則進(jìn)行插入操作，而且需要從上下文中推測(cè)出隱式變量的全部屬性。 例：程序中首次出現(xiàn) a=5和 x=，可根據(jù)常量 5和 a為整型變量、 x為實(shí)型變量。 2023/4/1 26 ?非塊程序結(jié)構(gòu)語(yǔ)言：指用該語(yǔ)言編寫(xiě)的每一個(gè)可獨(dú)立編譯的程序是一個(gè)不包含子塊的單一模塊程序，該模塊中聲明的所有變量是屬于整個(gè)模塊的。 ?非塊程序結(jié)構(gòu)語(yǔ)言的符號(hào)表組織方式主要采用 ① 無(wú)序表 ② 有序表 ③ 散列表。 非塊程序結(jié)構(gòu)語(yǔ)言的符號(hào)表結(jié)構(gòu) 2023/4/1 27 ① 無(wú)序表： 規(guī)定符號(hào)表中表項(xiàng)按符號(hào)被掃描到的先后順序填入 。 例：程序中符號(hào)的出現(xiàn)情況如下： ???? ?a??//a 第一次出現(xiàn) ? b? ?//b 第一次出現(xiàn) ??a?//a 第二次出現(xiàn) ? d? ?//d 第一次出現(xiàn) ??c?//c 第一次出現(xiàn) ? b? ?//b 第二次出現(xiàn) ?? 其中 h為表頭， p為表尾 優(yōu)點(diǎn)：結(jié)構(gòu)簡(jiǎn)單、節(jié)省空間，插入、查找操作簡(jiǎn)單、易于實(shí)現(xiàn)。 缺點(diǎn)：查找效率低。對(duì)于含有 N項(xiàng)的符號(hào)表，查找某個(gè)符號(hào)，平均要做 N/2次比較。 2023/4/1 28 ② 有序表： 對(duì)每一個(gè)符號(hào)排序組織的符號(hào)表，在符號(hào)表中的表項(xiàng)按其符號(hào)的字符代碼串（可以看成一個(gè)整數(shù)值）值的大小從大到小（或從小到大）排列的。 編譯掃描次序是 a， b， d， c。 由于 c代碼小于 d代碼，因此 c應(yīng)在 d表項(xiàng)之前。 排序表的表項(xiàng)建立及符號(hào)查找，通常采用 二分法 。 例：程序中符號(hào)的出現(xiàn)情況如下： ???? ?a??//a 第一次出現(xiàn) ? b? ?//b 第一次出現(xiàn) ??a?//a 第二次出現(xiàn) ? d? ?//d 第一次出現(xiàn) ??c?//c 第一次出現(xiàn) ? b? ?//b 第二次出現(xiàn) ?? 其中 h為表頭， p為表尾 2023/4/1 29 名字 類型 維數(shù) m int 0 main keyword 0 n int 5 name char 0 x real 0 例： 給出編譯下面程序的有序符號(hào)表。 main() { int m,n[5]。 real x。 char name。 } 2023/4/1 30 ③散列符號(hào)表： 散列符號(hào)表不僅可以提高查找操作的效率，同時(shí)也可以提高插入操作的效率，所以在許多實(shí)際編譯器的符號(hào)表實(shí)現(xiàn)中均采用了散列技術(shù) 散列符號(hào)表又稱哈希 (hash)符號(hào)表，其關(guān)鍵在于哈希函數(shù)，將程序中出現(xiàn)的符號(hào)通過(guò)哈希函數(shù)進(jìn)行映射，得到的函數(shù)值作為該符號(hào)在表中的位置。 2023/4/1 31 ? 散列函數(shù) (哈希函數(shù) )具有如下性質(zhì)： 1） 函數(shù)值只依賴于對(duì)應(yīng)的符號(hào) 。 2） 函數(shù)的計(jì)算簡(jiǎn)單且高效 。 3） 函數(shù)值能比較均勻地分布在一定范圍內(nèi) 。 ? 散列函數(shù)：除法散列函數(shù) 、 乘法散列函數(shù) 、 多項(xiàng)式除法散列函數(shù) 、 平方取中散列函數(shù)等等 。 ? 沖突處理辦法：順序法、倍數(shù)法和鏈表法。 2023/4/1 32 例：用 “ 質(zhì)數(shù)除余法 ” 構(gòu)造散列符號(hào)表 。 1） 根據(jù)各符號(hào)名中的字符確定正整數(shù) h 2） 將整數(shù) h除以符號(hào)表長(zhǎng)度 N， 然后取其余數(shù) ， 該余數(shù)作為符
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1