編譯原理與技術(shù)講義 第6章 符號(hào)表的組織和管理VIP

1、編譯原理與技術(shù)第6章符號(hào)表的組織和管理 青島大學(xué)信息工程學(xué)院主要內(nèi)容符號(hào)表的作用 符號(hào)表的主要屬性及其作用 符號(hào)表的組織結(jié)構(gòu) 名字的作用范圍編譯原理與技術(shù)26.1 符號(hào)表的作用 登記符號(hào)屬性值在源程序的各個(gè)分析階段，編譯程序根據(jù)標(biāo)識(shí)符的聲明信息收集它屬性的有關(guān)值，并把它們存放在符合表中。每種語(yǔ)言規(guī)則定義了不同的符號(hào)屬性；即使是同一個(gè)語(yǔ)言，不同的編譯程序也可能會(huì)定義并且收集不同的屬性信息?，F(xiàn)代編程語(yǔ)言中一般包括常數(shù)聲明、變量聲明、類型聲明和過(guò)程/函數(shù)聲明等四類聲明。對(duì)于每類聲明，編譯程序要收集、存儲(chǔ)和應(yīng)用的屬性完全不同。 編譯原理與技術(shù)36.1 符號(hào)表的作用例6.1 C語(yǔ)言的變量聲明short

2、int a;float b = 0.0;把標(biāo)識(shí)符a聲明為短整數(shù)型，把b聲明為浮點(diǎn)類型，而且初始化為0。那么，編譯程序?qū)γ總€(gè)變量要記錄它的類型，以便執(zhí)行類型檢查和分配存儲(chǔ)，比如短整型變量i占2個(gè)字節(jié)；要記錄它在存儲(chǔ)器中的位置（相對(duì)位移或絕對(duì)地址），以便目標(biāo)程序運(yùn)行時(shí)訪問；若像b有初始值，則還需要記錄這個(gè)初始值。 編譯原理與技術(shù)46.1 符號(hào)表的作用例6.2 下面是計(jì)算階乘n!的C語(yǔ)言的函數(shù)聲明：int factory ( int n) int t;if (n = = 0) | | n = = 1) t = 1;else t = n factory (n1); return t;對(duì)于函數(shù)facto

3、ry要記錄的屬性包括：函數(shù)的名稱，各種變量如參數(shù)、返回值、局部變量及其類型，同時(shí)還要記錄函數(shù)的調(diào)用信息，以便在函數(shù)體執(zhí)行完畢以后返回到調(diào)用點(diǎn)，特別是對(duì)這種允許遞歸調(diào)用的函數(shù)，要為每次調(diào)用保留上面提到的所有信息。 編譯原理與技術(shù)56.1 符號(hào)表的作用查找符號(hào)的屬性 符號(hào)表存放了源程序中的各種類型的信息，比如數(shù)值、變量類型、參數(shù)傳遞的地址等，在分析和翻譯源程序的過(guò)程中會(huì)被不斷地查詢。例如，對(duì)于上述的變量聲明，如果源程序有代碼a + b時(shí)，就需要查找、計(jì)算表達(dá)式中運(yùn)算數(shù)的類型和值，以便計(jì)算出表達(dá)式。又如，在源程序中如果出現(xiàn)了函數(shù)調(diào)用factory (6)，編譯程序就需要查找到factory的聲明，找

4、到實(shí)參6的地址并傳給形參n，執(zhí)行函數(shù)factory的體，并返回值，等。編譯原理與技術(shù)66.1 符號(hào)表的作用檢查符號(hào)的合法性 例如，對(duì)于上述聲明，代碼 a = a + b，C語(yǔ)言的編譯將檢查變量a和b的類型，把表達(dá)式a + b的結(jié)果轉(zhuǎn)換成短整型，僅取整數(shù)部分進(jìn)行賦值。在其它強(qiáng)類型語(yǔ)言，如Pascal和Ada，表達(dá)式運(yùn)算數(shù)的類型必須一致，不能進(jìn)行隱式類型轉(zhuǎn)換，對(duì)于這樣的表達(dá)式a + b，編譯程序在語(yǔ)義分析的過(guò)程中將發(fā)現(xiàn)并報(bào)告類型錯(cuò)誤的信息。又如，面向?qū)ο笳Z(yǔ)言的繼承性和多態(tài)性允許同一個(gè)消息在不同的環(huán)境中調(diào)用不同的方法（函數(shù)），即調(diào)用同名但在不同的類中實(shí)現(xiàn)的方法。這就需要編譯或者運(yùn)行時(shí)在方法的符號(hào)表中

5、查詢?cè)趨?shù)、返回?cái)?shù)以及方法方面名字一致的實(shí)現(xiàn)。編譯原理與技術(shù)76.1 符號(hào)表的作用作為目標(biāo)代碼生成階段地址分配的依據(jù) 標(biāo)識(shí)符由它定義的存儲(chǔ)類型或它在程序中的位置來(lái)確定。首先是要確定變量存儲(chǔ)的區(qū)域。例如，在Java語(yǔ)言中，整數(shù)的類型（以及所占用的字節(jié)）有byte（1個(gè)字節(jié)）、short（2個(gè)字節(jié)）、int（4個(gè)字節(jié)）以及l(fā)ong（8個(gè)字節(jié)），而float類型占4個(gè)字節(jié)，double類型占8個(gè)字節(jié)。又如，對(duì)寄存器變量，編譯將盡可能地把它們保留在機(jī)器的寄存器當(dāng)中，以提高運(yùn)行速度；而對(duì)在一個(gè)文件中定義的外部變量，它們要在不同的源程序文件之間訪問，需要編譯程序把它們放在所有源程序文件都可以方便尋找到的存

6、儲(chǔ)器的位置。其次，要根據(jù)標(biāo)識(shí)符出現(xiàn)的順序，決定標(biāo)識(shí)符在某個(gè)存儲(chǔ)區(qū)域中的具體位置，而有關(guān)區(qū)域的標(biāo)志及其相對(duì)位置都是作為該標(biāo)識(shí)符的語(yǔ)義信息存放在它的符號(hào)表中的。編譯原理與技術(shù)86.2 符號(hào)表的主要屬性及其作用不同的符號(hào)類別包含了不同的屬性，由于它們的信息不同，也就導(dǎo)致了符號(hào)表的組織有較大的差別。例如，數(shù)量類型的變量名字和過(guò)程名字：對(duì)于一個(gè)變量名要記錄其類型（如整型、實(shí)型、布爾型等）、占用的存儲(chǔ)字節(jié)以及相對(duì)與某個(gè)基準(zhǔn)位置的相對(duì)位置；對(duì)一個(gè)過(guò)程名要記錄的屬性包括參數(shù)的個(gè)數(shù)及其類型，該過(guò)程是否有返回值，過(guò)程中的變量聲明，甚至過(guò)程聲明（如果像Pascal語(yǔ)言允許嵌套過(guò)程聲明）等信息。 編譯原理與技術(shù)96.

7、2 符號(hào)表的主要屬性及其作用符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性符號(hào)名 符號(hào)名可以是變量名、函數(shù)名（操作名）、類型名、類對(duì)象名等每個(gè)符號(hào)名通常由若干個(gè)（非空）的字符組成的字符串來(lái)表達(dá)，在語(yǔ)言中它們通常是一個(gè)變量、函數(shù)或?qū)ο蟮奈灰茦?biāo)志，因此在符號(hào)表中的符號(hào)名作為表項(xiàng)的唯一區(qū)別一般是不允許重名的。符號(hào)名與它在符號(hào)表中的位置建立起一一對(duì)應(yīng)的關(guān)系，這使得我們可以用一個(gè)符號(hào)在表中的位置來(lái)代替該符號(hào)名、訪問其信息。通常把一個(gè)標(biāo)識(shí)符在符號(hào)表中的位置值稱為該標(biāo)識(shí)符的內(nèi)部代碼。在經(jīng)過(guò)分析處理的源程序中，標(biāo)識(shí)符不再是一個(gè)字符串而是一個(gè)表示內(nèi)部碼的整數(shù)值，這不但便于識(shí)別，而且也可以壓縮存儲(chǔ)和表達(dá)

8、的長(zhǎng)度。 編譯原理與技術(shù)106.2 符號(hào)表的主要屬性及其作用 符號(hào)名語(yǔ)言中的符號(hào)名通常用標(biāo)識(shí)符來(lái)表示。根據(jù)語(yǔ)言的定義，程序中出現(xiàn)的重名標(biāo)識(shí)符定義將按照該標(biāo)識(shí)符在程序中的作用域和可視規(guī)則進(jìn)行相應(yīng)的處理。而在程序的運(yùn)行過(guò)程中，符號(hào)表中的符號(hào)名始終是唯一的標(biāo)志。在一些允許操作重載、類繼承的語(yǔ)言中，函數(shù)名、操作名允許重名，對(duì)于重載操作的標(biāo)識(shí)符，它們可以通過(guò)參數(shù)的個(gè)數(shù)與類型以及返回值的類型來(lái)區(qū)別；而對(duì)于操作的繼承，編譯器可以構(gòu)造繼承圖，同時(shí)保存類結(jié)構(gòu)，這樣就可以為每個(gè)操作和屬性找到唯一的定義。例如，對(duì)應(yīng)不同的參數(shù)類型，可以定義幾個(gè)求和重載函數(shù)：int sum ( int a, int b) double

9、 sum ( double a, double b)float sum（float a, float b, float c）當(dāng)某個(gè)函數(shù)中調(diào)用到重載函數(shù)時(shí)，編譯器根據(jù)實(shí)參的類型和個(gè)數(shù)去調(diào)用相應(yīng)的函數(shù)。編譯原理與技術(shù)116.2 符號(hào)表的主要屬性及其作用符號(hào)種屬 由于語(yǔ)言中符號(hào)所擁有的屬性可能不同，其組織就可以采用不同的數(shù)據(jù)結(jié)構(gòu)，可以用符號(hào)的種屬來(lái)區(qū)別每個(gè)符號(hào)的基本劃分。根據(jù)不同的語(yǔ)言，符號(hào)的種屬可以包括：簡(jiǎn)單變量、結(jié)構(gòu)型變量、數(shù)組、過(guò)程、類型、類等?？梢砸罁?jù)符號(hào)種屬的劃分來(lái)組織符號(hào)表，一種方式是為每個(gè)種屬的標(biāo)識(shí)符建立一張表，這樣，可以對(duì)符號(hào)表類似地安排組織結(jié)構(gòu)、進(jìn)行同樣的操作；另外一種方式把所有種

10、屬的標(biāo)識(shí)符統(tǒng)一安排在一張表中，根據(jù)符號(hào)的種屬進(jìn)行條件判斷，對(duì)不同種屬的特殊型執(zhí)行不同的存儲(chǔ)安排和操作。符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性編譯原理與技術(shù)126.2 符號(hào)表的主要屬性及其作用符號(hào)類型 現(xiàn)代程序語(yǔ)言中的一個(gè)重要構(gòu)造就是數(shù)據(jù)類型（類型），它是變量標(biāo)識(shí)符的重要屬性，函數(shù)的數(shù)據(jù)類型指的是該函數(shù)返回值的數(shù)據(jù)類型。現(xiàn)代語(yǔ)言通常都有如下的基本類型：整型、實(shí)型、字符型、布爾型、邏輯型等；符號(hào)的類型屬性從源程序中該符號(hào)的定義中得到變量符號(hào)的數(shù)據(jù)類型屬性不但決定了該變量的數(shù)據(jù)在存儲(chǔ)器中的存儲(chǔ)格式，也規(guī)定了可以對(duì)該變量施加的操作運(yùn)算。符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息

11、其它屬性編譯原理與技術(shù)136.2 符號(hào)表的主要屬性及其作用符號(hào)類型 目前的大多數(shù)語(yǔ)言都在基本類型的基礎(chǔ)上定義復(fù)合數(shù)據(jù)類型，如數(shù)組、集合和記錄。許多語(yǔ)言還允許程序員自己定義數(shù)據(jù)類型。這些復(fù)合類型的基本元素可以是基本類型，也可以是復(fù)合類型。作為存儲(chǔ)變量地址的指針類型所指向的變量可以是基本的數(shù)據(jù)類型，也可以是其它任何一種復(fù)合數(shù)據(jù)類型。符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性每一個(gè)變量的類型是符號(hào)表中標(biāo)識(shí)符屬性的重要信息。 編譯原理與技術(shù)146.2 符號(hào)表的主要屬性及其作用存儲(chǔ)類別 大多數(shù)程序語(yǔ)言對(duì)變量的存儲(chǔ)類別采用兩種方式。一種是用關(guān)鍵字指定，例如，在FORTRAN語(yǔ)言中用COMMO

12、N來(lái)定義公共存儲(chǔ)區(qū)域，允許不同程序段都可以訪問這些數(shù)據(jù)；又如，C和C+語(yǔ)言規(guī)定static定義的變量屬于文件的靜態(tài)存儲(chǔ)變量或?qū)儆诤瘮?shù)內(nèi)部的靜態(tài)存儲(chǔ)變量，這些變量在編譯時(shí)分配存儲(chǔ)空間，如果定義時(shí)沒有初值，編譯器還需要將它們初始化為0。另一種方式是根據(jù)定義變量的聲明在程序中的位置來(lái)決定。例如，C+規(guī)定在一個(gè)文件中定義的變量缺省為外部的，即程序的公共存儲(chǔ)變量；而在函數(shù)體內(nèi)缺省存儲(chǔ)類別關(guān)鍵字所定義的變量是內(nèi)部變量，是屬于該函數(shù)體所獨(dú)有的私有存儲(chǔ)變量，因而是動(dòng)態(tài)地分配存儲(chǔ)空間。區(qū)別符號(hào)存儲(chǔ)類型地屬性是編譯過(guò)程中語(yǔ)義處理、檢查和存儲(chǔ)分配的重要依據(jù)。符號(hào)的存儲(chǔ)類別同時(shí)還決定了符號(hào)變量的作用域、可見性和它的生

13、命周期等性質(zhì) 。符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性編譯原理與技術(shù)156.2 符號(hào)表的主要屬性及其作用作用域 一個(gè)標(biāo)識(shí)符在程序中起作用的范圍稱為其作用域。一般來(lái)說(shuō)，定義一個(gè)符號(hào)的位置及存儲(chǔ)類型就決定了該符號(hào)的作用域，就是它可以出現(xiàn)的場(chǎng)合，可以在程序中作為參數(shù)、表達(dá)式的運(yùn)算數(shù)等被引用。C語(yǔ)言中外部變量的作用域是整個(gè)程序，一個(gè)外部符號(hào)的定義在整個(gè)策劃能夠許中只能出現(xiàn)一次，為了方便使用和編譯，同名標(biāo)識(shí)符的其它說(shuō)明可以多次出現(xiàn)。FORTRAN語(yǔ)言中的COMMON變量的作用域則不是整個(gè)程序，而只能在定義這個(gè)COMMON塊的函數(shù)或過(guò)程中引用。面向?qū)ο笳Z(yǔ)言，如C+，的每個(gè)類都引入了一個(gè)獨(dú)

14、立的類域。 符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性編譯原理與技術(shù)166.2 符號(hào)表的主要屬性及其作用作用域與可見性 標(biāo)識(shí)符的可見性從另外一個(gè)角度說(shuō)明其有效性，它與作用域有一定一致性。標(biāo)識(shí)符的作用域包含可見范圍，但是，可見范圍不會(huì)超過(guò)作用域。可見性在理解同名是不是合法的作用域嵌套時(shí)十分直觀。對(duì)于外層塊域內(nèi)層塊定義的同名標(biāo)識(shí)符，在外層作用域中，內(nèi)層所定義的標(biāo)識(shí)符時(shí)不可見的，即外層所引用的是外層所定義的標(biāo)識(shí)符；同樣，在內(nèi)層作用域中，外層的標(biāo)識(shí)符將被內(nèi)層的同名標(biāo)識(shí)符所屏蔽，變得不可見，即外層中同名標(biāo)識(shí)符的可見范圍是作用域中挖去內(nèi)層塊的范圍，在內(nèi)存塊形成了作用域洞 。符號(hào)名符號(hào)種屬符號(hào)

15、類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性編譯原理與技術(shù)176.2 符號(hào)表的主要屬性及其作用例6.3 圖6.1（b）顯示了下列程序段中變量的作用域與可見性，其中int m的作用域在括號(hào)中不可見，即這個(gè)程序塊在int m的作用域中挖了一個(gè)洞。 int m = 1;float n; float m = 3.14; n = 5.5; m+;int m和float n的作用域int m和n可見float m不可見float m的作用域float m和n可見int m不可見符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性編譯原理與技術(shù)18存儲(chǔ)分配信息 編譯程序需要根據(jù)符號(hào)的存儲(chǔ)類別定義以及它們?cè)诔绦?/p>

16、中出現(xiàn)的位置和順序來(lái)確定每一個(gè)符號(hào)應(yīng)該分配的存儲(chǔ)區(qū)域及其具體位置。通常情況下，編譯為每個(gè)符號(hào)分配一個(gè)相對(duì)于某個(gè)基址的相對(duì)位移，而不是絕對(duì)的內(nèi)存地址。編譯程序中有關(guān)源程序的存儲(chǔ)組織和分配的問題將在第7章中詳細(xì)討論。符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性6.2 符號(hào)表的主要屬性及其作用編譯原理與技術(shù)196.2 符號(hào)表的主要屬性及其作用其它屬性 數(shù)組內(nèi)情向量 需要把描述數(shù)組屬性的信息如數(shù)組類型、維數(shù)、每個(gè)維的上下界、數(shù)組元素的首地址等登錄在符號(hào)表中，以便確定數(shù)組在存儲(chǔ)器占用的空間和數(shù)組元素的確定，并且完成數(shù)組的翻譯。記錄結(jié)構(gòu)型的成員信息 一個(gè)記錄結(jié)構(gòu)型的變量包含若干成員，每個(gè)成員的

17、數(shù)據(jù)類型可以彼此不同，因此，一個(gè)記錄結(jié)構(gòu)型變量在存儲(chǔ)分配時(shí)所占空間的大小由其成員來(lái)確定，而且，對(duì)每個(gè)成員的訪問還需要它所屬成員排列次序的屬性信息。函數(shù)或過(guò)程的形參 函數(shù)或過(guò)程的形參作為其局部變量，同時(shí)又是對(duì)外部調(diào)用的接口。每個(gè)函數(shù)或過(guò)程形參的個(gè)數(shù)、類型、排列順序都體現(xiàn)了調(diào)用函數(shù)或過(guò)程時(shí)的屬性，它們都應(yīng)該反映在符號(hào)表中，以便在過(guò)程調(diào)用的時(shí)候進(jìn)行參數(shù)傳遞，并且執(zhí)行語(yǔ)義檢查（如處理函數(shù)名的重載）。在面相對(duì)象語(yǔ)言中，還必須把一個(gè)類或其超類所定義同名方法存放在一個(gè)方法表中，指向每個(gè)方法的實(shí)現(xiàn)操作，以便實(shí)現(xiàn)面相對(duì)象的繼承性質(zhì)。 符號(hào)名符號(hào)種屬符號(hào)類型存儲(chǔ)類別作用域存儲(chǔ)分配信息其它屬性編譯原理與技術(shù)206.

18、3 符號(hào)表的組織結(jié)構(gòu)符號(hào)表的整體組織結(jié)構(gòu)符號(hào)名欄目也叫主欄，其內(nèi)容是源程序中出現(xiàn)的標(biāo)識(shí)符，它是區(qū)分每個(gè)表項(xiàng)的關(guān)鍵碼。對(duì)于保留字、類型、函數(shù)，它們的名字（標(biāo)識(shí)符）就是符號(hào)表的關(guān)鍵碼；對(duì)于語(yǔ)言中的保留字，它們本身就是表項(xiàng)中的關(guān)鍵碼；對(duì)于語(yǔ)言中操作符，如乘冪“*”、賦值號(hào)“:=、+=”或者FORTRAN中的拼寫操作“.GT.”，其字符或字符串就作為該操作符表項(xiàng)的關(guān)鍵碼。 符號(hào)名信息欄屬性值1屬性值2屬性值m表項(xiàng)1（入口1）表項(xiàng)2（入口2）表項(xiàng)n（入口n）編譯原理與技術(shù)216.3 符號(hào)表的組織結(jié)構(gòu)編譯程序?qū)Ψ?hào)表的總體組織可以有3種形式假設(shè)有下列三種類型的符號(hào)及其屬性： 第一類符號(hào)符號(hào)種屬名字類型值地

19、址 第二類符號(hào) 符號(hào)種屬名字字節(jié)數(shù)第三類符號(hào)符號(hào)種屬名字值嵌套數(shù)地址編譯原理與技術(shù)226.3 符號(hào)表的組織結(jié)構(gòu)第一種（如圖6.3所示）：根據(jù)符號(hào)類型進(jìn)行分類，把屬性完全相同的那些符號(hào)安排在一張表中這樣就構(gòu)造出許多不同的符號(hào)表，每個(gè)表的信息欄目中屬性個(gè)數(shù)和結(jié)構(gòu)完全一樣，而且每個(gè)表項(xiàng)的屬性欄目都是等長(zhǎng)、有效。這種單個(gè)符號(hào)表的管理和操作都比較方便，空間使用效率也高。缺點(diǎn)是一個(gè)編譯程序要同時(shí)管理若干個(gè)不同類型的符號(hào)表，符號(hào)表分得太散，對(duì)不同類型符號(hào)表中的共同屬性必須設(shè)置重復(fù)的管理機(jī)制，增加了符號(hào)表管理的工作量和復(fù)雜度。 符號(hào)表1符號(hào)種屬名字類型值地址符號(hào)表2符號(hào)種屬名字字節(jié)數(shù)符號(hào)表3符號(hào)種屬名字值嵌套

20、數(shù)地址編譯原理與技術(shù)236.3 符號(hào)表的組織結(jié)構(gòu)第二種（如圖6.4所示）：把語(yǔ)言中的所有符號(hào)都組織在一張符號(hào)表中。優(yōu)點(diǎn)是總體管理符號(hào)表集中、單一，不同類型符號(hào)中的相同屬性得到了一致的管理和處理。為了完整地存放所有屬性就導(dǎo)致每個(gè)表項(xiàng)所包含的屬性個(gè)數(shù)不一樣，出現(xiàn)不等長(zhǎng)的表項(xiàng)，這就極大地提高了符號(hào)表管理和處理的復(fù)雜性。為了保持表項(xiàng)等長(zhǎng)，把所有符號(hào)的全部屬性都作為符號(hào)表中信息欄目的屬性，這樣的組織有助于減低符號(hào)表的管理和處理的復(fù)雜性。但是對(duì)于不同類型的符號(hào)，可能增加了無(wú)用的屬性空間，從而降低編譯程序的空間使用效率。例如，對(duì)于第二類符號(hào)，單一組織的符號(hào)表中就超過(guò)一般的屬性不需要，極大地浪費(fèi)存儲(chǔ)空間。 符

21、號(hào)種屬名字類型值字節(jié)數(shù)地址1地址2編譯原理與技術(shù)246.3 符號(hào)表的組織結(jié)構(gòu)第三種是前兩種的折衷形式。根據(jù)屬性的相似程度把符號(hào)表分成若干類型，每個(gè)類型組織成一張表，每張表中記錄的符號(hào)都有很多相同的屬性。這種組織方式在管理的復(fù)雜程度和空間的使用效率方面都取得了上述兩種組織的這種效果。而且，可以根據(jù)目標(biāo)系統(tǒng)的體系結(jié)構(gòu)和編譯程序設(shè)計(jì)者的經(jīng)驗(yàn)，對(duì)符號(hào)表的分類進(jìn)行選擇和調(diào)整。例如，可以將上面的類型一和類型三的符號(hào)合成一張表，類型二構(gòu)成一個(gè)單獨(dú)的符號(hào)表。第一類和第三類共同的符號(hào)表第二類符號(hào)的符號(hào)表符號(hào)種屬名字類型值嵌套數(shù)地址符號(hào)種屬名字字節(jié)數(shù)編譯原理與技術(shù)256.3 符號(hào)表的組織結(jié)構(gòu)關(guān)鍵碼域的組織符號(hào)表的

22、關(guān)鍵碼域就是符號(hào)本身，它可以是語(yǔ)言的保留字、操作符，也可以是標(biāo)識(shí)符，如變量名、常數(shù)名、函數(shù)名、類型名、類名等程序結(jié)構(gòu)。語(yǔ)言文法的詞法對(duì)各種符號(hào)都有嚴(yán)格的定義。保留字和操作符的名字一般是只有唯一的拼寫方法，而且不能用當(dāng)作其它用途的用戶定義的標(biāo)識(shí)符。標(biāo)識(shí)符通常是以字母開頭的、長(zhǎng)度確定或不限長(zhǎng)度的字母和數(shù)字組成的字符串。如果語(yǔ)言對(duì)標(biāo)識(shí)符的長(zhǎng)度有限制，可以讓符號(hào)表中關(guān)鍵碼域有標(biāo)識(shí)符允許的最大長(zhǎng)度以容納語(yǔ)言的整個(gè)標(biāo)識(shí)符單詞。 但是，如果語(yǔ)言對(duì)標(biāo)識(shí)符的長(zhǎng)度不加限制，或者為了避免最大標(biāo)識(shí)符長(zhǎng)度過(guò)大而浪費(fèi)存儲(chǔ)空間，通常的做法是另外設(shè)立一個(gè)存放標(biāo)識(shí)符單詞的字符數(shù)組，在符號(hào)表的名字欄目中僅給出標(biāo)識(shí)符單詞在這個(gè)數(shù)組

23、中的首地址和符號(hào)長(zhǎng)度的二元組。這樣，符號(hào)表的關(guān)鍵碼域可以有一致的大小，而且，同時(shí)也可以節(jié)省存儲(chǔ)空間。 編譯原理與技術(shù)266.3 符號(hào)表的組織結(jié)構(gòu)例6.4 假定有標(biāo)識(shí)符student、name、birthday、code、p，它們依次存放在上述的標(biāo)識(shí)符單詞數(shù)組中，其間沒有間隔標(biāo)志，這樣的符號(hào)表結(jié)構(gòu)如圖6.6所示 。tudentnamebirthdaycodeps符號(hào)名信息.編譯原理與技術(shù)276.3 符號(hào)表的組織結(jié)構(gòu)不等長(zhǎng)域的組織 上述對(duì)標(biāo)識(shí)符不限長(zhǎng)度的處理是組織符號(hào)名的一種間接方式，這種方式可以推廣到屬性域不相等的情形。我們可以把一些共同屬性直接記錄在符號(hào)表的信息欄，把某些特殊的屬性記錄在其它地

24、方，并且在符號(hào)表的信息欄中增設(shè)一個(gè)指針，指向這個(gè)存放特殊屬性值的位置。例6.5 圖6.7示意了通過(guò)符號(hào)表訪問內(nèi)情向量的組織結(jié)構(gòu)，符號(hào)表有兩個(gè)數(shù)組array1和array2，它們分別有n維和1維。 符號(hào)名信息欄內(nèi)情向量表類型.地址基址n上界1下界1array1數(shù)組.上界n下界narray2數(shù)組基址1上界1下界1.編譯原理與技術(shù)286.3 符號(hào)表的組織結(jié)構(gòu)符號(hào)表的操作對(duì)于給定符號(hào)，查詢此名字是否在符號(hào)表中；對(duì)于給定符號(hào)，在符號(hào)表中訪問它的屬性信息；對(duì)于給定符號(hào)，在符號(hào)表中更新它的屬性信息；在符號(hào)表中插入一個(gè)新的符號(hào)及其相關(guān)信息；刪除一個(gè)或一組無(wú)用的表項(xiàng)。編譯原理與技術(shù)296.3 符號(hào)表的組織結(jié)構(gòu)插

25、入、查找、更新和刪除的函數(shù)可以說(shuō)明如下：procedure insert (token.entry: Addess; type: Typekind);把入口是entry的符號(hào)token的類型type插入符號(hào)表。類似地也可以插入其它信息，如變量的值，譬如procedure setvalue (variable.entry: Addess; value: Valuetype);對(duì)在符號(hào)表入口的變量variable設(shè)置值value。function lookup (entry: Addess): Typekind;查找符號(hào)表中入口是entry的標(biāo)識(shí)符，返回它的類型。function getvalue

26、 (entry: Addess): Valuekind;得到符號(hào)表中入口是entry的標(biāo)識(shí)符的數(shù)值。function delete (entry: Addess): Boolean;把入口是entry的表項(xiàng)從符號(hào)表中刪除，如果成功則返回真值true，不成功則為假值false。編譯原理與技術(shù)306.3 符號(hào)表的組織結(jié)構(gòu)三種常見的符號(hào)表的結(jié)構(gòu)：線性表、搜索樹和散列表組織 線性表組織是按照符號(hào)被掃描到的先后順序填寫各個(gè)表項(xiàng)，可以用一個(gè)多維數(shù)組或多個(gè)一維數(shù)組來(lái)存放符號(hào)的信息。線性表需要兩個(gè)指針來(lái)方便管理和操作：一個(gè)指針指向該符號(hào)表的開始位置，另一個(gè)指針指向符號(hào)表的下一個(gè)可用位置。線性表是最基本的數(shù)據(jù)結(jié)

27、構(gòu)，可以方便、直接地實(shí)現(xiàn)上述的插入、查找和刪除三種基本操作，而且每種的操作時(shí)間都是符號(hào)表大小的線性函數(shù)，對(duì)于有N個(gè)表項(xiàng)的符號(hào)表，這些操作的平均時(shí)間都是N/2左右（算法時(shí)間復(fù)雜性為(N)）。由于線性表無(wú)需附加空間，比較節(jié)省存儲(chǔ)。如果編譯器對(duì)處理時(shí)間要求不高，或者符號(hào)個(gè)數(shù)不大（如關(guān)鍵字），符號(hào)表就可以采用線性表結(jié)構(gòu)。編譯原理與技術(shù)316.3 符號(hào)表的組織結(jié)構(gòu)搜索樹結(jié)構(gòu)搜索樹可以在構(gòu)造符號(hào)表的同時(shí)，按照符號(hào)名的字典順序把表項(xiàng)整理排列，提高符號(hào)表查找操作的速度。這樣就可以采用折半查找的方式，加快搜索的速度。對(duì)于有N個(gè)表項(xiàng)的符號(hào)表，每次查找最多只需要做logN次比較（因此這種查找法也叫對(duì)數(shù)查找法）。但是

28、，由于符號(hào)表在編譯過(guò)程中是邊填寫邊引用，動(dòng)態(tài)地建立、更新以及刪除表項(xiàng)，這樣，每增加和刪除一個(gè)表項(xiàng)都需要對(duì)符號(hào)表進(jìn)行重新排序，這同樣浪費(fèi)時(shí)間。因此，搜索樹結(jié)構(gòu)不適合用于構(gòu)造符號(hào)表，除了需要額外的空間構(gòu)造搜索樹以外，整體而言，它們實(shí)現(xiàn)這三類操作效率不是最優(yōu)，而且刪除操作的實(shí)現(xiàn)過(guò)于復(fù)雜。 編譯原理與技術(shù)326.3 符號(hào)表的組織結(jié)構(gòu)符號(hào)表處理的關(guān)鍵問題散列組織統(tǒng)一了查詢與插入操作技術(shù)，相對(duì)來(lái)說(shuō)具有較高的時(shí)空效率，為上述三種操作提供的時(shí)間基本上是常數(shù)。特別是散列表結(jié)構(gòu)符合編譯過(guò)程邊填寫邊引用符號(hào)表的特性，是實(shí)現(xiàn)符號(hào)表的最佳數(shù)據(jù)結(jié)構(gòu)，在實(shí)踐中的使用最多。 線性表結(jié)構(gòu)填表快，查詢慢；搜索樹結(jié)構(gòu)查詢快，填表慢

29、。如何保證查詢與插入表項(xiàng)這兩個(gè)基本操作的都能高效地完成。編譯原理與技術(shù)336.3 符號(hào)表的組織結(jié)構(gòu)散列方法散列方法在表項(xiàng)的存儲(chǔ)位置與它的關(guān)鍵碼之間建立一個(gè)確定的對(duì)應(yīng)函數(shù)關(guān)系（哈希函數(shù)，雜湊函數(shù)，hash），使每個(gè)關(guān)鍵碼symbol與散列結(jié)構(gòu)（散列表，哈希表，雜湊表）中的唯一的存儲(chǔ)位置相對(duì)應(yīng)，即hash(symbol)。在搜索時(shí)，首先對(duì)表項(xiàng)的關(guān)鍵碼用哈希函數(shù)計(jì)算出對(duì)應(yīng)的表項(xiàng)的存儲(chǔ)位置，在散列表中按此位置取出表項(xiàng)進(jìn)行比較，若關(guān)鍵碼相等，則搜索成功。在填入表項(xiàng)時(shí)，依同樣函數(shù)計(jì)算存儲(chǔ)位置，并按此位置存放表項(xiàng)。由于使用這種方法進(jìn)行搜索時(shí)不必多次比較關(guān)鍵碼，因此搜速速度比較快，可以到達(dá)逼近具有此關(guān)鍵碼的表

30、項(xiàng)的實(shí)際存放地址。編譯原理與技術(shù)346.3 符號(hào)表的組織結(jié)構(gòu)對(duì)哈希函數(shù)的基本要求計(jì)算簡(jiǎn)單、高效；函數(shù)值能均勻地分布在1和N之間，對(duì)不同的關(guān)鍵碼都返回一個(gè)代表存儲(chǔ)位置的不同值。構(gòu)造哈希函數(shù)的算法有許多，例如，若取N為素?cái)?shù)，就可以定義哈希函數(shù)為symbol/N的余數(shù)，其中symbol是某個(gè)符號(hào)的代碼。由于語(yǔ)言中的標(biāo)識(shí)符可以相互區(qū)別，它們的代碼值都是不同的。 編譯原理與技術(shù)356.3 符號(hào)表的組織結(jié)構(gòu)散列沖突的解決不同的關(guān)鍵碼經(jīng)過(guò)雜湊運(yùn)算以后，有可能得到相同的雜湊值，這種現(xiàn)象稱為散列沖突。一種常用的方法是鏈地址法。把有N個(gè)地址的散列表改為N個(gè)桶，桶號(hào)與散列地址一一對(duì)應(yīng)，第i（1iN）個(gè)桶號(hào)即為第i個(gè)

31、散列地址，每個(gè)桶則是一個(gè)線性鏈表（稱為同義詞表），鏈表中的表項(xiàng)具有相同的散列函數(shù)值。若出現(xiàn)了沖突，即一個(gè)表項(xiàng)的散列值所對(duì)應(yīng)的地址已經(jīng)被占據(jù)，則需把這個(gè)表項(xiàng)放到該桶的鏈尾或鏈?zhǔn)住?編譯原理與技術(shù)366.3 符號(hào)表的組織結(jié)構(gòu).addr.HashTable1hn名字.sym1sym2.symSymbolTablea2addra3屬性1.屬性j.屬性m.hash()鏈表指針.nulla2.a3.next.如何在符號(hào)表中使用散列表技術(shù) 對(duì)于每個(gè)符號(hào)表增加一個(gè)地址鏈項(xiàng)（初始化為null）；建立一個(gè)散列表（桶），它是一個(gè)含n個(gè)符號(hào)表入口地址的一維數(shù)組，每個(gè)散列表的表項(xiàng)初始化為null，表示散列函數(shù)值所對(duì)應(yīng)的

32、符號(hào)表的表項(xiàng)沒有占用。對(duì)符號(hào)表的操作實(shí)際上就是通過(guò)散列函數(shù)間接地操作符號(hào)表。 編譯原理與技術(shù)376.3 符號(hào)表的組織結(jié)構(gòu)通過(guò)散列函數(shù)間接地操作符號(hào)表 符號(hào)表中填入一個(gè)新的sym符號(hào)（1）首先對(duì)于符號(hào)sym用散列函數(shù)hash在散列表HashTable中查找出它在符號(hào)表SymbolTable中的位置h：hash(sym)返回的值在1n之間，令指針ptr := HashTableh；否則p := hull。（2）如果ptr 為null，則把sym的信息填在SymbolTableptr所對(duì)應(yīng)的一個(gè)符號(hào)表的表項(xiàng)中。 如果ptr不是null，則表示出現(xiàn)了沖突： 首先在符號(hào)表中得到下一個(gè)新的可用的項(xiàng)（地址用

33、next表示）， 接著在散列表中把同義詞表的表頭改為next， 然后填寫這個(gè)新得到符號(hào)表的表項(xiàng)內(nèi)容：把鏈表指針由null改成SymbolTableptr的鏈表指針，填寫sym的其它屬性值。 編譯原理與技術(shù)386.4 名字的作用范圍 名字的聲明和作用域 程序語(yǔ)言中的聲明是把信息聯(lián)系到名字（標(biāo)識(shí)符）的一種語(yǔ)法結(jié)構(gòu)。編程語(yǔ)言中一般包括5類聲明：常量聲明、變量聲明、類型聲明和過(guò)程/函數(shù)聲明以及類聲明常量聲明把值聯(lián)解到名字 。類型聲明把名字綁定到新構(gòu)造的類型或者為已經(jīng)存在的名字創(chuàng)建一個(gè)別名。 變量聲明通常把名字綁定到一個(gè)類型，同時(shí)還隱式地綁定了其它屬性。一個(gè)聲明起作用的程序部分稱為該聲明的作用域。過(guò)程中

34、出現(xiàn)的名字，如果是在該過(guò)程的一個(gè)聲明的作用域內(nèi)，就稱為局部于該過(guò)程的；否則叫做非局部的。 編譯原理與技術(shù)396.4 名字的作用范圍先聲明后使用是一條在大多數(shù)程序中普遍采用的規(guī)則，它要求一個(gè)名字的聲明在程序的正文中在它的引用之前。這條規(guī)則允許編譯器一邊分析程序一邊建立符號(hào)表：一旦在程序代碼中遇到了名字引用才執(zhí)行符號(hào)表的查找操作；如果查找失敗，就出現(xiàn)了違反先聲明后使用的規(guī)則，編譯器就能發(fā)出一個(gè)適當(dāng)?shù)腻e(cuò)誤消息。所以，這條規(guī)則允許一遍掃描的編譯構(gòu)造。編譯原理與技術(shù)406.4 名字的作用范圍塊結(jié)構(gòu)與符號(hào)表的分層次管理 塊結(jié)構(gòu)是現(xiàn)代程序語(yǔ)言的普通構(gòu)造，它是程序中可以包含聲明的任何程序構(gòu)造。在Pascal語(yǔ)言中，主程序和過(guò)程/函數(shù)聲明是塊結(jié)構(gòu)；C語(yǔ)言中，函數(shù)聲明以及花括號(hào)內(nèi)的復(fù)合語(yǔ)句表示塊結(jié)構(gòu)。Java語(yǔ)言中的包package把一組相關(guān)的類封裝在一起，也構(gòu)成塊結(jié)構(gòu)。 作用域服從最近嵌套規(guī)則（1）程序塊B中聲明的作用域包括b自身；（2）如果名字x沒有在B中聲明，那么，B中x的出現(xiàn)是在外圍程序塊B的x聲明的作用域中，而且B比其它任何含x聲明的程序塊在程序正文中