第六章符号表组织ppt课件

1、内容提要:第 6 章 符号表组织 - 语义分析之一6.1 符号表的位置和作用6.2 符号表的组织与管理6.3 符号表的构造设计6.4 符号表的构造过程例如 6.5 运转时辰存储分配6.1 符号表的位置和功能 符号表是标识符的动态语义词典，属于编译中语义分析的知识库；主要内容： 名字 标识符源码，用作查询关键字； 类型 - 该标识符的数据类型及其相关信息； 种类 - 该标识符在源程序中的语义角色； 地址 - 与值单元相关的一些信息； 定义和重定义检查； 类型匹配校验； 数据的越界和溢出检查； 值单元存储分配信息； 函数、过程的参数传送与校验； 符号表的功能标识符四种语义信息6.2 符号表的组织与

2、管理6.2.1 符号表的任务原理 遇 定义性标识符(在阐明中)- 把语义信息填入表中，并修正其TOKEN的指针，使其指向相应的表项：i , )该标识符符号表项 遇 运用性标识符(在语句中)- 查符号表的相应项，查到后修正其TOKEN的指针，使其指向相应的表项：6.2.2 符号表的查询、访问方式线性表、顺序表、索引表和散列表，皆可以采用。i , )该标识符符号表项6.2.3 符号表的维护、管理方式 一个源文件有假设干个函数组成，通常，每个函数对应一个符号表，此外，还是有一个公用符号表； 符号表如何管理？往往取决于所属言语的程序构造，就 C言语来说，可以在内存设置一定长度的符号表区，并建立适当的索

3、引机制，访问相应的符号表：公用符号表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(

4、下标变量)，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)NAMETYPCATADDR 构造：NEME(名字) 标识符源码(或内部码)TYP(类型

5、) 指针，指向类型表相应项；CAT(种类) 种类编码： f/P(函数)，c(常量)，t(类型)，d(域名)， v,vn,vf(变量，换名形参，赋值形参)；ADDR(地址) 指针，根据标识符的种类不同，分别指向：PFINFL,CONSL,LENL,VALL,6.3.2 类型表(TAPEL) 构造：TVALTPOINTTVAL(类码) 类型代码： i(整型)，r(实型)，c(字符型)，b(布尔型)， a(数组型)，d(构外型)，TPOINT(指针) 根据数据类型不同，指向不同的信息表项： 根本数据类型(i,r,c,b) nul(空指针)； 数组类型(a) 指向数组表； 构造类型(d) 指向构造表;

6、 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(域成分类型指针

7、) 指针，指向idk域成分类型(在类型表中的信息); ID OFF TP每个域占表中一个纪录6.3.5 函数表(PFINFL) 构造：LEVEL OFF FNENTRYPARAM LEVEL(层次号) 该过函静态层次嵌套号, OFF(区距) 该过函本身数据区起始单元相对该过函值区区头位置 ； FN(参数个数) 该过函的方式参数的个数； PARAM(参数表) 指针，指向形参表； ENTRY(入口地址) 该函数目的程序首地址(运转时填写)； - 过程或函数语义信息6.3.6 其他表() 常量表(CONSL)- 存放相应常量的初值； 长度表(LENL) 存放相应数据类型所占值单元个数； 活动纪录表(

8、VALL) 一个函数(或过程)虚拟的值单元存储分配表；此分配表在运转调用时才可用，故称活动纪录。 构造： 构造： 构造： 6.4 符号表的构造过程例如： ENT 2 ? v3 vnitp y v2 vfrtp x暂时变量值区 b值 y值 数组a值区 管理区 exp值 x值 链接表3.14 50 1itp1011051 a ac,i,r,bv1v2v3v4v5 t arr v4 v a crtppai v5 vrtp b v3vnitp y v2 vfrtp x frtpexpSYNBLPFINFLVALLCONSLLENLAINFLTYPEL设：整型占1个存储单元，【例6.2】有类型阐明: T

9、YPE arr = ARRAY 1.10 OF ARRAY 1.5 OF INTEGER; 试填写符号表。 SYNBLTYPEL i r c bAINFLarra110a15itp设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。 420tLENL200【例6.3】有类型阐明:试填写符号表。 SYNBLTYPELAINFLrecd110dbtp设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。 1 tLENLTYPE rec = RECORD u: INTEGER; v: ARRAY 1.10 OF BOOLEAN; r: RECORD x, y : REAL

10、END END; i,r,c,bRINFLu0itpuitpd4v4avd10r14x0rtprtprrtpdxdd8y8yrtp81630【例6.4】试填写符号表。 SYNBLTYPELvf?rtp设：实型占8个存储单元，整型占4个单元，布尔型和字符型占1个单元。 ? PROCEDURE P1(VAR x: REAL; y: INTEGER); BEGIN END; i r c bPFINFLrtpP1rtppxvny2yrtp有过程阐明:设P1所在层LEVEL=1，即所定义的层LEVEL=2,1P122?Entryxvn? vf? 注： ？ 该标识符的值单元首址， 为相对地址LEVEL,

11、offset LEVEL 该标识符所在层次号， offset 区距，存储分配时可定。6.5 运转时辰存储分配处理的问题：标识符变量的地址分配与对它们的访问。 6.5.1 标识符值单元分配 值单元分配分两类： 在编译阶段即可完成真实的地址分配。在编译时对一切数据对象分配固定的存储单元，且在运转是一直坚持不变。1.静态分配2.动态分配 指在运转时辰进展的值单元分配，在编译时只能进展相对地址分配。 栈式动态分配； 堆式动态分配。 值单元分配是以过程函数为单位的。 注：6.5.2 活动记录 1.三个概念过程：一个可执行模块，过程或函数，通常完成特定的功能。活动：过函的一次执行。每执行一次过程体，那么产

12、生该过函的一个活动。活动记录：一个有构造的延续存储块。用来存储过函一次执行中所需求的信息。 假设不支持可变数据构造，活动记录的体积是可以在编译时确定的。 活动记录仅是一种存储映像，编译程序所进展的运转时辰存储分配是在符号表中进展的。 6.5.2 活动记录续 2.活动记录的构造 临时单元 内情向量 局部变量 形式单元 静态链 动态链 返回地址VALLTOPSP衔接数据部分数据1衔接数据区前往地址： 动态链： 指向调用该过程的主调程序的活动记录的指针； 静态链： 指向静态直接外层活动记录的指针。 2方式单元用来存放实参的值或地址。 3部分数据区 用来存放部分变量、内情向量、暂时单元。 4栈指针SP

13、 指向现行过程活动记录的起点，即第一个单元； TOP 指向已占用栈顶单元，即活动记录的最后一个单元。 6.5.3 简单的栈式存储分配 没有分程序构造，过程定义不允许嵌套，但允许过程的递归调用。 以C言语为例:1C言语程序的存储组织 【例6.5】C言语过程调用关系：Main( ) Q( ) R( ) 那么，活动记录栈形状为： R的活动记录 Q的活动记录Main的活动记录 全局数据区TOPSP2C的活动记录 临时单元 内情向量 局部变量 形式单元 参数个数 返回地址 Old SPOld SP值，即前一活动记录的地址； 其中：SPTOP6.5.4 嵌套过程言语的栈式存储分配 过程嵌套的一个关键问题：

14、标识符的作用域问题 。 标识符的作用范围往往与它所处的过程相关，也就是说，同一个标识符，在不同的程序段里，代表不同的对象，具有不同的性质，因此要分配不同的存储空间。 标识符的有效范围：1在外层未定义，而在内层定义的，服从内层定义；2在外层已定义，而在内层未定义的，服从全范围；3在外层已定义，而在内层也定义的，在外层服从外层定义，在内层服从内层定义。服从最小作用域原理；1.标识符的作用域2.活动记录6.5.4 嵌套过程言语的栈式存储分配续 问题的提出： 过程Q能够会援用到它的任不测层过程的最新活动记录中的某些数据。 为了在活动记录中查找这些非部分名字所对应的存储空间，过程Q运转时必需设法跟踪它的

15、一切外层过程的最新活动记录的地址。 处理问题的思想：处理方案： 活动记录中添加静态链！使其指向直接外层的最新活动记录的首地址； 临时单元 内情向量 局部变量 形式单元 参数个数 静态链 返回地址 Old SPSPTOP衔接数据3.嵌套层次显示表(display)和活动记录构造(1)衔接数据区：用于访问外层的变量 Old SP前往地址全局Display地址参数个数 方式单元 显示区表(Display) 部分变量 内情向量 暂时单元SPTOP01202；衔接数据 全局display地址 主调过程的显示区表首址；老SP 主调过程的活动记录首址；(2)参数个数：3；3(3)形参值单元区：4入口为4；换

16、名形参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前往地址全局

17、Display地址参数个数 方式单元 显示区表(Display) 部分变量 内情向量 暂时单元SPTOPOld SP前往地址全局Display地址参数个数 方式单元 显示区表(Display) 部分变量 内情向量 暂时单元Q的活动记录 R的活动记录 拷贝l个单元 拷贝本身的SPl+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 INTE

18、GER; 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按相应类型长度分配；接上页：SYNBLi,r,c,bTYPELPFINFLP1的VALLCONSLLENLAINFL局部变量Display表形式单元参数个数全局Display返回地址Old SP过程P1定义的层次为l=3 01234-1112-131415161718-2122-61P1p332Entryxx2rtpvf(3,4)xrtpvf(3,4)(3,12)yybtpbtpvnvny(3,12)(4,4)pairtpc3.14arra110itp4t40mitpvm(3,18)ava(3,22)lrtpvl62-69(3,62)F1rtpf432Entryzzkkrtprtpitpitpvfvfvfvf(4,4)(4,12)(4,12)程序片段 一个