編譯原理陳火旺版8章8

1、第八章 符號(hào)表 8.1符號(hào)表的組織與作用符號(hào)表的組織與作用一、符號(hào)表的作用一、符號(hào)表的作用 一張符號(hào)表的每一項(xiàng)包含兩大欄一張符號(hào)表的每一項(xiàng)包含兩大欄,即即名字欄名字欄和和信息欄信息欄。表格形式如下所示：表格形式如下所示： 名字欄（Name）信息欄（Information） 第一項(xiàng)（入口1）第二項(xiàng)（入口2）第n項(xiàng)（入口n） 名字欄名字欄用來存放標(biāo)識(shí)符或其內(nèi)部碼；用來存放標(biāo)識(shí)符或其內(nèi)部碼；信息欄信息欄包含許多子包含許多子欄和標(biāo)志位，用來記錄與該項(xiàng)名字相對(duì)應(yīng)的種種不同屬性。欄和標(biāo)志位，用來記錄與該項(xiàng)名字相對(duì)應(yīng)的種種不同屬性。 （5）從表中刪除一個(gè)或一組名字。）從表中刪除一個(gè)或一組名字。在整個(gè)編譯期間

2、，對(duì)于符號(hào)表的訪問可概括為如下幾類操作：在整個(gè)編譯期間，對(duì)于符號(hào)表的訪問可概括為如下幾類操作：（1）對(duì)給定名字，查詢此名是否已在表中；）對(duì)給定名字，查詢此名是否已在表中；（2）往表中填入一個(gè)新名字；）往表中填入一個(gè)新名字；（3）對(duì)給定名字，訪問它的相關(guān)信息；）對(duì)給定名字，訪問它的相關(guān)信息；（4）對(duì)給定名字，往表中填寫或更新它的某些信息）對(duì)給定名字，往表中填寫或更新它的某些信息;二、符號(hào)表的組織方式二、符號(hào)表的組織方式 1、各項(xiàng)各欄所占存儲(chǔ)單元的長度固定、各項(xiàng)各欄所占存儲(chǔ)單元的長度固定 2、間接方式安排名字欄、間接方式安排名字欄poolelpmasNAMEINFORMATION , 6 , 4p

3、ool4elpmas6NAMEINFORMATION如果各種名字所需的信息（如果各種名字所需的信息（INFORMATION ）空間長短不一，）空間長短不一，那么，我們可把一些那么，我們可把一些共同屬性共同屬性直接登記在直接登記在符號(hào)表的信息欄符號(hào)表的信息欄中，中，而把某些而把某些特殊屬性特殊屬性登記在登記在別的地方別的地方，并在信息欄中附設(shè)一指示并在信息欄中附設(shè)一指示器，指向存放特殊屬性的地方。器，指向存放特殊屬性的地方。例如：對(duì)于數(shù)組標(biāo)識(shí)符例如：對(duì)于數(shù)組標(biāo)識(shí)符專門開辟一個(gè)信息表區(qū)，即為專門開辟一個(gè)信息表區(qū)，即為數(shù)組信息表數(shù)組信息表也稱為也稱為內(nèi)情向量表內(nèi)情向量表維數(shù)維數(shù)首地址首地址界差界差d

4、1 界差界差dn上界上界I1 上界上界In下界下界U1 下界下界Un內(nèi)情向量表內(nèi)情向量表在符號(hào)表的地址欄中存入符號(hào)在符號(hào)表的地址欄中存入符號(hào)表與內(nèi)情向量表連接入口地址表與內(nèi)情向量表連接入口地址 NAMEINFORMATIONCAT地址地址a符號(hào)表符號(hào)表 （1）把每一項(xiàng)置于連續(xù)的把每一項(xiàng)置于連續(xù)的K個(gè)存儲(chǔ)單元中，從而給出一個(gè)存儲(chǔ)單元中，從而給出一 張張K*N個(gè)存儲(chǔ)單元的表。個(gè)存儲(chǔ)單元的表。 （2） 把整個(gè)符號(hào)表分成把整個(gè)符號(hào)表分成M個(gè)子表，每個(gè)子表含個(gè)子表，每個(gè)子表含N項(xiàng)。假項(xiàng)。假定子表定子表Ti的每一項(xiàng)所需的字?jǐn)?shù)為的每一項(xiàng)所需的字?jǐn)?shù)為Ki，那么，那么，K=K1+Km。對(duì)于任何對(duì)于任何i,T1i

5、,Tmi的并置就構(gòu)成符號(hào)表第的并置就構(gòu)成符號(hào)表第i項(xiàng)的全部項(xiàng)的全部內(nèi)容。內(nèi)容。一張可容納一張可容納N項(xiàng)項(xiàng)的符號(hào)表在存儲(chǔ)器中的的符號(hào)表在存儲(chǔ)器中的兩種兩種表示方式：表示方式： T1 T2 T3 T4N1N2N3K1K2K3K4K=K1+K2+K3+K4例8.1 FORTRAN符號(hào)表程序段： SUBROUTINE INCWAP(M,N)10 K=M+1 M=M+4 N=K RETURN END主要表格見p2258.2 整理與查找整理與查找 一、線性表一、線性表 2、提高查找效率的辦法：給每一項(xiàng)附設(shè)一個(gè)指示器，這些指示器、提高查找效率的辦法：給每一項(xiàng)附設(shè)一個(gè)指示器，這些指示器把所有的項(xiàng)按把所有的項(xiàng)按

6、“最新最近最新最近”訪問原則連接成一條鏈，這條鏈的訪問原則連接成一條鏈，這條鏈的第一第一個(gè)個(gè)元素所指的項(xiàng)是元素所指的項(xiàng)是最新最近最新最近被查詢過的項(xiàng)，被查詢過的項(xiàng)，第二個(gè)第二個(gè)元素所指的項(xiàng)是元素所指的項(xiàng)是次新近次新近被查詢過的項(xiàng)，諸如此類。每當(dāng)填入新項(xiàng)時(shí)，總讓鏈頭指向被查詢過的項(xiàng)，諸如此類。每當(dāng)填入新項(xiàng)時(shí)，總讓鏈頭指向最新項(xiàng)，含有這種鏈條的線性表叫做最新項(xiàng)，含有這種鏈條的線性表叫做自適應(yīng)線性表自適應(yīng)線性表。1、線性表介紹、線性表介紹符號(hào)表的三種構(gòu)造法和處理法：符號(hào)表的三種構(gòu)造法和處理法： 線性查找、線性查找、二叉樹、二叉樹、雜湊技術(shù)。雜湊技術(shù)。 BC I XYZ J1INFORMATIONNA

7、ME項(xiàng)數(shù)項(xiàng)數(shù)1234AVAILABLE線性符號(hào)表線性符號(hào)表平均查找次數(shù)平均查找次數(shù)n/2二、對(duì)折查找與二叉樹二、對(duì)折查找與二叉樹 （3）若要查找的項(xiàng)大于中項(xiàng)，則）若要查找的項(xiàng)大于中項(xiàng)，則 就到就到n/2+2n的各項(xiàng)中去查找。的各項(xiàng)中去查找。在造表的同時(shí)把表格中的項(xiàng)按名字的在造表的同時(shí)把表格中的項(xiàng)按名字的“大小大小”順序整理排列。順序整理排列。所謂所謂名字的名字的“大小大小”通常是通常是指名字的內(nèi)碼二進(jìn)制。指名字的內(nèi)碼二進(jìn)制。對(duì)于經(jīng)對(duì)于經(jīng)順序化順序化的表格的查找可用的表格的查找可用對(duì)折法。對(duì)折法。對(duì)折法的對(duì)折法的查找方法查找方法如下：如下：（1）首先把要查找的項(xiàng)和中項(xiàng)）首先把要查找的項(xiàng)和中項(xiàng)（即

8、第（即第n/2+1項(xiàng)）作比較，若項(xiàng)）作比較，若 相等，則宣布查找成功。相等，則宣布查找成功。（2）若要查找的項(xiàng)小于中項(xiàng)，）若要查找的項(xiàng)小于中項(xiàng)，則繼續(xù)在則繼續(xù)在1n/2的各項(xiàng)中去查找。的各項(xiàng)中去查找。順序化的線性符號(hào)表順序化的線性符號(hào)表 XYZ J1 I BCINFORMATIONNAME項(xiàng)數(shù)項(xiàng)數(shù)1234AVAILABLE查找次數(shù)不超過查找次數(shù)不超過1+log2n 二叉樹的形成過程如下二叉樹的形成過程如下：令第一個(gè)碰到的名字作為令第一個(gè)碰到的名字作為“根根”結(jié)點(diǎn)，它結(jié)點(diǎn)，它 的左、右指示器均置為空，的左、右指示器均置為空，當(dāng)要加入新結(jié)點(diǎn)時(shí)，首先把它和根結(jié)點(diǎn)的值作比較，小者放在右枝當(dāng)要加入新結(jié)點(diǎn)

9、時(shí)，首先把它和根結(jié)點(diǎn)的值作比較，小者放在右枝上，大者放在左枝上。如果根結(jié)點(diǎn)的左（右）上，大者放在左枝上。如果根結(jié)點(diǎn)的左（右） 枝已成子樹，則讓新枝已成子樹，則讓新結(jié)點(diǎn)和子樹的根再作比較。重復(fù)上述步結(jié)點(diǎn)和子樹的根再作比較。重復(fù)上述步 驟，直至把新結(jié)點(diǎn)插入使它驟，直至把新結(jié)點(diǎn)插入使它成為二叉樹成為二叉樹 的一個(gè)端末結(jié)點(diǎn)（葉）為止。的一個(gè)端末結(jié)點(diǎn)（葉）為止。把符號(hào)表組織成一棵把符號(hào)表組織成一棵二叉樹二叉樹(二叉排序樹二叉排序樹）令每項(xiàng)是一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)附設(shè)令每項(xiàng)是一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)附設(shè)兩個(gè)指示器欄兩個(gè)指示器欄，一欄為，一欄為LEFT（左枝），令一欄為（左枝），令一欄為RIGHT（右枝）。每個(gè)結(jié)點(diǎn)的

10、主欄內(nèi)碼值被（右枝）。每個(gè)結(jié)點(diǎn)的主欄內(nèi)碼值被看成是代表該結(jié)點(diǎn)的值?？闯墒谴碓摻Y(jié)點(diǎn)的值。要求：要求：任何結(jié)點(diǎn)任何結(jié)點(diǎn)P右枝右枝的所有結(jié)點(diǎn)值均應(yīng)的所有結(jié)點(diǎn)值均應(yīng)小于小于結(jié)點(diǎn)結(jié)點(diǎn)P的值的值，而，而左枝左枝的任何結(jié)點(diǎn)值均應(yīng)的任何結(jié)點(diǎn)值均應(yīng)大于大于結(jié)點(diǎn)結(jié)點(diǎn)P的值的值。 I BC XYZ J1INFORMATIONNAME項(xiàng)數(shù)項(xiàng)數(shù)1234AVAILABLEJ1根LEFTRIGHT00 0XYZ00BC00I0三、雜湊技術(shù)三、雜湊技術(shù) 1、假定有一個(gè)足夠大的區(qū)域，這個(gè)區(qū)域用來填寫一張含、假定有一個(gè)足夠大的區(qū)域，這個(gè)區(qū)域用來填寫一張含N項(xiàng)的符號(hào)項(xiàng)的符號(hào)表。構(gòu)造一個(gè)表。構(gòu)造一個(gè)地址函數(shù)地址函數(shù)H，對(duì)任何名字，

11、對(duì)任何名字，H函數(shù)的取值于函數(shù)的取值于0至至N-1之間之間。即不論對(duì)此項(xiàng)查表或填表，都能從即不論對(duì)此項(xiàng)查表或填表，都能從H函數(shù)中獲得它在表中的位置。函數(shù)中獲得它在表中的位置。 2、對(duì)地址函數(shù)、對(duì)地址函數(shù)H有有兩點(diǎn)要求兩點(diǎn)要求：（1）函數(shù)的計(jì)算要簡單、高效；）函數(shù)的計(jì)算要簡單、高效；（2）函數(shù)值能比較均勻的分布在）函數(shù)值能比較均勻的分布在0至至N-1之間。之間。3、構(gòu)造函數(shù)、構(gòu)造函數(shù)H的辦法：的辦法：直接地址法、數(shù)字分析法、平方取中法、直接地址法、數(shù)字分析法、平方取中法、折疊法、除留余數(shù)法、隨機(jī)數(shù)法折疊法、除留余數(shù)法、隨機(jī)數(shù)法4、解決地址沖突的辦法：、解決地址沖突的辦法： 開放地址法、再哈希法、

12、鏈地址法、開放地址法、再哈希法、鏈地址法、建立一個(gè)公共溢出區(qū)建立一個(gè)公共溢出區(qū) 3、填入一個(gè)新的項(xiàng)的過程：、填入一個(gè)新的項(xiàng)的過程： （1）先計(jì)算出）先計(jì)算出H函數(shù)的值函數(shù)的值h（在（在0與與N-1之間），將之間），將HASHTABLEh 的值賦給的值賦給P（若未曾有雜湊值為（若未曾有雜湊值為h的項(xiàng)名填入過，則將的項(xiàng)名填入過，則將P置空）。置空）。（2）然后將）然后將HASHTABLEh置為置為AVAILABLE，再把新名及其鏈，再把新名及其鏈接指示接指示 器的值器的值P填進(jìn)指針?biāo)赶虻姆?hào)表位置。填進(jìn)指針?biāo)赶虻姆?hào)表位置。 4、使用此方法的查表過程如下：、使用此方法的查表過程如下： 首先計(jì)算

13、出此項(xiàng)的函數(shù)首先計(jì)算出此項(xiàng)的函數(shù)H的值等于的值等于h，然后就指示器，然后就指示器 HASHTABLEh所指的項(xiàng)鏈逐一按序查找（線性查找）所指的項(xiàng)鏈逐一按序查找（線性查找）雜湊技術(shù)：使用一張雜湊鏈表通過間接方式查添符號(hào)表。雜湊技術(shù)：使用一張雜湊鏈表通過間接方式查添符號(hào)表。將具有相同雜湊值符號(hào)名連成一串，便于線性查找。雜湊表是一將具有相同雜湊值符號(hào)名連成一串，便于線性查找。雜湊表是一個(gè)可容納個(gè)可容納N個(gè)指示器值的一維數(shù)組，它的每個(gè)元素的初值全為個(gè)指示器值的一維數(shù)組，它的每個(gè)元素的初值全為null。符號(hào)表除了通常包含的欄外，還增設(shè)了一鏈接欄，他符號(hào)表除了通常包含的欄外，還增設(shè)了一鏈接欄，他把所有持有

14、相把所有持有相同雜湊值的符號(hào)名連接成一條鏈同雜湊值的符號(hào)名連接成一條鏈。（見下頁）。（見下頁）availableSYM1H（SYM1）=hp=HASHTABLEh=nullHASHTABLEh=AVAVILABLE=n1SYM1null 01hN-1雜湊表雜湊表符號(hào)表符號(hào)表 LinkInformationName n1n2n3n1nullavailableSYM2H（SYM2）=hp=HASHTABLEh= n1HASHTABLEh=AVAVILABLE=n2n2SYM2n1SYM3H（SYM3）=hp=HASHTABLEh= n2HASHTABLEh=AVAVILABLE=n3n3SYM3n

15、2availableavailable8.3名字的作用范圍名字的作用范圍 對(duì)于對(duì)于過程嵌套結(jié)構(gòu)型過程嵌套結(jié)構(gòu)型的程序設(shè)計(jì)語言，的程序設(shè)計(jì)語言，每層過程中說明的名字每層過程中說明的名字只局限于該過程只局限于該過程，離開了所在的過程就無意義了。也就是說，離開了所在的過程就無意義了。也就是說， 同一個(gè)標(biāo)識(shí)符，具有不同的性質(zhì)，要求分配不同的存儲(chǔ)空間。同一個(gè)標(biāo)識(shí)符，具有不同的性質(zhì)，要求分配不同的存儲(chǔ)空間。這樣，如何組織符號(hào)表，使得同一個(gè)標(biāo)識(shí)符在不同的作用域中這樣，如何組織符號(hào)表，使得同一個(gè)標(biāo)識(shí)符在不同的作用域中能得到正確的引用，而不會(huì)產(chǎn)生混亂。能得到正確的引用，而不會(huì)產(chǎn)生混亂。通常實(shí)現(xiàn)通常實(shí)現(xiàn)最近嵌套作

16、用域規(guī)則最近嵌套作用域規(guī)則的辦法是：對(duì)每個(gè)過程指定一個(gè)的辦法是：對(duì)每個(gè)過程指定一個(gè)唯一的編號(hào)，即過程的順序號(hào)，以便跟蹤過程里的局部名字。唯一的編號(hào)，即過程的順序號(hào)，以便跟蹤過程里的局部名字。在符號(hào)表中，表示在符號(hào)表中，表示局部名字用一個(gè)二元組：局部名字用一個(gè)二元組：對(duì)一個(gè)名字查找符號(hào)表是對(duì)一個(gè)名字查找符號(hào)表是:只有當(dāng)表項(xiàng)中的名字其字符逐個(gè)匹配只有當(dāng)表項(xiàng)中的名字其字符逐個(gè)匹配,并且該記錄相關(guān)的編號(hào)和當(dāng)前所處理的過程的編號(hào)匹配時(shí)并且該記錄相關(guān)的編號(hào)和當(dāng)前所處理的過程的編號(hào)匹配時(shí),才能才能確定查找成功確定查找成功.Pascal的符號(hào)表組織的符號(hào)表組織 1、在在Pascal程序中標(biāo)識(shí)符的作用域是包含說

17、明該標(biāo)識(shí)符的一個(gè)最程序中標(biāo)識(shí)符的作用域是包含說明該標(biāo)識(shí)符的一個(gè)最小分程序。具體的概括為如下幾點(diǎn)：小分程序。具體的概括為如下幾點(diǎn)：（1）如果一個(gè)標(biāo)識(shí)符在某一分程序首部已作說明如果一個(gè)標(biāo)識(shí)符在某一分程序首部已作說明，則不論此分程序，則不論此分程序是否含有內(nèi)層分程序，也不論內(nèi)分程序在嵌套多少層，只要在內(nèi)是否含有內(nèi)層分程序，也不論內(nèi)分程序在嵌套多少層，只要在內(nèi)層分程序未再次對(duì)該標(biāo)識(shí)符加以說明，層分程序未再次對(duì)該標(biāo)識(shí)符加以說明，則此標(biāo)識(shí)符在整個(gè)分程序中則此標(biāo)識(shí)符在整個(gè)分程序中均有定義，且有相同的屬性均有定義，且有相同的屬性。（2）程序中的）程序中的標(biāo)號(hào)局限于定義該標(biāo)號(hào)的最小分程序標(biāo)號(hào)局限于定義該標(biāo)號(hào)的最

18、小分程序。（3）由于）由于Pascal程序中的過程可具有嵌套的結(jié)構(gòu)，因此，可將每程序中的過程可具有嵌套的結(jié)構(gòu)，因此，可將每 一過程說明都假想為一個(gè)分程序。出現(xiàn)在過程體中的非形式一過程說明都假想為一個(gè)分程序。出現(xiàn)在過程體中的非形式 參數(shù)，參數(shù)，依其在相應(yīng)的過程體中被說明與否，確定它們對(duì)過程而言是局部變依其在相應(yīng)的過程體中被說明與否，確定它們對(duì)過程而言是局部變量還是非局部變量，量還是非局部變量，而形式參數(shù)則總是局限于相應(yīng)而形式參數(shù)則總是局限于相應(yīng) 的過程體的的過程體的。PASCAL程序中的標(biāo)識(shí)符（或標(biāo)號(hào)）的作用域，總是與說明（定義）程序中的標(biāo)識(shí)符（或標(biāo)號(hào)）的作用域，總是與說明（定義）這些標(biāo)識(shí)符的分

19、程序的層次相聯(lián)系的這些標(biāo)識(shí)符的分程序的層次相聯(lián)系的。參見P232（1） 針對(duì)符號(hào)表設(shè)計(jì)為針對(duì)符號(hào)表設(shè)計(jì)為棧符號(hào)表?xiàng)７?hào)表，新名字出現(xiàn)總是從棧頂填入。，新名字出現(xiàn)總是從棧頂填入。為了保證從內(nèi)層向外層查，查找操作從符號(hào)表的棧頂往底部查找。為了保證從內(nèi)層向外層查，查找操作從符號(hào)表的棧頂往底部查找。2、對(duì)于嵌套結(jié)構(gòu)型程序設(shè)計(jì)語言（、對(duì)于嵌套結(jié)構(gòu)型程序設(shè)計(jì)語言（Pascal）的特點(diǎn)，可采用如下）的特點(diǎn)，可采用如下 辦法辦法：（2）過程的嵌套層次表（過程的嵌套層次表（display），是引入的一個(gè)顯示層次關(guān)系），是引入的一個(gè)顯示層次關(guān)系表表。其作用是為了描述過程的嵌套層次，指出當(dāng)前正處理的各嵌套。其作用是

20、為了描述過程的嵌套層次，指出當(dāng)前正處理的各嵌套的過程（或函數(shù)）相應(yīng)的子符號(hào)表在棧符號(hào)表中的起始位置（相對(duì)的過程（或函數(shù)）相應(yīng)的子符號(hào)表在棧符號(hào)表中的起始位置（相對(duì)地址）。地址）。（3）在信息欄中引入一個(gè)指針域（在信息欄中引入一個(gè)指針域（previous)，用來鏈接它在同一，用來鏈接它在同一個(gè)過程內(nèi)的下一名字在表中的下標(biāo)（相對(duì)位置）。每一層最后一個(gè)個(gè)過程內(nèi)的下一名字在表中的下標(biāo)（相對(duì)位置）。每一層最后一個(gè)域名字，指針域之值為域名字，指針域之值為0。這樣每當(dāng)需要查找個(gè)新名字時(shí)，就能通。這樣每當(dāng)需要查找個(gè)新名字時(shí)，就能通過過display表找出當(dāng)前正在處理的最內(nèi)層的過程及所有外層的子符號(hào)表找出當(dāng)前正在處理的最內(nèi)層的過程及所有外層的子符號(hào)表在棧符號(hào)表中的位置。然后通過指針域可以找到同一個(gè)過程內(nèi)的表在棧符號(hào)表中的位置。然后通過指針域可以找到同一個(gè)過程內(nèi)的所有被說明的名字。所有被說明的名字。 例：例： procedure/B1 var a,b:real; procedure/B2 var c,d:real; procedure/B3 var e,f:real; begin end; begin end; begin end; PreviousInformation Name1110987654321棧符號(hào)表?xiàng)７?hào)表DISPLAYab