符号表的管理 1.符号表的结构与组织 ☆ 2.符号表的局部化处理.

Presentation on theme: "符号表的管理 1.符号表的结构与组织 ☆ 2.符号表的局部化处理."— Presentation transcript:

1 符号表的管理 1.符号表的结构与组织 ☆ 2.符号表的局部化处理

2 符号表 符号表是存放标识符信息的一种表. 标识符的信息= 标识符的属性 = 标识符的语义
符号表 = 标识符的属性表 = 标识符的词典 =名字表 符号表在编译的不同阶段都要用到 在语义分析中，符号表所登记的内容将用于语义检查（如检查一个名字的使用和原先的声明是否一致）; 在产生中间代码中，用于类型检查及转换； 在目标代码生成阶段，当对名字进行地址分配时，符号表是地址分配的依据；

3 组织符号表主要解决的问题： 合理地组织符号表的意义：
在编译程序工作的过程中，需要对符号表进行频繁的访问（查表和填表等操作），因此，合理地组织符号表，并相应地选择好查表和填表的方法，是提高编译程序效率的重要一环。 组织符号表主要解决的问题： 符号表的总体组织 符号表表项的排列 符号表的局部化 符号表的总体组织 符号表的总体组织： 各类标识符属性个数不一样，其内部表示的长度不一样， 符号表表项的排列:各个标识符及属性是按怎样的次序放入表中的，该次序将影响查表的方法。 符号表的局部化：以C语言分程序为例；是合理地组织符号表的重要内容。 是将所有标识符内部表示放到一张表里还是分别放到多个表里。

4 1 符号表的组织 一、符号表的总体组织 符号表的每一项包含两部分：标识符的名字；该标识符的属性特征信息。
1 符号表的组织 一、符号表的总体组织 符号表的每一项包含两部分：标识符的名字；该标识符的属性特征信息。 不同类别的标识符所包含的信息是不同的。 符号表的总体组织既可以采用多表结构，也可以采用单表结构,也可以二者折中。究竟采用哪种结构并没有统一的规定，编译程序可根据实际处理语言的需要进行选择。

5 1、多表结构 是将属性完全相同的那些符号存放在一张符号表中，从而有常量表、类型表、变量表、函数过程表等。 例如：假设有下列3类符号及其所需之属性：

6 第1种组织方法得到三张符号表： 优点：每个表的属性个数和结构完全相同，便于对同类标识符统一管理，空间效率高。 缺点：需同时管理若干个符号表，增加了总体管理的工作量和复杂度。

7 2、单表结构 是将所有符号都组织在一张符号表中，把所有符号的可能属性作为符号表表项属性。 优点：总体管理集中单一，且不同种类符号的共同属性可一致地管理和处理。 缺点：由于符号属性的不同，将增加无用的属性空间，从而增加了空间开销。

8 符号表被频繁地用来建表、查表、填充和引用表的属性，因此表项的排列组织对系统运行的效率起着十分重要的作用。
二、符号表表项的排列 符号表被频繁地用来建表、查表、填充和引用表的属性，因此表项的排列组织对系统运行的效率起着十分重要的作用。 由于符号表的建立是一次性的，符号表的查找是重复性的，因此查表的方法更为重要, 对查表效率的要求决定了建表的方法。

9 例如，有一程序中出现符号的情况如下： ……………… …a………… ………b…… ………d…… …c………… …… 排序组织及 二分法查找 线性组织 散列组织

10 线性组织的例子 例如，有一个结构： struct tag1 { … memb1 … memb2 struct tag2 { … memb3
} stv;

11 例如有函数：func1 (para1,para2,para3)

12 2 符号表的局部化处理 一、问题的引出 （1）源语言程序的局部化单位 程序中允许有声明的部分称为一个局部化单位，通常是一个子程序(函数、过程)或分程序。在局部化单位中声明的标识符在这个局部化单位内起作用 ： Procedure P（……）…………….....end Function F（……）………………… end int F（……）{………………… } {…………………………… } 注：主程序也可以被看作为一个局部化单位。

13 procedure P( )； var x,y:integer； procedure Q( )； var x,z:real; begin
标识符的嵌套作用域原则：外层局部化单位中的标识符作用域要将内层声明同名标识符的局部化单位剔除。 Pascal过程声明嵌套的例子 procedure P( )； var x,y:integer； procedure Q( )； var x,z:real; begin x..z..y.. end ......x.....y.. 局部化单位2 局部化单位1

14 带有分程序的C程序的例子 void main( ) { } int a = 1; B1 int b = 1; printf(“a = %d, b = %d\n”, a, b); int b = 2; B2 int a = 3; B3 printf(“a = %d, b = %d\n”,a, b); int b = 4; B4 a = 3, b = 2 a = 1, b = 4 a = 1, b = 1

15 （2）在语言程序的局部化单位中，标识符的出现分为定义性出现和使用性出现。
⑴定义性出现的标识符：局部化单位的声明部分出现的标识符，其作用是确定该标识符的属性信息，如名字，类型，存储位置等。一个标识符在一个局部化单位只能被声明一次。 ⑵使用性出现的标识符：在语句部分出现的标识符。

16 在一个程序的局部化区里，同一个标识符不能被声明两次。 标识符的使用有无声明 强类型语言规定标识符必须先声明后使用，弱类型语言无要求。
(3) 局部化区的语义错误检查 变量的重复声明 在一个程序的局部化区里，同一个标识符不能被声明两次。 标识符的使用有无声明 强类型语言规定标识符必须先声明后使用，弱类型语言无要求。 这个问题对我们的处理上有什么影响呢？ 在一个局部化区的时候，我们要考虑这样一些语义上的问题，我们主要考虑的是两类语义错误的问题，第一大类的语义错误就是变量的重复声明，第二大类就是变量没有声明的使用。 第一类问题：变量的重复声明。 在一个程序的局部化区里，同一个标识符不能被声明两次，比方说~~ 大家知道标识符是一个名字，对应的是某一个单元。如果在一个局部化区一个变量被声明了两次，计算机处理起来就没有办法处理了。比方说一个班的同学有俩同学名字一样，我们处理起来的时候就不太好处理。都叫张三，考试交卷就写个名字，我们就很难知道是哪个同学。有的时候就加个大张三 小张三。但是如果是两个班，一个班里有一个叫张三的，在不同的作用域，我们就能够区分开，所以说要考虑标识符不能重复声明。 第二类问题就是：标识符的使用没有声明，现在的程序设计语言都属于强类型语言，也就是说所有的标识符都要给出对应的声明，没有声明出现的标识符我们认为就是有错的。比方说（），在某些弱类型的语言中也可以不用这么声明，比方说qbasac。

17 一个局部化单位所建立的所有符号表表项称为该局部化单位的符号表。其有效范围是该局部化单位。
编译程序针对定义性出现标识符所做的处理工作：首先查找当前局部化单位的符号表中有无与此同名者，若有，则报告重复定义的语义错误；若无，则将该标识符的名字及其属性填入符号表。 void main( ) { } int a = 1; B1 int b = 1; { } printf(“a = %d, b = %d\n”, a, b); int b = 2; B2 { } int a = 3; B3 printf(“a = %d, b = %d\n”,a, b); int b = 4; B4 printf(“a = %d, b = %d\n”,a, b);

18 例1.( 注:将fun1和fun2作为无参函数) int x=10; fun1( ) {int x=20, z; …. z=x+10; }
{int y; y=x+30; x intPtr varKind dir m 10 fun1 routKind ... .... fun2 routKind ... .. .... x intPtr varKind dir 1 m 20 z m+1 y intPtr varKind dir 1 m

19 在程序的点P处，对它有效的符号表是包含P的那些嵌套外层的局部化单位的符号表。
}

20 二、符号表的组织 从符号表的组织方式上看，可分为两大类：一类是局部式，一类是全局式。
全局式符号表则把整个程序的符号表作为一个表，即建表和查表单位是整个符号表； 局部式符号表是指把每个局部化单位的符号表作为一个独立的表来处理，即把每个局部符号表作为建表和查表单位。

21 三、全局式线性组织的符号表的局部化处理思想
每当进入一个局部化区，记住本层符号表的始地址； 每当遇到定义性标识符时，构造其语义信息并查本层符号表，若查到同名标识符，则表示有错，否则往符号表里填写标识符及其语义信息。 每当遇到使用性标识符时，查整个符号表（从后往前），若查不到同名标识符，则表示有错，否则找出相应语义信息并将它传给有关部分。 每当结束一个局部化区时，“作废”本层符号表。

22 带有分程序的C程序的例子 void main( ) { } int a = 1; B1 int b = 1; printf(“a = %d, b = %d\n”, a, b); int b = 2; B2 int a = 3; B3 printf(“a = %d, b = %d\n”,a, b); int b = 4; B4 ………1 a …….1 b …….2 b …….4 b ………3 a a = 3, b = 2 a = 1, b = 4 a = 1, b = 1

23 用一个Scope栈来实现标识符的嵌套作用域，Scope[ℓ]指向ℓ层局部化区符号表起始地址；
“删除”本层符号表的方法一般有两种： 1.真删除法:当退出一个局部化单位时，删除掉该局部化单位的符号表； ℓ表示层数计数器，s表示符号表的最后一项的地址，则删除式的局部化算法如下： s := Scope[ℓ]-1 ℓ := ℓ -1 ;

24 基于全局表结构的真删除法 int x,y; int f(int z) { x = x+1; return (z*z) }
scope栈栈底 t0时刻 int x,y; int f(int z) { x = x+1; return (z*z) } int g(int u, int v) {.. .} void main() x = 0; g(x, f(2)) … x t1时刻 … y 局部化单位1 t2时刻 … f 局部化单位2 … g … z t3时刻 … u … main 局部化单位3 … v t4时刻 局部化单位4 t5时刻

25 2.驻留法:不删除表，但采取一定措施不去查那些已无效的符号表部分。驻留式方法又可分为标记法和跳转法。
标记法是给每个表项增加一个标记域，当某个表项变为无效时，就将该标记域设为无效； 跳转法，又可分为有从前往后和从后往前两种。

26 跳转法的主要思想是（考虑从后往前的情形）：
每当退出一个局部化区时，将一个跳转项添入到符号表中： s := s +1 ； SymbTab[s]:=( # , Scope[ℓ]-1); POP(Scope). 当查表时，从当前符号表的末项SymbTab[s]开始往前查，当遇到跳转项时跳到跳转项的地址部分所指向的地址继续查找。 例如：如果要查的是X的属性，则查表过程大致可描述如下：( 开始i 取s值) [1] if SymbTab[i].name = X then return(SymbTab[i].attrib); [2] if SymbTab[i].name = # then i= SymbTab[i].addr else i = i - 1; [3] if i = 0 then Error else goto [1].

27 基于全局表结构的驻留法 … x int x,y; int f(int z) { x = x+1; return (z*z) }
scope栈栈底 … x int x,y; int f(int z) { x = x+1; return (z*z) } int g(int u, int v) {.. .} void main() x = 0; g(x, f(2)) 局部化单位1 t0时刻 t1时刻 t2时刻 t3时刻 t4时刻 t5时刻 局部化单位3 局部化单位2 局部化单位4 … y … f … z … # … g … u … v … # … main … # … #

28 四、局部式线性组织的符号表的局部化处理思想
在不同时刻，不是所有的局部符号表都有效。为了标记在某一时刻，哪些符号表是有效的，用到一个辅助数据结构Scope栈(栈便于体现标识符的嵌套作用域原则)。 Scope栈用于存放当前有效的局部化单位的局部符号表的始地址。每当进入一个新的局部化区，就将它的符号表始地址存入Scope栈，当退出一个局部化区时，再将Scope栈的栈顶元素弹出。 删除法、驻留法之分都是基于全局表的结构，而对局部表只有删除法。

29 局部表结构的管理 … u int x,y; int f(int z) { x = x+1; return (z*z) }
int g(int u, int v) {.. .} void main() x = 0; g(x, f(2)) … z … v t1时刻 … x t2时刻 局部化单位1 … y 局部化单位2 … f t3时刻 scope栈 栈底 … g 局部化单位3 … main t4时刻 局部化单位4 t5时刻

30 3 程序设计语言符号表的实例 3.1 Pascal语言的符号表的管理
3 程序设计语言符号表的实例 3.1 Pascal语言的符号表的管理 Pascal语言的最大特点就是允许嵌套的过程声明。规定Pascal主程序的层数为0，在主程序中声明的标识符(包括过/函标识符)的层数为1，在第i层过/函中声明的标识符(包括形参和局部标识符)的层数为i+1(i≥1)。 用一个Scope栈来实现标识符的嵌套作用域。 Scope栈的每项指向当前仍有效的某层符号表的首项，具体说Scope(0) 指向0层符号表的首项，Scope(i) 指向i层符号表的首项。

31 关于Pascal语言的符号表的实例(删除法)
PROGRAM example; 符号表 procedure P1( ) var i,j,k:integer; {注释--t1时刻} procedure Q2( ) var a, b: real; procedure R3( ) {--t2时刻} var a,b:boolean; {--t3时刻} begin R的过程体（a,b,i) end Q的过程体（a,b,i) end; procedure S2( ) var c,e:char; {--t4时刻} S的过程体（a,b,i,Q) end ; {--t5时刻} P的过程体 （a,b,i,P,Q,S) end; 21. begin..P( );..end. P i j k Q S a b c R e a Scope栈 b

32 关于Pascal语言的符号表的实例 (跳转法)
PROGRAM example; …. 符号表 procedure P1( ) var i,j,k:integer; {注释--t1时刻} procedure Q2( ) var a, b: real; procedure R3( ) {--t2时刻} var a,b:boolean; {--t3时刻} begin R的过程体（a,b,i) end Q的过程体（a,b,i) end; procedure S2( ) var c,e:char; {--t4时刻} S的过程体（a,b,i,Q) end ; {--t5时刻} P的过程体 （a,b,i,P,Q,S) end; 21. begin..P( );..end. P i j k Q a Scope栈 b R a b # # S c e # #

33 3.2 C语言的符号表的管理 C语言不允许函数的嵌套声明。
一个C程序是由若干个函数并列组成的（其中一定要有main函数），这些函数的地位都是相同的。从main函数调用开始执行，在后面声明的函数可以调用在它之前声明的函数。 C语言的每个标识符的层次只有两个，即0层和1层。全局标识符和所有的函数标识符的层数是0，函数的形式参数和局部标识符的层数是1。

34 （1） 简单的C语言符号表 int x,y; void swap(int* a, int*b ) { int tmp; tmp = *a;
off0:函数 形参第一 个可用 区距 int x,y; void swap(int* a, int*b ) { int tmp; tmp = *a; *a = *b; *b = tmp; } void main() x = 10; y = 20; swap(&x,&y); level off x varKind intPtr dir y varKind intPtr dir 1 swap routKind NULL actual size false a varKind atptr indir 1 offo b varKind btptr indir 1 offo+1 tmp varKind intPtr dir 1 offo+2 # main routKind NULL actual null size False # # atptr→ btptr→ 1 pointerTy intPtr btptr→ 1 pointerTy intPtr

35 （2） 带有分程序结构的C语言符号表 当考虑C语言的分程序语句时，C程序符号表的构造将变得复杂一些。C语言的分程序语句(也称程序块)是由“{”和“}”括起来的程序段，其中可以包含标识符声明，还允许一个块嵌套在另一个块内。 一个分程序就是一个局部化区。分界符"{"和"}"标记分程序的开始和结束，分界符保证分程序不是相互独立就是一个嵌在另一个里面.

36 一、基于线性组织的表的全局符号表 ( 假定第一个可用区距为0 )
参数指针 一、基于线性组织的表的全局符号表 ( 假定第一个可用区距为0 ) main() {1 int a； float b，d； {2 int c； float a； {3 int d; float c; {4 float d; …… a=b+c+d; } 4 } 3 {5 char d; } 5 } 2 } 1 level off main routKind NULL actual false a varKind intPtr dir 1 b varKind realPtr dir 1 d varKind realPtr dir 1 3 c varKind intPtr dir 1 5 a varKind realPtr dir 1 6 d varKind intPtr dir 1 8 c varKind realPtr dir 1 9 d varKind realPtr dir 1 11 # # d varKind charPtr dir 1 13 # # #

37 二、基于散列表的全局符号表 分程序嵌套的层数与过/函嵌套的层数有着本质的差别。过/函嵌套的层数的概念是为了给标识符分配内存地址而提出来的，不同的层数对应于不同的内存块的起始地址(第九章将有详细说明)。而分程序结构中，无论分程序嵌套多少层，外层分程序和内层分程序中标识符的层数都是相同的，分程序中声明的标识符都属于所在函数的局部量，因此层数都是1。 分程序结构局部化处理的基本思想是： 给每个分程序分配一个编号，其他同PACSL语言。

38 ( 假定第一个可用区距为m ) 1.进入分第一层程序 分析： 进入第二层分程序之前可用区距为m+5
例1: main（） {1 int a； float b，d； {2 int c； float a； {3 int d; float c; {4 float d; …… a=b+c+d; 4} … 3} 2} 1} float b l m+1 int a m d m+3 … 1.进入分第一层程序 分析： 进入第二层分程序之前可用区距为m+5

39 此时可用区距为m+5 2.进入分第二层程序 进入第三层分程序之前可用区距为m+8 分析：
例1: main（） {1 int a； float b，d； {2 int c； float a； {3 int d; float c; {4 float d; …… a=b+c+d; 4} … 3} 2} 1} float b l m+1 a 2 m+6 … d m+3 int 1 m c m+5 2.进入分第二层程序 进入第三层分程序之前可用区距为m+8 分析：

40 此时可用区距为m+8 3.进入分第三层程序 进入第四层分程序之前可用区距为m+11 分析：
例1: main（） {1 int a； float b，d； {2 int c； float a； {3 int d; float c; {4 float d; …… a=b+c+d; 4} … 3} 2} 1} float b l m+1 a 2 m+6 … int d 3 m+8 1 m c m+9 m+5 m+3 3.进入分第三层程序 进入第四层分程序之前可用区距为m+11 分析：

41 此时可用区距为m+11 4.进入分第四层程序 分析： main函数的局部量共用12个存储单元.
例1: main（） {1 int a； float b，d； {2 int c； float a； {3 int d; float c; {4 float d; …… a=b+c+d; 4} … 3} 2} 1} … float a 2 m+6 int a 1 m … float b l m+1 float c 3 m+9 … int c 2 m+5 … int d 3 m+8 d float 4 m+11 … float d l m+3 4.进入分第四层程序 分析： main函数的局部量共用12个存储单元.

42 3.3 嵌套式语言并列式语言的比较 特殊情形，从程序设计语言的角度来说有嵌套式语言和并列式语言
从处理难度角度来说，可能嵌套式语言复杂，并列式简单。 嵌套式语言里还要考虑变量运行环境。 并列式语言的局部化区比较固定，层数分成两层，全局量定义成0层，局部量定义成1层。分配地址特殊情形就是分程序结构，分程序可以是嵌套的，他的层数都是看成同一层，查局部化区每个分程序看成一个独立的局部化区。

43 作业 P119

44 习题：假设当前层数为L，可用偏移为off0，试写出各个程序点的层数和偏移的变化情况。(d为第一个形参的可用区距）)
①typedef at = int a[10][10]； typedef bt = struct {int number; at score;}； ②at x,y; ③int f （at a, ④at* b, ⑤float x） { ⑥bt m; ⑦int n; ………… }⑧ void g（） {⑨ int l; ………… } （ℓ，off0 ） （ℓ，off0 ） （ℓ，off0+200 ） （ℓ+1，d+100 ） （ℓ+1，d+101 ） （ℓ+1，d+103 ） （ℓ+1，d+204） （ℓ，off0+200 ） （ℓ+1，d） （ℓ，off0+200 ）