西安电子科技大学编译原理04-3

14.4符号表简介符号表的作用：连接声明与引用的桥梁，记住每个符号的相关信息，如作用域和类型等，帮助编译的各个阶段正确有效地工作。符号表的基本目标：有效记录信息、快速准确查找。即如下基本要求：•正确存储各类信息；•适应不同阶段的需求；•便于有效地进行查找、插入、删除和修改等操作；•空间可以动态扩充。24.4.1符号表条目逻辑上讲：每个声明的符号在符号表中占据一行，称为一个条目，用于存放符号的相关信息（包括其名字）。•条目内容：名字＋属性。•符号表中的内容（条目种类）：保留字、标识符、特殊符号（包括算符、分隔符等）等等。•多个子表：(1)不同类别的符号可以存放在不同的子表中，如变量名表、过程名表、保留字表等。(2)每个作用域一个子表•查询符号的依据：组合关键字34.4.1符号表条目（续）为C/C++构造的符号表中，组合关键字至少应该包括三项：名字＋作用域＋类型（符号种类）1.若一个名字x在同一作用域中有多个（正确）声明，则引用x时需要根据上下文确定x到底指哪个对象。2.因此有些程序设计语言中，不允许这样的声明，以简化编译时的处理。//C代码片段...intx;{//引用x}关于组合关键字：intx;structx{doubley,z;};44.4.2构成名字的字符串的存储方式直接存储：定长数据名字属性名字属性sort#a#readarray#draw_a_red_line_for_object_a#↑101sortareadarraydraw_a_red_line_for_object_a↑101间接存储：变长数据sortproc…aint…readarrayproc…draw_a_red_line_for_object_aboolean…101proc…106int…108proc…118boolean…101/4proc…105/1int…106/9proc…115/28boolean…5名字的间接存储方法可以推广到任意属性，为解决复杂信息的存储问题提供了借鉴，即：•任何一个复杂的属性，均可以为其另辟空间（空间本身可以是任意复杂结构）•并将此空间的存储位置（指针）保存在该属性在条目中的对应位置即可。任何复杂结构4.4.2构成名字的字符串的存储方式关键字属性X…空间共享64.4.3名字的作用域源程序中的名字可以出现在不同的范围内，并且可以具有不同的意义。1.两种划分范围的方式：并列的和嵌套的。2.不同的语言采用不同的方式：如Pascal的过程定义可以是嵌套的，而C的过程定义是并列的；但程序块既可嵌套亦可并列。3.名字的作用域：名字在哪个范围内起作用。在并列的两个范围内声明的名字的作用域互不相干；在嵌套的两个范围内声明的名字，其作用域就需要制定规则（名字的作用域规则）来限定，以使得任何一个名字在任何范围内涵义都是无二义的。74.4.3名字的作用域（续1）2最近嵌套规则（mostcloselynested）：以程序块为例，也适用于过程。1.程序块B中声明的名字的作用域包括B；2.如果名字x未在B中声明，那么B中x的出现是在外围程序块B’的x声明的作用域中，即B'满足：•B'有x的声明，并且•B'比其它任何含x声明的程序块更接近被嵌套的B。1静态作用域规则（static-scoperule）：编译时就可以确定名字的作用域。名字的作用域规则：规定一个名字在什么样的范围内应该表示什么意义。8通俗地讲，最近嵌套规则指：•(在名字声明处)从外向内看：一个名字的声明在离其最近的内层、包括声明所在层起作用，•（在名字引用处）从内向外看：它处在所遇到的第一个声明该名字的作用域中。例子：找张三本班张三；软件学院张三；西电张三；…4.4.3名字的作用域（续2）94.4.3名字的作用域（续3）例4.29符合作用域规则的C程序。voidmain(){inta=0,b=0;/*B0层*/}声明作用域inta=0B0–B2intb=0B0–B1intb=1B1-B3inta=2B2intb=3B3{intb=1;/*B1层，被B0嵌套*/}{inta=2,c=4,d=5;/*B2层，被B1嵌套*/}{intb=3;/*B3层，与B2并列*/}printf(%d%d\n,a,b);printf(%d%d\n,a,b);printf(%d%d\n,a,b);printf(%d%d\n,a,b);/*结果为：0，0*//*结果为：0，1*//*结果为：0，3*//*结果为：2，1*/123456789101112104.4.4线性表为正确反映名字的作用域，线性表应具有栈特征，即符号的加入和删除，均在线性表的一端（表头）进行。线性表上的操作：关键字=名字＋作用域；查找：从表头(栈顶)开始，遇到的第一个符合条件的名字；插入：先查找，再加入在表头（栈顶）；aB00#bB00bB11aB22cB24dB251voidmain()2{inta=0,b=0;//B03{intb=1;//B14{inta=2,c=4,d=5;}//B27{intb=3;}//B311}}114.4.4线性表（续1）删除：(a)暂时：将在同一作用域的名字同时摘走，适当保存；(b)永久：将在同一作用域的名字同时摘走，不再保存。修改：先查找，修改第一个遇到的符合条件的名字的信息。bB331voidmain()2{inta=0,b=0;//B03{intb=1;//B14{inta=2,c=4,d=5;}//B27{intb=3;}//B311}}aB00#bB00bB11aB22cB24dB25124.4.4线性表（续2）线性表上操作的效率（n个条目）：查找一个名字：成功查找(平均)：(n+1)/2不成功查找：n插入一个新名字：查找n次，再加入到表头。xii1建立x个条目的符号表(最坏)：c=cx(x+1)/2134.4.5散列表1散列表的构成将线性表分成m个小表。构造hash函数，使符号均匀散布在m个子表中。若散列均匀，则时间复杂度会降到原线性表的1/m。名字挂在两个链上(便于删除操作)：1.散列链(hashlink)：链接所有具有相同hash值的元素，表头在表头数组中；2.作用域链(scopelink)：链接所有在同一作用域中的元素，表头在作用域表中。S1、S2、S4在同一作用域S3在另一作用域01ikm-1S1S2S3S4其中：hash(S1)=hash(S2)=ihash(S3)=hash(S4)=k01ikm-1S1S2S3S4142散列表上的操作4.4.5散列表（续1）1.查找：首先计算符号的hash值k，然后进入下标为k的子表，在该子表中沿hashlink，象查找单链表中的名字一样查找。2.插入：首先查找，以确定要插入的名字是否已在表中，若不在，则要分别沿hashlink和scopelink插入到两个链中，方法均是插在表头，即两个表均可看作是栈。3.删除：把以作用域链连在一起的所有元素从当前符号表中删除。（如果是临时删除，则保留作用域链所链的子表，下次使用时直接加入到散列链中即可）。15012325...b=1B1b=0B0a=2B2a=0B04.4.5散列表（续2）设：hash(s)=ord(s)-ord('a')1voidmain()2{inta=0,b=0;//B03{intb=1;//B14{inta=2,c=4,d=5;}//B27{intb=3;}//B311}}分析到B2中：B0B0^#B1B1^#B2B2^#B3B3^#d=5B2c=4B2作用域表示作用域标识作用域链表头{直接嵌套的作用域}[phone]...b=1B1b=0B0a=2B2a=0B04.4.5散列表（续2）设：hash(s)=ord(s)-ord('a')1voidmain()2{inta=0,b=0;//B03{intb=1;//B14{inta=2,c=4,d=5;}//B27{intb=3;}//B311}}B0B0^#B1B1^#B2B2^#B3B3^#退出B2时：重新整理，得下页d=5B2c=4B217012325...b=1B1b=0B0a=2B2a=0B04.4.5散列表（续2）设：hash(s)=ord(s)-ord('a')1voidmain()2{inta=0,b=0;//B03{intb=1;//B14{inta=2,c=4,d=5;}//B27{intb=3;}//B311}}B0B0^#B1B1^#B2B2^#B3B3^#退出B2时：c=4B2d=5B218012325...b=1B1b=0B0a=2B2a=0B04.4.5散列表（续2）设：hash(s)=ord(s)-ord('a')1voidmain()2{inta=0,b=0;//B03{intb=1;//B14{inta=2,c=4,d=5;}//B27{intb=3;}//B311}}B0B0^#B1B1^#B2B2^#B3B3^#进入B3中：b=3B3c=4B2d=5B2193散列函数的计算目标：使得符号均匀分布一种可行的hash函数方案：1.从串s=c1c2…ck的字符确定正整数h：令：h0=0,计算：hi=αhi-1+ci,1≤i≤k,得到：h=hkα=1或α是素数，如α=65599。2.取一素数m,令h=hmodm。思考题：根据上述方法，设计一个hash函数并测试之。根据测试结果讨论各参数值对函数结果的影响。关键：hash:string→integer203散列函数的计算（续1）#includeiostream.hconstintPRIME=211;constintEOS='\0';inthashpjw(char*s){char*p;unsignedh=0,g;for(p=s;*p!=EOS;p++){h=(h4)+(*p);if(g=h&0xf0000000){h=h^(g24);h=h^g;}}returnh%PRIME;}(1)为每行语句写注释；(2)写出此函数的计算公式；(3)若参数是abcd，试给出返回值。思考题（P177）：对于下列函数：