《编译原理-刘善梅》第8章 符号表.ppt

第八章符号表 符号表的组织与作用整理和查找符号表的内容名字的作用范围 第八章符号表 符号表的作用 一致性检查和作用域分析 辅助代码生成 第一项 入口1 第二项 入口2 第n项 入口n 8 1符号表的组织与作用 符号表的每一项 入口 包含两大栏 名字栏 也称主栏 关键字栏信息栏 记录相应的不同属性 分为若干子栏 8 1符号表的组织与作用 对符号表的操作 填入名称查找名字访问信息填写修改信息删除 对符号表进行操作的时机 定义性出现intx 使用性出现ifx 100 按名字的不同种属建立多张符号表 如常数表 变量名表 过程名表 符号表的组织方式 1 安排各项各栏的存储单元为固定长度2 用间接方式安排各栏存储单元 8 1符号表的组织与作用 符号表的结构 用间接方式安排各栏存储单元 内情向量表 符号表 用间接方式安排各栏存储单元 符号表的存放次序 一张可容纳N项的符号表在存储器中可用下述两种不同的方式之一表示 假定每项需用K个字 1 把每一项置于连续K存储单元中 构成一张K N的表2 把整个符号表分成m个子表 如T1 T2 Tm 每个子表含有N项 8 1符号表的组织与作用 K K1 K2 K3 K4 例 PASCAL程序段 PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END PROCEDUREINCWAP M N INTEGER LABELSTART VARK INTEGER BEGINSTART K M 1 M N 4 N K END 第八章符号表 符号表的组织与作用整理和查找符号表的内容名字的作用范围 8 2整理和查找 1 线性查找2 二分查找3 杂凑查找 HASH技术 8 2整理和查找 1 线性查找按关键字出现的顺序填写各项 填表快 查找慢 结构简单 节省空间 效率低 查找时间复杂度 O n 改进 自适应线性表 给每一项附设一个指示器 这些指示器把所有的项按 最新最近 访问原则连接成一条链 这条链的第一个元素所指的项是最新最近被查询过的项 第二个元素所指的项是次新近被查询过的项 诸如此类 每当填入新项时 总让链头指向最新项 2 二分查找表格中的项按名字的 大小 顺序整理排列 填表慢 查找快 查找时间复杂度 O Log2n 改进 组织成二叉树 3 杂凑查找 HASH技术 杂凑函数H SYM 0 N 1N 符号表的项数 要求 1 函数计算简单高效2 函数值分布均匀填表快 查找快 杂凑技术 HASH技术 杂凑技术使用一张杂凑链表通过间接方式查填符号表 常常把所有相同杂凑值得符号名连成一串 便于线性查找 杂凑表是一个可容纳N个指针的一维数组 它的每个元素的初值全为null 符号表除了通常包含的栏外还增设一链接栏 它把所有持相同杂凑值的符号名连接成一条链 填入一个新的SYM的过程 1 先计算出H SYM 的值h 在0与N 1之间 将HASHTABLE h 的值赋给P 若未曾有杂凑值为h的项名填入过 则将P置空 2 然后置HASHTABLE h available 再把新名SYM及其链接指示器LINK的值P填进指针available所指向的符号表位置 使用此方法的查表过程如下 首先计算出此项的函数H的值等于h 然后就指示器HASHTABLE h 所指的项链逐一按序查找 线性查找 杂凑技术 HASH技术 available SYM1 H SYM1 h p HASHTABLE h null HASHTABLE h AVAVILABLE n1 SYM1 n1 null available SYM2 H SYM2 h p HASHTABLE h n1 HASHTABLE h AVAVILABLE n2 n2 SYM2 n1 SYM3 H SYM3 h p HASHTABLE h n2 HASHTABLE h AVAVILABLE n3 n3 SYM3 n2 available available 第八章符号表 符号表的组织与作用整理和查找符号表的内容名字的作用范围 8 4符号表的内容 对于变量名 数组名和过程名 它们的信息栏中一般要求有下列信息 1 变量类型 整 实或布尔等 种属 简单变量 数组 过程等 大小 长度 即所需的存储单元字数 相对数 指分配给该名字的存储单元的相对地址 若为数组 则记录其内情向量 形式参数标志 是否对这个变量进行过赋值的标志位 8 4符号表的内容 2 过程是否为程序的外部过程 若为函数 类型是什么 其说明是否处理过 是否递归 形式参数是些什么 为了与实在参数进行比较 必须把它们的种属 类型信息同过程名联系在一起 第八章符号表 符号表的组织与作用整理和查找符号表的内容名字的作用范围 8 3名字的作用范围 PROGRAMMAIN integerX YCOMMON C A B ENDSUBROUTINESUB1 realX ZCOMMON C A1 B1 END programP vara b integer procedureP1 i1 j1 integer varc d integer end procedureP2 i2 j2 integer vara c integer procedureP21 varb1 b2 boolean end end end 1 FORTRAN的符号表组织 并列结构语言 一个FORTRAN程序由一个主程序段和若干个辅程序段组成 变量 数组和语句函数名的作用范围就是它们所处的那个程序段 对于一遍扫描的编译程序 可以逐段产生其目标代码 当一程序段处理完后 它的所有的局部名均无需保存在符号表中 需要继续留在符号表总的只是全局名 把局部名和全局名分别存在不同的地方 PASCALPASCAL程序本身可以看成是一个操作系统所调用的过程 过程可以嵌套和递归 一个PASCAL过程 过程头 说明段 由一系列的说明语句组成 begin执行体 由一系列的执行语句组成 end 2 嵌套结构语言的符号表组织如PASCAL ALGOL ADA作用域遵循 最近嵌套原则 允许同一个标识符在不同的过程中代表不同的名字 名字作用域规则 最近嵌套原则 一个在子程序B1中说明的名字X只在B1中有效 局部于B1 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明 则原来的名字X在B2中仍然有效 如果B2对X重新作了说明 那么 B2对X的任何引用都是指重新说明过的这个X programmainvarA B real procedureP1varB boolean begin endprocedureP2varA integer begin endbegin end A real B real B bool A integr 两种做法 引入 过程编号 属性 查找时 先查找本过程编号的名字 查不到则查找外层过程编号的名字 等等 按 栈 式思想组织符号表 查找时 从后往前查找 碰到的第一个名字就是所需查找的名字 名字作用域分析 嵌套结构语言 对每个过程指定一个唯一的编号 层次 即过程的顺序号 以便跟踪过程里的局部名字 在符号表中 表示局部名字用一个二元组 对一个名字查找符号表的原则 只有当表项中的名字的字符逐个匹配 并且该记录相关的编号和当前所处理的过程的编号匹配时 才能确定查找成功 引入 过程编号 属性 1 将符号表设计为栈符号表 新名字出现总是从栈顶填入 为了保证从内层向外层查 查找操作从符号表的栈顶往底部查找 2 过程的嵌套层次表 display 是引入的一个显示层次关系表 其作用是为了描述过程的嵌套层次 指出当前正在活动着的各嵌套的过程 或函数 相应的子符号表在栈符号表中的起始位置 相对地址 Display表也是一个栈 栈顶为level 用来指示层次 即指向当前的最内层过程的子符号表在栈符号表中的起始位置 3 在符号表的信息栏中引入一个指针域 previous 用来链接它在同一个过程内的下一名字在表中的下标 相对位置 每一层最后一个域名字 指针域之值为0 这样每当需要查找个新名字时 就能通过display表找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置 然后通过指针域可以找到同一个过程内的所有被说明的名字 按 栈 式思想组织符号表 例 procedure B1vara b real procedure B2varc d real procedure B3vare f real begin end begin end begin end 栈符号表 DISPLAY a b top sp 1 level level 2 0 B2 c d top sp 4 level 3 0 5 0 B3 e f top sp 7 level 6 0 8 0 procedure B1vara b rea