第7單元符號表(編譯原理)

內(nèi)容提要:第8章符號表組織----語義分析之二8.1符號表的地位和作用8.2符號表的組織與管理8.3符號表的結(jié)構(gòu)設(shè)計8.4符號表的構(gòu)造過程示例

8.5運行時刻存儲分配合肥師范學院計算機系18.1符號表的地位和功能

符號表是標識符的動態(tài)語義詞典，屬于編譯中語義分析的知識庫；主要內(nèi)容：⑴名字

—

標識符源碼，用作查詢關(guān)鍵字；⑵類型

--該標識符的數(shù)據(jù)類型及其相關(guān)信息；⑶種類

--該標識符在源程序中的語義角色；⑷地址--與值單元相關(guān)的一些信息；①定義和重定義檢查；②類型匹配校驗；③數(shù)據(jù)的越界和溢出檢查；④值單元存儲分配信息；⑤函數(shù)、過程的參數(shù)傳遞與校驗；…

符號表的功能標識符四種語義信息合肥師范學院計算機系28.2符號表的組織與管理8.2.1符號表的工作原理⑴遇定義性標識符(在說明中)---把語義信息填入表中，并修改其TOKEN的指針，使其指向相應(yīng)的表項：（i,)該標識符符號表項⑵遇應(yīng)用性標識符(在語句中)---查符號表的相應(yīng)項，查到后修改其TOKEN的指針，使其指向相應(yīng)的表項：8.2.2符號表的數(shù)據(jù)結(jié)構(gòu)線性表、順序表、索引表和散列表，皆可以采用。（i,)該標識符符號表項合肥師范學院計算機系38.2.3符號表的維護、管理方式※一個源文件有若干個函數(shù)組成，通常，每個函數(shù)對應(yīng)一個符號表，此外，還是有一個公用符號表；※符號表如何管理？往往取決于所屬語言的程序結(jié)構(gòu)，就C語言來說，可以在內(nèi)存設(shè)置一定長度的符號表區(qū)，并建立適當?shù)乃饕龣C制，訪問相應(yīng)的符號表：公用符號表FUNCTION2符號表FUNCTION1符號表…現(xiàn)行函數(shù)符號表全局符號表區(qū)局部符號表區(qū)

…索引機制合肥師范學院計算機系4FUNCTIONexp(x:REAL;VARy:INTEGER):REAL;CONSTpai=3.14;TYPEarr=ARRAY[1..5,1..10]OFINTEGER;VARa:arr;b,a:real;BEGIN…;a[2,5]:=100;b:=z+8;…END;8.3符號表的結(jié)構(gòu)設(shè)計【例8.1】有下列函數(shù)過程：⑴需要進符號表的標識符：exp(函數(shù),附帶信息:類型、參數(shù)情況和入口地址…),pai(常量),arr(類型),a(下標變量)，b(簡單變量)，…⑵怎樣檢查出：a

重定義、z

無定義以及下表變量a[2,5]的值地址在何處？…合肥師范學院計算機系5※符號表的體系結(jié)構(gòu)設(shè)計

由于標識符的種類不同，導致語義屬性也不盡相同；怎樣組織符號表？下面提供一個符號表的體系結(jié)構(gòu)：SYNBL（符號表）

NAMETYPECATADDR

…PFINFL(函數(shù)表)CONSL(常量表)AINFL(數(shù)組表)RINFL(結(jié)構(gòu)表)VALL(活動紀錄)LENL(長度表)TYPEL（類型表）

TVALTPOINT·…名字類型種類地址tokeni·合肥師范學院計算機系68.3.1符號表總表(SYNBL)NAMETYPCATADDR※結(jié)構(gòu)：NEME(名字)—

標識符源碼(或內(nèi)部碼)TYP(類型)–

指針，指向類型表相應(yīng)項；CAT(種類)–

種類編碼：

f(函數(shù))，c(常量)，t(類型)，d(域名)，

v,vn,vf(變量，換名形參，賦值形參)；ADDR(地址)–

指針，根據(jù)標識符的種類不同，分別指向：PFINFL,CONSL,LENL,VALL,…合肥師范學院計算機系78.3.2類型表(TAPEL)※結(jié)構(gòu)：TVALTPOINTTVAL(類碼)–

類型代碼：

i(整型)，r(實型)，c(字符型)，b(布爾型)，

a(數(shù)組型)，d(結(jié)構(gòu)型)，…TPOINT(指針)–

根據(jù)數(shù)據(jù)類型不同，指向不同的信息表項：①基本數(shù)據(jù)類型(i,r,c,b)–nul(空指針)；②數(shù)組類型(a)–

指向數(shù)組表；③結(jié)構(gòu)類型(d)–

指向結(jié)構(gòu)表;…

合肥師范學院計算機系88.3.3數(shù)組表(AINFL)

※結(jié)構(gòu)：LOWUPCTPCLEN每維占表中一個紀錄LOW(數(shù)組的下界)--（C語言自動設(shè)為：0）;UP(數(shù)組的上界)—CTP(成分類型指針)–

指針，指向該維數(shù)組成分類型(在類型表中的信息);CLEN(成分類型的長度)–

成分類型的數(shù)據(jù)所占值單元的個數(shù)；

※這里假定：值單元個數(shù)依字長為單位計算。合肥師范學院計算機系98.3.4結(jié)構(gòu)表(RINFL)

※結(jié)構(gòu)：每個域占表中一個紀錄ID(結(jié)構(gòu)的域名)—OFF(區(qū)距)—是idk的值單元首址相對于所在記錄值區(qū)區(qū)頭位置；約定：off1=0，

off2=off1+LEN(tp1),……offn=offn-1+LEN(tpn-1)。

idn-1的長度

TP(域成分類型指針)–

指針，指向idk域成分類型(在類型表中的信息);

ID

OFF

TP合肥師范學院計算機系108.3.5函數(shù)表(PFINFL)※結(jié)構(gòu)：LEVELOFFFNENTRYPARAM…LEVEL(層次號)–該過函靜態(tài)層次嵌套號,OFF(區(qū)距)–該過函自身數(shù)據(jù)區(qū)起始單元相對該過函值區(qū)區(qū)頭位置；

FN(參數(shù)個數(shù))–

該過函的形式參數(shù)的個數(shù)；

PARAM(參數(shù)表)–

指針，指向形參表；

ENTRY(入口地址)–

該函數(shù)目標程序首地址(運行時填寫)；----

過程或函數(shù)語義信息合肥師范學院計算機系118.3.8其他表(…)

⑴常量表(CONSL)--存放相應(yīng)常量的初值；⑵長度表(LENL)–

存放相應(yīng)數(shù)據(jù)類型所占值單元個數(shù)；⑶活動紀錄表(VALL)–

一個函數(shù)(或過程)虛擬的值單元存儲分配表；此分配表在運行調(diào)用時才可用，故稱活動紀錄?！Y(jié)構(gòu)：※結(jié)構(gòu)：

…合肥師范學院計算機系128.4符號表的構(gòu)造過程示例：ENT…2?v3vnitpyv2vfrtpx臨時變量值區(qū)b值y值

數(shù)組a值區(qū)

管理區(qū)exp值x值

鏈接表3.14501itp1011051aac,i,r,bv1v2v3v4v5t

arrv4vacrtppaiv5vrtpbv3vnitpyv2vfrtpxfrtpexpSYNBLPFINFLVALLCONSLLENLAINFLTYPEL合肥師范學院計算機系13【例8.2】有類型說明:

TYPEarr=ARRAY[1..10]OFARRAY[1..5]OFINTEGER;

試填寫符號表。

SYNBLTYPEL

i

r

c

bAINFLarra110a15itp設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。

420tLENL200合肥師范學院計算機系14【例8.3】有類型說明:試填寫符號表。

SYNBLTYPELAINFLrecd110dbtp設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。

1tLENLTYPErec=RECORDu:INTEGER;v:ARRAY[1..10]OFBOOLEAN;r:RECORDx,y:REALENDEND;i,r,c,bRINFLu0itpuitpd4v4avd10r14x0rtprtprrtpdxdd8y8yrtp81630合肥師范學院計算機系15【例8.4】試填寫符號表。

SYNBLTYPELvf?rtp設(shè)：實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。

?PROCEDUREP1(VARx:REAL;y:INTEGER);……BEGIN……END;ircbPFINFLrtpP1rtppxvny2yrtp有過程說明:設(shè)P1所在層LEVEL=1，即所定義的層LEVEL=2,1P122?Entryxvn?vf?注：

？——

該標識符的值單元首址，為相對地址（LEVEL,offset）

LEVEL——該標識符所在層次號，

offset——區(qū)距，存儲分配時可定。合肥師范學院計算機系168.5運行時刻存儲分配※解決的問題：標識符變量的地址分配與對它們的訪問。8.5.1標識符值單元分配

值單元分配分兩類：

在編譯階段即可完成真實的地址分配。在編譯時對所有數(shù)據(jù)對象分配固定的存儲單元，且在運行是始終保持不變。1.靜態(tài)分配2.動態(tài)分配

指在運行時刻進行的值單元分配，在編譯時只能進行相對地址分配。

·棧式動態(tài)分配；

·堆式動態(tài)分配。

值單元分配是以過程函數(shù)為單位的。

注：合肥師范學院計算機系178.5.2活動記錄

1.三個概念過程：一個可執(zhí)行模塊，過程或函數(shù)，通常完成特定的功能。活動：過函的一次執(zhí)行。每執(zhí)行一次過程體，則產(chǎn)生該過函的一個活動?；顒佑涗洠阂粋€有結(jié)構(gòu)的連續(xù)存儲塊。用來存儲過函一次執(zhí)行中所需要的信息。

如果不支持可變數(shù)據(jù)結(jié)構(gòu)，活動記錄的體積是可以在編譯時確定的。

活動記錄僅是一種存儲映像，編譯程序所進行的運行時刻存儲分配是在符號表中進行的。

合肥師范學院計算機系188.5.2活動記錄（續(xù)）

2.活動記錄的結(jié)構(gòu)

臨時單元

內(nèi)情向量

局部變量

形式單元

靜態(tài)鏈

動態(tài)鏈

返回地址VALLTOPSP連接數(shù)據(jù)局部數(shù)據(jù)（1）連接數(shù)據(jù)區(qū)·返回地址：

·動態(tài)鏈：

指向調(diào)用該過程的主調(diào)程序的活動記錄的指針；

·靜態(tài)鏈：

指向靜態(tài)直接外層活動記錄的指針。

（2）形式單元用來存放實參的值或地址。

（3）局部數(shù)據(jù)區(qū)

用來存放局部變量、內(nèi)情向量、臨時單元。（4）棧指針SP

—

指向現(xiàn)行過程活動記錄的起點，即第一個單元；

TOP

—指向（已占用）棧頂單元，即活動記錄的最后一個單元。

合肥師范學院計算機系198.5.3簡單的棧式存儲分配

沒有分程序結(jié)構(gòu)，過程定義不允許嵌套，但允許過程的遞歸調(diào)用。·以C語言為例:1．C語言程序的存儲組織

【例8.5】C語言過程調(diào)用關(guān)系：Main()Q()R()

則，活動記錄棧狀態(tài)為：R的活動記錄Q的活動記錄Main的活動記錄

全局數(shù)據(jù)區(qū)TOPSP2．C的活動記錄

臨時單元

內(nèi)情向量

局部變量

形式單元

參數(shù)個數(shù)

返回地址OldSPOldSP值，即前一活動記錄的地址；

其中：SPTOP合肥師范學院計算機系208.5.3簡單的棧式存儲分配（續(xù)）

3．C語言的過程調(diào)用與返回（1）過程調(diào)用①過程調(diào)用的四元式序列：(param,entry(t1),_,_)

……(param,entry(tn),_,_)(call,entry(P),n,_)②

對應(yīng)的目標指令：(i+3)[TOP]:=entry(ti).Addr

//將ti地址填到活動記錄的形參區(qū)去

·(param,entry(ti),_,_)對應(yīng)的指令：·(call,entry(P),n,

_)對應(yīng)的指令：1[TOP]:=SP//保護現(xiàn)行SP3[TOP]:=n//傳遞參數(shù)個數(shù)JSPP第n個實參地址

過程P的入口地址

參數(shù)個數(shù)

……SPTOP主調(diào)過程活動記錄子過程P的活動記錄OldSP返回地址參數(shù)個數(shù)形參區(qū)t1………

……

…

t1

……主調(diào)過程活動記錄SPTOP子過程P的活動記錄SPn③子過程P需完成的工作：定義自己的活動記錄；

SP:=TOP+1//定義過程P的SP1[SP]:=返回地址//保護返回地址TOP:=TOP+L//定義新TOPLSPSP返回地址TOPSPTOP合肥師范學院計算機系218.5.3簡單的棧式存儲分配（續(xù)）

3．C語言的過程調(diào)用與返回（2）過程返回①過程返回的四元式：(ret,_,_,_)

②

對應(yīng)的目標指令：TOP:=SP-1//恢復(fù)TOPSP:=0[SP]//恢復(fù)SPX:=2[TOP]//取返回地址，X為某一變址器UJ0[X]//按X中的返回地址實行變址轉(zhuǎn)移

……

…

t1nSP

……主調(diào)過程活動記錄子過程P的活動記錄LSPTOPTOPTOPSPSPX返回地址返回地址X合肥師范學院計算機系228.5.4嵌套過程語言的棧式存儲分配

·過程嵌套的一個關(guān)鍵問題：標識符的作用域問題

。

標識符的作用范圍往往與它所處的過程相關(guān)，也就是說，同一個標識符，在不同的程序段里，代表不同的對象，具有不同的性質(zhì)，因此要分配不同的存儲空間。

·標識符的有效范圍：（1）在外層未定義，而在內(nèi)層定義的，服從內(nèi)層定義；（2）在外層已定義，而在內(nèi)層未定義的，服從全范圍；（3）在外層已定義，而在內(nèi)層也定義的，在外層服從外層定義，在內(nèi)層服從內(nèi)層定義。服從最小作用域原理；1.標識符的作用域合肥師范學院計算機系232.活動記錄8.5.4嵌套過程語言的棧式存儲分配（續(xù)）

·問題的提出：

過程Q可能會引用到它的任意外層過程的最新活動記錄中的某些數(shù)據(jù)。

為了在活動記錄中查找這些非局部名字所對應(yīng)的存儲空間，過程Q運行時必須設(shè)法跟蹤它的所有外層過程的最新活動記錄的地址?！そ鉀Q問題的思想：·解決方案：

活動記錄中增加靜態(tài)鏈！使其指向直接外層的最新活動記錄的首地址；

臨時單元

內(nèi)情向量

局部變量

形式單元

參數(shù)個數(shù)

靜態(tài)鏈

返回地址OldSPSPTOP連接數(shù)據(jù)合肥師范學院計算機系243.嵌套層次顯示表(display)和活動記錄結(jié)構(gòu)(1)連接數(shù)據(jù)區(qū)：用于訪問外層的變量

OldSP返回地址全局Display地址參數(shù)個數(shù)……形式單元

……顯示區(qū)表(Display)……局部變量……內(nèi)情向量……臨時單元SPTOP0120～2；連接數(shù)據(jù)

·全局display地址—

主調(diào)過程的顯示區(qū)表首址；·老SP—

主調(diào)過程的活動記錄首址；(2)參數(shù)個數(shù)：3；3(3)形參值單元區(qū)：4入口為4；·換名形參（vn）—

分配2個單元（地址傳遞）；·賦值形參（vf）—

按相應(yīng)類型長度分配；

l為層次號，包含直接外層嵌套的l個過程的活動記錄的首址，再加上本過程的活動記錄首址；(4)顯示區(qū)表(display)：占l+1個單元；l+1·類型標識符、常量標識符等不分配值單元；(5)局部變量區(qū)：入口為off+l+2；·off為形參區(qū)最后一個值單元地址；·局部變量值單元按相應(yīng)類型長度分配地址；編譯系統(tǒng)定義的變量，按局部變量值單元分配原則分配地址；(8)臨時變量區(qū)：合肥師范學院計算機系254.Display表的建立則Q與R的display表的關(guān)系如下:

設(shè)過程調(diào)用關(guān)系為Q()

R()，且R()的層次號為l，OldSP返回地址全局Display地址參數(shù)個數(shù)……形式單元

……顯示區(qū)表(Display)……局部變量……內(nèi)情向量……臨時單元SPTOPOldSP返回地址全局Display地址參數(shù)個數(shù)……形式單元

……顯示區(qū)表(Display)……局部變量……內(nèi)情向量……臨時單元Q的活動記錄

R的活動記錄

拷貝l個單元

拷貝自身的SPl+1個單元合肥師范學院計算機系26【例8.8】0programP;vara,x:integer;

1procedureQ(b:integer);vari:integer;

2procedureR(u:integer;varv:integer);varc,d:integer;beginifu=1thenu=u+1;u,v

……

c,dv:=(a+c)+(b-d);

……

b,iend{R}begin

……R(1,x);

……

a,xend{Q}

1procedureS;varc,i:integer;begina:=1;c,iQ(c);

……end{S}begina:=0;S;

……end.層次：設(shè)有Pascal程序片段如下：變量作用域：過程調(diào)用關(guān)系為：PSQR

合肥師范學院計算機系27試給出程序運行時的活動記錄關(guān)系?！纠?.8】局部變量Display表參數(shù)個數(shù)全局Display返回地址OldSPP的活動記錄(0層)0001230405-8a9-12x局部變量Display表參數(shù)個數(shù)全局Display返回地址OldSP局部變量Display表形式單元參數(shù)個數(shù)全局Display返回地址OldSP局部變量Display表形式單元參數(shù)個數(shù)全局Display返回地址OldSPS的活動記錄(1層)040013ci13141518171819-2223-26Q的活動記錄(1層)1317272829130b31-340353627i37-40R的活動記錄(2層)2741423543244u45-48v49-5002741515253cd54-5758-61R活動記錄Q活動記錄S活動記錄P活動記錄活動記錄棧a-(0,5)x-(0,9)c-(1,6)i-(1,10)b-(1,4)i-(1,10)u-(2,4)v-(2,8)c-(2,15)d-(2,19)合肥師范學院計算機系285.值單元的地址分配

·值單元分配是依據(jù)活動記錄的結(jié)構(gòu)，在符號表中進行的。

設(shè)有Pascal程序片段如下，P1所在層level=2；【例8.7】PROCEDUREP1(x:REAL;VARy:BOOLEAN);CONSTpai=3.14;TYPEarr=ARRAY[1..10]OFINTEGER;VARm:INTEGER;a:arr;l:REAL;FUNCTIONF1(z:REAL;k:INTEGER):REAL;BEGIN……END;

……;BEGIN

……;END;試給出符號表組織及值單元分配情況。

設(shè)：(1)實型占8個存儲單元，整型占4個單元，布爾型和字符型占1個單元。

(2)換名形參vn分配2個單元，賦值形參vf按相應(yīng)類型長度分配；合肥師范學院計算機系29接上頁：SYNBLi,r,c,bTYPELPFINFLP1的VALLCONSLLENLAINFL局部變量Display表形式單元參數(shù)個數(shù)全局Display返回地址OldSP·過程P1定義的層次為l=301234-1112-131415161718-2122-61P1p332Entryxx2rtpvf(3,4)xrtpvf(3,4)(3,12)yybtpbtpvnvny(3,12)(4,4)pairtpc3.14arra110itp4t40mitpvm(3,18)ava(3,22)lrtpvl62-69(3,62)F1rtpp432Entryzzkkrtprtpitpitpvfvfvfvf(4,4)(4,12)(4,12)合肥師范學院計算機系30※習題：【習題8.1】解釋下述詞語：⑴符號表；⑵標識符的語義信息；⑶符號表的功能；（4）c語言符號表的管理方式?！玖曨}8.2】設(shè)有程序片斷如下，試填寫符號表：

floatexe(x,y)intx,y[5][10];{floata;intb[5][10];

…b[2,5]=15;…}

※如何確定下表變量b[2][5]的地址？合肥師范學院計算機系31Z->S1(0)S->a2A3(1)|b4B5(2)A->06A7(3)|18(4)B->09B10(5)|111(6)第5章習題解答【習題5.10】

：【習題5.10】P100_4.10考慮文法：G(S)S->aA|bB;A->0A|1;B->0B|1⑴構(gòu)造活前綴的DFA(即句柄識別器)【解】※擴展文法，編碼：①②③⑥⑦⑧⑨⑩0+SaA0OKr(1)r(3)r(4)r(2)bA1B0④0Br(5)r(6)111011※活前綴的DFA(即句柄識別器):∵句柄識別器(DFA)中無沖突狀態(tài)！∴G(S)是LR(0)文法!⑵是LR(0)文法嗎？⑤合肥師范學院計算機系32第5章習題解答【習題5.10】

：B1011109

9r(5)r(5)r(5