符号表简介.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

18、idth=10*4=40 (3) D1id:T2 enter(a,array(10,integer),0) offset=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.val, T1.type); T.width:=num.val*T1.width; (6)TT1 T.ty

19、pe:=pointer(T1.type); T.width:=4;,D3,D1 ; D2,a : T2,x : T3,int,a array(10,integer) 0,24,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.width=10*4=40 (3) D1id:T2 enter(a,array(10,integ

20、er),0) offset=40 (4) T3int T3.type=integer T3.width=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.width:=8; (5)Tarray num of T1 T.type:=array(num.val, T1.type); T.width:=num.val*T1.width; (6)TT1 T.type:=pointe

21、r(T1.type); T.width:=4;,D3,D1 ; D2,x : T3,int,a array(10,integer) 0,25,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.width=10*4=40 (3) D1id:T2 enter(a,array(10,integer),0) offset=40

22、(4) T3int T3.type=integer T3.width=4 (5) D2id:T3 enter(x,integer,40) offset=44,(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.val, T1.type); T.width:=num.val*T1.wid

23、th; (6)TT1 T.type:=pointer(T1.type); T.width:=4;,D3,D1 ; D2,x : T3,a array(10,integer) 0,x integer 40,26,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.width=10*4=40 (6) D3D1;D2,(1)DD

24、;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.val, T1.type); T.width:=num.val*T1.width; (6)TT1 T.type:=pointer(T1.type); T.width:=4;,D3,D1 ; D2,a array(10,integer) 0,x

25、integer 40,27,4.4 声明语句的翻译,过程的定义与声明 过程（procedure）：过程头过程体； 函数：过程有返回值的话称为函数 主程序（main）是被操作系统调用的过程 过程的三种形式：过程定义、过程声明和过程调用 (Ada)过程定义： procedure swap(x,y:in out integer) is - 规格说明 temp : integer; - 体中的声明 begin temp := x; x := y; y := temp; end swap; - 可执行语句序列 过程声明： procedure swap(x, y: in out integer); - 过

26、程声明 过程引用： swap(a, b); - 过程调用,28,4.4 声明语句的翻译,先声明后引用原则 过程定义可以写在对它的引用之后或引用时看不到的地方。在这样的情况下，引用前必须先声明。而若引用前已定义，则声明可省略，因为定义已包括了声明。,29,4.4 声明语句的翻译,左值与右值 形式上，出现在赋值号左边和右边的变量称为左值和右值 实质上，左值必须具有存储空间，右值可以仅是一个值，而没有存储空间。 形象地讲，左值是容器，右值是内容。 (1) const two = 2; - 声明一个值为2的常量two (2) x : integer; - 声明一个类型为整型数的变量x (3) func

27、tion max(a, b : integer) return integer; - 声明一个返回值类型是整型数的函数max (4) x := two; - x当前值为2 (5) x := two + x; - x当前值变为4 (6) x := max(two,x)+x; - x当前值变为8 (7) 4 := x; - 字面量不能作为左值 (8) two := x; - 常量不能作为左值 (9) max(two,x) := two; - 函数返回值不能作为左值 (10) x+two := x+two; - 表达式的值不能作为左值,30,4.4 声明语句的翻译,参数传递 形参与实参 定义时的参数

28、称为形参(parameter或formal parameter) 引用时的参数称为实参(argument或actual parameter) 常见的参数传递形式：（不同的语言提供不同的形式） 值调用（call by value） 引用调用（call by reference） 复写恢复（copy-in/copy-out） 换名调用（call by name） 参数传递方法的实质： 实参是代表左值、右值、还是实参本身的正文。,31,4.4 声明语句的翻译,值调用 值调用的特点：过程内部对参数的修改，不影响作为实参的变量原来的值。 实参的特点：任何可以作为右值的对象均可作为实参。 参数传递和过程内

29、对参数的使用原则： 过程定义时形参被当作局部名看待，并在过程内部为形参分配存储单元； 调用过程前，首先计算实参并将值（实参的右值）放入形参的存储单元； 过程内部对形参单元中的数据直接访问。,32,4.4 声明语句的翻译,值调用举例： program reference( input, output); var a, b : integer; procedure swap(x, y : integer); var temp : integer; begin temp:=x; x:=y; y:=temp end; begin a:=1; b:=2; swap(a, b); writeln(a=,

30、a); writeln(b=, b) end. 运行结果：a=1 b=2,/ 等价的C+程序 #include void swap(int x, int y) int temp; temp=x; x=y; y=temp; void main () int a(1), b(2); swap(a, b); cout“a=“a“b=“b; ,缺陷：得不到结果的返回值,33,4.4 声明语句的翻译,引用调用 引用调用的特点：过程内部对形参的修改，等价于直接对实参的修改。 实参的特点：必须是左值。 参数传递和过程内对参数的使用原则： 定义时形参被当作局部名看待，并在过程内部为形参分配存储单元； 调用过程

31、前，将作为实参的变量的地址放进形参的存储单元； 过程内部把形参单元中的数据当作地址，进行间接访问,34,4.4 声明语句的翻译,引用调用举例： program reference( input, output); var a, b : integer; procedure swap( var x, y : integer); var temp : integer; begin temp:=x; x:=y; y:=temp end; begin a:=1; b:=2; swap(a, b); writeln(a=, a); writeln(b=, b) end. 运行结果：a=2 b=1,/ 等

32、价的C+程序 #include void swap(int ,35,4.4 声明语句的翻译,值调用模拟引用调用 #include void swap(int *x, int *y) int temp; temp=*x; *x=*y; *y=temp; void main () int a(1), b(2); swap( ,注意： C语言只有值调用 因此：只能用值调用形式模拟引用调用的效果 同样：过程式程序设计语言可以模拟面向对象的继承机制 结论：语言与程序设计范型（方法）不是一一对应的关系,36,4.4 声明语句的翻译,引用调用的副作用(调用过程中形参和实参共用同一地址) int a=2; v

33、oid add_one(int 本意：a=3 结果：a=4 原因：实参与非本地量共用一个存储空间，使得在过程内改变参数值的同时，也改变了非本地量的值。,37,4.4 声明语句的翻译,复写恢复 复写-恢复的特点：(值调用和引用调用的结合) 过程内部对参数的修改不直接影响实参，避免了副作用 返回时将形参内容恢复给实参，实现了参数的返回。 实参的特点：必须是左值。 参数传递和过程内对参数的使用原则： 过程定义时形参被当作局部名，在过程内部为形参分配单元(复写)； 调用过程前，计算实参并将右值放入形参的存储单元； 过程内部对形参单元中的数据直接访问； 过程返回前，将形参右值放回实参的存储单元(恢复)。

34、,38,4.4 声明语句的翻译,复写-恢复举例 （Ada支持：将参数声明为in out 形式） procedure test is - Ada源程序 a : integer; procedure add_one(x:in out integer); - 复写-恢复调用 begin a:=x+1; x:=x+1; end add_one; begin a:=2; a:=add_one(a); put_line(a=, a); end test; /引用调用模拟复写-恢复参数传递的演示程序 int a=2; void add_one(int ,39,4.4 声明语句的翻译,换名调用 严格讲，换名调

35、用并不能算作真正的过程调用和参数传递。 换名调用由Algol的复写规则定义： 过程被认为宏，每次对过程的调用，实质上是用过程体替换过程调用，替换中用实参的文字替换体中的形参。这样的替换方式被称为宏替换或宏展开； 区分被调用过程的局部名和调用过程的名字。宏展开前被调用过程的每个局部名被重新命名成可区别的名字； 当需要保持实参的完整性时，可为实参加括弧。 换名调用的C+形式是宏定义(#define)，在预处理时进行宏替换，将过程体直接展开在它被调用的地方，消除了过程调用和参数传递，运行速度快。,40,4.4 声明语句的翻译,正文替换有时会带来一些不期望的结果： 例：swap(i, ai) 换名调用在过程体中可以展开为： Temp:=i; i=ai; ai=temp;,作业,P240:4.4,41,