第六章符号表组织

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,内容提要:,第 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),结构：,NEME(名字)标识符源,码,码(或内部码),TYP(类型),指针，指,向,向类型表相应项,；,；,CAT(种类),种类编码,：,：,f/P(函数),，,，c(常量)，t(类型)，d(域名)，,v,vn,vf(变量，换名形,参,参，赋值形参),；,；,ADDR(地址)指针，,根,根据标识符的种类不同，分别指向,：,：PFINFL,CONSL,LENL,VALL,6.3.2,类,类型表(TAPEL),结构：,TVAL(类码)类型代码,：,：,i(整型)，r(实型)，c(字符型)，b(布尔型)，,a(数组型)，d(结构型)，,TPOINT(,指,指针)根,据,据数据类型不同,，,，指向不同的信,息,息表项：,基本数据类,型,型(i,r,c,b)nul(,空,空指针)；,数组类型(a)指向数,组,组表；,结构类型(d)指向结,构,构表;,6.3.3,数,数组表(AINFL),结构：,每维占表中一个,纪,纪录,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,域成分类型(在,类,类型表中的信息);,每个域占表中一,个,个纪录,6.3.5,函,函数表(PFINFL),结构：,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,设：,整,整型,占,占1,个,个存,储,储单,元,元，,【例6.2】,有,有类,型,型说,明,明:,TYPEarr=ARRAY1.10OFARRAY1.5OFINTEGER;,试填,写,写符,号,号表,。,。,SYNBL,TYPEL,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:ARRAY1.10OFBOOLEAN;,r:RECORDx,y:REALEND,END;,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(VARx:REAL;y:INTEGER);,BEGIN,END;,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）连接数,据,据区,返回地址：,动态链：,指向调用该过,程,程的主调程序,的,的活动记录的,指,指针；,静态链：,指向静态直接,外,外层活动记录,的,的指针。,（2）形式单,元,元,用来存放实参,的,的值或地址。,（3）局部数,据,据区,用来存放局部,变,变量、内情向,量,量、临时单元,。,。,（4）栈指针,SP 指向现行,过,过程活动记录,的,的起点，即第,一,一个单元；,TOP指向（已占,用,用）栈顶单元,，,，即活动记录,的,的最后一个单