编译原理第9章(清华大学).ppt

第第9章章 符号表符号表  9.1符号表的作用和地位符号表的作用和地位9.2符号的主要属性及作用符号的主要属性及作用9.3符号表的组织符号表的组织饥菌铝碉拽耘瘫霉降稽炉幕小丽造凝颁翁韩歹氯简宰砌销顿袜爷茅邓辗粘编译原理第9章(清华大学)编译原理第9章(清华大学)符号表的作用和地位符号表的作用和地位-----语义检查的依据语义检查的依据目标代码生成阶段地址分配的依据目标代码生成阶段地址分配的依据 在编译程序中符号表用来存放语言程序中出现的在编译程序中符号表用来存放语言程序中出现的有关标识符的属性信息，有关标识符的属性信息，符号表中所登记的信符号表中所登记的信息在编译的不同阶段都要用到息在编译的不同阶段都要用到在语义分析中，符号表所登记的内容将用于语义在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码否一致）和产生中间代码在目标代码生成阶段，当对符号名进行地址分配在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据对一个多遍扫时，符号表是地址分配的依据对一个多遍扫描的编译程序，不同遍所用的符号表也往往各描的编译程序，不同遍所用的符号表也往往各有不同。

因为每遍所关心的信息各有差异因为每遍所关心的信息各有差异气魁坤锥磁忙艳径料代肾豪亿植洲址矛箭缸描著昧缝硷亡吧待妻衰奠察核编译原理第9章(清华大学)编译原理第9章(清华大学)一张符号表的每一项（或称入口才包含两大栏（或称区段、字域），即名字栏和信息栏                      名字栏(NAME)  信息栏(INFORMATION）第1项（入口1） 第2项（入口2）     … 第n项（入口n） 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，由于查填符号表一般是通过匹配名字来寮现的，因此，名字栏也称主栏主栏的内容称为关键字（key word） 仕般丛智后麓骡铣配泻案装判机屯耐诵许爬倡映衷盗尘神菠辩扇骂钝孩穗编译原理第9章(清华大学)编译原理第9章(清华大学)在整个编译期间，对于符号表的操作大致可归纳为五类：• 对给定名字，查询名字是否已在表中；• 往表中填入一个新的名字；• 对给定名字，访问它的某些信息；• 对给定名字，填写或更新它的某些信息；• 删除一个或一组无用的项不同种类的表格所涉及的操作往往也是不同的上述五个方面只是一些基本的共同操作尽涅尹蚀肉宽皇辈利俭劳六移俱锻疡陌樊旬吝佛懒绢耽淆附遂觉侵惩鳃悲编译原理第9章(清华大学)编译原理第9章(清华大学)属性属性(信息）信息）几种通常都是需要的。

几种通常都是需要的1 名子名子 2 类型类型 3 存储类别存储类别 4 作用域及可视性作用域及可视性 5 存储分配信息存储分配信息 6 其它属性其它属性 （１）　数组内情向量（１）　数组内情向量                          （２）　记录结构型的成员信息（２）　记录结构型的成员信息                          （３）　函数及过程的形参（３）　函数及过程的形参 拦其灸彬傲邹丽顶画搂梢聪戚集玲税圣增官寐盈灵最硅莹涅酱恤定躲豺谰编译原理第9章(清华大学)编译原理第9章(清华大学)符号表的组织符号表的组织总体组织和表项属性信息组织总体组织和表项属性信息组织 第一种：第一种： 把属性种类完全相同的那些符号组织在把属性种类完全相同的那些符号组织在一起，构造出表项是分别为等长的多个符号表一起，构造出表项是分别为等长的多个符号表 第二种：第二种： 把所有语言中的符号都组织在一张符号把所有语言中的符号都组织在一张符号表中组成一张包括了所有属性的庞大的符号表中组成一张包括了所有属性的庞大的符号表表 第三种折衷方式是根据符号属性相似程度分类组第三种折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较织成若干张表，每张表中记录的符号都有比较多的相同属性。

多的相同属性 暑甭锥锈色废蠢拟烙好风刑梗委灵弧同幢阳屋喉欢敖享翘家钎吊子袋眠后编译原理第9章(清华大学)编译原理第9章(清华大学)编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等SUBROUTINE   INCWAP（M，N）10    K＝M＋1      M＝M＋4      N＝K      RETURN      END经编译头三阶段后所产生的主要表格有：符号名表SNT、常数表CT、入口名表ENT、标号表LT和四元式表QT  延画呼竞霓酥波扦焕员河朵匣聘颤狈泄捻毗王腮膝奠严抓坊彬泳孔浸极刚编译原理第9章(清华大学)编译原理第9章(清华大学) 符号名表SNT             NAME     INFORMATION（1）M           哑元，整数，变量（2）N            哑元，整数，变量（3）K            整数，变量                                    仁戊情幕洽瓶潍驱璃孩翔辐坎龙疏茄投玲堡源碰耍贾殴桌殴巡橡癸琅皆娠编译原理第9章(清华大学)编译原理第9章(清华大学)         常数表CT                      值（VALUE）              (1)    1           （2） 4                             入口名表ENT            NAME                    INFORMATION （1）INCWAP     二目子程序，入口QT(1)/*记录入口名INCWAP的入口地址＊／                     标号表LT            LABLE    INFORMATION （1）10                   QT(4)/*记录了标号10对应的四元式序列号＊／沥怯述智掸买舶软杀旨缚嗽临脸扔隐或腔注迁慨撮迢唯岗童抢全荆厂妈腺编译原理第9章(清华大学)编译原理第9章(清华大学)四元式表四元式表QT吠谴评衍求缨个延崖筑箱历雇怔昭溶拘欠秸聂汐柒琳允氛公想型曹知莉抬编译原理第9章(清华大学)编译原理第9章(清华大学)符号表项的排列符号表项的排列符符号号表表作作为为一一个个多多元元组组，，表表中中元元组组的的排排列列组组织织是是构构造造符符号号表表的的重重要要成成分分。

在在编编译译程程序序的的整整个个工工作作过过程程中中，，符符号号表表被被频频繁繁地地用用来来建建立立表表项项，，找找查查表表项项，，填填充充和和引引用用表表项项的的属属性性因因此此表表项项的的排排列列组组织织对对该该系系统统运运行行的的效效率率起起着着十十分分重重要要的的作作用用在在编编译译程程序序中中，，符符号号表表项项的的组组织织传传统统上上采采用用三三种种构构造造方方法法即即线线性性法法，，二二分分法法及散列法及散列法驯锡缚已诬疵沦六国驱妈棱状泛戊顿迫鲤澎歉入嘻臻疗幢陀澈困围座地忘编译原理第9章(清华大学)编译原理第9章(清华大学)关键字域的组织关键字域的组织符号表的关键字域（段）就是符号名称符号表的关键字域（段）就是符号名称   等长关键字域（段）符号表等长关键字域（段）符号表 不不等等长长关关键键字字段段符符号号表表---采采用用关关键键字字池池的的索引结构索引结构卵膝焚可纠苦笆蔚祥地槽慕袄澄匈尝标萌峙秆辖风渔部缄改怜责跋瘪碰如编译原理第9章(清华大学)编译原理第9章(清华大学)分程序结构的符号表分程序结构的符号表对于具有分程序型结构的语言程序，不同层次分对于具有分程序型结构的语言程序，不同层次分程序中定义的标识符号具有不同的作用域和不程序中定义的标识符号具有不同的作用域和不同的可视性规则。

通常对于具有分程序结构的同的可视性规则通常对于具有分程序结构的语言可用两种方式组织它们的符号表：语言可用两种方式组织它们的符号表： 一是对一是对每个分程序建立一个独立的分表结构的符号表；每个分程序建立一个独立的分表结构的符号表；一是把各分程序符号组织在一张单表结构的符一是把各分程序符号组织在一张单表结构的符号表中号表中 汗题劫负雪羔典泥葡蚊合颜酞封乔闽老帘汛簇军衡乾祭醇坯蠢祥蜡椎佬耸编译原理第9章(清华大学)编译原理第9章(清华大学)分表结构的组织管理分表结构的组织管理其基本思想是，每当编译程序扫描到一个其基本思想是，每当编译程序扫描到一个分程序结构开始时，为该分程序建立一分程序结构开始时，为该分程序建立一张符号表，在该分程序中定义的标识符，张符号表，在该分程序中定义的标识符，都被登录在该符号表中而当编译程序都被登录在该符号表中而当编译程序扫描到一个分程序的结束时，编译程序扫描到一个分程序的结束时，编译程序释放为该分程序所建立的符号表这种释放为该分程序所建立的符号表这种符号表的分表结构与源程序的分程序层符号表的分表结构与源程序的分程序层次结构一一对应次结构一一对应 冉狠焕崖勘凹巩自橡萍诱楔剔吾阁佛活郴亦标掳砒夹藕非林张匹贸哲钱敌编译原理第9章(清华大学)编译原理第9章(清华大学)单表结构的组织管理单表结构的组织管理其其基基本本思思想想是是，，所所有有分分程程序序中中定定义义的的标标识识符符都都集集中中在在单单张张符符号号表表中中。

为为了了实实现现分分程程序序构构造造中中标标识识符符的的作作用用域域和和可可视视性性规规则则的的要要求求,在在符符号号表表中中可可设设立立一一个个属属性性域域用用来来登登录录符符号号所所在在分分程程序序的的层次层次进进入入分分程程序序时时，，层层次次要要增增加加一一层层.在在退退出出一一个个分分程程序序时时，，层层次次降降低低一一层层，，且且需需要要把把符符号号表表中中，，所所有在退出的分程序中登录的符号项清除有在退出的分程序中登录的符号项清除庄啄测酮须唁彬纬赐撵邻增氦限颓方阿债漠肝肆萎棚佰羚墨闪衬憨耽鸳科编译原理第9章(清华大学)编译原理第9章(清华大学)嵌套结构型程序设计语言（Pascal）的特点，可采用的办法：．将其符号表设计为栈符号表，当新的名字出现总是从栈顶填入查找操作从符号表的栈顶往底部查（保证先查最近出现的名字）因为程序是分层的，并且一个过程结束时将释放相应的子符号表，因此查找范围与线性表比相对要小一些．引入一个显示（DISPLAY）层次关系表，称为过程的嵌套层次表其作用是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（相对地址）。

DISPLAY表也是一个栈，栈顶指针为level当进入一个新过程时，level增加1；每当退出一个过程时，level减1DISPLAY(level)总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置．在符号表的信息栏中引入一个指针域（previous）用以链接它在同一过程内的前一域名字在表中的下标（相对位置）每一层的最后一个域名字，其previous之值为0这样，每当需要查找一个新名字时，就能通过DISPLAY找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置然后，通过previous可以找到同一过程内的所有被说明的名字怯刷折它海穿议旧鞍裹萤枢罩尤按勤致啤怠遂舱眼哈耐题租哑男遥猜秃枝编译原理第9章(清华大学)编译原理第9章(清华大学)说明部分的分析与处理说明部分的分析与处理•对每个过程对每个过程说明的对象说明的对象（（变量变量，，常量常量和和过程过程））造名字表造名字表–填写填写标识符的标识符的所在所在层次层次、、属性属性和分配的和分配的相对位置相对位置标识符的属性不同时，所需填入的信息也不同登录信息由符的属性不同时，所需填入的信息也不同登录信息由ENTERENTER过程完成。

过程完成恫玛垛辑画译习芽防惦在伐妥胀篡虑熄奔娟补笺段河钡署榷磊庞扒藏务稗编译原理第9章(清华大学)编译原理第9章(清华大学)说明部分的分析与处理（程序）说明部分的分析与处理（程序）•说明类型的定义：   object= (constant, variable,procedur) （（定义定义纯量纯量/ /枚举枚举类型）类型）•名字表的定义    table:array[0..txmax] of record     name:alfa;     case kind:object of            constant:(val:integer);            variable:procedur:(level,adr,size:                                          integer); 姑啥掷蛊欺需凌篮昏钉夸囚逸劳玖最松囊达军彭许疆婪抽情妥拘湘窘蚤钡编译原理第9章(清华大学)编译原理第9章(清华大学)例程序说明部分为：例程序说明部分为：CONST A=35CONST A=35，，B=49B=49；；VAR CVAR C，，D D，，E E；；PROCEDURE PPROCEDURE P；；VAR G VAR G ；；… …       名字名字                 类型类型                层次层次/值值              地址地址         存储空间存储空间Const（常量）常量）无无层次层次对应名字表对应名字表声尝刽妒砍淖澡佩共孔蔚椽病兔娄茬呜菲才撞钱吭酬牵奋插刻燎悬辗鹅挚编译原理第9章(清华大学)编译原理第9章(清华大学) PL/0编译程序编译程序•Table表的表的下标指针下标指针tx补充说明：补充说明： 主程序主程序BLOCK第第1次次调用调用blockBLOCK（（0，，0，，…）） 0 0 ...BLOCK BLOCK（（LEV+1,TX，，…））( (递归递归进入进入分程序分程序) )LEVtxLEVtx（（6））6 （（9））1 tx是是BLOCK的的实际实际值参值参电芯钱蜀烦棕炎凹冷佛捉揪甸签伶膘鼎揽只沥壮懦骂品州焉痊筋肯俄普浪编译原理第9章(清华大学)编译原理第9章(清华大学)。