編譯原理-符號表3

1、廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO1v 符號表作為編譯系統(tǒng)的重要設(shè)施，貫穿于符號表作為編譯系統(tǒng)的重要設(shè)施，貫穿于文法分析文法分析、檢檢查查和和語義處理語義處理的編譯全過程。的編譯全過程。v 在編譯程序中符號表用來存放源程序中出現(xiàn)的在編譯程序中符號表用來存放源程序中出現(xiàn)的有關(guān)名字有關(guān)名字的屬性信息的屬性信息，這些信息集中反映了，這些信息集中反映了名字的語義特征屬性名字的語義特征屬性。v 符號表總體結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)下列因素有關(guān)：符號表總體結(jié)構(gòu)的設(shè)計(jì)和實(shí)現(xiàn)下列因素有關(guān)： 源語言的復(fù)雜性（包括詞法結(jié)構(gòu)、語法結(jié)構(gòu)的復(fù)雜性）源語言的復(fù)雜性（包括詞法結(jié)構(gòu)、語法結(jié)構(gòu)的復(fù)雜性） 對于編譯系統(tǒng)在

2、時(shí)間效率和空間效率方面的要求對于編譯系統(tǒng)在時(shí)間效率和空間效率方面的要求廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO2知知識識結(jié)結(jié)構(gòu)構(gòu) 廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO3v9.1 符號表的作用和地位符號表的作用和地位v9.2 符號的主要屬性及作用符號的主要屬性及作用v9.3 符號表的組織符號表的組織v9.4 符號表的管理符號表的管理廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO4v符號表中所登記的信息在編譯的不同階段都要用符號表中所登記的信息在編譯的不同階段都要用到。例如：在到。例如：在詞法分析詞法分析及及語法分析語法分析過程中不斷更過程中不斷更新表中的信息，新

3、表中的信息，v另外，在詞法分析到代碼生成的各階段則會從表另外，在詞法分析到代碼生成的各階段則會從表中獲取不同的屬性信息。中獲取不同的屬性信息。v符號表的功能主要?dú)w結(jié)為以下幾個(gè)方面：符號表的功能主要?dú)w結(jié)為以下幾個(gè)方面：v 收集符號屬性收集符號屬性 v 作為上下文語義的合法性檢查的依據(jù)作為上下文語義的合法性檢查的依據(jù)v 作為目標(biāo)代碼生成階段地址分配的依據(jù)作為目標(biāo)代碼生成階段地址分配的依據(jù) 廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO5v編譯程序掃描說明部分收集有關(guān)標(biāo)識符的屬性，編譯程序掃描說明部分收集有關(guān)標(biāo)識符的屬性，并在符號表中建立符號的相應(yīng)屬性信息。并在符號表中建立符號的相應(yīng)屬性信息。

4、v例如例如：編譯程序分析到下述兩個(gè)說明語句：編譯程序分析到下述兩個(gè)說明語句： int A; float B5;v則在符號表中收集到關(guān)于符號則在符號表中收集到關(guān)于符號A的屬性是一個(gè)整的屬性是一個(gè)整型變量，關(guān)于符號型變量，關(guān)于符號B的屬性是具有的屬性是具有5個(gè)浮點(diǎn)型元個(gè)浮點(diǎn)型元素的一維數(shù)組。素的一維數(shù)組。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO6v通過符號表中屬性記錄可進(jìn)行相應(yīng)通過符號表中屬性記錄可進(jìn)行相應(yīng)上下文的語義檢查上下文的語義檢查。v例如：例如：在一個(gè)在一個(gè)C語言程序中出現(xiàn)語言程序中出現(xiàn)int i3,5; /定義整型數(shù)組定義整型數(shù)組ifloat i4,2; /定義實(shí)型數(shù)組定義實(shí)

5、型數(shù)組i，重定義沖突，重定義沖突int i3,5; /定義整型數(shù)組定義整型數(shù)組i，重定義沖突，重定義沖突 v從本例還可以看出，無論在后面兩句中從本例還可以看出，無論在后面兩句中i的其它屬性的其它屬性與前一句是否完全相同，只要與前一句是否完全相同，只要標(biāo)識符名標(biāo)識符名重定義重定義，就將，就將產(chǎn)生產(chǎn)生重定義重定義沖突的語義錯(cuò)誤。沖突的語義錯(cuò)誤。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO7v 每個(gè)符號變量在目標(biāo)代碼生成時(shí)需要確定其每個(gè)符號變量在目標(biāo)代碼生成時(shí)需要確定其在存儲分在存儲分配中的位置配中的位置（主要是相對位置）。（主要是相對位置）。v 要確定一個(gè)變量在目標(biāo)代碼生成時(shí)的地址，需要：

6、要確定一個(gè)變量在目標(biāo)代碼生成時(shí)的地址，需要：v 首先要確定其被分配的區(qū)域。首先要確定其被分配的區(qū)域。例如例如，在，在C語言中有語言中有公公共區(qū)、文件靜態(tài)區(qū)、函數(shù)靜態(tài)區(qū)、函數(shù)運(yùn)行時(shí)的動態(tài)共區(qū)、文件靜態(tài)區(qū)、函數(shù)靜態(tài)區(qū)、函數(shù)運(yùn)行時(shí)的動態(tài)區(qū)區(qū)等。等。v 其次是根據(jù)其次是根據(jù)變量出現(xiàn)的次序變量出現(xiàn)的次序。通常使用在該區(qū)域中。通常使用在該區(qū)域中相相對于區(qū)頭的相對位置對于區(qū)頭的相對位置來決定該變量在某個(gè)區(qū)中所處的來決定該變量在某個(gè)區(qū)中所處的具體位置。具體位置。cba動態(tài)區(qū)頭位置動態(tài)區(qū)頭位置廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO8v9.1 符號表的作用和地位符號表的作用和地位v9.2 符號的主要

7、屬性及作用符號的主要屬性及作用v9.3 符號表的組織符號表的組織v9.4 符號表的管理符號表的管理廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO9v信息欄信息欄包含許多子欄和標(biāo)志位，用來記錄相應(yīng)名包含許多子欄和標(biāo)志位，用來記錄相應(yīng)名字和各種屬性。字和各種屬性。v名字欄名字欄也稱主欄。主欄的內(nèi)容稱為也稱主欄。主欄的內(nèi)容稱為關(guān)鍵字關(guān)鍵字（key word）。）。名字欄名字欄類型欄類型欄作用域欄作用域欄v符號表包括符號表包括名字欄名字欄和和信息欄信息欄(可有多列可有多列)。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO10v雖然不同的語言定義的標(biāo)識符屬性不盡相同，下雖然不同的語言定義的標(biāo)

8、識符屬性不盡相同，下列幾種屬性通常都是需要的：列幾種屬性通常都是需要的：v 符號名符號名 v 符號的存儲類別符號的存儲類別 v 符號變量的存儲分配信息符號變量的存儲分配信息 v 符號的其它屬性符號的其它屬性：數(shù)組內(nèi)情向量、記錄結(jié)構(gòu)型：數(shù)組內(nèi)情向量、記錄結(jié)構(gòu)型的成員信息、函數(shù)及過程的形參的成員信息、函數(shù)及過程的形參 符號的類型符號的類型 符號的作用域及可視性符號的作用域及可視性廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO11 符號名符號名 v 符號表中設(shè)置一個(gè)符號名域，存放該標(biāo)識符，該域通常就是符號表的關(guān)鍵字域。(書P205) 符號的類型符號的類型 v 標(biāo)識符中除過程標(biāo)識符之外，函數(shù)和變

9、量標(biāo)識符都具有數(shù)據(jù)類型（data type）屬性。對于函數(shù)的數(shù)據(jù)類型指的是該函數(shù)值的數(shù)據(jù)類型?；緮?shù)據(jù)類型有整型、實(shí)型、字符型、邏輯型（布爾型）及位組型等，符號的類型屬性是在該符號的定義時(shí)得到。變量符號的類型屬性決定了該變量的數(shù)據(jù)在存儲空間的存儲格式，還決定了在該變量上可以施加的運(yùn)算操作。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO12v大多數(shù)語言對變量的存儲類別定義采用兩種方式：大多數(shù)語言對變量的存儲類別定義采用兩種方式：v(1) 用用關(guān)鍵字關(guān)鍵字指定。指定。v例如在例如在C語言中用語言中用static定義是屬于文件的靜態(tài)定義是屬于文件的靜態(tài)存儲變量或?qū)儆诤瘮?shù)內(nèi)部的靜態(tài)存儲變量。存儲

10、變量或?qū)儆诤瘮?shù)內(nèi)部的靜態(tài)存儲變量。v(2) 根據(jù)根據(jù)變量聲明在程序中的位置變量聲明在程序中的位置來決定。來決定。v例如例如在在C語言中，在函數(shù)體外定義的變量是缺省是語言中，在函數(shù)體外定義的變量是缺省是程序的程序的公共存儲變量公共存儲變量，而在函數(shù)體內(nèi)定義的變量，而在函數(shù)體內(nèi)定義的變量是是該函數(shù)所獨(dú)有的私有存儲變量該函數(shù)所獨(dú)有的私有存儲變量。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO13v 一個(gè)變量的作用域即一個(gè)變量的作用域即該變量可以出現(xiàn)的場合該變量可以出現(xiàn)的場合，也就是說在，也就是說在某個(gè)變量作用域范圍內(nèi)該變量是某個(gè)變量作用域范圍內(nèi)該變量是可引用的可引用的，這就是，這就是變量可變量

11、可視性的作用域規(guī)則。視性的作用域規(guī)則。v 但是變量可視性但是變量可視性不僅僅不僅僅取決于它的作用域，還有兩種情況取決于它的作用域，還有兩種情況影響到一個(gè)變量的可視性。影響到一個(gè)變量的可視性。v 函數(shù)的形式參數(shù)函數(shù)的形式參數(shù)：影響變量可視性的舉例：影響變量可視性的舉例int a； / 外部定義的整型變量外部定義的整型變量aint func(a, b)float a； / 函數(shù)內(nèi)部定義的局部整型變量函數(shù)內(nèi)部定義的局部整型變量a, int b； b = b + a; / 引用的是哪一個(gè)引用的是哪一個(gè)a？ 在函數(shù)在函數(shù)func中可看中可看到的是到的是float a，看不到看不到int a。廣東工業(yè)大學(xué)

12、計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO14v 在在C語言的最新文本中增加了一個(gè)語法記號語言的最新文本中增加了一個(gè)語法記號 ，使得可，使得可以在函數(shù)內(nèi)部顯式地引用外部的同名變量。以在函數(shù)內(nèi)部顯式地引用外部的同名變量。v 上例可改寫如下：上例可改寫如下：v int a = 2;int func (a, b)float a = -1;int b = 1; b = b + a; b = b + a v 則則b = ？2引用引用float a引用引用int a廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO15v 分程序分程序(或復(fù)合語句或復(fù)合語句)結(jié)構(gòu)結(jié)構(gòu)： 影響變量可視影響變量可視性的舉例性的

13、舉例v int a； / 第一層開頭第一層開頭,定義局部整型變量定義局部整型變量achar a； / 第二層開頭第二層開頭,定義局部字符型變量定義局部字符型變量a / 第三層開頭第三層開頭float a； / 第四層頭第四層頭,定義局部實(shí)型變量定義局部實(shí)型變量a / 第四層尾第四層尾a / 引用的是哪個(gè)引用的是哪個(gè)a？ / 第三層尾第三層尾 / 第二層尾第二層尾 / 第一層尾第一層尾 第二層的第二層的char a所以，在符號表屬性中需要所以，在符號表屬性中需要記錄表示記錄表示該符號在程序結(jié)構(gòu)該符號在程序結(jié)構(gòu)上被定義的層次上被定義的層次。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO16v

14、 可以根據(jù)以下因素來確定每一個(gè)變量應(yīng)分配到哪一個(gè)存儲可以根據(jù)以下因素來確定每一個(gè)變量應(yīng)分配到哪一個(gè)存儲區(qū)區(qū)(靜態(tài)或動態(tài)存儲區(qū)靜態(tài)或動態(tài)存儲區(qū))，以及在該區(qū)中的具體位置：，以及在該區(qū)中的具體位置： 符號變量的存儲類別定義符號變量的存儲類別定義 這些變量出現(xiàn)的位置和次序這些變量出現(xiàn)的位置和次序v 在符號表中用在符號表中用相對區(qū)頭的位移量相對區(qū)頭的位移量表示。表示。v 例如有以下程序段例如有以下程序段(C語言語言)int a; float b; struct cc int d; float e; c; .標(biāo)識標(biāo)識符符類型類型位置屬位置屬性性aint0bfloat4dint0efloat4ccc8廣東

15、工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO17v 數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量 內(nèi)情向量包括內(nèi)情向量包括數(shù)組類型，維數(shù)數(shù)組類型，維數(shù)，各維的上、下界各維的上、下界及及數(shù)數(shù)組首地址組首地址，這些屬性信息是確定存儲分配時(shí)數(shù)組所占，這些屬性信息是確定存儲分配時(shí)數(shù)組所占空間的大小和數(shù)組元素位置的依據(jù)。空間的大小和數(shù)組元素位置的依據(jù)。v 記錄結(jié)構(gòu)型的成員信息記錄結(jié)構(gòu)型的成員信息 一個(gè)記錄結(jié)構(gòu)型的變量，在存儲分配時(shí)所占空間大一個(gè)記錄結(jié)構(gòu)型的變量，在存儲分配時(shí)所占空間大小要由它的全體組成成員來確定，另外對于記錄結(jié)構(gòu)小要由它的全體組成成員來確定，另外對于記錄結(jié)構(gòu)型變量還需要有它所屬成員排列次序的屬性信息。型

16、變量還需要有它所屬成員排列次序的屬性信息。v 函數(shù)及過程的形參函數(shù)及過程的形參 每個(gè)函數(shù)或過程的形參個(gè)數(shù)、形參的排列次序及每個(gè)每個(gè)函數(shù)或過程的形參個(gè)數(shù)、形參的排列次序及每個(gè)形參的類型形參的類型，都體現(xiàn)了調(diào)用該函數(shù)或過程時(shí)的屬性，都體現(xiàn)了調(diào)用該函數(shù)或過程時(shí)的屬性，它們都應(yīng)該反映在符號表的函數(shù)或過程標(biāo)識符的項(xiàng)中。它們都應(yīng)該反映在符號表的函數(shù)或過程標(biāo)識符的項(xiàng)中。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO18v9.1 符號表的作用和地位符號表的作用和地位v9.2 符號的主要屬性及作用符號的主要屬性及作用v9.3 符號表的組織符號表的組織v9.4 符號表的管理符號表的管理廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院

17、廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO19v 假設(shè)假設(shè)一個(gè)語言程序發(fā)現(xiàn)有下列一個(gè)語言程序發(fā)現(xiàn)有下列3類符號及其所需之屬性：類符號及其所需之屬性：第第1類符號類符號 屬性屬性1屬性屬性2 屬性屬性3第第2類符號類符號 屬性屬性1屬性屬性2 屬性屬性4第第3類符號類符號 屬性屬性2屬性屬性5 屬性屬性6v 第一種造表方式第一種造表方式：構(gòu)造構(gòu)造等長表項(xiàng)等長表項(xiàng)的多個(gè)表的多個(gè)表v 注意：各屬性注意：各屬性不一定不一定等長等長廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO20v 假設(shè)假設(shè)一個(gè)語言程序發(fā)現(xiàn)有下列一個(gè)語言程序發(fā)現(xiàn)有下列3類符號及其所需之屬性：類符號及其所需之屬性：第第1類符號類符號 屬性屬性

18、1屬性屬性2 屬性屬性3第第2類符號類符號 屬性屬性1屬性屬性2 屬性屬性4第第3類符號類符號 屬性屬性2屬性屬性5 屬性屬性6v 第二種造表方式第二種造表方式：構(gòu)造一張構(gòu)造一張包括所有包括所有屬性屬性的表的表v 缺點(diǎn)：可能會造成缺點(diǎn)：可能會造成存儲空間的存儲空間的浪費(fèi)浪費(fèi),管管理的復(fù)雜理的復(fù)雜.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO21v 假設(shè)假設(shè)一個(gè)語言程序發(fā)現(xiàn)有下列一個(gè)語言程序發(fā)現(xiàn)有下列3類符號及其所需之屬性：類符號及其所需之屬性：第第1類符號類符號 屬性屬性1屬性屬性2 屬性屬性3第第2類符號類符號 屬性屬性1屬性屬性2 屬性屬性4第第3類符號類符號 屬性屬性2屬性屬性5

19、 屬性屬性6v 第三種造表方式第三種造表方式：據(jù)符號據(jù)符號屬性相似程度屬性相似程度分類造若干分類造若干個(gè)表。個(gè)表。v 缺點(diǎn)：仍然存在可能的缺點(diǎn)：仍然存在可能的存儲空間存儲空間浪費(fèi)浪費(fèi),需設(shè)計(jì)者需設(shè)計(jì)者根據(jù)經(jīng)驗(yàn)和要求進(jìn)行選根據(jù)經(jīng)驗(yàn)和要求進(jìn)行選擇和調(diào)整擇和調(diào)整.廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO22v 下面單獨(dú)考察下面單獨(dú)考察“第一，二類符號之符號表第一，二類符號之符號表”第第1類符號類符號 屬性屬性1屬性屬性2 屬性屬性3第第2類符號類符號 屬性屬性1屬性屬性2 屬性屬性4第第3類符號類符號 屬性屬性2屬性屬性5 屬性屬性6v 對第對第1類符號來說，類符號來說，屬性值屬性值4欄

20、欄是冗余的，而對于第是冗余的，而對于第2類符號，類符號，則則屬性值屬性值3欄是冗余的。欄是冗余的。v 把把屬性值屬性值3和和屬性值屬性值4合并成合并成屬屬性值性值34。v 在當(dāng)該表項(xiàng)符號是屬第在當(dāng)該表項(xiàng)符號是屬第1類時(shí)，類時(shí)，屬性值屬性值34中收集的是中收集的是屬性值屬性值3的值；若是第的值；若是第2類符號時(shí)，類符號時(shí)，屬性屬性值值34中收集的是中收集的是屬性值屬性值4的值。的值。C語言中可用語言中可用UNION來實(shí)現(xiàn)。這樣來實(shí)現(xiàn)。這樣的組織結(jié)構(gòu)會增加符號表管理和運(yùn)的組織結(jié)構(gòu)會增加符號表管理和運(yùn)行的行的復(fù)雜性復(fù)雜性，但減少了，但減少了空間開銷空間開銷。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)

21、院LOGO23造表方式造表方式第一種：第一種：構(gòu)造等構(gòu)造等長表項(xiàng)的多個(gè)表長表項(xiàng)的多個(gè)表第二種：第二種： 構(gòu)造一張構(gòu)造一張包括所有屬性包括所有屬性的表的表第三種：第三種：據(jù)符號屬性相據(jù)符號屬性相似程度似程度分類造若干個(gè)表分類造若干個(gè)表優(yōu)點(diǎn)優(yōu)點(diǎn)缺點(diǎn)缺點(diǎn)對于單個(gè)表，對于單個(gè)表，管管理方便一致，空理方便一致，空間效率高。間效率高。 編譯程序?qū)⑼瑫r(shí)編譯程序?qū)⑼瑫r(shí)管理若干個(gè)表，管理若干個(gè)表，而且對各類符號而且對各類符號的共同屬性的管的共同屬性的管理必須設(shè)置重復(fù)理必須設(shè)置重復(fù)的運(yùn)行機(jī)制的運(yùn)行機(jī)制。 管理集中單一，不管理集中單一，不同種類符號的共同同種類符號的共同屬性可一致地管理屬性可一致地管理和處理。和處理

22、。 由于屬性各有不同，由于屬性各有不同，為完整表達(dá)各類符為完整表達(dá)各類符號的全部屬性必將號的全部屬性必將出現(xiàn)不等長的表項(xiàng)，出現(xiàn)不等長的表項(xiàng)，以及表項(xiàng)中屬性位以及表項(xiàng)中屬性位置的交錯(cuò)重疊，這置的交錯(cuò)重疊，這就極大地增加了管就極大地增加了管理復(fù)雜度。理復(fù)雜度。在管理復(fù)雜性及時(shí)空在管理復(fù)雜性及時(shí)空效率方面都取得折衷效率方面都取得折衷的效果。的效果。 無法制定形式化的構(gòu)無法制定形式化的構(gòu)造規(guī)則，依賴于符號造規(guī)則，依賴于符號表構(gòu)造者的經(jīng)驗(yàn)。未表構(gòu)造者的經(jīng)驗(yàn)。未必能適應(yīng)編譯過程中必能適應(yīng)編譯過程中出現(xiàn)的所有情況。出現(xiàn)的所有情況。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO24v 在編譯程序中，符號

23、表項(xiàng)的組織傳統(tǒng)上采用三種構(gòu)造方法：在編譯程序中，符號表項(xiàng)的組織傳統(tǒng)上采用三種構(gòu)造方法：線性法線性法，二分法二分法和和散列法散列法。v 1. 線性組織線性組織v 這種方法規(guī)定符號表中表項(xiàng)按它的符號這種方法規(guī)定符號表中表項(xiàng)按它的符號被掃描到的先后順序被掃描到的先后順序登錄。例如有一程序中出現(xiàn)符號的情況如下：登錄。例如有一程序中出現(xiàn)符號的情況如下：a /第第1次出現(xiàn)次出現(xiàn)ab /第第1次出現(xiàn)次出現(xiàn)ba /第第2次出現(xiàn)次出現(xiàn)ad /第第1次出現(xiàn)次出現(xiàn)dc /第第1次出現(xiàn)次出現(xiàn)cb /第第2次出現(xiàn)次出現(xiàn)bv h：表頭，是表的開始位置；：表頭，是表的開始位置；v p：符號表當(dāng)前的結(jié)束位置。：符號表當(dāng)前的結(jié)

24、束位置。優(yōu)點(diǎn)優(yōu)點(diǎn)：缺點(diǎn)缺點(diǎn)：無空白項(xiàng)，存儲空間效率無空白項(xiàng)，存儲空間效率高高查找效率查找效率低下低下廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO25v2. 排序組織及二分法排序組織及二分法 v符號表中的表項(xiàng)按其符號的字符代碼串符號表中的表項(xiàng)按其符號的字符代碼串(可以看成可以看成一個(gè)一個(gè)整數(shù)值整數(shù)值)的值的大小的值的大小從大到小從大到小(或從小到大或從小到大)排排列。列。優(yōu)點(diǎn)優(yōu)點(diǎn)：缺點(diǎn)缺點(diǎn)：查找效率查找效率高高造表過程需要耗費(fèi)較大的造表過程需要耗費(fèi)較大的代價(jià)代價(jià)(表項(xiàng)的表項(xiàng)的比較比較和和移動移動)廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO26v散列組織散列組織(哈希表哈希表)具

25、有具有較高的運(yùn)行效率，因而較高的運(yùn)行效率，因而絕大多數(shù)編譯程序中的絕大多數(shù)編譯程序中的符號表采用符號表采用散列組織散列組織。v關(guān)鍵在于采用適當(dāng)?shù)年P(guān)鍵在于采用適當(dāng)?shù)墓：瘮?shù)希函數(shù)以及以及沖突解決辦沖突解決辦法法。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO27v符號表符號表的的關(guān)鍵字域關(guān)鍵字域就是就是符號本身符號本身，它可以是，它可以是語言的語言的保留字保留字，操作符號操作符號或或標(biāo)識符標(biāo)識符(包括包括變量變量名名，函數(shù)名函數(shù)名，記錄結(jié)構(gòu)標(biāo)志記錄結(jié)構(gòu)標(biāo)志等等)。v關(guān)鍵字域的組織有兩種方式：關(guān)鍵字域的組織有兩種方式：v(1) 等長關(guān)鍵字域等長關(guān)鍵字域(段段)符號表符號表 v(2) 不等長

26、關(guān)鍵字段符號表不等長關(guān)鍵字段符號表-采用采用關(guān)鍵字池關(guān)鍵字池的索引結(jié)構(gòu)的索引結(jié)構(gòu)。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO28v為使得符號表中存放標(biāo)識符的關(guān)鍵字段等長，需要為使得符號表中存放標(biāo)識符的關(guān)鍵字段等長，需要將關(guān)鍵字段設(shè)置為將關(guān)鍵字段設(shè)置為標(biāo)識符的最大長度標(biāo)識符的最大長度。v例如例如C語言的關(guān)鍵字段長度是語言的關(guān)鍵字段長度是32個(gè)字節(jié)，其中前個(gè)字節(jié)，其中前31個(gè)是存放名字，第個(gè)是存放名字，第32個(gè)是存放字符串結(jié)束標(biāo)志。個(gè)是存放字符串結(jié)束標(biāo)志。由于程序由于程序中的標(biāo)識中的標(biāo)識符長短不符長短不一，用等一，用等長結(jié)構(gòu)會長結(jié)構(gòu)會產(chǎn)生產(chǎn)生溢出溢出或或冗余冗余。凵凵 凵凵 凵凵 凵凵

27、廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO29v如果希望既保證關(guān)鍵字段的等長，又要減少甚至如果希望既保證關(guān)鍵字段的等長，又要減少甚至消除冗余，可采用消除冗余，可采用關(guān)鍵字池的索引結(jié)構(gòu)關(guān)鍵字池的索引結(jié)構(gòu)。 v 假設(shè)有一組假設(shè)有一組標(biāo)識符標(biāo)識符 anexemplerof key-wrdsfieldv 關(guān)鍵字段的組織結(jié)關(guān)鍵字段的組織結(jié)構(gòu)如右圖：構(gòu)如右圖：廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO30v符號表屬性域的組織，根據(jù)屬性性質(zhì)大致分成兩符號表屬性域的組織，根據(jù)屬性性質(zhì)大致分成兩類：類：v一類是一類是符號的屬性值符號的屬性值的的類型類型相同，并且是相同，并且是等長的等長的，則

28、該屬性域的類型結(jié)構(gòu)就可用其則該屬性域的類型結(jié)構(gòu)就可用其長度長度及及類型類型來定來定義。義。v例如例如boolean，int，float等基本數(shù)據(jù)類型等基本數(shù)據(jù)類型v另一類另一類符號的屬性值符號的屬性值的的類型類型相同，但相同，但不不等長等長，則，則該屬性域的定義該屬性域的定義不能不能用簡單的數(shù)據(jù)類型來定義。用簡單的數(shù)據(jù)類型來定義。v例如：例如：數(shù)組內(nèi)情向量。數(shù)組內(nèi)情向量。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO31v 下面我們討論一些典型的下面我們討論一些典型的等長等長屬性值域的組織。屬性值域的組織。 v (1) 表示某個(gè)符號的表示某個(gè)符號的布爾性質(zhì)的屬性域布爾性質(zhì)的屬性域，可用，

29、可用1個(gè)個(gè)bit位來位來表示；也可用表示；也可用1個(gè)布爾量來表示。如個(gè)布爾量來表示。如 defined 1 /* defined true */ 表示已定義表示已定義 defined 0 /* defined false */ 表示尚未定義表示尚未定義符號類型符號類型3個(gè)個(gè)bit位表示位表示整數(shù)值表示整數(shù)值表示char0000short0011int0102long0113unsigned1004float1015double1116v(2) 表示表示符號的符號的數(shù)據(jù)類型數(shù)據(jù)類型可以用可以用若干個(gè)若干個(gè)bit位來位來表示；也可用表示；也可用1個(gè)整型量來表示。個(gè)整型量來表示。v以以C語言為例：語

30、言為例：廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO32v 對于對于表示符號之表示符號之間關(guān)系的屬性間關(guān)系的屬性，可，可用用指針指針或或指針鏈指針鏈來來構(gòu)造。構(gòu)造。v如如函數(shù)符號函數(shù)符號與它的與它的形參符號形參符號之間的關(guān)之間的關(guān)系屬性：系屬性：“函數(shù)函數(shù)-形形參參”指針域。例：指針域。例：v func1 (para1, para2, para3);v func2 () 廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO33v 設(shè)有一個(gè)設(shè)有一個(gè)C語言的結(jié)語言的結(jié)構(gòu)體變量結(jié)構(gòu)構(gòu)體變量結(jié)構(gòu):v struct tag1 memb1; memb2; struct tag2 memb3; me

31、mb4; memb5; memb6; memb7; stv; 標(biāo)識標(biāo)識符符結(jié)構(gòu)結(jié)構(gòu)定義定義結(jié)構(gòu)結(jié)構(gòu)-成成員域員域tag1m1m2tag2m3m4m5m6m7stv“空空”“空空”廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO342v符號的某些屬性值符號的某些屬性值是是不等長不等長的，的，例如例如數(shù)組內(nèi)情向量數(shù)組內(nèi)情向量。v設(shè)有下列兩個(gè)數(shù)組設(shè)有下列兩個(gè)數(shù)組array1(subscrip1, subscrip2)array2(subscrip3, subscrip4, subscrip5, subscrip6)“0”值用來表示值用來表示下標(biāo)到此為止下標(biāo)到此為止廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大

32、學(xué)計(jì)算機(jī)學(xué)院LOGO35v 在某些程序語言的結(jié)構(gòu)中，分程序的分層結(jié)構(gòu)允許同在某些程序語言的結(jié)構(gòu)中，分程序的分層結(jié)構(gòu)允許同名標(biāo)識符具有的生存期發(fā)生名標(biāo)識符具有的生存期發(fā)生重疊重疊，即存在，即存在同名標(biāo)識符同名標(biāo)識符。v 為實(shí)現(xiàn)這種同名標(biāo)識符的語義功能，符號表中需要設(shè)為實(shí)現(xiàn)這種同名標(biāo)識符的語義功能，符號表中需要設(shè)立立下推鏈域的組織下推鏈域的組織。v 下推鏈域要求：在進(jìn)入內(nèi)層結(jié)構(gòu)并發(fā)生下推鏈域要求：在進(jìn)入內(nèi)層結(jié)構(gòu)并發(fā)生重名標(biāo)識符定重名標(biāo)識符定義義時(shí)，時(shí)，v (1) 把當(dāng)前符號中外層的該符號下把當(dāng)前符號中外層的該符號下推到推到下推鏈中，下推鏈中，v (2) 在符號表被下推的表項(xiàng)處，建立內(nèi)層的同名標(biāo)識在

33、符號表被下推的表項(xiàng)處，建立內(nèi)層的同名標(biāo)識符表項(xiàng)。符表項(xiàng)。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO36v 例：例： int i ; .(1)v .v func( ) (2)v v float i; . (3)v . (4)v int i5 ;(5)v . (6)v int i;(7)v v i(8)v v .i(9)v 廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO37v9.1 符號表的作用和地位符號表的作用和地位v9.2 符號的主要屬性及作用符號的主要屬性及作用v9.3 符號表的組織符號表的組織v9.4 符號表的管理符號表的管理廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LO

34、GO38v在整個(gè)編譯期間，對于符號表的操作大致可歸納在整個(gè)編譯期間，對于符號表的操作大致可歸納為五類：為五類：v對給定名字，對給定名字，查詢查詢名字是否已在表中；名字是否已在表中；v往表中往表中填入填入一個(gè)新的名字；一個(gè)新的名字；v對給定名字，對給定名字，訪問訪問它的某些信息；它的某些信息；v對給定名字，對給定名字，填寫填寫或或更新更新它的某些信息；它的某些信息；v刪除刪除一個(gè)或一組無用的項(xiàng)。一個(gè)或一組無用的項(xiàng)。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO39v符號表的行為主要包括：符號表的行為主要包括：v1. 符號表的符號表的初始化初始化v2. 符號的符號的登錄登錄v3. 符號的符號

35、的查找查找v4. 有關(guān)分程序結(jié)構(gòu)的符號表層次有關(guān)分程序結(jié)構(gòu)的符號表層次管理管理v對符號表的這些管理除初始化之外，其它都是對符號表的這些管理除初始化之外，其它都是動動態(tài)態(tài)進(jìn)行的。進(jìn)行的。 廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO40v 不同組織方法的符號表有不同的初始化方法。不同組織方法的符號表有不同的初始化方法。v 符號表的表長是漸增變化的情況符號表的表長是漸增變化的情況v 只需將表尾推向表頭，表示該符號表中還沒有任何表項(xiàng)。只需將表尾推向表頭，表示該符號表中還沒有任何表項(xiàng)。v 符號表的表長是確定的情況符號表的表長是確定的情況v對這類符號表的初始化方法，需對這類符號表的初始化方法，需

36、要將表中全部表項(xiàng)值清除。要將表中全部表項(xiàng)值清除。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO41v 一個(gè)符號表項(xiàng)的登錄最基本的是該符號的一個(gè)符號表項(xiàng)的登錄最基本的是該符號的名字名字登錄登錄。此外。此外還有關(guān)于該還有關(guān)于該名字的屬性名字的屬性的的登錄登錄。v (1) 對于對于線性方法線性方法組織的組織的符號表符號表，通常把該表的，通常把該表的尾指針尾指針p指向的表項(xiàng)是作為新創(chuàng)建的表項(xiàng)，之后將指向的表項(xiàng)是作為新創(chuàng)建的表項(xiàng)，之后將p推向下一個(gè)備推向下一個(gè)備用表項(xiàng)。用表項(xiàng)。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO42v (2) 對于二分法組織的符號表，在創(chuàng)建了新的表項(xiàng)后，根對于二分

37、法組織的符號表，在創(chuàng)建了新的表項(xiàng)后，根據(jù)登錄符號在符號表中按用二分法選定一個(gè)位置，把據(jù)登錄符號在符號表中按用二分法選定一個(gè)位置，把該位該位置以后的所有原表項(xiàng)置以后的所有原表項(xiàng)下移下移一個(gè)表項(xiàng)的位置，然后在一個(gè)表項(xiàng)的位置，然后在選定位選定位置置登錄新符號。登錄新符號。symbol kv 對于散列表，新符對于散列表，新符號的登錄是通過號的登錄是通過雜雜湊算法湊算法決定登錄表決定登錄表項(xiàng)的位置。項(xiàng)的位置。v 如果產(chǎn)生沖突，則如果產(chǎn)生沖突，則應(yīng)用應(yīng)用沖突解決沖突解決算法。算法。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO43v 名字屬性大都取決于編譯程序獲得某個(gè)符號時(shí)，編譯程序名字屬性大都取決

38、于編譯程序獲得某個(gè)符號時(shí)，編譯程序所處的所處的程序掃描點(diǎn)的狀態(tài)程序掃描點(diǎn)的狀態(tài)。 v 例如例如在下面的程序段中獲取到的符號在下面的程序段中獲取到的符號a的屬性，是取決于的屬性，是取決于編譯程序掃描到編譯程序掃描到“anm,”時(shí)的有關(guān)狀態(tài)。時(shí)的有關(guān)狀態(tài)。v func(x, y)struct tag int anm, t;關(guān)鍵關(guān)鍵字域字域類型類型屬性屬性存儲類別存儲類別屬性屬性符號作用域符號作用域?qū)傩詫傩源鎯Ψ峙鋵俅鎯Ψ峙鋵傩孕詳?shù)組內(nèi)情向數(shù)組內(nèi)情向量屬性量屬性aintAuto(動動態(tài)存儲區(qū)態(tài)存儲區(qū))LEVEL = 1相對于相對于tag的位移量的位移量n*m的二的二維數(shù)組維數(shù)組廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院

39、廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO44v 查找的一般步驟為：查找的一般步驟為：v (1) 在在保留字表保留字表和和運(yùn)算符表運(yùn)算符表中查找該符號是否中查找該符號是否保留字保留字或或運(yùn)算符運(yùn)算符。若是，轉(zhuǎn)向。若是，轉(zhuǎn)向(2)，否則轉(zhuǎn)向，否則轉(zhuǎn)向(3)v (2) 把該符號轉(zhuǎn)換為保留字或運(yùn)算符的內(nèi)部代碼把該符號轉(zhuǎn)換為保留字或運(yùn)算符的內(nèi)部代碼(表示表示)。v (3) 在在標(biāo)識符表標(biāo)識符表中進(jìn)行查找。若在查找到則表示該符號中進(jìn)行查找。若在查找到則表示該符號已在符號表中登錄，檢查是否需要登錄新屬性；否則表已在符號表中登錄，檢查是否需要登錄新屬性；否則表示該符號是一個(gè)新的需要登錄的符號。示該符號是一個(gè)新的需要登錄

40、的符號。v 符號表的查找算法：符號表的查找算法：順序查找順序查找、折半查找折半查找和和雜湊查找雜湊查找。廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO45v通常對于具有分程序結(jié)構(gòu)的語言可用兩種方通常對于具有分程序結(jié)構(gòu)的語言可用兩種方式組織它們的符號表：式組織它們的符號表：v方法一方法一：對每個(gè)分程序建立一個(gè)：對每個(gè)分程序建立一個(gè)獨(dú)立的獨(dú)立的分表分表結(jié)構(gòu)的符號表；結(jié)構(gòu)的符號表；v方法二方法二：把各分程序符號組織在：把各分程序符號組織在一張單表結(jié)一張單表結(jié)構(gòu)的構(gòu)的符號表中。符號表中。 廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院廣東工業(yè)大學(xué)計(jì)算機(jī)學(xué)院LOGO46v 源程序的形式：源程序的形式：v /第第1層分程序?qū)臃殖绦騣nt a;float b, d; /第第2層分程序?qū)臃殖绦騣nt c;float a;/第第3層分程序?qū)臃殖绦騣nt d;float c; /第第4層分程