编译原理-第八章——符号表.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第八章 符号表,符号表用来存放语言程序中出现的有关标识符的属性信息。,符号表每一项包含两部分：名字（标识符），此名字的有关信息,符号表的功能：,1.,收集符号属性。,2.,上下文语义的合法性检查的依据。,3.,作为目标代码生成阶段地址分配的依据。,种属：简单变量，数组，过程,类型：整，实，布尔,符号表的组织与作用,一张符号表的每一项（入口）包含两大栏（区域、字段）：名字栏和信息栏。,名字栏称主栏，主栏的内容称为关键字，一般不允许重名。,名字栏,（,NAME,）,信息栏（,INFORMATION,）,第,1,项（入口,1,）,第,2,项（入口,2,）,第,n,项（入口,n,）,符号表的组织方式,1.,各项各栏所占存储单元的长度都是固定的，每栏的内容可直接填写在有关区段。,NAME,INFORMATION,，,6,，,4,S,A,M,P,L,E,L,O,O,P,2.,用间接方式安排名字栏。,NAME,INFORMATION,S,A,M,P,L,E,L,O,O,P,6,4,对信息栏也可做类似处理，把一些共同属性直接登记在符号表信息栏，而把特殊属性登记在别的地方。,整理与查找,线性查找、二叉树和杂凑技术,1.,线性表,每一项按先来者先填。查找时从表的第一项开始顺序查找。,要填进新名字时，先查找表格，已在表中则不填，报重名错；若不在表中，填进,AVAILABLE,所在位置，,AVAILABLE,指向下一空白项。,一张含,n,项的线性表，查找其中某项，平均做,n/2,次比较。,自适应线性表，添加指示器，将所有项按“最新最近”访问原则连成一条链。,2.,对折查找与二叉树,将表格中项按名字“大小”顺序排列。“名字大小”指名字的内码二进值。,对折查找一项最多只需,1,log2N,次比较。,将符号表组织成一棵二叉树。每项是一个结点，结点主栏的内码值视为该结点的值。任何结点,P,的右枝,(RIGHT),的所有结点值小于,P,的值，而左枝,(LEFT),的值均大于,P,的值。,3.,杂凑技术,构造地址函数,H,。对任何名字,SYM,，,H(SYM),取值,0,N-1,之间，从,H(SYM),获得,SYM,在表中的位置。,如：可取,N,为质数，,H(SYM),定义为,SYM/N,的余数。,如何解决“地址冲突”,?,可使用一张杂凑（链）表将所有相同杂凑值的符号名连成一串。,名字的作用范围,名字的作用范围和它所处的那个过程相联系。,FORTRAN,的符号表组织,将局部名登记在表格区的一端，全局名登记在表格区的另一端。,Pascal,的符号表组织,将其符号表设计为栈符号表，当新的名字出现总是从栈顶填入。,引入一个显示（,DISPLAY）,层次关系表，称为过程的嵌套层次表。其作用是为了描述过程的嵌套层次，指出当前正在活动着的各嵌套的过程（或函数）相应的子符号表在栈符号表中的起始位置（相对地址）。,在符号表的信息栏中引入一个指针域（,previous）,用以链接它在同一过程内的前一域名字在表中的下标（相对位置）。,Program B1(input,output);,const a=10;,var,b,c:integer,;,e:real,;,Program B2();,var,f:int,;,NAME,INFORMATION,PREVIOUS,7,6,f,7,5,B2,0,4,e,5,3,c,4,2,b,3,1,a,2,SP,TOP,1,6,DISPLAY,