《編譯原理》第8章 符號表

第八章符號表符號表的組織與作用整理和查找符號表的內(nèi)容名字的作用范圍編輯ppt第八章符號表符號表的作用:一致性檢查和作用域分析;輔助代碼生成.編輯ppt名字欄（Name）信息欄（Information）…………第一項（入口1）第二項（入口2）第n項（入口n）8.1符號表的組織與作用符號表的每一項(入口)包含兩大欄:名字欄，也稱主欄，關鍵字欄信息欄，記錄相應的不同屬性，分為若干子欄.編輯ppt8.1符號表的組織與作用對符號表的操作:填入名稱查找名字訪問信息填寫修改信息刪除編輯ppt對符號表進行操作的時機：定義性出現(xiàn)intx；使用性出現(xiàn)ifx<100……按名字的不同種屬建立多張符號表，如常數(shù)表、變量名表、過程名表、…符號表的組織方式:1.安排各項各欄的存儲單元為固定長度2.用間接方式安排各欄存儲單元8.1符號表的組織與作用編輯pptpoolelpmasNAMEINFORMATION?,6?,4pool4elpmas6NAMEINFORMATION??符號表的結(jié)構(gòu)用間接方式安排各欄存儲單元編輯ppt維數(shù)首地址界差d1???界差dn上界I1???上界In下界U1???下界Un內(nèi)情向量表???NAMEINFORMATIONCAT地址??a?符號表用間接方式安排各欄存儲單元編輯ppt符號表的存放次序:一張可容納N項的符號表在存儲器中可用下述兩種不同的方式之一表示（假定每項需用K個字）1.把每一項置于連續(xù)K存儲單元中，構(gòu)成一張K*N的表2.把整個符號表分成m個子表，如T1,T2,…Tm，每個子表含有N項.8.1符號表的組織與作用T1T2T3T4N1N2N3K1K2K3K4K=K1+K2+K3+K4編輯ppt例:PASCAL程序段：PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.編輯pptPROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.編輯pptPROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.編輯pptPROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.編輯pptPROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.編輯pptPROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.編輯ppt第八章符號表符號表的組織與作用整理和查找符號表的內(nèi)容名字的作用范圍編輯ppt8.2整理和查找1.線性查找2.二分查找3.雜湊查找(HASH技術(shù))編輯ppt8.2整理和查找1.線性查找按關鍵字出現(xiàn)的順序填寫各項。填表快，查找慢。結(jié)構(gòu)簡單，節(jié)省空間，效率低，查找時間復雜度：O(n)。改進：自適應線性表：給每一項附設一個指示器，這些指示器把所有的項按“最新最近”訪問原則連接成一條鏈，這條鏈的第一個元素所指的項是最新最近被查詢過的項，第二個元素所指的項是次新近被查詢過的項，諸如此類。每當填入新項時，總讓鏈頭指向最新項。編輯ppt2.二分查找表格中的項按名字的“大小”順序整理排列。填表慢,查找快。查找時間復雜度:O(Log2n)改進：組織成二叉樹。3.雜湊查找(HASH技術(shù))雜湊函數(shù)H(SYM)：0~N-1N：符號表的項數(shù)。要求：1.函數(shù)計算簡單高效2.函數(shù)值分布均勻填表快，查找快編輯ppt雜湊技術(shù)(HASH技術(shù))雜湊技術(shù)使用一張雜湊鏈表通過間接方式查填符號表，常常把所有相同雜湊值得符號名連成一串，便于線性查找。雜湊表是一個可容納N個指針的一維數(shù)組，它的每個元素的初值全為null。符號表除了通常包含的欄外還增設一鏈接欄，它把所有持相同雜湊值的符號名連接成一條鏈編輯ppt填入一個新的SYM的過程：（1）先計算出H(SYM)的值h（在0與N-1之間），將HASHTABLE[h]的值賦給P（若未曾有雜湊值為h的項名填入過，則將P置空）。（2）然后置HASHTABLE[h]=available，再把新名SYM及其鏈接指示器LINK的值P填進指針available所指向的符號表位置。使用此方法的查表過程如下：首先計算出此項的函數(shù)H的值等于h，然后就指示器

HASHTABLE[h]所指的項鏈逐一按序查找（線性查找）雜湊技術(shù)(HASH技術(shù))編輯pptavailableSYM1H（SYM1）=hp=HASHTABLE[h]=nullHASHTABLE[h]=AVAVILABLE=n1SYM1null…

…01hN-1雜湊表符號表……

……

……………LinkInformationNamen1n2n3n1nullavailableSYM2H（SYM2）=hp=HASHTABLE[h]=n1HASHTABLE[h]=AVAVILABLE=n2n2SYM2n1SYM3H（SYM3）=hp=HASHTABLE[h]=n2HASHTABLE[h]=AVAVILABLE=n3n3SYM3n2availableavailable編輯ppt第八章符號表符號表的組織與作用整理和查找符號表的內(nèi)容名字的作用范圍編輯ppt8.4符號表的內(nèi)容對于變量名、數(shù)組名和過程名，它們的信息欄中一般要求有下列信息：1.變量類型：整、實或布爾等；種屬：簡單變量、數(shù)組、過程等；大?。洪L度，即所需的存儲單元字數(shù)；相對數(shù)：指分配給該名字的存儲單元的相對地址；若為數(shù)組，則記錄其內(nèi)情向量；形式參數(shù)標志；是否對這個變量進行過賦值的標志位。編輯ppt8.4符號表的內(nèi)容2.過程是否為程序的外部過程？若為函數(shù)，類型是什么？其說明是否處理過？是否遞歸？形式參數(shù)是些什么？為了與實在參數(shù)進行比較，必須把它們的種屬、類型信息同過程名聯(lián)系在一起。編輯ppt第八章符號表符號表的組織與作用整理和查找符號表的內(nèi)容名字的作用范圍編輯ppt8.3名字的作用范圍在許多程序語言中,名字都有一個確定的作用范圍.作用域：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。兩種程序體結(jié)構(gòu):并列結(jié)構(gòu)，如FORTRAN嵌套結(jié)構(gòu)，如PASCAL，ADA編輯pptPROGRAMMAIN…integerX，YCOMMON/C/A，B…ENDSUBROUTINESUB1…realX，ZCOMMON/C/A1，B1…END編輯pptprogramP;vara,b:integer;procedureP1(i1,j1:integer);varc,d:integer…end;procedureP2(i2,j2:integer);vara,c:integer;procedureP21;varb1,b2:boolean;…end;…end;…end.編輯ppt1.

FORTRAN的符號表組織（并列結(jié)構(gòu)語言）一個FORTRAN程序由一個主程序段和若干個輔程序段組成.變量、數(shù)組和語句函數(shù)名的作用范圍就是它們所處的那個程序段。對于一遍掃描的編譯程序，可以逐段產(chǎn)生其目標代碼。當一程序段處理完后，它的所有的局部名均無需保存在符號表中，需要繼續(xù)留在符號表總的只是全局名。把局部名和全局名分別存在不同的地方.編輯pptPASCALPASCAL程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；end2.

嵌套結(jié)構(gòu)語言的符號表組織如PASCAL、ALGOL、ADA作用域遵循"最近嵌套原則".編輯ppt允許同一個標識符在不同的過程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個在子程序B1中說明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個內(nèi)層子程序且B2中對標識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2對X的任何引用都是指重新說明過的這個X。編輯pptprogrammainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integr)編輯ppt兩種做法:引入"過程編號"屬性。查找時，先查找本過程編號的名字，查不到則查找外層過程編號的名字，…，等等.按"棧"式思想組織符號表。查找時，從后往前查找，碰到的第一個名字就是所需查找的名字.名字作用域分析（嵌套結(jié)構(gòu)語言）編輯ppt對每個過程指定一個唯一的編號（層次），即過程的順序號，以便跟蹤過程里的局部名字。在符號表中，表示局部名字用一個二元組：<名字,過程編號>對一個名字查找符號表的原則:只有當表項中的名字的字符逐個匹配,并且該記錄相關的編號和當前所處理的過程的編號匹配時,才能確定查找成功.引入"過程編號"屬性編輯ppt（1）將符號表設計為棧符號表，新名字出現(xiàn)總是從棧頂填入。為了保證從內(nèi)層向外層查，查找操作從符號表的棧頂往底部查找。（2）過程的嵌套層次表（display），是引入的一個顯示層次關系表。其作用是為了描述過程的嵌套層次，指出當前正在活動著的各嵌套的過程（或函數(shù)）相應的子符號表在棧符號表中的起始位置（相對地址）。Display表也是一個棧，棧頂為level，用來指示層次，即指向當前的最內(nèi)層過程的子符號表在棧符號表中的起始位置。（3）在符號表的信息欄中引入一個指針域（previous)，用來鏈接它在同一個過程內(nèi)的下一名字在表中的下標（相對位置）。每一層最后一個域名字，指針域之值為0。這樣每當需要查找個新名字時，就能通過display表找出當前正在處理的最內(nèi)層的過程及所有外層的子符號表在棧符號表中的位置。然后通過指針域可以找到同一個過程內(nèi)的所有被說明的名字。按"棧"式思想組織符號表編輯ppt

例：procedure…//B1vara,b:real;procedure…//B2varc,d:real;procedure…//B3vare,f:real;begin…end;begin…end;begin…end;編輯ppt

…

…

…

…

…

…

…

…

PreviousInformationName1110987654321棧符號表DISPLAYabtopsp1levellevel20B2cdtopsp4level3050B3eftopsp7level6080procedure…//B1vara,b:real;procedure…//B2varc