第八章 符号表 符号表的作用: 一致性检查和作用域分析; 辅助代码生成..

Presentation on theme: "第八章 符号表 符号表的作用: 一致性检查和作用域分析; 辅助代码生成.."— Presentation transcript:

1 第八章 符号表 符号表的作用: 一致性检查和作用域分析; 辅助代码生成.

2 8.1 符号表的组织与作用 符号表的每一项(入口)包含两大栏: 对符号表的操作: 名字栏，也称主栏，关键字栏
8.1 符号表的组织与作用 符号表的每一项(入口)包含两大栏: 名字栏，也称主栏，关键字栏 信息栏，记录相应的不同属性，分为若干子栏. 对符号表的操作: 填入名称 查找名字 访问信息 填写修改信息 删除

3 按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表、… 符号的组织方式:
对符号表进行操作的时机： 定义性出现 使用性出现 按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表、… 符号的组织方式: 1. 安排各项各栏的存储单元为固定长度 2. 用间接方式安排各栏存储单元

4 符号表的存放次序: 1. 把每一项置于连续K存储单元中，构成一张K*N的表
2. 把整个符号表分成m个子表，如T1,T2,…Tm，每个子表含有N项.

5 例: PASCAL程序段： PROCEDURE INCWAP(M，N:INTEGER); LABEL START; VAR
K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END.

6 PROCEDURE INCWAP(M，N:INTEGER);
LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END.

7 PROCEDURE INCWAP(M，N:INTEGER);
LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END.

8 PROCEDURE INCWAP(M，N:INTEGER);
LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END.

9 PROCEDURE INCWAP(M，N:INTEGER);
LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END.

10

11 PROCEDURE INCWAP(M，N:INTEGER);
LABEL START; VAR K:INTEGER; BEGIN START: K:=M+1; M:=N+4; N:=K; END.

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

13 表格中的项按名字的“大小”顺序整理排列。 填表慢,查找快。查找时间复杂度:O(Log2n) 改进：组织成二叉树。
2. 二分查找 表格中的项按名字的“大小”顺序整理排列。 填表慢,查找快。查找时间复杂度:O(Log2n) 改进：组织成二叉树。 3. 杂凑查找(HASH技术) 杂凑函数H(SYM)：0~N-1 N：符号表的项数。 要求：1. 计算简单高效 2. 函数值分布均匀 填表快，查找快

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

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

16 名字标识符 1) 名字表(nametab) 名字表nametab：登记程序中出现的各种名字及其属性
Kind, 名字种类，可以是常量(constant)、变量(variable)、类型(type)、过程(procedure) leve, 名字所在的程序体的静态层次。规定主程序的层次为1，主程序中定义的层次为2，依次类推 type, 名字的类型，类型有整型(ints)、字符型(chars)、布尔型(bool)、数组(arrays)，对于无类型的名字填入notype ref, 当名字为数组类型或数组变量名时，ref指向该数组在数组信息表中的位置；当名字为过程名时，ref指向该过程在程序体表(btab)中的位置；其他情况ref为0 normal, 一个布尔量，用于标明名字是否为变量形参名，当名字是否为变量形参名时填入false，其他情况填入true或不填 adr, 当名字为变量名时（包括形参），存入该变量（或形参）在相应活动记录中分类的存贮单元的相对地址；对于过程名，填入他们相应代码的入口地址 val, 当名字为变量名时，填入他们的相应值 size, 当名字为类型名时，填入该类型数据所需存贮单元的数目 link, 指向同一程序体中定义的上一个名字在nametab中的位置，每个程序体在nametab中登记的第一个名字的link为0 名字所在的程序体的静态层次。规定主程序的层次为1，主程序中定义的层次为2，依次类推 指向同一程序体中定义的上一个名字在nametab中的位置，每个程序体在nametab中登记的第一个名字的link为0 名字标识符 一个布尔量，用于标明名字是否为变量形参名，当名字是否为变量形参名时填入false，其他情况填入true或不填 名字种类，可以是常量(constant)、变量(variable)、类型(type)、过程(procedure) 名字的类型，类型有整型(ints)、字符型(chars)、布尔型(bool)、数组(arrays)，对于无类型的名字填入notype 当名字为数组类型或数组变量名时，ref指向该数组在数组信息表中的位置；当名字为过程名时，ref指向该过程在程序体表(btab)中的位置；其他情况ref为0 adr, 当名字为变量名时(包括形参，存入该变量(或形参)在相应活动记录中分类的存贮单元的相对地址；对于过程名，填入他们相应代码的入口地址 val, 当名字为变量名时，填入他们的相应值 size, 当名字为类型名时，填入该类型数据所需存贮单元的数目

17 程序体表btab：记录个程序体的总信息，用于对源程序中定义的名字的作用域进行分析；对名字表进行管理
(2) 程序体表btab和层次显示表display 程序体表btab：记录个程序体的总信息，用于对源程序中定义的名字的作用域进行分析；对名字表进行管理 lastpar, 指向本程序体中最后一个形式参在nametab中的位置 last,指向本程序体中最后一个名字在nametab中的位置 psize, 本程序体所有形参所需体积、包括连接数据所占空间 vsize, 本程序体所有局部数据所需空间大小 本程序体所有局部数据所需空间大小 指向本程序体中最后一个名字在nametab中的位置 本程序体所有形参所需体积、包括连接数据所占空间 指向本程序体中最后一个形式参在nametab中的位置

18 层次显示表display：描述正在处理的各嵌套层，对程序体表进行管理
btab

19 (3)数组信息表atab 数组下限 数组上限 数组元素的体积 数组本身的体积
inxtyp, 数组的下标类型 eltyp, 数组元素类型 elref, 当元素为数组时，它指向该元素数组信息在atab表中的位置，其他情况为0 low, high, 分别表示数组上下限 elsize, size,分别表示数组元素的体积和数组本身的体积 数组下限 数组上限 数组元素的体积 数组本身的体积 当元素为数组时，它指向该元素数组信息在atab表中的位置，其他情况为0 数组元素类型 数组的下标类型

20 type a=array[1..10, 1..10] of integer;
nametab atab

21 (4) 中间代码表code code：用于存放编译程序所产生的每条中间代码。

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

23 PROGRAM MAIN … integer X，Y COMMON /C/A，B END SUBROUTINE SUB1 real X，Z COMMON /C/A1，B1

24 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.

25 1. FORTRAN的符号表组织 一个FORTRAN程序由一个主程序段和若干个辅程序段组成. 把局部名和全局名分别存在不同的地方. 2. 嵌套结构语言的符号表组织 如PASCAL、ALGOL、ADA作用域遵循"最近嵌套原则".

26 PASCAL PASCAL程序本身可以看成是一个操作系统所调用的过程，过程可以嵌套和递归。 一个PASCAL过程： 过程头；
说明段（由一系列的说明语句组成）； begin 执行体（由一系列的执行语句组成）； end

27 作用域：一个名字能被使用的区域范围称作这个名字的作用域。 允许同一个标识符在不同的过程中代表不同的名字。 名字作用域规则--"最近嵌套原则"
一个在子程序B1中说明的名字X只在B1中有效（局部于B1）； 如果B2是B1的一个内层子程序且B2中对 标识符X没有新的说明，则原来的名字X在 B2中仍然有效。如果B2对X重新作了说明， 那么，B2对X的任何引用都是指重新说明 过的这个X。

28 A(real) B(real) B(bool) A(integr) program main var A, B : real; … procedure P1 var B:boolean; begin end procedure P2 var A:integer;

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

30 PL语言的中间代码 指令格式： opcod l a 编译是如何确定变量的层数(地址)？
运行是如何根据指令中变量的层数和相对地址确定变量的存储单元？

31 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.

32 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.

33 b1 := a + b 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. function position(id:alfa):integer; var i,j:integer; begin nametab[0].name:=id; j:=level; repeat i:=btab[ display[j] ].last; while nametab[i].name<>id do i:=nametab[i].link; j:=j-1 until (j<0) or (i<>0); if (i=0) then error(10); position:=i end; { position } b1 := a + b

34 PL语言的中间代码 指令格式： opcod l a 编译是如何确定变量的层数(地址)？
运行时如何根据指令中变量的层数和相对地址确定变量的存储单元？