第六章符号表组织.ppt

,第6章符号表组织,-语义分析之一,6.1符号表的地位和作用6.2符号表的组织与管理6.3符号表的结构设计6.4符号表的构造过程示例6.5运行时刻存储分配,6.1符号表的地位和功能,符号表是标识符的动态语义词典，属于编译中语义分析的知识库；主要内容：,名字标识符源码，用作查询关键字；类型-该标识符的数据类型及其相关信息；种类-该标识符在源程序中的语义角色；地址-与值单元相关的一些信息；,定义和重定义检查；类型匹配校验；数据的越界和溢出检查；值单元存储分配信息；函数、过程的参数传递与校验；,符号表的功能,标识符四种语义信息,6.2符号表的组织与管理,6.2.1符号表的工作原理,遇定义性标识符(在说明中)-把语义信息填入表中，并修改其TOKEN的指针，使其指向相应的表项：,遇应用性标识符(在语句中)-查符号表的相应项，查到后修改其TOKEN的指针，使其指向相应的表项：,6.2.2符号表的查询、访问方式,6.2.3符号表的维护、管理方式,一个源文件有若干个函数组成，通常，每个函数对应一个符号表，此外，还是有一个公用符号表；,符号表如何管理？往往取决于所属语言的程序结构，就C语言来说，可以在内存设置一定长度的符号表区，并建立适当的索引机制，访问相应的符号表：,全局符号表区,局部符号表区,索引机制,6.3符号表的结构设计,【例6.1】有下列函数过程：,需要进符号表的标识符：,exp(函数,附带信息:类型、参数情况和入口地址),pai(常量),arr(类型),a(下标变量)，b(简单变量)，,怎样检查出：a重定义、z无定义以及下表变量,a2,5的值地址在何处？,符号表的体系结构设计,由于标识符的种类不同，导致语义属性也不尽相同；怎样组织符号表？下面提供一个符号表的体系结构：,名字类型种类地址,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(区距)是idk的值单元首址相对于所在记录值区区头位置；约定：off1=0，off2=off1+LEN(tp1),offn=offn-1+LEN(tpn-1)。idn-1的长度TP(域成分类型指针)指针，指向idk域成分类型(在类型表中的信息);,每个域占表中一个纪录,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,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,TYPErec=RECORDu:INTEGER;v:ARRAY1.10OFBOOLEAN;r:RECORDx,y:REALENDEND;,RINFL,u,0,itp,u,itp,d,4,v,4,a,v,d,10,r,14,x,0,rtp,rtp,r,rtp,d,x,d,d,8,y,8,y,rtp,8,16,30,【例6.4】,试填写符号表。,SYNBL,TYPEL,vf,?,rtp,设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。,?,PROCEDUREP1(VARx:REAL;y:INTEGER);BEGINEND;,PFINFL,rtp,P1,rtp,p,x,vn,y,2,y,rtp,有过程说明:,设P1所在层LEVEL=1，即所定义的层LEVEL=2,P1,2,?,Entry,x,vn,?,vf,?,注：,？该标识符的值单元首址，为相对地址（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的活动记录,OldSP值，即前一活动记录的地址；,其中：,SP,TOP,6.5.4嵌套过程语言的栈式存储分配,过程嵌套的一个关键问题：,标识符的作用域问题。,标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间。,标识符的有效范围：,（1）在外层未定义，而在内层定义的，服从内层定义；,（2）在外层已定义，而在内层未定义的，服从全范围；,（3）在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义。,服从最小作用域原理；,1.标识符的作用域,2.活动记录,6.5.4嵌套过程语言的栈式存储分配（续）,问题的提出：,过程Q可能会引用到它的任意外层过程的最新活动记录中的某些数据。,为了在活动记录中查找这些非局部名字所对应的存储空间，过程Q运行时必须设法跟踪它的所有外层过程的最新活动记录的地址。,解决问题的思想：,解决方案：,活动记录中增加静态链！使其指向直接外层的最新活动记录的首地址；,SP,TOP,连接数据,3.嵌套层次显示表(display)和活动记录结构,(1)连接数据区：,用于访问外层的变量,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，,SP,TOP,Q的活动记录,R的活动记录,拷贝l个单元,拷贝自身的SP,l+1个单元,5.值单元的地址分配,值单元分配是依据活动记录的结构，在符号表中进行的。,设有Pascal程序片段如下，P1所在层level=2；,【例6.6】,PROCEDUREP1(x:REAL;VARy:BOOLEAN);CONSTpai=3.14;TYPEarr=ARRAY1.10OFINTEGER;VARm:INTEGER;a:arr;l:REAL;FUNCTIONF1(z:REAL;k:INTEGER):REAL;BEGINEND;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,rtp,vf,(3,4),x,