9_符号表.ppt

《9_符号表.ppt》由会员分享，可在线阅读，更多相关《9_符号表.ppt（37页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、 表格管理表格管理n n种类种类n n符号表、关键字表、层次表、常数表符号表、关键字表、层次表、常数表关键字表关键字表n n表项结构表项结构n n关键字标识关键字标识(整数，如整数，如WHILE，IF)n n关键字名字关键字名字(字符串，如字符串，如while，if)n n常用的操作：常用的操作：n nintIsKeyword(charName);层次表层次表n n保保存存各各级级分分程程序序、循循环环语语句句、条条件语句的有关信息件语句的有关信息n n如：局部名字、转移标号等如：局部名字、转移标号等n n辅助标识符的管理辅助标识符的管理符号表符号表n n保存名字及其属性保存名字及其属性n n

2、名字：变量名，过程名，标号名名字：变量名，过程名，标号名和常数名和常数名n n属性：种类，类型，存储类别，属性：种类，类型，存储类别，作用域等作用域等n n作用作用n n绑定的完成、空间分配、绑定的完成、空间分配、n n特殊语法现象、语义合法性检查特殊语法现象、语义合法性检查符号表的功能符号表的功能n n建立表项建立表项n n以标识符为关键字以标识符为关键字n n属性的设置与引用属性的设置与引用n n类型、作用域、存储类别、地址等类型、作用域、存储类别、地址等符号表的实现符号表的实现n n实现方法：实现方法：n n线性表、排序表、散列表（哈希）线性表、排序表、散列表（哈希）n n特殊问题特殊问

3、题n n结构成员、函数参数、分程序结构结构成员、函数参数、分程序结构n n性能性能n n优先考虑查找的效率优先考虑查找的效率第第9 9章章 符号表符号表9.1 9.1 符号表的作用和地位符号表的作用和地位9.2 9.2 符号的主要属性及作用符号的主要属性及作用9.3 9.3 符号表的组织符号表的组织6符号表的作用和地位符号表的作用和地位语义检查的依据语义检查的依据和目标代码生成阶段地址分配的依据和目标代码生成阶段地址分配的依据 属属性性信信息息：存存放放语语言言程程序序中中出出现现的的有有关关标标识识符符的的属性信息，在编译的不同阶段都要用到。属性信息，在编译的不同阶段都要用到。语语义义检检查

4、查：在在语语义义分分析析中中，符符号号表表所所登登记记的的内内容容将将用用于于语语义义检检查查（如如检检查查一一个个名名字字的的使使用用和和原原先的说明是否一致）和产生中间代码。先的说明是否一致）和产生中间代码。存存诸诸分分配配：在在目目标标代代码码生生成成阶阶段段，当当对对符符号号名名进进行地址分配时，符号表是地址分配的依据。行地址分配时，符号表是地址分配的依据。对对一一个个多多遍遍扫扫描描的的编编译译程程序序，因因为为每每遍遍所所关关心心的的信信息息各各有有差差异异，所所用用的的符符号号表表内内容容也也往往往往各各有有不同。不同。一一一一张张张张符符符符号号号号表表表表的的的的每每每每一一

5、一一项项项项(或或或或称称称称入入入入口口口口)包包包包含含含含两两两两大大大大栏栏栏栏（或或或或称称称称区区区区段段段段、字域），即字域），即字域），即字域），即名字栏名字栏名字栏名字栏和和和和信息栏信息栏信息栏信息栏。名字栏名字栏名字栏名字栏(NAME)NAME)信息栏（信息栏（信息栏（信息栏（INFORMATIONINFORMATION）第第第第1 1项（入口项（入口项（入口项（入口1 1）第第第第2 2项（入口项（入口项（入口项（入口2 2）第第第第n n项（入口项（入口项（入口项（入口n n）信信信信息息息息栏栏栏栏包包包包含含含含许许许许多多多多子子子子栏栏栏栏和和和和标标标标志志

6、志志位位位位，用用用用来来来来记记记记录录录录相相相相应应应应名名名名字字字字和和和和种种种种种种种种不不不不同同同同属属属属性性性性，由由由由于于于于查查查查填填填填符符符符号号号号表表表表一一一一般般般般是是是是通通通通过过过过匹匹匹匹配配配配名名名名字字字字来来来来实实实实现现现现的的的的，因因因因此此此此，名名名名字字字字栏栏栏栏也也也也称称称称主主主主栏栏栏栏，主主主主栏栏栏栏的的的的内内内内容容容容称称称称为为为为关关关关键字（键字（键字（键字（keywordkeyword）。）。）。）。在在整整个个编编译译期期间间，对对于于符符号号表表的的操操作作大大致致可可归归纳为五类：纳为五

7、类：往表中填入一个新的名字；往表中填入一个新的名字；对给定名字，查询名字是否已在表中；对给定名字，查询名字是否已在表中；对给定名字，访问它的某些信息；对给定名字，访问它的某些信息；对给定名字，更新它的某些信息；对给定名字，更新它的某些信息；删除一个或一组无用的项。删除一个或一组无用的项。不同种类的表格所涉及的操作往往也是不同不同种类的表格所涉及的操作往往也是不同的。上述五个方面只是一些基本的共同操作。的。上述五个方面只是一些基本的共同操作。9.2 9.2 符号属性符号属性(信息）信息）几种通常都是需要的。几种通常都是需要的。1符号名符号名2符号的类型符号的类型3符号的存储类别符号的存储类别4符

8、号的作用域及可视性符号的作用域及可视性5符号变量的存储分配信息符号变量的存储分配信息6符号的其它属性符号的其它属性数组内情向量数组内情向量记录记录结构型的成员信息结构型的成员信息函数及过程的形参函数及过程的形参符号表的组织符号表的组织总体组织和表项属性信息组织总体组织和表项属性信息组织第一种：第一种：把属性种类完全相同的那些符号组把属性种类完全相同的那些符号组在一起，构造出表项是分别为等长的多个在一起，构造出表项是分别为等长的多个符号表符号表第二种：把所有语言中的符号都组织在一张第二种：把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞符号表中。组成一张包括了所有属性的庞大的符

9、号表大的符号表第三种：折衷方式是根据符号属性相似程度第三种：折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。号都有比较多的相同属性。编译程序按名字的不同种属分别使用许多符号编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等。表，如常数表、变量名表、过程名表等等。PROCEDUREINCWAP（M，N）BEGIN10：KM1MM4NKEND经编译头三阶段后所产生的主要表格有：符经编译头三阶段后所产生的主要表格有：符号名表号名表SNT、常数表常数表CT、入口名表入口名表ENT、标标号表号表LT和

10、四元式表和四元式表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四元式表四元式表QTn nL1:ifabgot

11、oL2；n ngotoLnext；n nL2:ifcygotoL5；n ngotoL1；n nL5:x:=z+1；n ngotoL3；n nL4:x:=y；n ngotoL1；n nLnext:例：例：符号表项的排列符号表项的排列符符号号表表作作为为一一个个多多元元组组，表表中中元元组组的的排排列列组组织织是是构构造造符符号号表表的的重重要要成成分分。在在编编译译程程序序的的整整个个工工作作过过程程中中，符符号号表表被被频频繁繁地地用用来来建建立立表表项项，找找查查表表项项，填填充充和和引引用用表表项项的的属属性性。因因此此表表项项的的排排列列组组织织对对该该系系统统运运行行的的效效率率起起着

12、着十十分分重重要要的的作作用用。在在编编译译程程序序中中，符符号号表表项项的的组组织织传传统统上上采采用用三三种种构构造造方方法法。即即线线性性法法，排排序序组组织织法法及及散散列列法。法。关键字域的组织关键字域的组织符号表的关键字域（段）符号表的关键字域（段）符号名、符号本身符号名、符号本身(1)等长关键字域（段）符号表等长关键字域（段）符号表(P215图图9.9)(2)不不等等长长关关键键字字段段符符号号表表采采用用关关键键字字池的索引结构。池的索引结构。(P215图图9.10)分程序结构的符号表分程序结构的符号表对对于于具具有有分分程程序序型型结结构构的的语语言言程程序序，不不同同层层次

13、次分分程程序序中中定定义义的的标标识识符符号号具具有有不不同同的的作作用用域域和和不不同同的的可可视视性性规规则则。通通常常对对于于具具有有分分程程序序结结构的语言可用两种方式组织它们的符号表：构的语言可用两种方式组织它们的符号表：(1)对对每每个个分分程程序序建建立立一一个个独独立立的的分分表表结结构构的的符号表；符号表；(2)把把各各分分程程序序符符号号组组织织在在一一张张单单表表结结构构的的符符号表中。号表中。分表结构的组织管理分表结构的组织管理基本思想：每当编译程序扫描到一个分基本思想：每当编译程序扫描到一个分程序结构开始时，为该分程序建立一张符程序结构开始时，为该分程序建立一张符号表

14、，在该分程序中定义的标识符，都被号表，在该分程序中定义的标识符，都被登录在该符号表中。登录在该符号表中。而当编译程序扫描到一个分程序的结束而当编译程序扫描到一个分程序的结束时，编译程序释放为该分程序所建立的符时，编译程序释放为该分程序所建立的符号表。号表。这种符号表的分表结构与源程序的分程这种符号表的分表结构与源程序的分程序层次结构一一对应序层次结构一一对应P227图9.23单表结构的组织管理单表结构的组织管理基基本本思思想想：所所有有分分程程序序中中定定义义的的标标识识符符都都集集中中在在单单张张符符号号表表中中。为为了了实实现现分分程程序序构构造造中中标标识识符符的的作作用用域域和和可可视

15、视性性规规则则的的要要求求,在在符符号号表表中中可可设设立立一一个个属属性性域域用用来来登登录录符号所在分程序的层次。符号所在分程序的层次。进进入入分分程程序序时时，层层次次要要增增加加一一层层。在在退退出出一一个个分分程程序序时时，层层次次降降低低一一层层，且且需需要要把把符符号号表表中中，所所有有在在退退出出的的分分程程序序中中登登录录的符号项清除。的符号项清除。P228图9.25嵌套结构型程序设计语言嵌套结构型程序设计语言(Pascal)Pascal)的特点的特点可采用的办法之一：可采用的办法之一：将将其其符符号号表表设设计计为为栈栈符符号号表表，当当新新的的名名字字出出现现总是从栈顶填

16、入。总是从栈顶填入。查查找找操操作作从从符符号号表表的的栈栈顶顶往往底底部部查查（保保证证先先查查最近出现的名字）。最近出现的名字）。因因为为程程序序是是分分层层的的，并并且且一一个个过过程程结结束束时时将将释释放放相相应应的的子子符符号号表表，因因此此查查找找范范围围与与线线性性表表比相对要小一些。比相对要小一些。嵌套结构型程序设计语言嵌套结构型程序设计语言(Pascal)Pascal)的特点的特点可采用的办法之二：可采用的办法之二：引引入入一一个个显显示示(DISPLAY)层层次次关关系系表表，称称为为过过程程的的嵌嵌套套层层次次表表。其其作作用用是是为为了了描描述述过过程程的的嵌嵌套套层

17、层次次，指指出出当当前前正正在在活活动动着着的的各各嵌嵌套套的的过过程程（或或函函数数）相相应应的的子子符符号号表表在在栈栈符符号号表表中中的的起起始始位位置置(相相对对地地址址)。DISPLAY表表也也是是一一个个栈栈，栈栈顶顶指指针针为为level。当当进进入入一一个个新新过过程程时时，level增增加加1；每每当当退退出出一一个个过过程程时时，level减减1。DISPLAYlevel总总是是指指向向当当前前正正在在处处理理的的最最内内层层的的过过程程的的子子符符号号表表在在栈符号表中的起始位置。栈符号表中的起始位置。嵌套结构型程序设计语言嵌套结构型程序设计语言(Pascal)Pasca

18、l)的特点的特点可采用的办法之三：可采用的办法之三：在在 符符 号号 表表 的的 信信 息息 栏栏 中中 引引 入入 一一 个个 指指 针针 域域(previous)用用以以链链接接它它在在同同一一过过程程内内的的前前一一域域名名字字在在表表中中的的下下标标(相相对对位位置置)。每每一一层层的的最最后后一一个个域域名名字字，其其previous之之值值为为0。这这样样，每每当当需需要要查查找找一一个个新新名名字字时时，就就能能通通过过DISPLAY找找出出当当前前正正在在处处理理的的最最内内层层的的过过程程及及所所有有外外层层的的子子符符号号表表在在栈栈符符号号表表中中的的位位置置。然然后后，

19、通通过过previous可可以以找找到到同同一过程内的所有被说明的名字。一过程内的所有被说明的名字。说明部分的分析与处理说明部分的分析与处理n n对每个过程对每个过程说明的对象说明的对象（变量变量，常量常量和和过过程程）造名字表造名字表n n登录标识符的属性。登录标识符的属性。n n填写填写标识符的标识符的所在所在层次层次、属性属性和分配的和分配的相对位置相对位置。标识符的属性不同时，所需。标识符的属性不同时，所需填入的信息也不同。填入的信息也不同。n n登录信息由登录信息由ENTERENTER过程完成。过程完成。课本课本课本课本P21P21说明部分的分析说明部分的分析与处理与处理（程程序）序

20、）n n说明类型的定义：说明类型的定义：object=(constant,variable,procedure)（定义定义纯量纯量/枚举枚举类型）类型）n n名字表的定义名字表的定义table:array0.txmaxofrecordname:alfa;casekind:objectofconstant:(val:integer);variable,procedure:(level,adr,size:integer);例程序说明部分为：例程序说明部分为：CONSTA=35，B=49；VARC，D，E；PROCEDUREP；VARG；名字名字 类型类型 层次层次/值值 地址地址 存储空间存储空间

21、Const（常量）常量）无无层次层次对应符号表对应符号表n ntx:table表的下标指针表的下标指针,是以是以值参数值参数形式使用的。形式使用的。n ndx:计算每个变量在运行栈中相对本计算每个变量在运行栈中相对本过程过程基地址基地址的偏移量的偏移量，放在，放在table表表中的中的adr域，域，生成目标代码生成目标代码时再时再放在放在code中的中的a域域参考参考参考参考PL/0PL/0PL/0PL/0编译程序的编译程序的编译程序的编译程序的BlockBlockBlockBlock函数及其递归调用函数及其递归调用函数及其递归调用函数及其递归调用变量定义语句的处理变量定义语句的处理语法：语法

22、：语法：语法：:=:=varvar ，；程序：程序：程序：程序：if sym=if sym=varsymvarsym then begin then begin getsymgetsym;repeat repeat vardeclarationvardeclaration;(*;(*变量说明处理变量说明处理变量说明处理变量说明处理*)*)while sym=while sym=commacomma do begin do begin getsymgetsym;vardeclarationvardeclaration end;end;if sym=if sym=semicolonsemicolo

23、n then then getsymgetsym else error(5)else error(5)until sym until symidentident;end;end;变量说明处理变量说明处理 procedureprocedure vardeclaration;begin if sym=ident then begin enter(variable);getsym end else error(4)end(*vardeclaration*);过程过程ENTER的实现的实现n ntx：table表的指针表的指针n n procedure enter(k:object);begin (*

24、enter object into table*)tx:=tx+1;with tabletx do(*开域开域语句语句*)begin name:=id;(*表示表示tabletx.name:=id;*)kind:=k;(*表示表示tabletx.kind:=k;*)过程过程ENTER的实现的实现 case k of constant:begin if numamax then begin error(31);num:=0;end;val:=num;(*tabletx.val:=num;*)end;过程过程ENTER的实现的实现variable:beginlevel:=lev;(*表示表示tab

25、letx.level:=lev*)adr:=dx;(*表示表示tabletx.adr:=dx*)dx:=dx+1;end;procedur:level:=lev(*表示表示tabletx.level:=lev;*)end(*case*);endend(*enter*);PL/0PL/0编译程序编译程序nTable表的表的下标指针下标指针tx补充说明：补充说明：主程序主程序BLOCK第第1次次调用调用blockBLOCK（0，0，）0 0 .BLOCK BLOCK（LEV+1,TX，）(递归递归进入进入分程序分程序)LEVtxLEVtx（6）6 （9）1 tx是是BLOCK的的实际实际值参值参过

26、程体的处理过程体的处理n对对语句进行语句进行语法语法分析分析n语语义义分分析析 当当遇遇到到标标识识符符的的引引用用时时就就调调用用 POSITIONPOSITION函函数数查查TABLETABLE表表，看看是是否否有有过过正正确确定定义义，若若已已有有，则则从从表表中中取取相相应应的的有有关关信信息息，供代码的生成使用。供代码的生成使用。若无定义则错若无定义则错。n当当语语法法语语义义正正确确时时，就就生生成成相相应应语语句句功功能能的的目标代码目标代码赋值赋值语句的语句的处理处理 if sym=ident then begin i:=position(id);if i=0 then err

27、or(11)else if tablei.kind variable then begin error(12);i:=0 end;getsym;if sym=becomes then getsym else error(13);expression(fsys);if i 0 then with table i do gen(sto,lev-level,adr)end 代码生成代码生成n代码生成是由过程代码生成是由过程GEN完成。完成。nGEN有有3个个参数参数，分别代表目标代码的，分别代表目标代码的功能码功能码，层差层差和和位移量位移量。例如。例如 gen(opr,0,16);gen(sto,lev-level,adr)lev：当前当前处理的处理的过程过程层次层次 level：被引用变量或过程所在被引用变量或过程所在层次层次 CX：为目标代码为目标代码code数组的下标指针数组的下标指针结构变换，结构变换，地址返填地址返填nif c then s getsym;n condition;n if sym=thensymn then getsymn else error(16);n cx1:=cx;n gen(jpc,0,0)n statement();n codecx1.a:=cx