当前位置: 首页 > >

第08章_符号表_图文

发布时间:

第八章 符号表

内容
符号表的组织与作用 整理与查找 名字的作用范围 符号表的内容

8.1 符号表的组织与作用
编译过程中编译器需要不断汇集和反复查证出现 在源程序中各种名字的属性和特征等有关信息。 这些信息通常记录在一张或几张符号表 符号表中。这些 符号表 信息将用于语义检查、产生中间代码以及最终生 成目标代码等不同阶段。 符号表的作用: 符号表的作用:
一致性检查和作用域分析; 辅助代码生成。

合理地组织符号表,减少符号表本身占据的存储 减少符号表本身占据的存储 空间,提高编译期间对符号表的访问效率,是提 空间,提高编译期间对符号表的访问效率 高编译器工作效率的重要一环。

8.1.1 符号表的作用
符号表的每一项(入口)包含两大栏:
名字栏,也称主栏,关键字栏 名字栏 信息栏,记录相应的不同属性,分为若干子栏. 信息栏

对符号表的操作:
查找名字 填入名字 访问给定名字的某些信息 填写或修改给定名字的某些信息 删除一个或一组无用的项

8.1.2 符号表的组织
对符号表进行操作的时机:
定义性出现 使用性出现

按名字的不同种属建立多张符号表,如常 数表、变量名表、过程名表、… 符号表的组织方式:
1. 安排各项各栏的存储单元为固定长度 2. 用间接方式安排各栏存储单元

8.1.2 符号表的组织
符号表在存储器中的表示方式(设符号表 可容纳N项,每项需用K个字):
1.把每一项置于连续K个存储单元中,构成一 把每一项置于连续 个存储单元中, 的表; 张K*N的表; 的表 2.把整个符号表分成 个子表,如T1,T2,…Tm, 把整个符号表分成m个子表 把整个符号表分成 个子表, 每个子表含有N项 每个子表含有 项。

8.1.2 符号表的组织
例: PASCAL程序段:
PROCEDURE INCWAP(M,N:INTEGER); LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END

表0.1 符 名 号 表SNT NAME INFORMATION M 形 参 , 式 数 整 型 值 数 , 参 N 形 参 , 式 数 整 型 值 数 , 参 K 整 , 量 型 变

表0. 常 表CT 2 数 值 ( UE VAL ) (1 ) 1 (2 ) 4

表 0.3 入口名表 ENT NAME INFORMATION (1) INCWAP 二目子程序, 入口四元式:1

表0.4 标 表LT 号 NAME INFORMATION (1)START 四 式 元 :(4)

表0.5 四 式 元 表QT OPR OPN1 OPN2 RESULT (1) link (2) par INCWAP 1 M (3) par INCWAP 2 N (4) + M 1 K (5) + N 4 M (6) := K N (7) return

8.2 整理和查找
1. 线性查找
按关键字出现的顺序填写各项。 填表快,查找慢。 结构简单,节省空间,效率低,查找时间复杂 度:O(n)。 改进:自适应线性表 自适应线性表

8.2 整理和查找
2. 二分查找
表格中的项按名字的“大小”顺序整理排列。 填表慢,查找快。查找时间复杂度:O(Log2n) 改进:组织成二叉树 组织成二叉树。 组织成二叉树

8.2 整理和查找
杂凑查找(HASH技术 技术) 3. 杂凑查找(HASH技术)
杂凑函数H(SYM):0~N-1 (N:符号表的项数)。 要求:
1. 计算简单高效 2. 函数值分布均匀

填表快,查找快

8.3 名字的作用域
在许多程序语言中,名字都有一个确定的作 用范围. 两种程序体结构:
并列结构,如FORTRAN 并列结构 嵌套结构,如PASCAL,ADA 嵌套结构

规定一个名字在什么样的范围内应该表示 什么意义的原则,被称为名字的作用域规 名字的作用域规 则。

8.3 名字的作用域
名字的作用域规则:
(1) 静态作用域原则 静态作用域原则:
编译时就可以确定名字的作用域,也可以说,仅从 静态读程序就可确定名字的作用域。

(2) 最近嵌套原则: 最近嵌套原则:
① 程序块B中声明的作用域包括B; ② 如果名字x不在B中声明,那么B中x的出现是在 外围程序块B'的x声明的作用域中,使得B'有x的声 明,并且B'比其它任何含x声明的程序块更接近被嵌 套的B。

8.3 名字的作用域
FORTRAN程序:
PROGRAM MAIN … integer X,Y COMMON /C/A,B … END SUBROUTINE SUB1 … real X,Z COMMON /C/A1,B1 … END

8.3 名字的作用域
FORTRAN的符号表组织
一个FORTRAN程序由一个主程序段和若干 个辅程序段组成. 把局部名和全局名分别存在不同的地方

符号表组织:(一遍扫描)把局部名 符号表组织 和全局名分别存在符号表的两端。局 部名表区域可重复使用。

8.3 名字的作用域
PASCAL程序:
program P; var a,b : integer; procedure P1(i1, j1:integer); var c,d : integer … end; procedure P2(i2, j2:integer); var a,c : integer; procedure P21; var b1,b2 : boolean; … end; … end; … end

8.3 名字的作用域
嵌套结构语言的符号表组织
如PASCAL、ALGOL、ADA作用域遵循“最 近嵌套原则”

两种做法:
引入“过程编号”属性。查找时,先查 引入“过程编号”属性 找本过程编号的名字,查不到则查找外 层过程编号的名字,…,等等。 式思想组织符号表。查找时, 按“栈”式思想组织符号表 从后往前查找,碰到的第一个名字就是 所需查找的名字。

8.4 符号表的内容
符号表的信息栏中登记了每个名字的有关 性质
类型: 类型:整、实或布尔等 种属:简单变量、数组、 种属:简单变量、数组、过程等 大小:长度, 大小:长度,即所需的存储单元字数 相对数: 相对数:指分配给该名字的存储单元的相对地 址

8.4 符号表的内容
语言编译程序的符号表: 例:PL 语言编译程序的符号表: 表格的定义
名字表(nametab) 名字表 程序体表(btab) 程序体表 层次显示表(display) 层次显示表 数组信息表(atab) 数组信息表 中间代码表(code)。 中间代码表 。

(1)名字表 )名字表(nametab)
名字表nametab:登记程序中出现的各种名 字及其属性
nam kind lev typ norm ref adr/val/size link e al

0 1 … tx→ →

(2)程序体表 )程序体表btab
程序体表btab:记录程序体的总信息,用于对 :记录程序体的总信息, 程序体表 源程序中定义的名字的作用域进行分析; 源程序中定义的名字的作用域进行分析;对名 字表进行管理

lastp ar last p size vsize 0 1
M

b→ x

(3)层次显示表 )层次显示表display
层次显示表display:描述正在处理的各嵌套层, 对程序体表进行管理

0 1
M

level→

(4)数组信息表 )数组信息表atab
in xtyp eltyp elref low h igh elsize size 1 2
M

ax→ →

例:type a=array[1..10, 1..10] of integer;
nm k d a e in ty p ref



M k tx →

nametab
a ty e a y p rra s n

inxtyp eltyp elref low high elsize size M n ints arrays M m ints ints ax→ →

atab
m 0 1 1 10 10 10 1 100 10

8.4 符号表的内容
(5)中间代码表 )中间代码表code
code:用于存放编译程序所产生的每条中间 : 代码。 代码。

小结
符号表的组织与作用 整理与查找 名字的作用范围 符号表的内容

练习
例1:C语言中规定变量标识符的定义可分 : 语言中规定变量标识符的定义可分 为extern, extern static, auto, local static和register五种存储类: 五种存储类: 和 五种存储类
(1) 对五种存储类所定义的每种变量,分别说 对五种存储类所定义的每种变量, 明其作用域。 明其作用域。 (2) 试给出适合上述存储类变量的内存分配方 式。 (3) 符号表中登记的存储类属性,在编译过程 符号表中登记的存储类属性, 中支持什么样的语义检查。 中支持什么样的语义检查。

练习
解:
(1) extern 定义的变量,其作用域是整个C 语言程序。 extern static 定义的变量,其作用域是该定义所在的C 程序文件。 auto 定义的变量,其作用域是该定义所在的例程。 local static 定义的变量,其作用域是该定义所在的例程。且在退出 该例程时,该变量的值仍保留。 register 定义的变量,其作用域与auto 定义的变量一样。这种变量 的值,在寄存器有条件时,可存放在寄存器中,以提高运行效率。 (2) 对extern 变量,设置一个全局的静态公共区进行分配。 对extern static 变量,为每个C 程序文件,分别设置一个局部静态 公共区进行分配。 对auto 和register 变量,设定它们在该例程的动态区中的相对区头 的位移量。而例程动态区在运行时再做动态分配。 对local static 变量,为每个具有这类定义的例程,分别设置一个内 部静态区进行分配。 (3) 实施标识符变量重复定义合法性检查,及引用变量的作用域范 围的合法性检查。




友情链接: