编译原理--符号表实验报告

《编译原理--符号表实验报告》由会员分享，可在线阅读，更多相关《编译原理--符号表实验报告（8页珍藏版）》请在金锄头文库上搜索。

1、山东大学威海分校信息工程学院软件工程系 山东大学威海分校信息工程学院软件工程系 网络安全 网络安全 实验报告 实验报告 编号： 姓名 谭鑫 院系 信息工程学院软 件工程专业 学号 20078001232 任课教师 贺红 指导教师贺红 实验地点 电子楼 101 实验时间 2010-5-7 实验名称 自学第八章符号表 同 组 人 预习报告(对实验主要内容的认识) 得分 1、符号表的组织与作用 2、整理与查找 3、名字的作用范围 4、符号表的内容 实验内容（问题，思路，程序，结果） 得分 1、什么是符号表？符号表有哪些重要作用？ 答： 编译过程中编译程序需要不断洪和反复查证出现在源程序中各种名字 的

2、属性和特征等有关信息。这些信息通常记录在一张或几张符号表中。符号表 的每一项包含两部分：一部分是名字（标识符）一部分是此名字的有关信息。 每个名字的有关信息一般指种属（如简单变量、数组、过程等） 、类型（如整、 实、布尔等）等等。 作用：在编译的各个分析阶段，每当遇到一个名字都要查找符号表。如果 发现一个新名字，或者发现已有名字的新信息，则要修改符号表，填入新名字 和新信息。 符号表中所登记的信息在编译的不同阶段都要用到。 在语义分析中， 符号表所登记的内容将用于语义检查 （如检查一个名字的使用和原先的说明是 否一致） 和产生中间代码。 在目标代码生成阶段， 当对符号名进行地址分配时， 符号表

3、是地址分配的依据。对于一个多遍扫描的编译程序，不同遍所用的符号 表也往往各有不同。 2、符号表的表项常包括哪些部分？各描述什么？ 答：符号表的表项常包括名字栏和信息栏两部分。 名字栏描述的是名字， 由于查填符号表一般是通过匹配名字来襀的， 因此， 名字栏也称为主栏，主栏的内容称为关键字。 信息栏包含许多子栏和标志位，用来记录相应名字的种种不同属性。 3、符号有的组织方式有哪些？它的组织取决于哪些因素？ 答：符号表的组织方式有两种： 让各栏所占的存储单元的长度都是固定的。 专门开辟一个信息表区，称为数组信息表（或内情向量表） ，将数组的 有关信息全部存入此表中。在符号表的地址栏中存入符号表与内情

4、向 量表连接的入口地址（即指针） 。 它的组织取决于对存储空间利用率的考虑。例如，有些语言规定标识符的 长度不得超过 8 个字符，则可采用第一种组织方式。而有许多语言对标识符的 长度几乎不加限制，或者说，标识符的长度范围甚宽，则可采用第二种组织方 式。 4、给出自适应线性表的查、填算法（注意修改自适应链） 。 答：(1)从词法分析器中读出要查找的单词。 (2)从自适应链所指的第一个元素开始查找，若找到，返回所需信息， 并将链头指向刚才查到的那个项。若未找到，则前往(3)。 (3)填入新项，让链头指向填入的新项。 重复(1)(3)步，直至所有单词均分析完毕。 5、设计一个算法，它将按字典顺序输出

5、二叉树上各结点的名字。 答： (1)将第一个碰到的名字作为 “根” 结点， 它的左右指示器均置为 null。(2)将新结点与根结点的值作比较，小者放在右枝上，大者放在左枝 上。如果根结点的左（右）枝已成子树，则转至(3)。 (3)让新结点与子树作比较，方法同(2)。 重复(1)(3)步，直至新结点插入时成为叶子结点为止转至(4)。 (4)从叶子结点由右向左，由下至上输出各结点的名字。 一、符号表的组织和作用一、符号表的组织和作用 1.1 符号表的作用符号表的作用 一张符号表的每一项（或称入口）白喊两大栏（或称区段、字域） ，即名字栏和信 息栏。 信息栏包含许多子栏和标志位，用来记录相应名字的种

6、种不同属性，由于查填符号 表一般是通过匹配名字来实现的，因此，名字栏也称主栏。主栏的内容称为关键字。 符号表中的每一项都是关于名字的说明。因此所保存的关于名字的信息取决与名字 的用途，所以各表项的格式不一定统一。对每一项可以用一个记录表示。为了使表中的 每个记录格式统一，可以在记录中设置指针，把某些信息放在表的外边，用指针指向存 放另外信息的空间。 在整个编译期间，对于符号表的操作大致可归纳为五类： 对给定名字，查询名字是否已在表中； 往表中填入一个新的名字； 对给定名字，访问它的某些信息； 对给定名字，填写或更新它的某些信息； 删除一个或一组无用的项。 不同种类的表格所涉及的操作往往也是不同

7、的。上述五个方面只是一些基本的共同 操作。 22 符号表的组织形式符号表的组织形式 总体组织和表项属性信息组织 第一种： 把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长 的多个符号表 第二种： 把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性 的庞大的符号表 第三种折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符 号都有比较多的相同属性。 编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表 等等。 SUBROUTINE INCWAP（M，N） 10 KM1 MM4 NK RETURN END 经编译头三阶段后所产生的主要表格

8、有： 符号名表 SNT、 常数表 CT、 入口名表 ENT、 标号表 LT 和四元式表 QT 二符号表的整理与查找二符号表的整理与查找 三种构造法和处理法，即线性查找、二叉树和杂凑技术。第一种办法最简单，但销 路低。二叉树的查找效率高一些，然而实现上略困难一点。杂凑表的效率最高，可是实 现上比较复杂而且要消耗一些额外的存储空间 2.1 线性表线性表 构造符号表最简单和最容易的办法是按关键字出现的顺序填写各个项。我们可以用 一个一维数组或多个一维数组来存放名字及有关信息。当碰到一个新名时就按顺序将它 填入表中，若需要了解一名字的有关信息，则就从第一项开始顺序查找。一张线性表的 结构如图 86 所

9、示。图中，指示器 AVAILABLE 总是指向空白区的首地址。 线性表中每一项的先后顺序是按先来者先填的原则安排的，编译程序不做任何整理 次序的工作。如果是显式说明的程序设计语言，则根据各名字在说明部分出现的先后顺 序填入表中（表尾）；如果是隐式说明的程序设计语言，则根据各名字首次引用的先后 顺序填入表中。当需要查找某个名字时，就从该表的第一项开始顺序查找，若一直查到 AVAILABLE 还未找到这个名字，就说明该名字不在表中。 对于一张含 n 项的线性表来说，欲从中查找一项，平均来说需要做 n2 次的比较。 显然使用这种方法效率很低。但由于线性表的结构简单而且节省存储空间，所以许多编 译程序

10、仍采用线性表。 2.2 对折查找与二叉树对折查找与二叉树 为了提高查表的速度，可以在造表的同时把表格中的项技名字的“大小”顺序整理 排列。所谓名字的“大小”通常是指名字的内码二进值。例如，规定值小者在前，值大 者在后。 对折查找的步骤： 假定表中已含有 n 项，要查找某项 SYM 时： 首先把 SYM 和中项（即第n2l 项）作比较，若相等，则宣布查到。 若 SYM 小于中项，则继续在 1n2的各项中去查找。 若 SYM 大于中项，则就到n22n 的各项中去查找。 这样一来，经一次比较就甩掉 n2 项。当继续在 l n2（或n2n）的范 围中查找时，我们同样采取首先同新中项作比较的办法。如果还

11、查找不到，再把查找范 围折半。显然，使用这种查找法每查找一项最多只须作 1log2N 次比较（因此这种查找法也叫对数查找法）。 这种办法虽好，但对一遍扫描的编译程序来说，没有太大的用处。因为，符号表是 边填边引用的，这意味着每填进一个新项都得做顺序化的整理工作，而这同样是极费时 间的。 一种变通办法是把符号表组织成一棵二又树。也就是说，我们令每项是一个结点， 每个结点附设两个指示器栏，一栏为 LEFT（左枝），另一栏为 RIGHT（右枝）。每个 结点的主栏内码值被看成是代表该结点的值。对于这种二叉树，我们有一个要求用 p 就 是，任何结点 p 右枝的所有结点值均应小于结点 p 的值，而左枝的任

12、何结点值均应大于 结点 p 的值。 二叉树的形成过程是：令第一个碰到的名字作为“根”结点，它的左、右指示器均 置为 null。当要加入新结点时，首先把它和根结点的值作比较，小者放在右枝上，大者放 在左枝上。如果根结点的左（右）枝已成子树，则让新结点和子树的根再作比较。重复 上述步骤，直至把新结点插入使它成为二叉树的一个端末结点（叶）为止。 2.3 杂凑技术杂凑技术 于表格处理来说， 根本问题在于如何保证查表与填表两方面的工作都能高效地进行。 对于线性表来说，填表快，查表慢。而对于对折法而言，则填表慢，查表快。杂凑法是 一种争取查表、填表两方面都能高速进行的统一技术。 方法：假定有一个足够大的区

13、域，这个区域以填写一张含 N 项的符号表。我们希望 构造一个地址函数 H，对任何名字 SYM，H（SYM）取值于 0 至 Nl 之间。这就是说， 不论对 SYM 查表或填表，我们都希望能从 H（SYM）获得它在表中的位置。例如，我们 用无符号整数作为项名，令 N17，把 H（SYM）定义为 SYMN 的余数。那么，名字 09将被置于表中的第 9 项，34将被置于表中的第 0 项，171将被置于表中的 第 1 项，如此等等。 对于地址函数 H 有两点要求：第一，函数的计算要简单、高效；第二，函数值能比 较均匀地分布在 0 至 Nl 之间。例如，若取 N 为质数，把 H（SYM）定义为 SYMN

14、的余数就是一个相当理想的函数。 凑技术常常使用一张杂凑（链）表通过间接方式查填符号表。时时把所有相同杂凑 值的符号名连成一串，便于线性查找。杂凑表是一个可容 N 个指示器值的一维数组，它 的每个元素的初值全为 null。 符号表除了通常包含的栏外还增设一链接栏， 它把所有持相 同杂凑值的符号名连接成一条链。填入一个新的 SYM 过程是： 首先计算出 H（SYM）的值（在 0 与 N1 之间）h，置 P：=HASHTABLEh（若 未曾有杂凑值为 h 的项名填入过，则 pnull）； 然后置 HASHTABLE h ： AVAILABLE， 再把新名 SYM 及其链接指示器 LINK 的值 p

15、填进 AVAILABLE 所指的符号表位置，并累增 AVAILABLE 的值使它指向下一个 空项的位置。 使用这种办法的查表过程是，首先计算出 H（SYM）h，然后就指示器 HASHTABLEh所指的项链逐一按序查找（线性查找）。 三、名字的作用范围三、名字的作用范围 实现最近嵌套作用域规则的办法是，对每个过程指定一个唯一的编号，即过程的顺序号，以便跟踪过程里的局部名字。为了对每个过程进行编号，可以按照识别过程开头 和结尾的语义规则，用语法制导翻译的方法实现。一个过程的编号（层次）作为本过程 中说明的全部局部量的组成部分，即编号被看成是名字的一个组成部分。于是，在符号 表中表示局部名字用一个二

16、元组：名字，过程编号。这种办法意味着我们把整个符 号表按不同的过程逻辑地划分为相应的不同段落。在查找每个名字时，先查对过程编号， 确定所属的表区段落，然后，再从此段落中查对标识符。也就是说，对一个名宇查找符 号表是：只有当表项中的名宇其字符逐个匹配，并且该记录相关的编号和当前所处理的 过程的编号匹配时，才能确定查找成功。 3.1 FORTRAN 的符号表组织的符号表组织 一个 FORTRAN 程序中由一个主程序段和若干过程段 （子程序段或函数段） 组成的。 变量、数组和语句函数名的作用范围就是它们所处的那个程序段（它们在这个程序段被 说明了的）。对于一个一遍扫描的编译程序，我们可以逐段产生其目标代码。于是，当 一程序段处理