《{企业组织设计}符号表组织符号表组织语义分析之一》由会员分享，可在线阅读，更多相关《{企业组织设计}符号表组织符号表组织语义分析之一（36页珍藏版）》请在金锄头文库上搜索。
1、,内容提要:,第 6 章 符号表组织,- 语义分析之一,6.1 符号表的地位和作用 6.2 符号表的组织与管理 6.3 符号表的结构设计 6.4 符号表的构造过程示例 6.5 运行时刻存储分配,6.1 符号表的地位和功能,符号表是标识符的动态语义词典，属于编译中语义分析的知识库；主要内容：, 名字 标识符源码，用作查询关键字； 类型 - 该标识符的数据类型及其相关信息； 种类 - 该标识符在源程序中的语义角色； 地址 - 与值单元相关的一些信息；, 定义和重定义检查； 类型匹配校验； 数据的越界和溢出检查； 值单元存储分配信息； 函数、过程的参数传递与校验；,符号表的功能,标识符四种语义信息,
2、6.2 符号表的组织与管理,6.2.1 符号表的工作原理, 遇 定义性标识符(在说明中)- 把语义信息填入表中，并修改其TOKEN的指针，使其指向相应的表项：, 遇 应用性标识符(在语句中)- 查符号表的相应项，查到后修改其TOKEN的指针，使其指向相应的表项：,6.2.2 符号表的查询、访问方式,6.2.3 符号表的维护、管理方式,一个源文件有若干个函数组成，通常，每个函数对应一个符号表，此外，还是有一个公用符号表；,符号表如何管理？往往取决于所属语言的程序结构，就 C语言来说，可以在内存设置一定长度的符号表区，并建立适当的索引机制，访问相应的符号表：,全局 符号表区,局部 符号表区,索引机
3、制,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的值地址在何处？, 符号表的体系结构设计,由于标
4、识符的种类不同，导致语义属性也不尽相同；怎样组织符号表？下面提供一个符号表的体系结构：,SYNBL（符号表） NAME TYPE CAT ADDR ,PFINFL(函数表),CONSL(常量表),AINFL(数组表),RINFL(结构表),VALL(活动纪录),LENL(长度表),TYPEL（类型表） TVAL TPOINT,名字 类型 种类 地址,token i ,6.3.1 符号表总表(SYNBL), 结构：,NEME(名字) 标识符源码(或内部码) TYP(类型) 指针，指向类型表相应项； CAT(种类) 种类编码： f(函数)，c(常量)，t(类型)，d(域名)， v,vn,vf(变量
5、，换名形参，赋值形参)； 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(
6、成分类型指针) 指针，指向该维数组成分类型(在类型表中的信息); CLEN(成分类型的长度) 成分类型的数据所占值单元的个数； 这里假定：值单元个数依字长为单位计算。,6.3.4 结构表(RINFL), 结构：,每个域占表中一个纪录,ID(结构的域名) OFF(区距)是idk的值单元首址相对于所在记录值区区头位置； 约定：off1=0， off2= off1+LEN(tp1), offn= offn-1+LEN(tpn-1)。 idn-1的长度 TP(域成分类型指针) 指针，指向idk域成分类型(在类型表中的信息);,6.3.5 函数表(PFINFL), 结构：,LEVEL(层次号) 该过函静
7、态层次嵌套号, OFF(区距) 该过函自身数据区起始单元相对该过函值区区头位置 ； FN(参数个数) 该过函的形式参数的个数； PARAM(参数表) 指针，指向形参表； ENTRY(入口地址) 该函数目标程序首地址(运行时填写)；,- 过程或函数语义信息,6.3.6 其他表(), 常量表(CONSL)- 存放相应常量的初值；, 长度表(LENL) 存放相应数据类型所占值单元个数；, 活动纪录表(VALL) 一个函数(或过程)虚拟的值单元存储分配表；此分配表在运行调用时才可用，故称活动纪录。, 结构：,6.4 符号表的构造过程示例：,ENT,2,?,v3,vn,itp,y,v2,vf,rtp,x
8、,临时变量值区,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】有类型说明: TYPE arr = ARRAY 1.10 OF ARRAY 1.5 OF INTEGER;,试填写符号表。,SYNBL,TYPEL,AINFL,arr,a,1,10,a,1,5
9、,itp,设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,4,20,t,LENL,200,【例6.3】有类型说明:,试填写符号表。,SYNBL,TYPEL,AINFL,rec,d,1,10,d,btp,设：实型占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,itp,u,itp,d,4,v,4,a,v,d,10,r,14,x,0,rtp,rtp,r,rtp
10、,d,x,d,d,8,y,8,y,rtp,8,16,30,【例6.4】,试填写符号表。,SYNBL,TYPEL,vf,?,rtp,设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,?,PROCEDURE P1(VAR x: REAL; y: INTEGER); BEGIN END;,PFINFL,rtp,P1,rtp,p,x,vn,y,2,y,rtp,有过程说明:,设P1所在层LEVEL=1，即所定义的层LEVEL=2,1,P1,2,2,?,Entry,x,vn,?,vf,?,注：,？ 该标识符的值单元首址， 为相对地址（LEVEL, offset）,LEVEL 该标识符所在
11、层次号，,offset 区距，存储分配时可定。,6.5 运行时刻存储分配,解决的问题：标识符变量的地址分配与对它们的访问。,6.5.1 标识符值单元分配,值单元分配分两类：,在编译阶段即可完成真实的地址分配。在编译时对所有数据对象分配固定的存储单元，且在运行是始终保持不变。,1.静态分配,2.动态分配,指在运行时刻进行的值单元分配，在编译时只能进行相对地址分配。,栈式动态分配；,堆式动态分配。,值单元分配是以过程函数为单位的。,注：,6.5.2 活动记录,1.三个概念,过程：,一个可执行模块，过程或函数，通常完成特定的功能。,活动：,过函的一次执行。每执行一次过程体，则产生该过函的一个活动。,
12、活动记录：,一个有结构的连续存储块。用来存储过函一次执行中所需要的信息。,如果不支持可变数据结构，活动记录的体积是可以在编译时确定的。,活动记录仅是一种存储映像，编译程序所进行的运行时刻存储分配是在符号表中进行的。,6.5.2 活动记录（续）,2.活动记录的结构,VALL,TOP,SP,连接数据,局部数据,（1）连接数据区,返回地址：,动态链：,指向调用该过程的主调程序的活动记录的指针；,静态链：,指向静态直接外层活动记录的指针。,（2）形式单元,用来存放实参的值或地址。,（3）局部数据区,用来存放局部变量、内情向量、临时单元。,（4）栈指针,SP 指向现行过程活动记录的起点，即第一个单元；,
13、TOP 指向（已占用）栈顶单元，即活动记录的最后一个单元。,6.5.3 简单的栈式存储分配,没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。,以C语言为例:,1C语言程序的存储组织,【例6.5】,C语言过程调用关系：,Main( ) Q( ) R( ),则，活动记录栈状态为：,TOP,SP,2C的活动记录,Old SP值，即前一活动记录的地址；,其中：,SP,TOP,6.5.3 简单的栈式存储分配（续）,3C语言的过程调用与返回,（1）过程调用, 过程调用的四元式序列：,(param, entry(t1), _, _) (param, entry(tn), _, _) (call,
14、entry(P), n, _), 对应的目标指令：,(i+3)TOP := entry(ti).Addr /将ti地址填到活动记录的形参区去,(param, entry(ti), _, _)对应的指令：,(call, entry(P), n, _)对应的指令：,1TOP := SP /保护现行SP 3TOP := n /传递参数个数 JSP P,第n个实参地址,过程P的入口地址,参数个数,SP,TOP,主调过程活动记录,子过程P的活动记录,Old SP,返回地址,参数个数,形参区,t1,主调过程活动记录,SP,TOP,子过程P的活动记录,SP,n, 子过程P需完成的工作：定义自己的活动记录；,
15、SP := TOP+1 /定义过程P的SP 1SP := 返回地址 /保护返回地址 TOP := TOP+L /定义新TOP,L,SP,SP,返回地址,TOP,SP,TOP,6.5.3 简单的栈式存储分配（续）,3C语言的过程调用与返回,（2）过程返回, 过程返回的四元式：,(ret, _, _, _), 对应的目标指令：,TOP := SP-1 /恢复TOP SP := 0SP /恢复SP X := 2TOP /取返回地址，X为某一变址器 UJ 0X /按X中的返回地址实行变址转移,主调过程活动记录,子过程P的活动记录,L,SP,TOP,TOP,TOP,SP,SP,X,返回地址,返回地址,X,6.5.4 嵌套过程语言的栈式存储分配,过程嵌套的一个关键问题：,标识符的作用域问题 。,标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间。,标识符的有效范围：,（1）在外层未定义，而在内层定义的，服从内层定义；,（2）在外层已定义，而在内层未定义的，服从全范围；,（3）在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义。,服从最小作用域原理；,1.标识符的作用域,2.活动记录,6.5.4 嵌套过程语言的栈式存储分配（续）,问题的提出：
