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