符号表的管理 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 （2）在语言程序的局部化单位中，标识符的出现分为定义性出现和使用性出现。
⑴定义性出现的标识符：局部化单位的声明部分出现的标识符，其作用是确定该标识符的属性信息，如名字，类型，存储位置等。一个标识符在一个局部化单位只能被声明一次。 ⑵使用性出现的标识符：在语句部分出现的标识符。 Pascal 结构为例： 程序头 program 程序名 声明部分 类型声明部分 type ，标识符定义性出现 变量声明部分 var，标识符定义性出现 过程声明部分procedure，声明部分定义性出现，过程体中标识符为使用性出现 程序体部分 begin … end.标识符为使用性出现

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

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

16 一个局部化单位所建立的所有符号表表项称为该局部化单位的符号表。其有效范围是该局部化单位。
编译程序针对定义性出现标识符所做的处理工作： 首先查找当前局部化单位的符号表中有无与此同名者，若有，则报告重复定义的语义错误；若无，则将该标识符的名字及其属性填入符号表。 编译程序针对使用性出现标识符所做的处理工作： 在点P处遇使用性出现的标识符查符号表时，只能按着由内层到外层的次序查在此处有效的那些局部化单位的符号表，这就要求对符号表的组织，使其能够在程序的每点判断出哪些局部化单位的符号表是有效的，这就是符号表局部化处理的本质。

17 例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

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

19 三、全局式线性组织的符号表的局部化处理思想
每当进入一个局部化区，记住本层符号表的始地址； 每当遇到定义性标识符时，查本层符号表，若查到同名标识符，则表示有错，否则往符号表里填写标识符及其语义信息。 每当遇到使用性标识符时，查整个符号表（从里层往外层），若查不到同名标识符，则表示有错，否则读取其语义信息进行相应操作。 每当结束一个局部化区时，“作废”本层符号表。

20 用一个Scope栈来实现标识符的嵌套作用域
Scope栈用于存放当前有效的局部化单位的符号表的始地址。每当进入一个新的局部化区，就将当前符号表地址存入Scope栈，当退出一个局部化区时，再将Scope栈的栈顶元素弹出。 “删除”本层符号表的方法一般有两种： 1.真删除法:当退出一个局部化单位时，删除掉该局部化单位的符号表； ℓ表示层数计数器，s表示符号表的最后一项的地址，则删除式的局部化算法如下： s := Scope[ℓ]-1 ℓ := ℓ -1 ;

21 基于全局表结构的真删除法 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时刻

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

23 基于全局表结构的驻留法 … 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 … # … #

24 四、局部式线性组织的符号表的局部化处理思想
仍然使用一个辅助Scope栈来体现标识符的嵌套作用域原则 每当进入一个新的局部化区，新建一张该局部化区的局部符号表，并将它的符号表始地址存入Scope栈，当退出一个局部化区时，再将Scope栈的栈顶元素弹出。 删除法、驻留法之分都是基于全局表的结构，而对局部表只有删除法。

25 局部表结构的管理 … 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时刻

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

27 关于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

28 关于Pascal语言的符号表的实例 (跳转法)
PROGRAM example0; …. 符号表 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 # #

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

30 （1） 简单的C语言符号表 int ; void swap(int* a, int*b ) { int tmp; tmp = *a;
off0:函数 形参第一 个可用 区距 int ; void swap(int* a, int*b ) { int tmp; tmp = *a; *a = *b; *b = tmp; } void main() x = 10; y = 20; swap(&x,&y); Scope栈 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→ 1 pointerTy intPtr btptr→ 1 pointerTy intPtr

31 （2） 带有分程序结构的C语言符号表 C语言的分程序语句(也称程序块)是由“{”和“}”括起来的程序段，其中可以包含标识符声明，还允许一个块嵌套在另一个块内。 一个分程序就是一个局部化区。分界符“{”和“}”标记分程序的开始和结束。 分程序无论嵌套多少层，其层数都是1，都属于所在函数的局部量，对应相同的内存块起始地址。

32 一、基于线性组织的表的全局符号表 ( 假定第一个可用区距为0 )
参数指针 一、基于线性组织的表的全局符号表 ( 假定第一个可用区距为0 ) main() {1 3. int a； 4. 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 Scope栈 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 # # #

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

34 习题：假设当前层数为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 ）