單元輔導(dǎo)(五)

1、單元輔導(dǎo)（五）符號(hào)表的組織和管理1符號(hào)表的作用主要用來(lái)存放程序語(yǔ)言中出現(xiàn)的有關(guān)標(biāo)識(shí)符的信息。編譯程序處理標(biāo)識(shí)符時(shí)主要涉及兩部分內(nèi)容，其一是標(biāo)識(shí)符自身，其二是與標(biāo)識(shí)符相關(guān)的信息。這些信息又包括：標(biāo)識(shí)符的類型，標(biāo)識(shí)符的種屬，標(biāo)識(shí)符的作用域。符號(hào)表的每一項(xiàng)通常由兩部分組成。第一部分是名字欄，其內(nèi)容為標(biāo)識(shí)符名，也稱為主欄。另一部分是與名字有關(guān)的信息欄，每一個(gè)信息欄又包括若干子欄和標(biāo)志位，用來(lái)記錄標(biāo)識(shí)符的不同特征。符號(hào)表的作用體現(xiàn)在下面幾個(gè)方面。首先，當(dāng)編譯程序掃描到語(yǔ)言程序中標(biāo)識(shí)符的說(shuō)明部分時(shí)，根據(jù)說(shuō)明語(yǔ)句的功能，符號(hào)表應(yīng)能記錄標(biāo)識(shí)符的相關(guān)信息；其次，符號(hào)表內(nèi)容為上下文語(yǔ)義的合法性檢查提供依據(jù)；最后生

2、成目標(biāo)代碼時(shí)，符號(hào)表中的內(nèi)容又是編譯程序分配存儲(chǔ)地址的依據(jù)。 2符號(hào)表的組織按照處理對(duì)象的特點(diǎn)，一般可以分為直接方式和間接方式。直接方式是指在符號(hào)表中直接填入源程序中定義的標(biāo)識(shí)符及其相關(guān)信息；間接方式是指單獨(dú)設(shè)置一個(gè)字符串?dāng)?shù)組，其中存放所有標(biāo)識(shí)符，在符號(hào)表的名字欄中設(shè)置兩項(xiàng)內(nèi)容：指針和整數(shù)，指針指向標(biāo)識(shí)符在數(shù)組中的位置，整數(shù)值表示標(biāo)識(shí)符的長(zhǎng)度。按標(biāo)識(shí)符的種屬有簡(jiǎn)單變量名表、數(shù)組名表、過(guò)程名表等。根據(jù)符號(hào)表名字欄的組織特點(diǎn)，符號(hào)表信息欄的組織方式也可以分為兩類，固定信息內(nèi)容和僅記載信息地址。 3符號(hào)表的建立和查找線性表：表的大小是線性的，其查找和刪除的效率比較穩(wěn)定，按先來(lái)先服務(wù)的原則排列，若線性

3、表中含有n項(xiàng)名字和信息，查找其中一次的平均比較次數(shù)為1/2，顯然查詢效率較低。二分查找和二叉樹(shù)：說(shuō)明見(jiàn)P128。在隨機(jī)的情況下，二叉排序樹(shù)的平均查找長(zhǎng)度為1+4log2N。較之線性表，雖然查找速度略低，但由于有左、右指針能動(dòng)態(tài)生成結(jié)構(gòu)，大減少了符號(hào)排序的時(shí)間，并且每查找一項(xiàng)所需比較次數(shù)仍和log2n成比例，所以二叉樹(shù)仍不失為一種實(shí)用的方法。散列法：又稱雜湊法或Hash法，散列法是上述線性表和二叉樹(shù)兩種方法的折中。說(shuō)明見(jiàn)P129，（1）將標(biāo)識(shí)符中的每一個(gè)字符轉(zhuǎn)換為一個(gè)非負(fù)整數(shù)；（2）用一定的方法將（1）中得到的整數(shù)組合成一個(gè)整數(shù)；（3）將結(jié)果數(shù)調(diào)整到0M-1范圍內(nèi)。設(shè)置一個(gè)散列表，使所有相同Ha

4、sh值的符號(hào)名連接成一條鏈，如果出現(xiàn)地址沖突，則順著這條鏈繼續(xù)查找。 4小 結(jié)（六）本單元主要介紹了符號(hào)表的作用、內(nèi)容和組織方法，并討論了對(duì)符號(hào)表的幾種不同建立和查找方法，主要有線性表、二分查找和二叉樹(shù)查找以及散列法。符號(hào)表是編譯程序中的一個(gè)主要數(shù)據(jù)結(jié)構(gòu)，它用來(lái)存放程序語(yǔ)言中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息。在符號(hào)表上有3種操作，即填入、查找和更新，其中查找的操作頻率最高，因此精心設(shè)計(jì)查找方法尤為重要。查找方法一般因符號(hào)表的組織結(jié)構(gòu)而定。線性表和自適應(yīng)線性表都是較簡(jiǎn)單的方法，其名字欄的內(nèi)容按關(guān)鍵字的順序填寫，線性表的平均查找次數(shù)為n/2。若名字欄中的標(biāo)識(shí)符是有序排列，則可用二分法查找。二分查找法建表慢，查表快。二叉樹(shù)查找法是將每一個(gè)標(biāo)識(shí)符作為二叉樹(shù)的一個(gè)結(jié)點(diǎn)值，按照二叉樹(shù)的生成原則，動(dòng)態(tài)排列標(biāo)識(shí)符。該方法建表快，查表慢。二分查找和二叉樹(shù)查找的平均次數(shù)與log2n成比例。散列查找法的關(guān)鍵是設(shè)計(jì)一個(gè)散列函數(shù)Hash，使得能在一個(gè)確定的空間M中，對(duì)每一個(gè)標(biāo)識(shí)符Ki，滿足 0 Hash(Ki) M1 (i=1,2,，n)對(duì)散列查找法要設(shè)法解決由散列函數(shù)什不惟一而引起的“地址沖突”。用散列法組織的符號(hào)表，其上的3種操作幾乎都能在懶定的時(shí)間內(nèi)完成，因此，實(shí)用性