第六章 符号表组织.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无定义以及下表变量 a 2 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 ARRAY 1 10 OFARRAY 1 5 OFINTEGER 试填写符号表 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 ARRAY 1 10 OFBOOLEAN 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 BEGIN END 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语言为例 1 C语言程序的存储组织 例6 5 C语言过程调用关系 Main Q R 则 活动记录栈状态为 TOP SP 2 C的活动记录 OldSP值 即前一活动记录的地址 其中 SP TOP 6 5 4嵌套过程语言的栈式存储分配 过程嵌套的一个关键问题 标识符的作用域问题 标识符的作用范围往往与它所处的过程相关 也就是说 同一个标识符 在不同的程序段里 代表不同的对象 具有不同的性质 因此要分配不同的存储空间 标识符的有效范围 1 在外层未定义 而在内层定义的 服从内层定义 2 在外层已定义 而在内层未定义的 服从全范围 3 在外层已定义 而在内层也定义的 在外层服从外层定义 在内层服从内层定义 服从最小作用域原理 1 标识符的作用域 2 活动记录 6 5 4嵌套过程语言的栈式存储分配 续 问题的提出 过程Q可能会引用到它的任意外层过程的最新活动记录中的某些数据 为了在活动记录中查找这些非局部名字所对应的存储空间 过程Q运行时必须设法跟踪它的所有外层过程的最新活动记录的地址 解决问题的思想 解决方案 活动记录中增加静态链 使其指向直接外层的最新活动记录的首地址 SP TOP 连接数据 3 嵌套层次显示表 display 和活动记录结构 1 连接数据区 用于访问外层的变量 1 2 0 2 连接数据 全局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 ARRAY 1 10 OFINTEGER VARm INTEGER a arr l REAL FUNCTIONF1 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