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