石河子大学信息科学与技术学院编译原理课件第九章 符号表.ppt

第9章 符号表 符号表的作用和地位-----语义检查的依据 目标代码生成阶段地址分配的依据 在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，符号表中所登记的信息在编译的不同阶段都要用到。 在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码。 在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。对一个多遍扫描的编译程序，不同遍所用的符号表也往往各有不同。因为每遍所关心的信息各有差异。 一张符号表的每一项（或称入口,或称区段、字域），即名字栏和信息栏。 ? ?信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，由于查填符号表一般是通过匹配名字来寮现的，因此，名字栏也称主栏。主栏的内容称为关键字（key word）。 符号属性(信息） 几种通常都是需要的。 1 符号名 2 符号的类型 3 符号的存储类别 4 符号的作用域及可视性 5 符号变量的存储分配信息 6 符号的其它属性 （１）　数组内情向量 （２）　记录结构型的成员信息 （３）　函数及过程的形参 符号表的组织 总体组织和表项属性信息组织 第一种： 把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表 第二种： 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表 第三种折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。 符号表项的排列 符号表作为一个多元组，表中元组的排列组织是构造符号表的重要成分。在编译程序的整个工作过程中，符号表被频繁地用来建立表项，找查表项，填充和引用表项的属性。因此表项的排列组织对该系统运行的效率起着十分重要的作用。在编译程序中，符号表项的组织传统上采用三种构造方法。即线性法，二分法及散列法。 编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等。 SUBROUTINE INCWAP（M，N） 10 K＝M＋1 M＝M＋4 N＝K RETURN END 经编译头三阶段后所产生的主要表格有：符号名表SNT、常数表CT、入口名表ENT、标号表LT和四元式表QT 符号名表SNT ? NAME INFORMATION （1）M 哑元，整数，变量 （2）N 哑元，整数，变量 （3）K 整数，变量 常数表CT  值（VALUE） (1) 1 (2) 4 入口名表ENT ? NAME INFORMATION ?（1）INCWAP 二目子程序，入口QT(1) /*记录入口名INCWAP的入口地址＊／ 标号表LT? LABLE INFORMATION ?（1）10 QT(4) /*记录了标号10对应的四元式序列号＊／ 二，折半查找 1，方法： 为了提高查表速度，在造表的同时把表中的项按名字的“大小” 顺序整理，所说名字的“大小”，通常是指名字的内码二进制值。 若规定由小 ? 大，那么对任何要找的名字来说，无论相对哪 一个参考点，我们总可以知道要找的名字在参考点的前面还是 后面。因此一个简单的算法是每次都把参考点定在中间。 我们已经知道，对 N 项名表，查找的平均长度为log2N (2为底数) 这较其线性查找，已经提高了许多，若1024项，是10：512 进一步的改进 不在表的中间进行试查，而是对每步的试查位置作较准确的推断，若要在下表中查名字CAT，查2/26 处似更合理一些，猜测的好坏和对名表的了解程度有关，若能知符号表中的每个字母开头的词有多少，就能有一个校准的初始推测。在编译中，带有实际的名字项是取自整个名字集中的一个非随机子集，并知道它们的某种总的信息。 Peterson 证明： 平均查找长度大约等于(1/2)*log2N，如1000项是 5 次。 评价 尽管如此，编译器不愿意采用它，它的致命弱点是， 添加一项就要重新整理，使它按序