编译原理课件第九章符号表.ppt

第第9章章 符号表符号表主要内容主要内容9.1符号表的作用和地位符号表的作用和地位9.2符号的主要属性及作用符号的主要属性及作用9.3符号表的组织符号表的组织重点、难点重点、难点符号的主要属性及作用符号的主要属性及作用符号表的作用和地位符号表的作用和地位-语义检查的依据语义检查的依据目标代码生成阶段地址分配的依据目标代码生成阶段地址分配的依据 在编译程序中符号表用来存放语言程序中出现的在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，有关标识符的属性信息，符号表中所登记的信符号表中所登记的信息在编译的不同阶段都要用到。息在编译的不同阶段都要用到。在语义分析中，符号表所登记的内容将用于语义在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码。否一致）和产生中间代码。在目标代码生成阶段，当对符号名进行地址分配在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。对一个多遍扫时，符号表是地址分配的依据。对一个多遍扫描的编译程序，不同遍所用的符号表也往往各描的编译程序，不同遍所用的符号表也往往各有不同。因为每遍所关心的信息各有差异。有不同。因为每遍所关心的信息各有差异。一张符号表的每一项（或称入口才包含两大栏（或称区段、字域），即名字栏和信息栏。名字栏(NAME)信息栏（INFORMATION）第1项（入口1）第2项（入口2）第n项（入口n）信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，由于查填符号表一般是通过匹配名字来寮现的，因此，名字栏也称主栏。主栏的内容称为关键字（keyword）。在整个编译期间，对于符号表的操作大致可归纳为五类：对给定名字，查询名字是否已在表中；往表中填入一个新的名字；对给定名字，访问它的某些信息；对给定名字，填写或更新它的某些信息；删除一个或一组无用的项。不同种类的表格所涉及的操作往往也是不同的。上述五个方面只是一些基本的共同操作。符号符号属性属性(信息）信息）几种通常都是需要的。几种通常都是需要的。1 符号名符号名2 符号的类型符号的类型3 符号的存储类别符号的存储类别4 符号的作用域及可视性符号的作用域及可视性5 符号变量的存储分配信息符号变量的存储分配信息 6 符号的其它属性符号的其它属性（）数组内情向量（）数组内情向量（）记录结构型的成员信息（）记录结构型的成员信息（）函数及过（）函数及过程的形参程的形参 符号表的组织符号表的组织总体组织和表项属性信息组织总体组织和表项属性信息组织第一种：第一种：把属性种类完全相同的那些符号组织在把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表一起，构造出表项是分别为等长的多个符号表第二种：第二种：把所有语言中的符号都组织在一张符号把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表中。组成一张包括了所有属性的庞大的符号表表第三种折衷方式是根据符号属性相似程度分类组第三种折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较织成若干张表，每张表中记录的符号都有比较多的相同属性。多的相同属性。编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等。SUBROUTINEINCWAP（M，N）10KM1MM4NKRETURNEND经编译头三阶段后所产生的主要表格有：符号名表SNT、常数表CT、入口名表ENT、标号表LT和四元式表QT符号名表SNTNAMEINFORMATION（1）M哑元，整数，变量（2）N哑元，整数，变量（3）K整数，变量常数表CT值（VALUE）(1)1（2）4入口名表ENTNAMEINFORMATION（1）INCWAP二目子程序，入口QT(1)/*记录入口名INCWAP的入口地址标号表LTLABLEINFORMATION（1）10QT(4)/*记录了标号10对应的四元式序列号四元式表QT符号表项的排列符号表项的排列符符号号表表作作为为一一个个多多元元组组，表表中中元元组组的的排排列列组组织织是是构构造造符符号号表表的的重重要要成成分分。在在编编译译程程序序的的整整个个工工作作过过程程中中，符符号号表表被被频频繁繁地地用用来来建建立立表表项项，找找查查表表项项，填填充充和和引引用用表表项项的的属属性性。因因此此表表项项的的排排列列组组织织对对该该系系统统运运行行的的效效率率起起着着十十分分重重要要的的作作用用。在在编编译译程程序序中中，符符号号表表项项的的组组织织传传统统上上采采用用三三种种构构造造方方法法。即即线线性性法法，二二分分法法及散列法。及散列法。关键字域的组织关键字域的组织符号表的关键字域（段）就是符号名称符号表的关键字域（段）就是符号名称 等长关键字域（段）符号表等长关键字域（段）符号表 不不等等长长关关键键字字段段符符号号表表-采采用用关关键键字字池池的的索引结构。索引结构。分程序结构的符号表分程序结构的符号表对于具有分程序型结构的语言程序，不同层次分对于具有分程序型结构的语言程序，不同层次分程序中定义的标识符号具有不同的作用域和不程序中定义的标识符号具有不同的作用域和不同的可视性规则。通常对于具有分程序结构的同的可视性规则。通常对于具有分程序结构的语言可用两种方式组织它们的符号表：语言可用两种方式组织它们的符号表：一是对一是对每个分程序建立一个独立的分表结构的符号表；每个分程序建立一个独立的分表结构的符号表；一是把各分程序符号组织在一张单表结构的符一是把各分程序符号组织在一张单表结构的符号表中号表中分表结构的组织管理分表结构的组织管理其基本思想是，每当编译程序扫描到一个其基本思想是，每当编译程序扫描到一个分程序结构开始时，为该分程序建立一分程序结构开始时，为该分程序建立一张符号表，在该分程序中定义的标识符，张符号表，在该分程序中定义的标识符，都被登录在该符号表中。而当编译程序都被登录在该符号表中。而当编译程序扫描到一个分程序的结束时，编译程序扫描到一个分程序的结束时，编译程序释放为该分程序所建立的符号表。这种释放为该分程序所建立的符号表。这种符号表的分表结构与源程序的分程序层符号表的分表结构与源程序的分程序层次结构一一对应次结构一一对应单表结构的组织管理单表结构的组织管理其其基基本本思思想想是是，所所有有分分程程序序中中定定义义的的标标识识符符都都集集中中在在单单张张符符号号表表中中。为为了了实实现现分分程程序序构构造造中中标标识识符符的的作作用用域域和和可可视视性性规规则则的的要要求求,在在符符号号表表中中可可设设立立一一个个属属性性域域用用来来登登录录符符号号所所在在分分程程序序的层次的层次进进入入分分程程序序时时，层层次次要要增增加加一一层层.在在退退出出一一个个分分程程序序时时，层层次次降降低低一一层层，且且需需要要把把符符号号表表中中，所有在退出的分程序中登录的符号项清除。所有在退出的分程序中登录的符号项清除。嵌套结构型程序设计语言（Pascal）的特点，可采用的办法：将其符号表设计为栈符号表，当新的名字出现总是从栈顶填入。查找操作从符号表的栈顶往底部查（保证先查最近出现的名字）。因为程序是分层的，并且一个过程结束时将释放相应的子符号表，因此查找范围与线性表比相对要小一些。引入一个显示（DISPLAY）层次关系表，称为过程的嵌套层次表。其作用是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（相对地址）。DISPLAY表也是一个栈，栈顶指针为level。当进入一个新过程时，level增加1；每当退出一个过程时，level减1。DISPLAY(level)总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。在符号表的信息栏中引入一个指针域（previous）用以链接它在同一过程内的前一域名字在表中的下标（相对位置）。每一层的最后一个域名字，其previous之值为0。这样，每当需要查找一个新名字时，就能通过DISPLAY找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置。然后，通过previous可以找到同一过程内的所有被说明的名字。说明部分的分析说明部分的分析与处理与处理对每个过程对每个过程说明的对象说明的对象（变量变量，常量常量和和过程过程）造名字表造名字表填写填写标识符的标识符的所在所在层次层次、属性属性和分配的和分配的相对位置相对位置。标识。标识符的属性不同时，所需填入的信息也不同。登录信息由符的属性不同时，所需填入的信息也不同。登录信息由ENTERENTER过程完成。过程完成。说明部分的分析说明部分的分析与处理与处理（程程序）序）说明类型的定义：object=(constant,variable,procedur)（定义定义纯量纯量/枚举枚举类型）类型）名字表的定义table:array0.txmaxofrecordname:alfa;casekind:objectofconstant:(val:integer);variable:procedur:(level,adr,size:integer);例程序说明部分为：例程序说明部分为：CONST A=35CONST A=35，B=49B=49；VAR CVAR C，D D，E E；PROCEDURE PPROCEDURE P；VAR G VAR G；名字名字 类型类型 层次层次/值值 地址地址 存储空间存储空间Const（常量）常量）无无层次层次对应名字表对应名字表 PL/0PL/0编译程序编译程序Table表的表的下标指针下标指针tx补充说明：补充说明：主程序主程序BLOCK第第1次次调用调用blockBLOCK（0，0，）0 0 .BLOCK BLOCK（LEV+1,TX，）(递归递归进入进入分程序分程序)LEVtxLEVtx（6）6 （9）1 tx是是BLOCK的的实际实际值参值参