第六章符号表组织bfqw

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,内容提要:,第 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】有类型说明:,TYPE arr = ARRAY 1.10 OF ARRAY 1.5 OF INTEGER;,试填写符号表。,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,TYPE rec = RECORD,u: INTEGER;,v: ARRAY 1.10 OF BOOLEAN;,r: RECORD x, y : REAL END,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个单元。,?,PROCEDURE P1(VAR x: 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,指向（已占用）栈顶单元，即活动记录的最后一个单元。,6.5.3,简单的栈式存储分配,没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。,以C语言为例:,1C语言程序的存储组织,【例6.5】,C语言过程调用关系：,Main( ),Q( ),R( ),则，活动记录栈状态为：,TOP,SP,2C的活动记录,Old SP,值，即前一活动记录的地址；,其中：,SP,TOP,6.5.4,嵌套过程语言的栈式存储分配,过程嵌套的一个关键问题：,标识符的作用域问题,。,标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间。,标识符的有效范围：,（1）在外层未定义，而在内层定义的，服从内层定义；,（2）在外层已定义，而在内层未定义的，服从全范围；,（3）在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义。,服从最小作用域原理,；,1.标识符的作用域,2.活动记录,6.5.4,嵌套过程语言的栈式存储分配（续）,问题的提出：,过程,Q,可能会引用到它的,任意外层过程,的最新活动记录中的某些数据。,为了在活动记录中查找这些非局部名字所对应的存储空间，过程,Q,运行时必须设法跟踪它的,所有外层过程,的最新活动记录的地址。,解决问题的思想：,解决方案：,活动记录中增加,静态链,！使其,指向直接外层,的,最新活动记录的首地址,；,SP,TOP,连接数据,3.嵌套层次显示表(display)和活动记录结构,(1)连接数据区：,用于访问外层的变量,Old SP,返回地址,全局Display地址,参数个数,形式单元,显示区表,(Display),局部变量,内情向量,临时单元,SP,TOP,0,1,2,02,；,连接数据,全局display地址 主调过程的显示区表首址；,老SP 主调过程的活动记录首址；,(2)参数个数：,3,；,3,(3)形参值单元区：,4,入口为4,；,换名形参（vn）,分配2个单元（地址传递）；,赋值形参（vf） 按相应类型长度分配；,l为层次号，包含,直接外层,嵌套的l个过程的活动记录的首址，再加上本过程的活动记录首址；,(4)显示区表(display)：,占l+1个单元,；,l+1,类型标识符、常量标识符等不分配值单元；,(5)局部变量区：,入口为off + l + 2,；,off为形参区最后一个值单元地址；,局部变量值单元按相应类型长度分配地址；,编译系统定义的变量，按局部变量值单元分配原则分配地址；,(6)临时变量区：,4. Display表的建立,则Q与R的display表的关系如下:,设过程调用关系为,Q( ),R( ),，且,R( ),的层次号为,l,，,Old SP,返回地址,全局Display地址,参数个数,形式单元,显示区表,(Display),局部变量,内情向量,临时单元,SP,TOP,Old SP,返回地址,全局Display地址,参数个数,形式单元,显示区表,(Display),局部变量,内情向量,临时单元,Q的活动记录,R的活动记录,拷贝l个单元,拷贝自身的SP,l+1个单元,5.,值单元的地址分配,值单元分配是依据活动记录的结构，在符号表中进行的。,设有Pascal程序片段如下，P1所在层level=2；,【例6.6】,PROCEDURE P1( x: REAL; VAR y: BOOLEAN );,CONST pai=3.14;,TYPE arr=ARRAY 1.10 OF INTEGER;,VAR m: INTEGER;,a: arr;,l: REAL;,FUNCTION F1( z: REAL; k: INTEGER ): REAL;,BEGIN END;,;,BEGIN,;,END;,试给出符号表组织及值单元分配情况。,设：,(1),实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,(2),换名形参vn分配2个单元，赋值形参vf按相应类型长度分配；,接上页：,SYNBL,TYPEL,PFINFL,P1的VALL,CONSL,LENL,AINFL,过程P1定义的层次为l=3,0,1,2,3,4-11,12-13,14,15,16,17,18-21,22-61,P1,p,3,3,2,Entry,x,x,2,r,tp,v,f,(3,4),x,r,tp,v,f,(3,4),(3,12),y,y,b,tp,b,tp,v,n,v,n,y,(3,12),(4,4),pai,r,tp,c,3.14,arr,a,1,10,i,tp,4,t,40,m,i,tp,v,m,(3,18),a,v,a,(3,22),l,r,tp,v,l,62-69,(3,62),F1,r,tp,f,4,3,2,Entry,z,z,k,k,r,tp,r,tp,i,tp,i,tp,v,f,v,f,v,f,v,f,(4,4),(4,12),(4,12),程序片段, 一个函数过程的符号表组织,FUNCTION exp(x:REAL;VAR y:INTEGER):REAL;,CONST pai=3.14;,TYPE arr=ARRAY1.5,1.10 OF INTEGER;,VAR a:arr; b:real;,BEGIN ; a2,5:=100; b:=6; END;, exp , rtp , f ,函数表, x , rtp , vf ,活动记录, pai , rtp , c ,常数表, arr , atp , t ,长度表, y , itp , vn ,活动记录, a , atp , v ,活动记录, b , rtp , v ,活动记录,谢谢收看！,再见,