6章符号表组织

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,内容提要:,第 6 章 符号表组织,-语义分析之一,6.1 符号表的地位和作用,6.2 符号表的组织与管理,6.3 符号表的结构设计,6.4 符号表的构造过程示例,6.5 运行时刻存储分配,6.1 符,号,号表的地位和,功,功能,符号表是标识符的动态语义词典，属于编译中,语,语义分析的知,识,识库；主要内,容,容：,名字 标识符源,码,码，用作查询,关,关键字；,类型-,该,标识符的数据,类,类型及其相关,信,信息；,种类-,该,标识符在源程,序,序中的语义角,色,色；,地址-与值单,元,元相关的一些,信,信息；,定义和重,定,定义检查；,类型匹配,校,校验；,数据的越,界,界和溢出检查,；,；,值单元存,储,储分配信息；,函数、过,程,程的参数传递,与,与校验；,符号表的功能,标识符四种语义信息,6.2 符,号,号表的组织与,管,管理,6.2.1,符,符号表的工,作,作原理,遇定义性标识符(在说明中)-,把,语义信息填入表中，并修,改,改其TOKEN的指针，使,其,其指向相应的,表,表项：,（i,),该,标识符,符号表项,遇应用性标识符(在语句中)-查符号表的相应,项,项，查到后修,改,改其TOKEN的指针，使,其,其指向相应的,表,表项：,6.2.2,符,符号表的查,询,询、访问方式,线性表、顺序表、索引表和散列表，皆可以采用。,（i,),该,标识符,符号表项,6.2.3,符,符号表的维,护,护、管理方式,一个源文件,有,有若干个函数,组,组成，通常，每个函数对应,一,一个符号表，此外，还是,有,有一个公用符号表；,符号表如何,管,管理？往往取,决,决于所属语言,的,的程序结构，,就,就 C语言来,说,说，可以在内,存,存设置一定长,度,度的符号表区，并建立适当,的,的索引机制，访问相应的,符,符号表：,公用,符号表,FUNCTION 2,符号表,FUNCTION 1,符号表,现行,函数符号表,全局,符,符号表区,局部 符,号,号表区,索引机制,FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;,CONST pai=3.14;,TYPE arr=ARRAY1.5,1.10 OF INTEGER;,VAR a:arr;b,a:real;,BEGIN ;a2,5:=100;b:=z+6;END;,6.3 符,号,号表的结构设,计,计,【例6.1】,有,有下列函数过,程,程：,需要进符,号,号表的标识符,：,：,exp(函数,附带信,息,息:类型、参,数,数情况和入口,地,地址),pai(常量),arr(类型),a(下标变量)，b(简单变量),，,，,怎样检查,出,出：a重定义、z无定义以及下,表,表变量,a2,5的值地址在何,处,处？,符号表的,体,体系结构设计,由于标识符的,种,种类不同，导,致,致语义属性也,不,不尽相同；怎,样,样组织符号表,？,？下面提供一,个,个符号表的体系结构：,SYNBL（符号表）,NAME TYPE CAT ADDR,PFINFL(函数表),CONSL(常量表),AINFL(数组表),RINFL(结构表),VALL(活动纪录),LENL(长度表),TYPEL（类型表）,TVAL TPOINT,名字 类型,种,种类 地址,token,i ,6.3.1,符,符号表总表(SYNBL),NAME,TYP,CAT,ADDR,结构：,NEME(名,字,字),标,识符源码(或,内,内部码),TYP(类型),指,针，指向类型,表,表相应项；,CAT(种类),种,类编码：,f(函数)，c(常量)，t(类型)，d(域名)，,v,vn,vf(变量，换,名,名形参，赋值,形,形参)；,ADDR(地,址,址),指,针，根据标识,符,符的种类不同，分别指,向,向：PFINFL,CONSL,LENL,VALL,6.3.2,类,类型表(TAPEL),结构：,TVAL,TPOINT,TVAL(类,码,码),类,型代码：,i(整型)，r(实型)，c(字符型)，b(布尔型)，,a(数组型)，d(结构型)，,TPOINT(指针),根,据数据类型不,同,同，指向不同,的,的信息表项：,基本数据,类,类型(i,r,c,b)nul(空指针)；,数组类型(a),指,向数组表；,结构类型(d),指,向结构表;,6.3.3,数,数组表(AINFL),结构：,LOW,UP,CTP,CLEN,每维占表中一,个,个纪录,LOW(数组,的,的下界)-,（,（C语言自动,设,设为：0）;,UP(数组的,上,上界),CTP(成分,类,类型指针),指,针，指向该维,数,数组成分类型(在类型表中,的,的信息);,CLEN(成,分,分类型的长度),成,分类型的数据,所,所占值单元的个数；,这里假,定,定：值单元个数依字长为单位计算,。,。,6.3.4,结,结构表(RINFL),结构：,每个域占表,中,中一个纪录,ID(结构,的,的域名),OFF(区,距,距)是id,k,的值单元首,址,址相对于所,在,在记录值区,区,区头位置；,约定：off,1,=0，,off,2,=off,1,+LEN(tp,1,),off,n,=off,n-1,+,LEN(tp,n-1,),。,id,n-1,的,长,长,度,度,TP(,域,域,成,成,分,分,类,类,型,型,指,指,针,针),指,针,，,，,指,指,向,向id,k,域,成,成,分,分,类,类,型,型(,在,在,类,类,型,型,表,表,中,中,的,的,信,信,息,息);,ID,OFF,TP,6.3.5,函,函,数,数,表,表(PFINFL),结,结,构,构,：,：,LEVEL,OFF,FN,ENTRY,PARAM,LEVEL(,层,层,次,次,号,号),该,该,过,过,函,函,静,静,态,态,层,层,次,次,嵌,嵌,套,套,号,号,OFF(,区,区,距,距),该,该,过,过,函,函,自,自,身,身,数,数,据,据,区,区,起,起,始,始,单,单,元,元,相,相,对,对,该,该,过,过,函,函,值,值,区,区,区,区,头,头,位,位,置,置,；,；,FN(,参,参,数,数,个,个,数,数),该,过,函,函,的,的,形,形,式,式,参,参,数,数,的,的,个,个,数,数,；,；,PARAM(,参,参,数,数,表,表),指,针,，,，,指,指,向,向,形,形,参,参,表,表,；,；,ENTRY(,入,入,口,口,地,地,址,址),该,函,数,数,目,目,标,标,程,程,序,序,首,首,地,地,址,址(,运,运,行,行,时,时,填,填,写,写),；,；,-过,程,程或函,数,数语,义,义,信,信,息,息,6.3.6,其,其,他,他,表,表(,),常,常,量,量,表,表(CONSL)-,存,存,放,放,相,相,应,应,常,常,量,量,的,的,初,初,值,值,；,；,长,长,度,度,表,表(LENL),存,放,相,相,应,应,数,数,据,据,类,类,型,型,所,所,占,占,值,值,单,单,元,元,个,个,数,数,；,；,活,活,动,动,纪,纪,录,录,表,表(VALL),一,个,函,函,数,数(,或,或,过,过,程,程),虚,虚,拟,拟,的,的,值,值,单,单,元,元,存,存,储,储,分,分,配,配,表,表,；,；,此,此,分,分,配,配,表,表,在,在,运,运,行,行,调,调,用,用,时,时,才,才,可,可,用,用,，,，,故,故,称,称活,动,动,纪,纪,录,录。,结构：,结构：,结,构,构：,6.4符,号,号,表,表,的,的,构,构,造,造,过,过,程,程,示,示,例,例：,ENT,2,?,v3,vn,itp,y,v2,vf,rtp,x,临,时,时,变,变,量,量,值,值,区,区,b,值,值,y,值,值,数,组,组a,值,值,区,区,管,理,理,区,区,exp,值,值,x,值,值,链,接,接,表,表,3.14,50,1,itp,10,1,10,5,1,a,a,c,i,r,b,v1,v2,v3,v4,v5,t,arr,v4,v,a,c,rtp,pai,v5,v,rtp,b,v3,vn,itp,y,v2,vf,rtp,x,f,rtp,exp,SYNBL,PFINFL,VALL,CONSL,LENL,AINFL,TYPEL,【例6.2】,有,有类,型,型说,明,明:,TYPEarr=ARRAY1.10OFARRAY1.5OFINTEGER;,试填,写,写符,号,号表,。,。,SYNBL,TYPEL,i,r,c,b,AINFL,arr,a,1,10,a,1,5,i,tp,设：,实,实型,占,占8,个,个存,储,储单,元,元，,整,整型,占,占4,个,个单,元,元，,布,布尔,型,型和,字,字符,型,型占1个,单,单元,。,。,4,20,t,LENL,200,【例6.3】,有,有类,型,型说,明,明:,试填,写,写符,号,号表,。,。,SYNBL,TYPEL,AINFL,rec,d,1,10,d,b,tp,设：实型占8个存储单,元,元，整型占4个单元，,布,布尔型和字,符,符型占1个,单,单元。,1,t,LENL,TYPErec=RECORD,u:INTEGER;,v:ARRAY 1.10 OFBOOLEAN;,r:RECORDx,y:REAL END,END;,i,r,c,b,RINFL,u,0,i,tp,u,i,tp,d,4,v,4,a,v,d,10,r,14,x,0,r,tp,r,tp,r,r,tp,d,x,d,d,8,y,8,y,r,tp,8,16,30,【例6.4,】,】,试填写符号,表,表。,SYNBL,TYPEL,v,f,?,r,tp,设：实型占8个存储单,元,元，整型占4个单元，,布,布尔型和字,符,符型占1个,单,单元。,?,PROCEDUREP1(VAR x:REAL;y:INTEGER);,BEGIN,END;,i,r,c,b,PFINFL,r,tp,P1,r,tp,p,x,v,n,y,2,y,r,tp,有过程说明:,设P1所在,层,层LEVEL=1，即,所,所定义的层LEVEL=2,1,P1,2,2,?,Entry,x,v,n,?,v,f,?,注：,？该,标,标识符的值,单,单元首址，,为相对地址,（,（LEVEL,offset）,LEVEL,该标,识,识符,所在层次号,，,，,offset 区,距,距，,存储分配时,可,可定,。,6.5,运,运行时刻存,储,储分配,解决的问题,：,：标识符变量的地址分配与对它们的,访,访问。,6.5.1,标识符值单,元,元分配,值单元分配,分,分两类：,在编译阶段即可完成真,实,实的地址分,配,配。在编译,时,时对所有数,据,据对象分配,固,固定的存储,单,单元，且在,运,运行是始终,保,保持不变。,1.静态分,配,配,2.动态分,配,配,指在运行时,刻,刻进行的值,单,单元分配，,在,在编译时只,能,能进行相对,地,地址分配。,栈式动态,分,分配；,堆式动态,分,分配。,值单元分配,是,是以过程函,数,数为单位的,。,。,注：,6.5.2,活动记录,1.三个概,念,念,过程：,一个可执行,模,模块，过程,或,或函数，通,常,常完成特定,的,的功能。,活动：,过函的一次,执,执行。每执,行,行一次过程,体,体，则产生,该,该过函的一,个,个活动。,活动记录：,一个有结构的连续存储,块,块。用来存,储,储过函一次,执,执行中所需,要,要的信息。,如果不支持,可,可变数据结,构,构，活动记,录,录的体积是,可,可以在编译,时,时确定的。,活动记录仅,是,是一种存储映像，编译程序,所,所进行的运,行,行时刻存储,分,分配是在符,号,号表中进行,的,的。,6.5.2,活动记录（,续,续）,2.活动记,录,录的结构,临时单元,内情向量,局部变量,形式单元,静态链,动态链,返回地址,VALL,TOP,SP,连接数据,局部数据,（1）连接,数,数据区,返回地址：,动