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语言来说，可以在内存设置一定长度的符号表区，并建立适当的索引机制，访问相应的符号表：公用符号表FUNCTION2符号表FUNCTION1符号表…现行函数符号表全局符号表区局部符号表区…索引机制FUNCTIONexp(x:REAL;VARy:INTEGER):REAL;CONSTpai=3.14;TYPEarr=ARRAY[1..5,1..10]OFINTEGER;VARa:arr;b,a:real;BEGIN…;a[2,5]:=100;b:=z+6;…END;6.3符号表的结构设计【例6.1】有下列函数过程：⑴需要进符号表的标识符：exp(函数,附带信息:类型、参数情况和入口地址…),pai(常量),arr(类型),a(下标变量)，b(简单变量)，…⑵怎样检查出：a重定义、z无定义以及下表变量a[2,5]的值地址在何处？…※符号表的体系结构设计由于标识符的种类不同，导致语义属性也不尽相同；怎样组织符号表？下面提供一个符号表的体系结构：SYNBL（符号表）NAMETYPECATADDR…PFINFL(函数表)CONSL(常量表)AINFL(数组表)RINFL(结构表)VALL(活动纪录)LENL(长度表)TYPEL（类型表）TVALTPOINT·…名字类型种类地址tokeni·6.3.1符号表总表(SYNBL)NAMETYPCATADDR※结构：•NEME(名字)—标识符源码(或内部码)•TYP(类型)–指针，指向类型表相应项；•CAT(种类)–种类编码：f(函数)，c(常量)，t(类型)，d(域名)，v,vn,vf(变量，换名形参，赋值形参)；•ADDR(地址)–指针，根据标识符的种类不同，分别指向：PFINFL,CONSL,LENL,VALL,…6.3.2类型表(TAPEL)※结构：TVALTPOINT•TVAL(类码)–类型代码：i(整型)，r(实型)，c(字符型)，b(布尔型)，a(数组型)，d(结构型)，…•TPOINT(指针)–根据数据类型不同，指向不同的信息表项：①基本数据类型(i,r,c,b)–nul(空指针)；②数组类型(a)–指向数组表；③结构类型(d)–指向结构表;…6.3.3数组表(AINFL)※结构：LOWUPCTPCLEN每维占表中一个纪录•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域成分类型(在类型表中的信息);IDOFFTP6.3.5函数表(PFINFL)※结构：LEVELOFFFNENTRYPARAM…•LEVEL(层次号)–该过函静态层次嵌套号,•OFF(区距)–该过函自身数据区起始单元相对该过函值区区头位置；•FN(参数个数)–该过函的形式参数的个数；•PARAM(参数表)–指针，指向形参表；•ENTRY(入口地址)–该函数目标程序首地址(运行时填写)；----过程或函数语义信息6.3.6其他表(…)⑴常量表(CONSL)--存放相应常量的初值；⑵长度表(LENL)–存放相应数据类型所占值单元个数；⑶活动纪录表(VALL)–一个函数(或过程)虚拟的值单元存储分配表；此分配表在运行调用时才可用，故称活动纪录。※结构：※结构：※结构：…6.4符号表的构造过程示例：ENT…2?v3vnitpyv2vfrtpx临时变量值区b值y值数组a值区管理区exp值x值链接表3.14501itp1011051aac,i,r,bv1v2v3v4v5tarrv4vacrtppaiv5vrtpbv3vnitpyv2vfrtpxfrtpexpSYNBLPFINFLVALLCONSLLENLAINFLTYPEL【例6.2】有类型说明:TYPEarr=ARRAY[1..10]OFARRAY[1..5]OFINTEGER;试填写符号表。SYNBLTYPELircbAINFLarra110a15itp设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。420tLENL200【例6.3】有类型说明:试填写符号表。SYNBLTYPELAINFLrecd110dbtp设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。1tLENLTYPErec=RECORDu:INTEGER;v:ARRAY[1..10]OFBOOLEAN;r:RECORDx,y:REALENDEND;i,r,c,bRINFLu0itpuitpd4v4avd10r14x0rtprtprrtpdxdd8y8yrtp81630【例6.4】试填写符号表。SYNBLTYPELvf?rtp设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。?PROCEDUREP1(VARx:REAL;y:INTEGER);……BEGIN……END;ircbPFINFLrtpP1rtppxvny2yrtp有过程说明:设P1所在层LEVEL=1，即所定义的层LEVEL=2,1P122?Entryxvn?vf?注：？——该标识符的值单元首址，为相对地址（LEVEL,offset）LEVEL——该标识符所在层次号，offset——区距，存储分配时可定。6.5运行时刻存储分配※解决的问题：标识符变量的地址分配与对它们的访问。6.5.1标识符值单元分配值单元分配分两类：在编译阶段即可完成真实的地址分配。在编译时对所有数据对象分配固定的存储单元，且在运行是始终保持不变。1.静态分配2.动态分配指在运行时刻进行的值单元分配，在编译时只能进行相对地址分配。·栈式动态分配；·堆式动态分配。值单元分配是以过程函数为单位的。注：6.5.2活动记录1.三个概念过程：一个可执行模块，过程或函数，通常完成特定的功能。活动：过函的一次执行。每执行一次过程体，则产生该过函的一个活动。活动记录：一个有结构的连续存储块。用来存储过函一次执行中所需要的信息。如果不支持可变数据结构，活动记录的体积是可以在编译时确定的。活动记录仅是一种存储映像，编译程序所进行的运行时刻存储分配是在符号表中进行的。6.5.2活动记录（续）2.活动记录的结构临时单元内情向量局部变量形式单元静态链动态链返回地址VALLTOPSP连接数据局部数据（1）连接数据区·返回地址：·动态链：指向调用该过程的主调程序的活动记录的指针；·静态链：指向静态直接外层活动记录的指针。（2）形式单元用来存放实参的值或地址。（3）局部数据区用来存放局部变量、内情向量、临时单元。（4）栈指针SP—指向现行过程活动记录的起点，即第一个单元；TOP—指向（已占用）栈顶单元，即活动记录的最后一个单元。6.5.3简单的栈式存储分配没有分程序结构，过程定义不允许嵌套，但允许过程的递归调用。·以C语言为例:1．C语言程序的存储组织【例6.5】C语言过程调用关系：Main()Q()R()则，活动记录栈状态为：R的活动记录Q的活动记录Main的活动记录全局数据区TOPSP2．C的活动记录临时单元内情向量局部变量形式单元参数个数返回地址OldSPOldSP值，即前一活动记录的地址；其中：SPTOP6.5.3简单的栈式存储分配（续）3．C语言的过程调用与返回（1）过程调用①过程调用的四元式序列：(param,entry(t1),_,_)……(param,entry(tn),_,_)(call,entry(P),n,_)②对应的目标指令：(i+3)[TOP]:=entry(ti).Addr//将ti地址填到活动记录的形参区去·(param,entry(ti),_,_)对应的指令：·(call,entry(P),n,_)对应的指令：1[TOP]:=SP//保护现行SP3[TOP]:=n//传递参数个数JSPP第n个实参地址过程P的入口地址参数个数……SPTOP主调过程活动记录子过程P的活动记录OldSP返回地址参数个数形参区t1………………t1……主调过程活动记录SPTOP子过程P的活动记录SPn③子过程P需完成的工作：定义自己的活动记录；SP:=TOP+1//定义过程P的SP1[SP]:=返回地址//保护返回地址TOP:=TOP+L//定义新TOPLSPSP返回地址TOPSPTOP6.5.3简单的栈式存储分配（续）3．C语言的过程调用与返回（2）过程返回①过程返回的四元式：(ret,_,_,_)②对应的目标指令：TOP:=SP-1//恢复TOPSP:=0[SP]//恢复SPX:=2[TOP]//取返回地址，X为某一变址器UJ0[X]//按X中的返回地址实行变址转移………t1nSP……主调过程活动记录子过程P的活动记录LSPTOPTOPTOPSPSPX返回地址返回地址X6.5.4嵌套过程语言的栈式存储分配·过程嵌套的一个关键问题：标识符的作用域问题。标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间。·标识符的有效范围：（1）在外层未定义，而在内层定义的，服从内层定义；（2）在外层已定义，而在内层未定义的，服从全范围；（3）在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义。服从最小作用域原理；1.标识符的作用域2.活动记录6.5.4嵌套过程语言的栈式存储分配（续）·问题的提出：过程Q可能会引用到它的任意外层过程的最新活动记录中的某些数据。为了在活动记录中查找这些非局部名字所对应的存储空间，过程Q运行时必须设法跟踪它的所有外层过程的最新活动记录的地址。·解决问题的思想：·解决方案：活动记录中增加静态链！使其指向直接外层的最新活动记录的首地址；临时单元内情向量局部变量形式单元参数个数静态链返回地址OldSPSPTOP连接数据3.嵌套层次显示表(display)和活动记录结构(1)连接数据区：用于访问外层的变量OldSP返回地址全局Display地址参数个数……形式单元……显示区表(Display)……局部变量……内情向量……临时单元SPTOP0120～2；连接数据·全局display地址—主调过程的显示区表首址；·老SP—主调过程的活动记录首址；(2)参数个数：3；3(3)形参值单元区：4入口为4；·换名形参（vn）—分配2个单元（地址传递）；·赋值形参