工科專業(yè)下編譯原理第八章

1、編譯原理電子教案第八章 符號(hào)表謝強(qiáng)計(jì)算機(jī)科學(xué)與技術(shù)學(xué)院 本章的主要內(nèi)容表的組織和使用整理與查找名字的作用范圍表的內(nèi)容本章要求 知識(shí)點(diǎn)：表的組織和使用，整理與查找，名字的作用范圍，表的內(nèi)容。深刻理解：表的組織和使用，整理與查找。熟練掌握：（1）表的組織和使用（2）整理與查找本章教學(xué)線索1 符號(hào)表的組織與作用 1.1 符號(hào)表的基本概念 1.2 符號(hào)表的組織 1.3 符號(hào)表的作用 2 符號(hào)表的整理和查找3 名字的作用范圍4 符號(hào)表的內(nèi)容1.1 符號(hào)表的基本概念符號(hào)表：用來存儲(chǔ)源程序中出現(xiàn)的各種名字的屬性和特征等信息。這些信息在編譯過程的不同階段都要用到。在語義分析階段，符號(hào)表記錄的內(nèi)容將用于語義檢查

2、和產(chǎn)生中間代碼。在目標(biāo)代碼生成階段，符號(hào)表是為符號(hào)名進(jìn)行地址分配的一句。符號(hào)表的維護(hù)：符號(hào)表的內(nèi)容可能在編譯過程中的不同階段填入。在編譯過程中，每當(dāng)掃描器識(shí)別出一個(gè)名字后，編譯程序就查閱符號(hào)表，看它是否在其中，如果是一個(gè)新名字就將它填入表中。它的有關(guān)信息將在詞法分析和語法、語義分析過程中逐步填入。符號(hào)表的構(gòu)成：一張符號(hào)表的每一項(xiàng)（或稱入口）包含兩大欄（或稱區(qū)段、字域），即名字欄（標(biāo)識(shí)符）和信息欄（種屬、類型等）。形式如下：名字欄（NAME）信息欄（INFORMATION） 說明：1）一般對符號(hào)表的查找都是通過匹配名字來實(shí)現(xiàn) 2）信息欄包含許多子欄和標(biāo)志位 3）對于復(fù)雜的名字信息，可以另外的空間

3、存放，在符號(hào)表中存放指向它的指針 符號(hào)表的操作：查詢插入更新刪除第1項(xiàng)（入口1）第2項(xiàng)（入口2）第n項(xiàng)（入口n）1.2 符號(hào)表的組織方法一：符號(hào)表的各項(xiàng)各欄采用固定的存儲(chǔ)單元，每一欄的內(nèi)容可以直接放置在有關(guān)區(qū)段中。這種方法易于組織、填寫和查找；缺點(diǎn)是靈活性大大受限；方法二：間接安排符號(hào)表的名字欄和各種種名字的信息。對于名字欄可以用一個(gè)獨(dú)立的字符串?dāng)?shù)組存放所有的標(biāo)志符，在符號(hào)表中的名字欄存放一個(gè)指示器和一個(gè)整數(shù)，指示器代表標(biāo)志符在字符數(shù)組中的位置，整數(shù)代表標(biāo)志符的長度；同樣，對于標(biāo)志符的屬性，可以將共同屬性放在符號(hào)表中，將其它特殊信息放在別的地方，在信息欄設(shè)置一個(gè)指向存放特殊信息的地方的指針。對

4、于數(shù)組一般專門開辟一個(gè)信息區(qū)，稱為數(shù)組信息表（內(nèi)情信息表），將數(shù)組的下標(biāo)符、維數(shù)、每維的長度等放在這個(gè)信息區(qū)中。NAMEINFORMATION，6，4NAMEINFORMATIONS A M P L E L O O P6 S A M P L E 4 L O O PNAME INFORMATION CAT 地址 a維數(shù)首地址界差d1界差dn上屆I1 下屆u1 上屆In 下屆un內(nèi)情向量表1.3 符號(hào)表的作用符號(hào)表的作用-語義檢查的依據(jù)目標(biāo)代碼生成階段地址分配的依據(jù)在編譯程序中符號(hào)表用來存放語言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息，符號(hào)表中所登記的信息在編譯的不同階段都要用到。在語義分析中，符號(hào)表所登

5、記的內(nèi)容將用于語義檢查（如檢查一個(gè)名字的使用和原先的說明是否一致）和產(chǎn)生中間代碼。在目標(biāo)代碼生成階段，當(dāng)對符號(hào)名進(jìn)行地址分配時(shí)，符號(hào)表是地址分配的依據(jù)。對一個(gè)多遍掃描的編譯程序，不同遍所用的符號(hào)表也往往各有不同。因?yàn)槊勘樗P(guān)心的信息各有差異。本章教學(xué)線索1 符號(hào)表的組織與作用 2 符號(hào)表的整理和查找 2.1 線形表 2.2 對折查找與二叉樹 2.3 雜湊技術(shù)（哈希表技術(shù)）3 名字的作用范圍4 符號(hào)表的內(nèi)容2.1 線形表 使用一個(gè)一維數(shù)組或多個(gè)一維數(shù)組來存放符號(hào)串的名字和相關(guān)信息。特點(diǎn)：1）按名字出現(xiàn)的先后順序依次填入； 2）查找時(shí)從頭到尾逐個(gè)查找；缺點(diǎn)：主要是查找非常慢。改進(jìn)的思路： 1）按照

6、編程習(xí)慣，可以反序查找 2）按“最新最近”訪問原則形成一條指向表的鏈，每次查找時(shí)都按這條鏈所指的順序查找。2.2 對折查找與二叉樹 為了提高查找效率，在構(gòu)造符號(hào)表時(shí)，把表格中的項(xiàng)按名字的“大小”順序整理排列；所謂名字的“大小”通常指名字的內(nèi)碼二進(jìn)制。 對于這種順序化的表的查找就可以使用對折法進(jìn)行查找。特點(diǎn)： 1）查找速度快； 2）順序化工作很費(fèi)時(shí)間，并且很多時(shí)候是沒必要的。二叉樹法：（是一種鏈表的方法）令每項(xiàng)是一個(gè)結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)附設(shè)兩個(gè)指示器欄，一欄為左枝，另一欄為右枝，每個(gè)結(jié)點(diǎn)的主欄內(nèi)碼值被看成是代表該結(jié)點(diǎn)的值。任何一個(gè)結(jié)點(diǎn)的右枝的所有結(jié)點(diǎn)值均小于該結(jié)點(diǎn)的值，而左枝的任何結(jié)點(diǎn)的值均大于該結(jié)點(diǎn)

7、的值。二叉樹的形成：令第一個(gè)碰到的名字作為“根”結(jié)點(diǎn)，它的左、右指示器均置為null；當(dāng)要加入新結(jié)點(diǎn)時(shí)，首先把它和根結(jié)點(diǎn)的值比較，小者放在右枝上，大者放在左枝上。如果根結(jié)點(diǎn)的左（右）枝已經(jīng)形成子樹，則讓新結(jié)點(diǎn)同子樹的根再比較。重復(fù)上述步驟，直到把新結(jié)點(diǎn)插入使它成為二叉樹的一個(gè)端末結(jié)點(diǎn)為止。特點(diǎn)：查找速度比對折查找效率低，空間要求多一點(diǎn)，但順序化時(shí)間少。2.3 雜湊技術(shù)（哈希表技術(shù)） 假定有一個(gè)足夠大的區(qū)域，這個(gè)區(qū)域用以填寫一張含N項(xiàng)的符號(hào)表。構(gòu)造一個(gè)地址函數(shù)H，對名字求其雜湊函數(shù)值，該值在0N-1之間。 必須要解決不同的名字對應(yīng)一個(gè)雜湊值。 在實(shí)現(xiàn)時(shí)，一般使用一張雜湊（鏈）表通過間接方式查填符

8、號(hào)表。將所有相同雜湊值的符號(hào)名連成一串，便于線形查找。填入過程：首先計(jì)算H(SYM)的值h，置PHASHTABLEh（若未曾有雜湊值為h的項(xiàng)名填入過，則Pnull）；然后置HASHTABLEh=available，再把新名SYM及其鏈接指示器LINK的值P填進(jìn)available所指的符號(hào)表位置，并累增available的值使它指向下一個(gè)空項(xiàng)的位置。查找方法：首先計(jì)算出H（SYM）h，然后就指示器HASHTABLEh所指的項(xiàng)鏈注意按序查找。特點(diǎn)：填表和查表速度都比較快。本章教學(xué)線索1 符號(hào)表的組織與作用 2 符號(hào)表的整理和查找3 名字的作用范圍 3.1 FOUTRAN的符號(hào)表組織 3.2 分程序

9、結(jié)構(gòu)的符號(hào)表 3.3 Pascal的符號(hào)表的組織4 符號(hào)表的內(nèi)容3.1 FOUTRAN的符號(hào)表組織 根據(jù)Fortran語言的特點(diǎn)，可以將程序現(xiàn)行段的局部名登記在表格區(qū)的一端，而把所有全局名登記在表格區(qū)的另一端，局部名區(qū)域可重復(fù)利用，當(dāng)一個(gè)程序段處理完成后，新的程序段又可在同一位置上建立新的局部名表。3.2 分程序結(jié)構(gòu)的符號(hào)表 對于具有分程序型結(jié)構(gòu)的語言程序，不同層次分程序中定義的標(biāo)識(shí)符號(hào)具有不同的作用域和不同的可視性規(guī)則。通常對于具有分程序結(jié)構(gòu)的語言可用兩種方式組織它們的符號(hào)表： 一是對每個(gè)分程序建立一個(gè)獨(dú)立的分表結(jié)構(gòu)的符號(hào)表；一是把各分程序符號(hào)組織在一張單表結(jié)構(gòu)的符號(hào)表中。分表結(jié)構(gòu)的組織管理

10、 其基本思想是，每當(dāng)編譯程序掃描到一個(gè)分程序結(jié)構(gòu)開始時(shí)，為該分程序建立一張符號(hào)表，在該分程序中定義的標(biāo)識(shí)符，都被登錄在該符號(hào)表中。而當(dāng)編譯程序掃描到一個(gè)分程序的結(jié)束時(shí)，編譯程序釋放為該分程序所建立的符號(hào)表。這種符號(hào)表的分表結(jié)構(gòu)與源程序的分程序?qū)哟谓Y(jié)構(gòu)一一對應(yīng)。單表結(jié)構(gòu)的組織管理其基本思想是，所有分程序中定義的標(biāo)識(shí)符都集中在單張符號(hào)表中。為了實(shí)現(xiàn)分程序構(gòu)造中標(biāo)識(shí)符的作用域和可視性規(guī)則的要求，在符號(hào)表中可設(shè)立一個(gè)屬性域用來登錄符號(hào)所在分程序的層次進(jìn)入分程序時(shí)，層次要增加一層.在退出一個(gè)分程序時(shí)，層次降低一層，且需要把符號(hào)表中，所有在退出的分程序中登錄的符號(hào)項(xiàng)清除。3.3 Pascal的符號(hào)表的組織

11、嵌套結(jié)構(gòu)型程序設(shè)計(jì)語言（Pascal）的特點(diǎn)，可采用的辦法：將其符號(hào)表設(shè)計(jì)為棧符號(hào)表，當(dāng)新的名字出現(xiàn)總是從棧頂填入。查找操作從符號(hào)表的棧頂往底部查（保證先查最近出現(xiàn)的名字）。因?yàn)槌绦蚴欠謱拥模⑶乙粋€(gè)過程結(jié)束時(shí)將釋放相應(yīng)的子符號(hào)表，因此查找范圍與線性表比相對要小一些。引入一個(gè)顯示（DISPLAY）層次關(guān)系表，稱為過程的嵌套層次表。其作用是為了描述過程的嵌套層次，指出當(dāng)前正在活動(dòng)著的各嵌套的過程（或函數(shù)）相應(yīng)的子符號(hào)表在棧符號(hào)表中的起始位置（相對地址）。DISPLAY表也是一個(gè)棧，棧頂指針為level。當(dāng)進(jìn)入一個(gè)新過程時(shí)，level增加1；每當(dāng)退出一個(gè)過程時(shí)，level減1。DISPLAY(le

12、vel)總是指向當(dāng)前正在處理的最內(nèi)層的過程的子符號(hào)表在棧符號(hào)表中的起始位置。在符號(hào)表的信息欄中引入一個(gè)指針域（previous）用以鏈接它在同一過程內(nèi)的前一域名字在表中的下標(biāo)（相對位置）。每一層的最后一個(gè)域名字，其previous之值為0。這樣，每當(dāng)需要查找一個(gè)新名字時(shí)，就能通過DISPLAY找出當(dāng)前正在處理的最內(nèi)層的過程及所有外層的子符號(hào)表在棧符號(hào)表中的位置。然后，通過previous可以找到同一過程內(nèi)的所有被說明的名字。本章教學(xué)線索1 符號(hào)表的組織與作用 2 符號(hào)表的整理和查找3 名字的作用范圍4 符號(hào)表的內(nèi)容4 符號(hào)表的內(nèi)容符號(hào)表的信息欄中登記了每個(gè)名字的有關(guān)性質(zhì)，如類型、種屬、大小以及現(xiàn)對數(shù)（指分配給該名字的存儲(chǔ)單元的相對地址）。變量： 類型（整、實(shí)、雙精度、布爾、字符、標(biāo)號(hào)或指針等）； 種屬（簡單變量、數(shù)組或記錄結(jié)構(gòu)等）；