編譯原理：第八章 符號表

編譯原理第八章符號表第八章符號表符號表的作用:一致性檢查和作用域分析;輔助代碼生成.8.1符號表的組織與作用符號表的每一項(入口)包含兩大欄:名字欄，也稱主欄，關(guān)鍵字欄信息欄，記錄相應(yīng)的不同屬性，分為若干子欄.對符號表的操作:填入名稱查找名字訪問信息填寫修改信息刪除對符號表進行操作的時機：定義性出現(xiàn)使用性出現(xiàn)按名字的不同種屬建立多張符號表，如常數(shù)表、變量名表、過程名表、…符號的組織方式:1.安排各項各欄的存儲單元為固定長度2.用間接方式安排各欄存儲單元符號表的存放次序:1.把每一項置于連續(xù)K存儲單元中，構(gòu)成一張K*N的表2.把整個符號表分成m個子表，如T1,T2,…Tm，每個子表含有N項.例:PASCAL程序段：PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1; M:=N+4; N:=K;END.8.2整理和查找1.線性查找按關(guān)鍵字出現(xiàn)的順序填寫各項。填表快，查找慢。結(jié)構(gòu)簡單，節(jié)省空間，效率低，查找時間復(fù)雜度：O(n)。改進：自適應(yīng)線性表2.二分查找表格中的項按名字的“大小”順序整理排列。填表慢,查找快。查找時間復(fù)雜度:O(Log2n)改進：組織成二叉樹。3.雜湊查找(HASH技術(shù))雜湊函數(shù)H(SYM)：0~N-1N：符號表的項數(shù)。要求：1.計算簡單高效2.函數(shù)值分布均勻填表快，查找快8.4符號表的內(nèi)容符號表的信息欄中登記了每個名字的有關(guān)性質(zhì)類型：整、實或布爾等種屬：簡單變量、數(shù)組、過程等大?。洪L度，即所需的存儲單元字?jǐn)?shù)相對數(shù)：指分配給該名字的存儲單元的相對地址PL語言編譯程序的符號表1.表格的定義名字表(nametab)程序體表(btab)層次顯示表(display)數(shù)組信息表(atab)中間代碼表(code)國防科技大學(xué)計算機系602教研室1)名字表(nametab)名字表nametab：登記程序中出現(xiàn)的各種名字及其屬性名字標(biāo)識符名字種類，可以是常量(constant)、變量(variable)、類型(type)、過程(procedure)名字所在的程序體的靜態(tài)層次。規(guī)定主程序的層次為1，主程序中定義的層次為2，依次類推名字的類型，類型有整型(ints)、字符型(chars)、布爾型(bool)、數(shù)組(arrays)，對于無類型的名字填入notype一個布爾量，用于標(biāo)明名字是否為變量形參名，當(dāng)名字是否為變量形參名時填入false，其他情況填入true或不填當(dāng)名字為數(shù)組類型或數(shù)組變量名時，ref指向該數(shù)組在數(shù)組信息表中的位置；當(dāng)名字為過程名時，ref指向該過程在程序體表(btab)中的位置；其他情況ref為0adr,當(dāng)名字為變量名時(包括形參，存入該變量(或形參)在相應(yīng)活動記錄中分類的存貯單元的相對地址；對于過程名，填入他們相應(yīng)代碼的入口地址val,當(dāng)名字為變量名時，填入他們的相應(yīng)值size,當(dāng)名字為類型名時，填入該類型數(shù)據(jù)所需存貯單元的數(shù)目指向同一程序體中定義的上一個名字在nametab中的位置，每個程序體在nametab中登記的第一個名字的link為0國防科技大學(xué)計算機系602教研室(2)程序體表btab和層次顯示表display程序體表btab：記錄個程序體的總信息，用于對源程序中定義的名字的作用域進行分析；對名字表進行管理指向本程序體中最后一個形式參在nametab中的位置指向本程序體中最后一個名字在nametab中的位置本程序體所有形參所需體積、包括連接數(shù)據(jù)所占空間本程序體所有局部數(shù)據(jù)所需空間大小層次顯示表display：描述正在處理的各嵌套層，對程序體表進行管理btab(3)數(shù)組信息表atab數(shù)組的下標(biāo)類型數(shù)組元素類型當(dāng)元素為數(shù)組時，它指向該元素數(shù)組信息在atab表中的位置，其他情況為0數(shù)組下限數(shù)組上限數(shù)組元素的體積數(shù)組本身的體積typea=array[1..10,1..10]ofinteger;nametabatab(4)中間代碼表codecode：用于存放編譯程序所產(chǎn)生的每條中間代碼。8.3名字的作用范圍在許多程序語言中,名字都有一個確定的作用范圍.兩種程序體結(jié)構(gòu):并列結(jié)構(gòu)，如FORTRAN嵌套結(jié)構(gòu)，如PASCAL，ADAPROGRAMMAIN…integerX，YCOMMON/C/A，B…ENDSUBROUTINESUB1…realX，ZCOMMON/C/A1，B1…ENDprogramP;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.1.

FORTRAN的符號表組織一個FORTRAN程序由一個主程序段和若干個輔程序段組成.把局部名和全局名分別存在不同的地方.2.嵌套結(jié)構(gòu)語言的符號表組織如PASCAL、ALGOL、ADA作用域遵循"最近嵌套原則".PASCALPASCAL程序本身可以看成是一個操作系統(tǒng)所調(diào)用的過程，過程可以嵌套和遞歸。一個PASCAL過程：過程頭；說明段（由一系列的說明語句組成）；begin執(zhí)行體（由一系列的執(zhí)行語句組成）；end作用域：一個名字能被使用的區(qū)域范圍稱作這個名字的作用域。允許同一個標(biāo)識符在不同的過程中代表不同的名字。名字作用域規(guī)則--"最近嵌套原則"一個在子程序B1中說明的名字X只在B1中有效（局部于B1）；如果B2是B1的一個內(nèi)層子程序且B2中對標(biāo)識符X沒有新的說明，則原來的名字X在B2中仍然有效。如果B2對X重新作了說明，那么，B2對X的任何引用都是指重新說明過的這個X。programmainvarA,B:real;

…

procedureP1varB:boolean;

…

begin

…end

procedureP2varA:integer;

…begin

…endbegin

…endA(real)B(real)B(bool)A(integr)兩種做法:引入"過程編號"屬性。查找時，先查找本過程編號的名字，查不到則查找外層過程編號的名字，…，等等.按"棧"式思想組織符號表。查找時，從后往前查找，碰到的第一個名字就是所需查找的名字.PL語言的中間代碼指令格式：opcodlaopcod：操作碼l：第一操作數(shù)，程序體層數(shù)a：第一操作數(shù)，相對地址編譯是如何確定變量的層數(shù)(地址)？運行是如何根據(jù)指令中變量的層數(shù)和相對地址確定變量的存儲單元？programP;vara,b:integer;

procedureP1(i1,j1:integer);varc,d:integer…end;

procedureP2(i2,j2:integer);vara,c:integer;

procedureP21;varb1,b2:boolean;…end;…end;…gramP;vara,b:integer;

procedureP1(i1,j1:integer);varc,d:integer…end;

procedureP2(i2,j2:integer);vara,c:integer;

procedureP21;varb1,b2:boolean;…end;…end;…gramP;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.functionposition(id:alfa):integer;vari,j:integer;beginnametab[0].name:=id;j:=level;

repeati:=btab[display[j]].last;whilenametab[i].name<>iddoi:=nametab[i].li