编译原理 符号表14.ppt

1、表格管理,种类 符号表、关键字表、层次表、常数表 关键字表 表项结构 关键字标识 (整数，如 WHILE，IF ) 关键字名字 (字符串，如while，if) 常用的操作： int IsKeyword( char Name );,层次表,保存各级分程序、循环语句、条件语句的有关信息 如：局部名字、转移标号等 辅助标识符的管理,符号表,保存名字及其属性 名字：变量名，过程名，标号名和常数名 属性：种类，类型，存储类别，作用域等 作用 绑定的完成、空间分配、 特殊语法现象、语义合法性检查,符号表的功能,建立表项 以标识符为关键字 属性的设置与引用 类型、作用域、存储类别、地址等,符号表的实现,实现

2、方法： 线性表、排序表、散列表（哈希） 特殊问题 结构成员、函数参数、分程序结构 性能 优先考虑查找的效率,6,第9章 符号表,9.1 符号表的作用和地位 9.2 符号的主要属性及作用 9.3 符号表的组织,符号表的作用和地位语义检查的依据和目标代码生成阶段地址分配的依据,属性信息：存放语言程序中出现的有关标识符的属性信息，在编译的不同阶段都要用到。 语义检查：在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的说明是否一致）和产生中间代码。 存诸分配：在目标代码生成阶段，当对符号名进行地址分配时，符号表是地址分配的依据。 对一个多遍扫描的编译程序，因为每遍所关心的信息

3、各有差异，所用的符号表内容也往往各有不同。,一张符号表的每一项(或称入口)包含两大栏（或称区段、字域），即名字栏和信息栏。 名字栏(NAME) 信息栏（INFORMATION） 第1项（入口1） 第2项（入口2） 第n项（入口n） 信息栏包含许多子栏和标志位，用来记录相应名字和种种不同属性，由于查填符号表一般是通过匹配名字来实现的，因此，名字栏也称主栏，主栏的内容称为关键字（key word）。,在整个编译期间，对于符号表的操作大致可归纳为五类： 往表中填入一个新的名字； 对给定名字，查询名字是否已在表中； 对给定名字，访问它的某些信息； 对给定名字，更新它的某些信息； 删除一个或一组无用的项

4、。 不同种类的表格所涉及的操作往往也是不同 的。上述五个方面只是一些基本的共同操作。,9.2 符号属性(信息）,几种通常都是需要的。 1 符号名 2 符号的类型 3 符号的存储类别 4 符号的作用域及可视性 5 符号变量的存储分配信息 6 符号的其它属性 数组内情向量 记录 结构型的成员信息函数及过程的形参,符号表的组织,总体组织和表项属性信息组织 第一种： 把属性种类完全相同的那些符号组在一起，构造出表项是分别为等长的多个符号表 第二种：把所有语言中的符号都组织在一张符号表中。组成一张包括了所有属性的庞大的符号表 第三种：折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都

5、有比较多的相同属性。,编译程序按名字的不同种属分别使用许多符号表，如常数表、变量名表、过程名表等等。 PROCEDURE INCWAP（M，N） BEGIN 10：KM1 MM4 NK END 经编译头三阶段后所产生的主要表格有：符号名表SNT、常数表CT、入口名表ENT、标号表LT和四元式表QT,符号名表SNT NAME INFORMATION （1）M 参数，整数，变量 （2）N 参数，整数，变量 （3）K 整数，变量 常数表CT 值（VALUE） (1) 1 (2) 4,入口名表ENT NAME INFORMATION （1）INCWAP 二目子程序，入口QT(1) /*记录入口名INC

6、WAP的入口地址 标号表LT LABLE INFORMATION （1）10 QT(4) /*记录了标号10对应的四元式序列号 四元式表QT,四元式表QT,L1: if a y goto L5； goto L1； L5: x := z + 1； goto L3； L4: x := y； goto L1； Lnext:,例：,符号表项的排列,符号表作为一个多元组，表中元组的排列组织是构造符号表的重要成分。在编译程序的整个工作过程中，符号表被频繁地用来建立表项，找查表项，填充和引用表项的属性。因此表项的排列组织对该系统运行的效率起着十分重要的作用。在编译程序中，符号表项的组织传统上采用三种构造方法

7、。即线性法，排序组织法及散列法。,关键字域的组织,符号表的关键字域（段） 符号名、符号本身 (1) 等长关键字域（段）符号表 (P215图9.9) (2) 不等长关键字段符号表采用关键字池的索引结构。 (P215图9.10),分程序结构的符号表,对于具有分程序型结构的语言程序，不同层次分程序中定义的标识符号具有不同的作用域和不同的可视性规则。通常对于具有分程序结构的语言可用两种方式组织它们的符号表： (1)对每个分程序建立一个独立的分表结构的符号表； (2)把各分程序符号组织在一张单表结构的符号表中。,分表结构的组织管理,基本思想：每当编译程序扫描到一个分程序结构开始时，为该分程序建立一张符号

8、表，在该分程序中定义的标识符，都被登录在该符号表中。 而当编译程序扫描到一个分程序的结束时，编译程序释放为该分程序所建立的符号表。 这种符号表的分表结构与源程序的分程序层次结构一一对应,P227图9.23,单表结构的组织管理,基本思想：所有分程序中定义的标识符都集中在单张符号表中。为了实现分程序构造中标识符的作用域和可视性规则的要求,在符号表中可设立一个属性域用来登录符号所在分程序的层次。 进入分程序时，层次要增加一层。在退出一个分程序时，层次降低一层，且需要把符号表中，所有在退出的分程序中登录的符号项清除。,P228图9.25,嵌套结构型程序设计语言(Pascal)的特点,可采用的办法之一：

9、 将其符号表设计为栈符号表，当新的名字出现总是从栈顶填入。 查找操作从符号表的栈顶往底部查（保证先查最近出现的名字）。 因为程序是分层的，并且一个过程结束时将释放相应的子符号表，因此查找范围与线性表比相对要小一些。,嵌套结构型程序设计语言(Pascal)的特点,可采用的办法之二： 引入一个显示(DISPLAY)层次关系表，称为过程的嵌套层次表。其作用是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置(相对地址)。DISPLAY表也是一个栈，栈顶指针为level。当进入一个新过程时，level增加1；每当退出一个过程时，level减1。DIS

10、PLAYlevel总是指向当前正在处理的最内层的过程的子符号表在栈符号表中的起始位置。,嵌套结构型程序设计语言(Pascal)的特点,可采用的办法之三： 在符号表的信息栏中引入一个指针域(previous)用以链接它在同一过程内的前一域名字在表中的下标(相对位置)。每一层的最后一个域名字，其previous之值为0。这样，每当需要查找一个新名字时，就能通过DISPLAY找出当前正在处理的最内层的过程及所有外层的子符号表在栈符号表中的位置。然后，通过previous可以找到同一过程内的所有被说明的名字。,说明部分的分析与处理,对每个过程说明的对象（变量，常量和过程）造名字表 登录标识符的属性。

11、填写标识符的所在层次、属性和分配的相对位置。标识符的属性不同时，所需填入的信息也不同。 登录信息由ENTER过程完成。,课本P21,说明部分的分析与处理（程序）,说明类型的定义： object= (constant, variable,procedure) （定义纯量/枚举类型） 名字表的定义 table:array0.txmax of record name:alfa; case kind:object of constant:(val:integer); variable,procedure:(level,adr,size : integer);,例程序说明部分为： CONST A=35，

12、B=49；VAR C，D，E；PROCEDURE P；VAR G ；,名字 类型 层次/值 地址 存储空间,Const（常量）无层次,对应符号表,tx : table表的下标指针,是以值参数形式使用的。 dx: 计算每个变量在运行栈中相对本过程基地址的偏移量 ，放在table表中的adr域，生成目标代码时再放在code中的a域,参考PL/0编译程序的Block函数及其递归调用,变量定义语句的处理,语法：: := var ， ； 程序： if sym=varsym then begin getsym; repeat vardeclaration; (*变量说明处理*) while sym=com

13、ma do begin getsym; vardeclaration end; if sym=semicolon then getsym else error(5) until symident; end;,变量说明处理,procedure vardeclaration; begin if sym=ident then begin enter(variable); getsym end else error(4) end (*vardeclaration*);,过程ENTER的实现,tx ：table表的指针 procedure enter(k:object ); begin (* enter

14、 object into table *) tx:=tx+1; with tabletx do (* 开域语句 *) begin name:=id;(*表示:=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: begin level:=lev; (* 表示table

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

16、行语法分析 语义分析 当遇到标识符的引用时就调用 POSITION函数查TABLE表，看是否有过正确定义，若已有，则从表中取相应的有关信息，供代码的生成使用。若无定义则错。 当语法语义正确时，就生成相应语句功能的目标代码,赋值语句的处理,if sym = ident then begin i:= position(id); if i= 0 then error(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,代码生成,代码生成是由过程GEN完成。 GEN有3个参