編譯原理課件第九章符號表

1、第第9章章 符號表符號表主要內(nèi)容主要內(nèi)容9.1符號表的作用和地位符號表的作用和地位9.2符號的主要屬性及作用符號的主要屬性及作用9.3符號表的組織符號表的組織重點、難點重點、難點符號的主要屬性及作用符號的主要屬性及作用符號表的作用和地位符號表的作用和地位-語義檢查的依據(jù)語義檢查的依據(jù)目標代碼生成階段地址分配的依據(jù)目標代碼生成階段地址分配的依據(jù) 在編譯程序中符號表用來存放語言程序中出現(xiàn)的在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關(guān)標識符的屬性信息，有關(guān)標識符的屬性信息，符號表中所登記的信符號表中所登記的信息在編譯的不同階段都要用到。息在編譯的不同階段都要用到。在語義分析中，符號表所登記的內(nèi)容將

2、用于語義在語義分析中，符號表所登記的內(nèi)容將用于語義檢查（如檢查一個名字的使用和原先的說明是檢查（如檢查一個名字的使用和原先的說明是否一致）和產(chǎn)生中間代碼。否一致）和產(chǎn)生中間代碼。在目標代碼生成階段，當對符號名進行地址分配在目標代碼生成階段，當對符號名進行地址分配時，符號表是地址分配的依據(jù)。對一個多遍掃時，符號表是地址分配的依據(jù)。對一個多遍掃描的編譯程序，不同遍所用的符號表也往往各描的編譯程序，不同遍所用的符號表也往往各有不同。因為每遍所關(guān)心的信息各有差異。有不同。因為每遍所關(guān)心的信息各有差異。一張符號表的每一項（或稱入口才包含兩大欄（或稱區(qū)段、字域），即名字欄和信息欄。名字欄(name)信息欄

3、（information）第1項（入口1）第2項（入口2）第n項（入口n）信息欄包含許多子欄和標志位，用來記錄相應名字和種種不同屬性，由于查填符號表一般是通過匹配名字來寮現(xiàn)的，因此，名字欄也稱主欄。主欄的內(nèi)容稱為關(guān)鍵字（keyword）。在整個編譯期間，對于符號表的操作大致可歸納為五類：對給定名字，查詢名字是否已在表中；往表中填入一個新的名字；對給定名字，訪問它的某些信息；對給定名字，填寫或更新它的某些信息；刪除一個或一組無用的項。不同種類的表格所涉及的操作往往也是不同的。上述五個方面只是一些基本的共同操作。符號符號屬性屬性(信息）信息）幾種通常都是需要的。幾種通常都是需要的。1 符號名符號名

4、2 符號的類型符號的類型3 符號的存儲類別符號的存儲類別4 符號的作用域及可視性符號的作用域及可視性5 符號變量的存儲分配信息符號變量的存儲分配信息 6 符號的其它屬性符號的其它屬性 （）數(shù)組內(nèi)情向量（）數(shù)組內(nèi)情向量 （）記錄結(jié)構(gòu)型的成員信息（）記錄結(jié)構(gòu)型的成員信息 （）函數(shù)及過（）函數(shù)及過程的形參程的形參 符號表的組織符號表的組織總體組織和表項屬性信息組織總體組織和表項屬性信息組織第一種：第一種： 把屬性種類完全相同的那些符號組織把屬性種類完全相同的那些符號組織在一起，構(gòu)造出表項是分別為等長的多個符號在一起，構(gòu)造出表項是分別為等長的多個符號表表第二種：第二種： 把所有語言中的符號都組織在一張

5、符把所有語言中的符號都組織在一張符號表中。組成一張包括了所有屬性的龐大的符號表中。組成一張包括了所有屬性的龐大的符號表號表第三種折衷方式是根據(jù)符號屬性相似程度分類組第三種折衷方式是根據(jù)符號屬性相似程度分類組織成若干張表，每張表中記錄的符號都有比較織成若干張表，每張表中記錄的符號都有比較多的相同屬性。多的相同屬性。編譯程序按名字的不同種屬分別使用許多符號表，如常數(shù)表、變量名表、過程名表等等。subroutineincwap（m，n）10km1mm4nkreturnend經(jīng)編譯頭三階段后所產(chǎn)生的主要表格有：符號名表snt、常數(shù)表ct、入口名表ent、標號表lt和四元式表qt符號名表sntnamei

6、nformation（1）m啞元，整數(shù)，變量（2）n啞元，整數(shù)，變量（3）k整數(shù)，變量常數(shù)表ct值（value）(1)1（2）4入口名表entnameinformation（1）incwap二目子程序，入口qt(1)/*記錄入口名incwap的入口地址標號表ltlableinformation（1）10qt(4)/*記錄了標號10對應的四元式序列號四元式表qt符號表項的排列符號表項的排列符號表作為一個多元組，表中元組的排列符號表作為一個多元組，表中元組的排列組織是構(gòu)造符號表的重要成分。在編譯組織是構(gòu)造符號表的重要成分。在編譯程序的整個工作過程中，符號表被頻繁程序的整個工作過程中，符號表被頻繁地

7、用來建立表項，找查表項，填充和引地用來建立表項，找查表項，填充和引用表項的屬性。因此表項的排列組織對用表項的屬性。因此表項的排列組織對該系統(tǒng)運行的效率起著十分重要的作用。該系統(tǒng)運行的效率起著十分重要的作用。在編譯程序中，符號表項的組織傳統(tǒng)上在編譯程序中，符號表項的組織傳統(tǒng)上采用三種構(gòu)造方法。即線性法，二分法采用三種構(gòu)造方法。即線性法，二分法及散列法。及散列法。關(guān)鍵字域的組織關(guān)鍵字域的組織符號表的關(guān)鍵字域（段）就是符號名稱符號表的關(guān)鍵字域（段）就是符號名稱 等長關(guān)鍵字域（段）符號表等長關(guān)鍵字域（段）符號表 不等長關(guān)鍵字段符號表不等長關(guān)鍵字段符號表-采用關(guān)鍵字池的采用關(guān)鍵字池的索引結(jié)構(gòu)。索引結(jié)構(gòu)。

8、分程序結(jié)構(gòu)的符號表分程序結(jié)構(gòu)的符號表對于具有分程序型結(jié)構(gòu)的語言程序，不同層次分對于具有分程序型結(jié)構(gòu)的語言程序，不同層次分程序中定義的標識符號具有不同的作用域和不程序中定義的標識符號具有不同的作用域和不同的可視性規(guī)則。通常對于具有分程序結(jié)構(gòu)的同的可視性規(guī)則。通常對于具有分程序結(jié)構(gòu)的語言可用兩種方式組織它們的符號表：語言可用兩種方式組織它們的符號表： 一是對一是對每個分程序建立一個獨立的分表結(jié)構(gòu)的符號表；每個分程序建立一個獨立的分表結(jié)構(gòu)的符號表；一是把各分程序符號組織在一張單表結(jié)構(gòu)的符一是把各分程序符號組織在一張單表結(jié)構(gòu)的符號表中號表中分表結(jié)構(gòu)的組織管理分表結(jié)構(gòu)的組織管理其基本思想是，每當編譯程序

9、掃描到一個其基本思想是，每當編譯程序掃描到一個分程序結(jié)構(gòu)開始時，為該分程序建立一分程序結(jié)構(gòu)開始時，為該分程序建立一張符號表，在該分程序中定義的標識符，張符號表，在該分程序中定義的標識符，都被登錄在該符號表中。而當編譯程序都被登錄在該符號表中。而當編譯程序掃描到一個分程序的結(jié)束時，編譯程序掃描到一個分程序的結(jié)束時，編譯程序釋放為該分程序所建立的符號表。這種釋放為該分程序所建立的符號表。這種符號表的分表結(jié)構(gòu)與源程序的分程序?qū)臃柋淼姆直斫Y(jié)構(gòu)與源程序的分程序?qū)哟谓Y(jié)構(gòu)一一對應次結(jié)構(gòu)一一對應單表結(jié)構(gòu)的組織管理單表結(jié)構(gòu)的組織管理其基本思想是，所有分程序中定義的標識符都集其基本思想是，所有分程序中定義的標識

10、符都集中在單張符號表中。為了實現(xiàn)分程序構(gòu)造中標中在單張符號表中。為了實現(xiàn)分程序構(gòu)造中標識符的作用域和可視性規(guī)則的要求識符的作用域和可視性規(guī)則的要求,在符號表中在符號表中可設立一個屬性域用來登錄符號所在分程序的可設立一個屬性域用來登錄符號所在分程序的層次層次進入分程序時，層次要增加一層進入分程序時，層次要增加一層.在退出一個分在退出一個分程序時，層次降低一層，且需要把符號表中，程序時，層次降低一層，且需要把符號表中，所有在退出的分程序中登錄的符號項清除。所有在退出的分程序中登錄的符號項清除。嵌套結(jié)構(gòu)型程序設計語言（pascal）的特點，可采用的辦法：將其符號表設計為棧符號表，當新的名字出現(xiàn)總是從

11、棧頂填入。查找操作從符號表的棧頂往底部查（保證先查最近出現(xiàn)的名字）。因為程序是分層的，并且一個過程結(jié)束時將釋放相應的子符號表，因此查找范圍與線性表比相對要小一些。引入一個顯示（display）層次關(guān)系表，稱為過程的嵌套層次表。其作用是為了描述過程的嵌套層次，指出當前正在活動著的各嵌套的過程（或函數(shù)）相應的子符號表在棧符號表中的起始位置（相對地址）。display表也是一個棧，棧頂指針為level。當進入一個新過程時，level增加1；每當退出一個過程時，level減1。display(level)總是指向當前正在處理的最內(nèi)層的過程的子符號表在棧符號表中的起始位置。在符號表的信息欄中引入一個指針

12、域（previous）用以鏈接它在同一過程內(nèi)的前一域名字在表中的下標（相對位置）。每一層的最后一個域名字，其previous之值為0。這樣，每當需要查找一個新名字時，就能通過display找出當前正在處理的最內(nèi)層的過程及所有外層的子符號表在棧符號表中的位置。然后，通過previous可以找到同一過程內(nèi)的所有被說明的名字。說明部分的分析說明部分的分析與處理與處理 對每個過程對每個過程說明的對象說明的對象（變量變量，常量常量和和過程過程）造名字表造名字表填寫填寫標識符的標識符的所在所在層次層次、屬性屬性和分配的和分配的相對位置相對位置。標識。標識符的屬性不同時，所需填入的信息也不同。登錄信息由符的

13、屬性不同時，所需填入的信息也不同。登錄信息由enterenter過程完成。過程完成。說明部分的分析說明部分的分析與處理與處理（程程序）序） 說明類型的定義：object=(constant,variable,procedur) （定義定義純量純量/ /枚舉枚舉類型）類型） 名字表的定義table:array0.txmaxofrecordname:alfa;casekind:objectofconstant:(val:integer);variable:procedur:(level,adr,size:integer);n na am me e：a a n na am me e：b b n na

14、 am me e：c c n na am me e：d d n na am me e：e e n na am me e：p p k ki in nd d：c co on ns st ta an nt t k ki in nd d：c co on ns st ta an nt t k ki in nd d：v va ar ri ia ab bl le e k ki in nd d：v va ar ri ia ab bl le e k ki in nd d：v va ar ri ia ab bl le e k ki in nd d：p pr ro oc ce ed du ur r v va al

15、l：3 35 5 v va al l：4 49 9 l le ev ve el l：l le ev v l le ev ve el l：l le ev v l le ev ve el l：l le ev v l le ev ve el l：l le ev v a ad dr r：d dx x a ad dr r：d dx x+ +1 1 a ad dr r：d dx x+ +2 2 a ad dr r： s si iz ze e：4 4 n na am me e：g g k ki in nd d：v va ar ri ia ab bl le e l le ev ve el l：l le ev v+ +1 1 a ad dr r：d dx x 例程序說明部分為：例程序說明部分為：const a=35const a=35，b=49b=49；var cvar c，d d，e e；procedure pprocedure p；va