符号表简介.ppt
《符号表简介.ppt》由会员分享,可在线阅读,更多相关《符号表简介.ppt(41页珍藏版)》请在三一文库上搜索。
1、4.3 符号表简介,符号表 名字(直接存储) 属性 sort proc, . a int, . readarray proc, . draw_a_red_line_for_object_a boolean, . 实现符号表的数据结构 线性表和散列表,1,4.3 符号表简介,线性表: 实现符号表最简单最容易的数据结构 可以通过数组或者单链表来实现 线性表应具有栈的性质,即符号的加入和删除均在线性表的一端进行,2,3,4.3 符号表简介,Example: 符号表的线性组织,1 void main() 2 int a=0, b=0; / B0 3 int b=1; / B1 4 int a=2, c
2、=4, d=5; / B2 7 int b=3; / B3 11 12 ,名字 属性(静态作用域,type) a=0 B0,int b=0 B0,int b=1 B1,int a=2(或b=3) B2 ,int (或B3,int) c=4 B2 ,int d=5 B2 ,int,顶 在 下 的 栈,4,4.3 符号表简介,Example:,线性表上的操作: 查找:从栈顶开始查找,遇到的第一个符合条件的名字即可 插入:先查找,若查到,则返回该名字在符号表中的位置; 否则加入到栈顶,名字 属性(静态作用域,type) a=0 B0,int b=0 B0,int b=1 B1,int a=2(或b=
3、3) B2 ,int (或B3,int) c=4 B2 ,int d=5 B2 ,int,顶 在 下 的 栈,5,4.3 符号表简介,Example:,名字 属性(静态作用域,type) a=0 B0,int b=0 B0,int b=1 B1,int a=2 B2 ,int c=4 B2 ,int d=5 B2 ,int,顶 在 下 的 栈,线性表上的操作: 从某个作用域退出时,从栈顶把该作用域的所有名字全部摘走, 存放在一个不活动的临时表中,以备后用。 例:当分析从B2退出并进入B3时,栈中的条目a=2,d=5,c=4退出, 条目b=3进入。,b=3 B3,int,1 void main(
4、) 2 int a=0, b=0; / B0 3 int b=1; / B1 4 int a=2, c=4, d=5; / B2 7 int b=3; / B3 11 12 ,6,4.3 符号表简介,删除:(a)暂时:将在同一作用域的名字同时摘走,适当保存;(b)永久:将在同一作用域的名字同时摘走,不再保存 线性表上操作的效率(n个条目): 成功查找(平均):n/2; 不成功查找:n 在符号表中插入n个名字和完成e次查找的时间复杂度为:n(n+e) 当n和e很大时,在线性表上进行查找效率低。,为了提高符号表查找效率:将线性表分成m个小表,构造hash函数,使名字均匀散布在子表中(散列表) 若散
5、列均匀,则时间复杂度会降到原线性表的1/m,7,4.3 符号表简介,8,4.3 符号表简介,散列表 如果散列均匀,查找时间复杂度较低至线性表的1/m,M个子表 M个子表的表头构成一个表头 数组 以散列函数的值(hash值)为下标 每个子表的组织与线性表相同 具有相同hash值得节点被散列 在相同的子表中 连接子表的链表被称为散列链,9,4.3 符号表简介,线性表中,相同作用域的名字会相对集中的存放在线性表的 某一段,进入或者退出某作用域时,此作用域的所有名字会 一同被摘走。,散列表中相同作用域的名字会被散列到不同的子表中,无法 同时摘走。,为了方便这种情况下条目的删除,需要为每个元素在原来散
6、列链(hash link)的基础上,再建立一个作用域链。,10,4.3 符号表简介,因此,散列表中有两个链: 散列链(hash link): 链接所有具有相同hash值的元素,表头在表头数组中; 作用域链(scope link):链接所有在同一作用域中的元素,表头在作用域链中。,S1 S2 S4在同一作用域 S3在另一作用域,作用域链,11,4.3 符号表简介,散列表上的操作 查找:首先计算散列函数,然后从散列函数所指示的入口进入某个线性表,在线性表中沿hash link,象查找单链表中的名字一样查找。 插入:首先查找,以确定要插入的名字是否已在表中,若不在,则要分别沿hash link和sc
7、ope link插入到两个链中,方法均是插在表头,即两个表均可看作是栈。 删除:把以作用域链连在一起的所有元素从当前符号表中删除,保留作用域链所链的子表,为后继工作使用(如果是临时删除,则下次使用时直接沿作用域链加入到散列链中即可)。,12,1 void main() 2 int a=0, b=0; / B0 3 int b=1; / B1 4 int a=2, c=4, d=5; / B2 7 int b=3; / B3 11 设:hash(s)=ord(s)-ord(a),退出B2进入B3:,进入B3:,分析在B2中:,13,4.3 符号表简介,散列函数的计算 hash: string i
8、nteger 减少冲突,分布均匀 充分考虑程序设计语言的特点 例:若有变量V001, V002, , V300,若以首字母的值作为hash值,会发生什么? 可行的hash函数计算方法: 从串s=c1c2ck的字符ci确定正整数h: 令: h0=0, 计算:hi=hi-1+ci, 1ik, =1或是素数,如=65599。 取一素数m, 令 hi=hi-1 mod m。,14,4.3 符号表简介,作业(P108):对于下列(散列)函数 #include const int PRIME=211; const int EOS=0; int hashpjw(char *s) char *p; unsig
9、ned h=0, g; for (p=s; *p!=EOS; p+) h = ( h 24 ); h = hg; return h%PRIME; (1) 为每行语句写注释; (2) 写出此函数的计算公式; (3) 若参数是“abcd“,试给出返回值。,15,4.4 声明语句的翻译,声明语句的作用是为可执行语句提供信息,以便 于其执行。对声明语句的处理,主要是将所需要 的信息正确地填写进合理组织的符号表中。,16,4.4 声明语句的翻译,变量的声明 变量的类型定义与声明 类型定义为编译器提供存储空间大小的信息, 变量声明为变量分配存储空间。 (简单数据类型是由程序设计语言预定义的,因此对简单变量
10、的声明一般不包括类型的定义) 组合数据的类型定义和变量声明有两种情况:定义与声明在一起,定义与声明分离。 定义确定存储空间,声明分配存储空间 简单数据类型的存储空间是已经确定的,如integer可以占4个字节,real可以占8个字节,char可以占1个字节等 组合数据类型变量的存储空间,需要编译器根据程序员提供的信息计算而定,17,4.4 声明语句的翻译,例:在Pascal程序中的类型定义与变量声明: 先定义后声明 type player = array12 of integer; matrix = array124 of char; var c, p : player; winner : b
11、oolean; (简单类型) display : matrix; movect : integer; (简单类型) 定义与声明同时 var c, p : array12 of integer; display : array124 of char; 强调: 简单变量声明中类型是预定义的; 组合变量声明中类型需自己定义。,定义了两个复杂类型,声明,18,4.4 声明语句的翻译,变量声明的语法制导翻译 变量声明的文法: D D ; D (1) | id : T (2) T int (3) | real (4) | array num of T (5) | T (6) (5)是数组类型的声明,其中的
12、数组元素个数由num表示,如num可以是5或10等。 (6)是指针类型的声明,其宽度(大小)是一个常量。数组元素的类型和指针所指对象的类型可以是任意合法类型。 可以声明多维数组:A :array d1 of array d2 of .array dn of int,19,4.4 声明语句的翻译,填写符号表信息的语法制导翻译 (1)DD;D (2)Did:T enter(id.name, T.type, offset); offset:=offset+T.width; (3)Tint T.type:=integer; T.width:=4; (4)Treal T.type:=real; T.wi
13、dth:=8; (5)Tarray num of T1 T.type:=array(num.val, T1.type); T.width:=num.val*T1.width; (6)TT1 T.type:=pointer(T1.type); T.width:=4; 全程量offset:记录当前符号存储的偏移量,初值设为0 属性.type和.width:变量的类型和所占据的存储空间 过程enter(name, type, offset):为type类型的变量name建立符号表条目,并为其分配存储空间(位置)offset,20,4.4 声明语句的翻译,例 声明的语法制导翻译:a : array 1
14、0 of int; x : int;(无分号),D D D ; D (1) | id : T (2) T int (3) | real (4) | array num of T (5) | T (6),21,4.4 声明语句的翻译,例 声明的语法制导翻译:a : array 10 of int; x : int;(无分号),序号 归约使用的产生式 语义处理结果 (1) T1int T1.type=integer T1.width=4,(1)DD;D (2)Did:T enter(id.name, T.type, offset); offset:=offset+T.width; (3)Tint
15、T.type:=integer; T.width:=4; (4)Treal,T.type:=real; T.width:=8; (5)Tarray num of T1 T.type:=array(num.val, T1.type); T.width:=num.val*T1.width; (6)TT1 T.type:=pointer(T1.type); T.width:=4;,D3,D1 ; D2,a : T2,x : T3,array 10 of T1,int,int,22,4.4 声明语句的翻译,例 声明的语法制导翻译:a : array 10 of int; x : int;(无分号),序
16、号 归约使用的产生式 语义处理结果 (1) T1int T1.type=integer T1.width=4 (2) T2arraynumof T1 T2.type=array(10,integer) T2.width=10*4=40,(1)DD;D (2)Did:T enter(id.name, T.type, offset); offset:=offset+T.width; (3)Tint T.type:=integer; T.width:=4; (4)Treal,T.type:=real; T.width:=8; (5)Tarray num of T1 T.type:=array(num
17、.val, T1.type); T.width:=num.val*T1.width; (6)TT1 T.type:=pointer(T1.type); T.width:=4;,D3,D1 ; D2,a : T2,x : T3,array 10 of T1,int,23,4.4 声明语句的翻译,例 声明的语法制导翻译:a : array 10 of int; x : int;(无分号),序号 归约使用的产生式 语义处理结果 (1) T1int T1.type=integer T1.width=4 (2) T2arraynumof T1 T2.type=array(10,integer) T2.w
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 符号 简介
链接地址:https://www.31doc.com/p-2495835.html