22ndCh8符号表II2009Spring.ppt

1、把分程序表中的 B4 移到 BP2 所指的一端，把它指向符号表的指示器 改为指向符号表 END 所指的位置。 2、把符号表中现行分程序 B4 所属的项全部移到死端 END 所指的位置。 当把符号表的项从活端移到死端时必须把他们和杂凑表的联系断开。因而 需要有哪些信誉好的足球投注网站每条杂凑链，从每条链中去掉所有属于 B4 的项（他们全在链的 首部），然后让链头指向链的剩余部分。 注意：去掉一个项名并不意味着除掉它在信息区的相应内容。我们已经说 过，在中间代码中代表项名的指示器实际上是指向信息区的。 3、把 AVAIL 和 CSP 分别调回到进入 B4 前的原值，即释放 B4 所占的 符号表活端区和字符串数组空间。 8.4 符号表的内容 符号表的信息栏中登记了每个名字的有关性质，如类型（整、实或布尔等）， 种属（简单变量、数组、过程等），大小（长度、即所需的存储单元字数）以 及相对数（指分配给该名字的存储单元的相对地址）。 不同的程序设计语言对于名字性质的定义各有不同，符号名的性质可能在编译 时候确定下来（说明语句或隐含约定），或者在目标程序运行时才能确定（没 有说明语句也没有隐含约定的语言）。 符号表中的信息栏的具体组织和安排取决于所翻译的具体语言与目标机器。 * * 二、折半查找 1、方法： 为了提高查表速度，在造表的同时把表中的项按名字的“大小” 顺序整理。所说名字的“大小”通常是指名字的内码二进制值。 若规定由小?大，那么对任何要找的名字来说无论相对哪一个参考点，我们总可以知道要找的名字在参考点的前面还是后面。因此一个简单的算法是每次都把参考点定在中间。 我们已经知道，对 N 项名表查找的平均长度为log2 N (2为底数) 这较之线性查找已经提高了许多。若有1024项，则为10：512。 进一步的改进 不在表的中间进行试查，而是对每步的试查位置作较准确的推断。若要在表中查名字CAT，查2/26 处似乎更合理一些。猜测的好坏和对名表的了解程度有关，若能知道符号表中每个字母开头的词有多少个，则可以有一个较准确的初始推测。在编译中，已知实际的名字项是取自整个名字集中的一个非随机子集，并知道它们的某种总的信息。 Peterson 证明：平均查找长度大约等于(1/2)*log2N。如有1000项，则查找长度是 5 次。 评价 尽管如此，编译器不愿意采用它。它的致命弱点是， 每添加一项就要重新整理使它按序。因此对于名字 表不合适。 但是对于固定的表，如定义符表等就很有用。 （插入固定表） right 结点值 内码 left 再改进 把符号表组织成一个二叉树，每一项是一个节点。节点组成： 根结点是第一个遇到的名字，此时左右指示器均为 null。 构造过程： 这样构造的树，保持任何结点 P 右枝的所有结点值小于结点 P 的值，而 P 左枝的所有结点值大于结点 P 的值： P 值 P 左枝的所有结点值； P 值 P 右枝的所有结点值。 再加入名字 LMN: ABCD LMN XYZA 加入新结点：因为 XYZA ABCD 置于左； 因为 ABAA ABCD 置于右。 RIGHT XYZA NULL NULL ABAA NULL NULL LMN NULL root NULL ABCD NULL RIGHT ABCD LEFT root NULL XYZA NULL 评价 优点 二叉树与对折查找的效率比较： 附设了左右指示器，耗费空间。 每查找一项所做的比较次数仍然和log2N 成比例。 顺序化整理工作十分简单！ 思考： 表格处理包括填表、查表，要两者都快才好。但是，线性表 和折半法只能占一边，能否找到更好的办法？ 先在一个限制比较多的情况下讨论。 三、直接取表法 K ? 表位置 若名字的第一个字母都不一样，那么我们可以用一个 26 元的向量作为符号表。 对每一个名字 K而言，映射函数I( K ) 就是 K 的第一个字母在字母表中的位置。 若表头为 100，则 I( K ) = 100+( K’ )*W Z .. … K .. … B .. A .. 26 元向量----符号表 I (A) I (B) I (K) 100 W 优点： 这个方法查、填都很快，一次就行。 函数唯一的时候，名字不需要保存。 缺点： 1、如果名字 26， 则要浪费表空间。 2、如果不同名字有相同的第一个字母，则本法无效，即使 26 字母也无效。 然而，它给我们一个启示：可以利用函数关系 查表、填表。 四、散列表 （hash table, comp