編譯原理第八章：符號表

第八章符號表8.1符號表的組織與作用8.2整理與查找8.3名字的作用范圍8.4符號表的內(nèi)容復(fù)習(xí)題8.1符號表的組織與作用

一、符號表組成一張符號表的每一項（入口）包含兩大欄（區(qū)段，字域），即名字欄和信息欄。

表格的形式第1項（入口1）

第n項（入口n）

二、符號表使用（基本操作）

1.（查表）對給定名字，查詢此名是否已在表中

2.（填表）填入新名

3.（訪表信息）對給定名字，訪問它的信息

4.（更新）對給定名字，往表中填寫或更新它的某些信息

5.（刪除）刪除一個或一組無用的項三、符號表的組織方式

1．直接填寫式NameInformationsample…loop…

2.用一個獨立的字符串?dāng)?shù)組，把所有標(biāo)識符放在其中（1）在符號表主欄放一個指示器和整數(shù)

NameInformation四、符號表種類符號名表常數(shù)表入口名表標(biāo)號表四元式表內(nèi)情向量表(維數(shù)n，首地址a，上界，下界，界差)

…8.2整理與查找

線性表辦法最簡單，效率低二叉樹效率高，實現(xiàn)困難雜湊效率最高，實現(xiàn)復(fù)雜,消耗額外存儲空間

一、線性表1.構(gòu)造按關(guān)鍵字出現(xiàn)順序填寫各個項“先來者先填”2.查找從第一項開始順序查找，若一直查找到AVAILBLE項還未找到，說明該名字不在表中

NameInformation

1J1--2XYZ--3I--4BC--

AVAILBAE→3．提高線性表查找效率（自適應(yīng)線性表）給每項附設(shè)一個指示器，這些指示器把所有的項按“最新最近”訪問原則連接成一條鏈，使得在任何時候，這條鏈的第一個元素所指的項是那個最新最近被查詢過的項，第二個元素所指的項是那個次新次近被查詢過的項,如此等等,…二、對折查找與二叉樹整理為了提高查表的速度，可以在造表的同時把表格中的項按名字的“大小”順序整理排列。2．對折查找（折半查找）

n項[n/2+1]

小中大

←↑→↑↑順序化整理極費時間3.符號表組織成二叉樹令每項是一個結(jié)點，每個結(jié)點附設(shè)兩個指示器欄，分別為LEFT，RIGHT。每個結(jié)點主欄內(nèi)碼值被看成是代表該結(jié)點的值，任何結(jié)點P右枝所有結(jié)點值均應(yīng)小于結(jié)點P的值，而左枝任何結(jié)點值均應(yīng)大于結(jié)點P的值。4.二叉樹形成過程令第一個碰到的名字作為“根“結(jié)點，它的左，右指示器均置為null.當(dāng)要加入新結(jié)點時，首先把它和根結(jié)點值作比較，小者放在右枝上，大者放在左枝上，如果根結(jié)點的左（右）枝已成子樹，則讓新結(jié)點和子樹的根再作比較，重復(fù)直至把新結(jié)點插入使它成為二叉樹的一個端末結(jié)點（葉子）為止。三、雜湊技術(shù)填表快，查表慢方法構(gòu)造一個地址函數(shù)H，對任何名字SYM，H（SYM）取值于0~N-1，不論對SYM查表或填表，都希望能從H（SYM）獲得它在表中的位置２．Hash函數(shù)構(gòu)造方法（1）直接定址法取關(guān)鍵字或關(guān)鍵字的某個線性函數(shù)值為Hash地址

H(key)=key或H(key)=a.key+b

（2）數(shù)字分析法若關(guān)鍵字是以r為基的數(shù)，且Hash表中可能出現(xiàn)的關(guān)鍵字都是事先知道的，則可取關(guān)鍵字的若干數(shù)位組成Hash地址（3）折迭法將關(guān)鍵字分割成位數(shù)相同的幾部分，然后取這幾部分的迭加和作為Hash地址（4）除留余數(shù)法取關(guān)鍵字被某個不大于哈希表表長m的數(shù)P除后所得余數(shù)為

Hash地址H(key)=keyMODP(P≤m)

（5）平方取中法取關(guān)鍵字平方的中間幾位為Hash地址（6）隨機數(shù)法選擇一個隨機函數(shù)，取關(guān)鍵字的隨機函數(shù)值為它的Hash地址3．處理沖突的方法（1）開放定址法

Hi=(H(key)+di)MODmi=1,2,….,k(k≤m-1)（2）再哈希法

Hi=RHi(key)i=1,2,…,k（3）鏈地址法將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈中（4）建立一個公共溢出區(qū)8.3名字的作用范圍

最近嵌套作用域原則：一個名字的作用域是那個包含了這個名字的說