編譯原理chapter8.1符號(hào)表的作用和地位

1、第8章 符號(hào)表8.1 符號(hào)表的作用和地位8.2 符號(hào)表項(xiàng)結(jié)構(gòu)及對(duì)符號(hào)表的操作8.3 符號(hào)的主要屬性及作用8.4 符號(hào)表的組織8.5 符號(hào)表項(xiàng)的排列8.6 分程序結(jié)構(gòu)的符號(hào)表8.7 表結(jié)構(gòu)的組織管理8.8 PASCAL符號(hào)表結(jié)構(gòu)8.1符號(hào)表的作用和地位1.符號(hào)表的地位 符號(hào)表中所登記的信息在編譯的不同階段都要用到。(1)語(yǔ)義檢查的依據(jù)在語(yǔ)義分析中，符號(hào)表所登記的內(nèi)容將用于語(yǔ)義檢查（如檢查一個(gè)名字的使用和原先的說(shuō)明是否一致）和產(chǎn)生中間代碼。(2)目標(biāo)代碼生成階段地址分配的依據(jù)在目標(biāo)代碼生成階段，當(dāng)對(duì)符號(hào)名進(jìn)行地址分配時(shí)，符號(hào)表是地址分配的依據(jù)。(3)其他對(duì)一個(gè)多遍掃描的編譯程序，不同遍所用的符號(hào)表

2、也往往各有不同。因?yàn)槊勘樗P(guān)心的信息各有差異。2.符號(hào)表的作用在編譯程序中符號(hào)表用來(lái)存放語(yǔ)言程序中出現(xiàn)的有關(guān)標(biāo)識(shí)符的屬性信息.8.2符號(hào)表項(xiàng)結(jié)構(gòu)及對(duì)符號(hào)表的管理一、符號(hào)表項(xiàng)結(jié)構(gòu)1、符號(hào)表通常由表項(xiàng)構(gòu)成。2、每一表項(xiàng)通常分為兩部分：主欄和信息欄。3、主欄內(nèi)容為標(biāo)志符名，在整個(gè)程序中唯一。4、每一信息欄包含若干子欄和標(biāo)志位，以記錄與標(biāo)志符名相關(guān)的各種屬性信息。二、符號(hào)表的操作 在整個(gè)編譯期間，對(duì)于符號(hào)表的操作大致可歸納為五類： 對(duì)給定名字，查詢名字是否已在表中； 往表中填入一個(gè)新的名字； 對(duì)給定名字，訪問(wèn)它的某些信息； 對(duì)給定名字，填寫(xiě)或更新它的某些信息； 刪除一個(gè)或一組無(wú)用的項(xiàng)。 不同種類的表格

3、所涉及的操作往往也是不同的。上述五個(gè)方面只是一些基本的共同操作。8.2符號(hào)表項(xiàng)結(jié)構(gòu)及對(duì)符號(hào)表的操作通常用到的屬性有：1 符號(hào)名：是每個(gè)表項(xiàng)的關(guān)鍵字，由它可找到每個(gè)標(biāo)志符在符號(hào)表中的位置；此位置充當(dāng)標(biāo)識(shí)符的內(nèi)部編碼。2 符號(hào)的類型：變量的類型決定相應(yīng)的存儲(chǔ)方式和可施加的運(yùn)算操作，常用于語(yǔ)義檢查。 3 符號(hào)的存儲(chǔ)類別：語(yǔ)義處理、檢查和存儲(chǔ)分配的重要依據(jù)。如C語(yǔ)言中的內(nèi)部和外部變量可由聲明變量的語(yǔ)句的位置表現(xiàn)出來(lái)。4 符號(hào)的作用域及可視性：作用域只是某符號(hào)在程序中的有效區(qū)域；在PASCAL中內(nèi)層變量會(huì)覆蓋外層同名變量，則外層該變量在內(nèi)層不可視。這些屬性是語(yǔ)義處理重要依據(jù)。8.3符號(hào)的主要屬性及作用5

4、 符號(hào)變量的存儲(chǔ)分配信息 ：根據(jù)符號(hào)變量的存儲(chǔ)類別定義及出現(xiàn)位置和次序確定的該變量對(duì)應(yīng)的存區(qū)位置。6 符號(hào)的其它屬性 (1)數(shù)組內(nèi)情向量 含有數(shù)組的維數(shù)，各維上下界，元素類型，存儲(chǔ)首地址，C值等。 (2)記錄結(jié)構(gòu)型的成員信息 含有元素屬性和排列次序等 (3)函數(shù)及過(guò)程的形參 含有參數(shù)個(gè)數(shù)、排列次序和參數(shù)的屬性等。8.3符號(hào)的主要屬性及作用8.4 符號(hào)表的組織 按照處理對(duì)象的特點(diǎn)，符號(hào)表的組織方式通常可分為：直接方式和間接方式。1、直接方式： 把語(yǔ)言中所有符號(hào)都組織在一張符號(hào)表中。組成一張包括了所有屬性的龐大的符號(hào)表，這種符號(hào)表的各欄長(zhǎng)度固定，結(jié)構(gòu)簡(jiǎn)單，方便填寫(xiě)和查找。2、間接方式：對(duì)于可變長(zhǎng)標(biāo)

5、志符，需用間接方式組織符號(hào)表。把屬性種類完全相同的那些符號(hào)組織在一起，構(gòu)造出表項(xiàng)是分別為等長(zhǎng)的多個(gè)符號(hào)表,各符號(hào)表的主欄包含兩項(xiàng)：指針和整數(shù)；指針指向標(biāo)志符在數(shù)組中位置，整數(shù)表示標(biāo)志符長(zhǎng)度。(2) 根據(jù)標(biāo)志符的種屬，如簡(jiǎn)單變量、數(shù)組、過(guò)程等，為同一種屬的標(biāo)志符建一張表，如常數(shù)表、變量名表、過(guò)程名表等等。3、信息欄的組織方式固定信息內(nèi)容、信息地址8.4 符號(hào)表的組織4、例 SUBROUTINE INCWAP（M，N）10 KM1 MM4 NK RETURN END 經(jīng)編譯頭三階段后所產(chǎn)生的主要表格有：符號(hào)名表SNT、常數(shù)表CT、入口名表ENT、標(biāo)號(hào)表LT和四元式表QT 8.4 符號(hào)表的組織 符號(hào)

6、名表SNT NAME INFORMATION（1）M 啞元，整數(shù)，變量（2）N 啞元，整數(shù)，變量（3）K 整數(shù)，變量 8.4 符號(hào)表的組織4、例 常數(shù)表CT 值（VALUE） (1) 1 （2） 4 入口名表ENT NAME INFORMATION（1）INCWAP 二目子程序，入口QT(1)/*記錄入口名INCWAP的入口地址 標(biāo)號(hào)表LT LABLE INFORMATION（1）10 QT(4)/*記錄了標(biāo)號(hào)10對(duì)應(yīng)的四元式序列號(hào)8.4 符號(hào)表的組織四元式表QTOPR AGR1 AGR2 RESULTLINKactpar INCWAP 1 Mactpar INCWAP 2 N + M 1 K

7、 + N 4 M + K N paract INCWAP 1 M paract INCWAP 2 N reto8.4 符號(hào)表的組織8.5符號(hào)表項(xiàng)的排列 符號(hào)表作為一個(gè)多元組，表中元組的排列組織是構(gòu)造符號(hào)表的重要成分。在編譯程序的整個(gè)工作過(guò)程中，符號(hào)表被頻繁地用來(lái)建立表項(xiàng)，找查表項(xiàng)，填充和引用表項(xiàng)的屬性。因此表項(xiàng)的排列組織對(duì)該系統(tǒng)運(yùn)行的效率起著十分重要的作用。在編譯程序中，符號(hào)表項(xiàng)的組織傳統(tǒng)上采用三種構(gòu)造方法。即線性法，二分法及散列法。8.6分程序結(jié)構(gòu)的符號(hào)表 對(duì)于具有分程序型結(jié)構(gòu)的語(yǔ)言程序，不同層次分程序中定義的標(biāo)識(shí)符號(hào)具有不同的作用域和不同的可視性規(guī)則。通常對(duì)于具有分程序結(jié)構(gòu)的語(yǔ)言可用兩種方

8、式組織它們的符號(hào)表： 一是對(duì)每個(gè)分程序建立一個(gè)獨(dú)立的分表結(jié)構(gòu)的符號(hào)表；一是把各分程序符號(hào)組織在一張單表結(jié)構(gòu)的符號(hào)表中 1、分表結(jié)構(gòu)的組織管理 基本思想: 每當(dāng)編譯程序掃描到一個(gè)分程序結(jié)構(gòu)開(kāi)始時(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)一一對(duì)應(yīng) 。8.7 表結(jié)構(gòu)的組織管理基本思想: 所有分程序中定義的標(biāo)識(shí)符都集中在單張符號(hào)表中。為了實(shí)現(xiàn)分程序構(gòu)造中標(biāo)識(shí)符的作用域和可視性規(guī)則的要求,在符號(hào)表中可設(shè)立一個(gè)屬性域用來(lái)登錄符號(hào)所在分程序的層次。 進(jìn)入分

9、程序時(shí)，層次要增加一層。在退出一個(gè)分程序時(shí)，層次降低一層，且需要把符號(hào)表中，所有在退出的分程序中登錄的符號(hào)項(xiàng)清除。2、單表結(jié)構(gòu)的組織管理8.7 表結(jié)構(gòu)的組織管理 根據(jù)嵌套結(jié)構(gòu)型程序設(shè)計(jì)語(yǔ)言（Pascal）的特點(diǎn)，可采用以下表結(jié)構(gòu)：將其符號(hào)表設(shè)計(jì)為棧符號(hào)表，當(dāng)新的名字出現(xiàn)總是從棧頂填入。查找操作從符號(hào)表的棧頂往底部查（保證先查最近出現(xiàn)的名字）。因?yàn)槌绦蚴欠謱拥模⑶乙粋€(gè)過(guò)程結(jié)束時(shí)將釋放相應(yīng)的子符號(hào)表，因此查找范圍與線性表比相對(duì)要小一些。引入一個(gè)顯示（DISPLAY）層次關(guān)系表，稱為過(guò)程的嵌套層次表。其作用是為了描述過(guò)程的嵌套層次，指出當(dāng)前正在活動(dòng)著的各嵌套的過(guò)程（或函數(shù)）相應(yīng)的子符號(hào)表在棧符號(hào)表

10、中的起始位置（相對(duì)地址）。DISPLAY表也是一個(gè)棧，棧頂指針為level。當(dāng)進(jìn)入一個(gè)新過(guò)程時(shí)，level增加1；每當(dāng)退出一個(gè)過(guò)程時(shí)，level減1。DISPLAY(level)總是指向當(dāng)前正在處理的最內(nèi)層的過(guò)程的子符號(hào)表在棧符號(hào)表中的起始位置。在符號(hào)表的信息欄中引入一個(gè)指針域（previous）用以鏈接它在同一過(guò)程內(nèi)的前一域名字在表中的下標(biāo)（相對(duì)位置）。每一層的最后一個(gè)域名字，其previous之值為0。這樣，每當(dāng)需要查找一個(gè)新名字時(shí)，就能通過(guò)DISPLAY找出當(dāng)前正在處理的最內(nèi)層的過(guò)程及所有外層的子符號(hào)表在棧符號(hào)表中的位置。然后，通過(guò)previous可以找到同一過(guò)程內(nèi)的所有被說(shuō)明的名字。8

11、.8 PASCAL符號(hào)表結(jié)構(gòu)說(shuō)明部分的分析與處理對(duì)每個(gè)過(guò)程說(shuō)明的對(duì)象（變量，常量和過(guò)程）造名字表填寫(xiě)標(biāo)識(shí)符的所在層次、屬性和分配的相對(duì)位置。標(biāo)識(shí)符的屬性不同時(shí)，所需填入的信息也不同。登錄信息由ENTER過(guò)程完成。8.8 PASCAL符號(hào)表結(jié)構(gòu)說(shuō)明部分的分析與處理（程序）說(shuō)明類型的定義： object= (constant, variable,procedur) （定義純量/枚舉類型）名字表的定義 table:array0.txmax of record name:alfa; case kind:object of constant:(val:integer); variable:procedur:(level,adr,size: integer); 8.8 PASCAL符號(hào)表結(jié)構(gòu)例程序說(shuō)明部分為：CONST A=35，B=49；VAR C，D，E；PROCEDURE P；VAR G ；