編譯原理清華大學(xué)第9章 符號(hào)表

1、武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓第第9章章 符號(hào)表符號(hào)表 在編譯程序中符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)在編譯程序中符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，屬性信息集中反映了標(biāo)的有關(guān)標(biāo)識(shí)符的屬性信息，屬性信息集中反映了標(biāo)識(shí)符的語(yǔ)義特征屬性。識(shí)符的語(yǔ)義特征屬性。 9.1 符號(hào)表的作用和地位符號(hào)表的作用和地位 9.2 符號(hào)的主要屬性及作用符號(hào)的主要屬性及作用 9.3 符號(hào)表的組織符號(hào)表的組織 9.3 符號(hào)表的管理符號(hào)表的管理武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓9.1 符號(hào)表的作用和地位符號(hào)表的作用和地位（1）收集符號(hào)屬性。）收集符號(hào)屬性。在編譯程序

2、中符號(hào)表用來(lái)在編譯程序中符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，符號(hào)表中所登記的信息在編譯的不同階段都要符號(hào)表中所登記的信息在編譯的不同階段都要用到。用到。（2）語(yǔ)義檢查的依據(jù)。）語(yǔ)義檢查的依據(jù)。在語(yǔ)義分析中，符號(hào)表在語(yǔ)義分析中，符號(hào)表所登記的內(nèi)容將用于語(yǔ)義檢查（如檢查一個(gè)名所登記的內(nèi)容將用于語(yǔ)義檢查（如檢查一個(gè)名字的使用和原先的說(shuō)明是否一致）和產(chǎn)生中間字的使用和原先的說(shuō)明是否一致）和產(chǎn)生中間代碼。代碼。（3）目標(biāo)代碼生成階段地址分配的依據(jù)。）目標(biāo)代碼生成階段地址分配的依據(jù)。在目在目標(biāo)代碼生成階段，當(dāng)對(duì)符號(hào)名進(jìn)行地址分配時(shí)，標(biāo)代碼生成階段，

3、當(dāng)對(duì)符號(hào)名進(jìn)行地址分配時(shí)，符號(hào)表是地址分配的依據(jù)。對(duì)一個(gè)多遍掃描的符號(hào)表是地址分配的依據(jù)。對(duì)一個(gè)多遍掃描的編譯程序，不同遍所用的符號(hào)表也往往各有不編譯程序，不同遍所用的符號(hào)表也往往各有不同。因?yàn)槊勘樗P(guān)心的信息各有差異。同。因?yàn)槊勘樗P(guān)心的信息各有差異。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓9.2 符號(hào)的主要屬性及作用符號(hào)的主要屬性及作用 在整個(gè)編譯期間，對(duì)于符號(hào)表的操作大致可在整個(gè)編譯期間，對(duì)于符號(hào)表的操作大致可歸納為五類(lèi)：歸納為五類(lèi)： 對(duì)給定名字，查詢(xún)名字是否已在表中；對(duì)給定名字，查詢(xún)名字是否已在表中； 往表中填入一個(gè)新的名字；往表中填入一個(gè)新的名字； 對(duì)給定名字，訪(fǎng)問(wèn)它

4、的某些信息；對(duì)給定名字，訪(fǎng)問(wèn)它的某些信息； 對(duì)給定名字，填寫(xiě)或更新它的某些信息；對(duì)給定名字，填寫(xiě)或更新它的某些信息； 刪除一個(gè)或一組無(wú)用的項(xiàng)。刪除一個(gè)或一組無(wú)用的項(xiàng)。 不同種類(lèi)的表格所涉及的操作往往也是不同不同種類(lèi)的表格所涉及的操作往往也是不同的。上述五個(gè)方面只是一些基本的共同操作。的。上述五個(gè)方面只是一些基本的共同操作。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓符號(hào)的主要符號(hào)屬性符號(hào)的主要符號(hào)屬性(信息）信息）下述幾項(xiàng)通常都是需要的：下述幾項(xiàng)通常都是需要的：1 符號(hào)名符號(hào)名 2 符號(hào)的數(shù)據(jù)類(lèi)型符號(hào)的數(shù)據(jù)類(lèi)型 3 符號(hào)的存儲(chǔ)類(lèi)別符號(hào)的存儲(chǔ)類(lèi)別 4 符號(hào)的作用域及可視性符號(hào)的作用域

5、及可視性 5 符號(hào)變量的存儲(chǔ)分配信息符號(hào)變量的存儲(chǔ)分配信息 6 符號(hào)的其它屬性符號(hào)的其它屬性 （1）數(shù)組內(nèi)情向量）數(shù)組內(nèi)情向量 （2）記錄結(jié)構(gòu)型的成員信息）記錄結(jié)構(gòu)型的成員信息 （3） 函數(shù)及過(guò)程的形參函數(shù)及過(guò)程的形參 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓9.3 符號(hào)表的組織符號(hào)表的組織9.3.1 符號(hào)表的總體組織符號(hào)表的總體組織第第1種：種： 把屬性種類(lèi)完全相同的那些符號(hào)組織在一把屬性種類(lèi)完全相同的那些符號(hào)組織在一起，構(gòu)造出表項(xiàng)是分別為等長(zhǎng)的多個(gè)符號(hào)表起，構(gòu)造出表項(xiàng)是分別為等長(zhǎng)的多個(gè)符號(hào)表 。第第2種：種： 把所有語(yǔ)言中的符號(hào)都組織在一張符號(hào)表把所有語(yǔ)言中的符號(hào)都組織在一

6、張符號(hào)表中。組成一張包括了所有屬性的龐大的符號(hào)表。中。組成一張包括了所有屬性的龐大的符號(hào)表。 第第3種：折衷方式是根據(jù)符號(hào)屬性相似程度分類(lèi)組種：折衷方式是根據(jù)符號(hào)屬性相似程度分類(lèi)組織成若干張表，每張表中記錄的符號(hào)都有比較多織成若干張表，每張表中記錄的符號(hào)都有比較多的相同屬性。的相同屬性。 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓編譯程序按名字的不同種屬分別使用許多符號(hào)表，如常數(shù)編譯程序按名字的不同種屬分別使用許多符號(hào)表，如常數(shù)表、變量名表、過(guò)程名表等等。表、變量名表、過(guò)程名表等等。SUBROUTINE INCWAP（M，N）10 KM1 MM4 NK RETURN END經(jīng)編譯

7、頭三階段后所產(chǎn)生的主要表格有：經(jīng)編譯頭三階段后所產(chǎn)生的主要表格有：符號(hào)名表符號(hào)名表SNT；常數(shù)表常數(shù)表CT；入口名表入口名表ENT；標(biāo)號(hào)表標(biāo)號(hào)表LT；四元式表四元式表QT 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 符號(hào)名表符號(hào)名表SNT NAME INFORMATION（1）M 啞元，整數(shù)，變量啞元，整數(shù)，變量（2）N 啞元，整數(shù)，變量啞元，整數(shù)，變量（3）K 整數(shù)，變量整數(shù)，變量 常數(shù)表常數(shù)表CT 值（值（VALUE） (1) 1 （2） 4武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 入口名表入口名表ENT NAME INFORMATION （1）INCWAP

8、二目子程序，入口二目子程序，入口QT(1)/*記錄入口名記錄入口名INCWAP的入口地址的入口地址 標(biāo)號(hào)表標(biāo)號(hào)表LT LABLE INFORMATION （1）10 QT(4)/*記錄了標(biāo)號(hào)記錄了標(biāo)號(hào)10對(duì)應(yīng)的四元式序列號(hào)對(duì)應(yīng)的四元式序列號(hào)武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓9.3.2 符號(hào)表項(xiàng)的排列符號(hào)表項(xiàng)的排列 符號(hào)表作為一個(gè)多元組，表中元組的排列組織符號(hào)表作為一個(gè)多元組，表中元組的排列組織是構(gòu)造符號(hào)表的重要成分。在編譯程序的整個(gè)工是構(gòu)造符號(hào)表的重要成分。在編譯程序的整個(gè)工作過(guò)程中，符號(hào)表被頻繁地用來(lái)建立表項(xiàng)，找查作過(guò)程中，符號(hào)表被頻繁地用來(lái)建立表項(xiàng)，找查表項(xiàng)，填充和引

9、用表項(xiàng)的屬性。因此表項(xiàng)的排列表項(xiàng)，填充和引用表項(xiàng)的屬性。因此表項(xiàng)的排列組織對(duì)該系統(tǒng)運(yùn)行的效率起著十分重要的作用。組織對(duì)該系統(tǒng)運(yùn)行的效率起著十分重要的作用。 在編譯程序中，符號(hào)表項(xiàng)的組織傳統(tǒng)上采用三在編譯程序中，符號(hào)表項(xiàng)的組織傳統(tǒng)上采用三種構(gòu)造方法。種構(gòu)造方法。 （1）線(xiàn)性組織）線(xiàn)性組織 （2）排序組織及二分法）排序組織及二分法 （3）散列法。）散列法。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓9.3.3 關(guān)鍵字域的組織關(guān)鍵字域的組織符號(hào)表的關(guān)鍵字域（段）就是符號(hào)名稱(chēng)符號(hào)表的關(guān)鍵字域（段）就是符號(hào)名稱(chēng) （1）等長(zhǎng)關(guān)鍵字域（段）符號(hào)表）等長(zhǎng)關(guān)鍵字域（段）符號(hào)表 （2）不等長(zhǎng)關(guān)鍵字段符

10、號(hào)表）不等長(zhǎng)關(guān)鍵字段符號(hào)表-采用關(guān)鍵字池采用關(guān)鍵字池的索引結(jié)構(gòu)。的索引結(jié)構(gòu)。9.3.4 其他域的組織其他域的組織 （1）等長(zhǎng)屬性值域組織）等長(zhǎng)屬性值域組織 （2）不等長(zhǎng)屬性值域組織）不等長(zhǎng)屬性值域組織9.3.5 下推鏈域的組織下推鏈域的組織武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓 9.4 符號(hào)表的管理符號(hào)表的管理 9.4.1 符號(hào)表的初始化符號(hào)表的初始化 9.4.2 符號(hào)的登錄符號(hào)的登錄 9.4.3 符號(hào)的查找符號(hào)的查找 9.4.4 符號(hào)表中分程序結(jié)構(gòu)層次的管理符號(hào)表中分程序結(jié)構(gòu)層次的管理 對(duì)于具有分程序型結(jié)構(gòu)的語(yǔ)言程序，對(duì)于具有分程序型結(jié)構(gòu)的語(yǔ)言程序，不同層次分程序中定義的標(biāo)

11、識(shí)符號(hào)具有不不同層次分程序中定義的標(biāo)識(shí)符號(hào)具有不同的作用域和不同的可視性規(guī)則。通常對(duì)同的作用域和不同的可視性規(guī)則。通常對(duì)于具有分程序結(jié)構(gòu)的語(yǔ)言可用兩種方式組于具有分程序結(jié)構(gòu)的語(yǔ)言可用兩種方式組織它們的符號(hào)表：織它們的符號(hào)表： 一是對(duì)每個(gè)分程序建立一是對(duì)每個(gè)分程序建立一個(gè)獨(dú)立的分表結(jié)構(gòu)的符號(hào)表；一是把各一個(gè)獨(dú)立的分表結(jié)構(gòu)的符號(hào)表；一是把各分程序符號(hào)組織在一張單表結(jié)構(gòu)的符號(hào)表分程序符號(hào)組織在一張單表結(jié)構(gòu)的符號(hào)表中中 武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓分表結(jié)構(gòu)的組織管理分表結(jié)構(gòu)的組織管理其基本思想是，每當(dāng)編譯程序掃描到一個(gè)分程其基本思想是，每當(dāng)編譯程序掃描到一個(gè)分程序結(jié)構(gòu)開(kāi)始時(shí)

12、，為該分程序建立一張符號(hào)表，在該序結(jié)構(gòu)開(kāi)始時(shí)，為該分程序建立一張符號(hào)表，在該分程序中定義的標(biāo)識(shí)符，都被登錄在該符號(hào)表中。分程序中定義的標(biāo)識(shí)符，都被登錄在該符號(hào)表中。而當(dāng)編譯程序掃描到一個(gè)分程序的結(jié)束時(shí)，編譯程而當(dāng)編譯程序掃描到一個(gè)分程序的結(jié)束時(shí)，編譯程序釋放為該分程序所建立的符號(hào)表。這種符號(hào)表的序釋放為該分程序所建立的符號(hào)表。這種符號(hào)表的分表結(jié)構(gòu)與源程序的分程序?qū)哟谓Y(jié)構(gòu)一一對(duì)應(yīng)分表結(jié)構(gòu)與源程序的分程序?qū)哟谓Y(jié)構(gòu)一一對(duì)應(yīng) 。武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓武漢理工大學(xué)計(jì)算機(jī)科學(xué)系林泓單表結(jié)構(gòu)的組織管理：?jiǎn)伪斫Y(jié)構(gòu)的組織管理：其基本思想是，所有分程序中定義的標(biāo)識(shí)符其基本思想是，所有分程序中定義的標(biāo)識(shí)符都集中在單張符號(hào)表中。為了實(shí)現(xiàn)分程序構(gòu)造中都集中在單張符號(hào)表中。為了實(shí)現(xiàn)分程序構(gòu)造中標(biāo)識(shí)符的作用域和可視性規(guī)則的