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

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

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

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

4、于數(shù)組一般專門開辟一個信息區(qū)，稱為數(shù)組信息表（內(nèi)情信息表），將數(shù)組的下標符、維數(shù)、每維的長度等放在這個信息區(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 符號表的作用符號表的作用-語義檢查的依據(jù)目標代碼生成階段地址分配的依據(jù)在編譯程序中符號表用來存放語言程序中出現(xiàn)的有關標識符的屬性信息，符號表中所登記的信息在編譯的不同階段都要用到。在語義分析中，符號表所登

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

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

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

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

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

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

11、嵌套結構型程序設計語言（Pascal）的特點，可采用的辦法：將其符號表設計為棧符號表，當新的名字出現(xiàn)總是從棧頂填入。查找操作從符號表的棧頂往底部查（保證先查最近出現(xiàn)的名字）。因為程序是分層的，并且一個過程結束時將釋放相應的子符號表，因此查找范圍與線性表比相對要小一些。引入一個顯示（DISPLAY）層次關系表，稱為過程的嵌套層次表。其作用是為了描述過程的嵌套層次，指出當前正在活動著的各嵌套的過程（或函數(shù)）相應的子符號表在棧符號表中的起始位置（相對地址）。DISPLAY表也是一個棧，棧頂指針為level。當進入一個新過程時，level增加1；每當退出一個過程時，level減1。DISPLAY(le

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