第1页：第八章符号表
第八章符号表
- 符号表的作用:
- 一致性检查和作用域分析;
- 辅助代码生成.
第2页：8.1符号表的组织与作用
8.1符号表的组织与作用
- 用
- 符号表的每一项(入口)包含两大栏:
- 名字栏，也称主栏，关键字栏
- 信息栏，记录相应的不同属性，分为若干子栏.
- 对符号表的操作:
- 填入名称
- 查找名字
- 访问信息
- 填写修改信息
- 删除
第3页：8.1符号表的组织与作用（续）
8.1符号表的组织与作用（续）
- 符号的组织方式
- 1.安排各项各栏的存储单元为固定长度2.用间接方式安排各栏存储单元
- 如常数表、变量名表、过程名表、…
- 定义性出现
- 使用性出现
第4页：8.1符号表的组织与作用
8.1符号表的组织与作用
符号表的存放次序:1.把每一项置于连续K存储单元中，构成一张K*N的表2.把整个符号表分成m个子表，如T1,T2,…Tm，每个子表含有N项.
第5页：PASCAL过程INCWAP示例
PASCAL过程INCWAP示例
PASCAL程序段：PROCEDURE INCWAP(M，N:INTEGER);LABEL START;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.
第6页：PASCAL过程INCWAP示例（续）
PASCAL过程INCWAP示例（续）
N:INTEGER);LABEL START;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.
第7页：PASCAL过程INCWAP示例
PASCAL过程INCWAP示例
N:INTEGER);LABEL START;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.
第8页：PASCAL过程INCWAP示例（续）
PASCAL过程INCWAP示例（续）
N:INTEGER);LABEL START;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.
第9页：PASCAL过程INCWAP示例
PASCAL过程INCWAP示例
N:INTEGER);LABEL START;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.
第10页：
第11页：PASCAL过程INCWAP示例
PASCAL过程INCWAP示例
N:INTEGER);LABEL START;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.
第12页：8.2整理和查找
8.2整理和查找
- 改进
- 自适应线性表
- 按关键字出现的顺序填写各项。
- 填表快，查找慢。
- 结构简单，节省空间，效率低，查找时间复杂度：O(n)。
第13页：2.二分查找
2.二分查找
- 改进
- 组织成二叉树。3.杂凑查找(HASH技术)
- 杂凑函数H(SYM)
- 0~N-1N：符号表的项数。
- 要求
- 1.计算简单高效2.函数值分布均匀
- 表格中的项按名字的“大小”顺序整理排列。
- 填表慢,查找快。查找时间复杂度:O(Log2n)
- 填表快，查找快
第14页：8.4符号表的内容
8.4符号表的内容
- 类型
- 整、实或布尔等
- 种属
- 简单变量、数组、过程等
- 大小
- 长度，即所需的存储单元字数
- 相对数
- 指分配给该名字的存储单元的相对地址
第15页：8.4符号表的内容（续）
8.4符号表的内容（续）
- 名字表(nametab)
- 程序体表(btab)
- 层次显示表(display)
- 数组信息表(atab)
- 中间代码表(code)
第16页：8.4符号表的内容
8.4符号表的内容
- 登记程序中出现的各种名字及其属性名字标识符名字种类，可以是常量(constant)、变量(variable)、类型(type)、过程(procedure)名字所在的程序体的静态层次。规定主程序的层次为1，主程序中定义的层次为2，依次类推名字的类型，类型有整型(ints)、字符型(chars)、布尔型(bool)、数组(arrays)，对于无类型的名字填入notype一个布尔量，用于标明名字是否为变量形参名，当名字是否为变量形参名时填入false，其他情况填入true或不填当名字为数组类型或数组变量名时，ref指向该数组在数组信息表中的位置；当名字为过程名时，ref指向该过程在程序体表(btab)中的位置；其他情况ref为0
- adr,当名字为变量名时(包括形参，存入该变量(或形参)在相应活动记录中分类的存贮单元的相对地址；对于过程名，填入他们相应代码的入口地址
- val,当名字为变量名时，填入他们的相应值
- size,当名字为类型名时，填入该类型数据所需存贮单元的数目指向同一程序体中定义的上一个名字在nametab中的位置，每个程序体在nametab中登记的第一个名字的link为0
第17页：8.4符号表的内容（续）
8.4符号表的内容（续）
- 体表btab记录个程序体的总信息，用于对源程序中定义的名字的作用域进行分析；对名字表进行管理指向本程序体中最后一个形式参在nametab中的位置指向本程序体中最后一个名字在nametab中的位置本程序体所有形参所需体积、包括连接数据所占空间本程序体所有局部数据所需空间大小
第18页：层次显示表display
层次显示表display
- 描述正在处理的各嵌套层，对程序体表进行管理btab
第19页：层次显示表display（续）
层次显示表display（续）
- 元素为数组时它指向该元素数组信息在atab表中的位置，其他情况为0数组下限数组上限数组元素的体积数组本身的体积
第20页：层次显示表display
层次显示表display
第21页：层次显示表display（续）
层次显示表display（续）
第22页：8.3名字的作用范围
8.3名字的作用范围
- 用范围
- 在许多程序语言中,名字都有一个确定的作用范围.
- 两种程序体结构:
- 并列结构，如FORTRAN
- 嵌套结构，如PASCAL，ADA
第23页：8.3名字的作用范围（续）
8.3名字的作用范围（续）
- YCOMMON /C/A，B…ENDSUBROUTINE SUB1…real X，ZCOMMON /C/A1，B1…END
第24页：8.3名字的作用范围
8.3名字的作用范围
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.
第25页：8.3名字的作用范围（续）
8.3名字的作用范围（续）
- 一个FORTRAN程序由一个主程序段和若干个辅程序段组成.
- 把局部名和全局名分别存在不同的地方.2.嵌套结构语言的符号表组织
- 如PASCAL、ALGOL、ADA作用域遵循"最近嵌套原则".
第26页：8.3名字的作用范围
8.3名字的作用范围
- 一个PASCAL过程
- 过程头；说明段（由一系列的说明语句组成）；begin执行体（由一系列的执行语句组成）；end
第27页：一个在子程序B1中说明
一个在子程序B1中说明
- 允许同一个标识符在不同的过程中代表不同的名字。
- 名字作用域规则--"最近嵌套原则"
- 如果B2是B1的一个内层子程序且B2中对标识符X没有新的说明，则原来的名字X在B2中仍然有效。如果B2对X重新作了说明，那么，B2对X的任何引用都是指重新说明过的这个X。
第28页：PASCAL嵌套过程作用域示例
PASCAL嵌套过程作用域示例
- real;…procedure P1var B:boolean;…begin…endprocedure P2var A:integer;…begin…endbegin…endA(real)B(real)B(bool)A(integr)
第29页：两种做法
两种做法
- 引入"过程编号"属性。查找时，先查找本过程编号的名字，查不到则查找外层过程编号的名字，…，等等.
- 按"栈"式思想组织符号表。查找时，从后往前查找，碰到的第一个名字就是所需查找的名字.
第30页：PL语言的中间代码
PL语言的中间代码
- 指令格式
- opcod l a
- l
- 第一操作数，程序体层数
- a
- 第一操作数，相对地址
- opcod：操作码
- 编译是如何确定变量的层数(地址)？
- 运行是如何根据指令中变量的层数和相对地址确定变量的存储单元？
第31页：PL语言的中间代码（续）
PL语言的中间代码（续）
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.
第32页：PL语言的中间代码
PL语言的中间代码
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.
第33页：PL语言的中间代码（续）
PL语言的中间代码（续）
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.function position(id:alfa):integer;var i,j:integer;beginnametab[0].name:=id; j:=level;repeati:=btab[ display[j] ].last;while nametab[i].name<>id doi:=nametab[i].link;j:=j-1until (j<0) or (i<>0);if (i=0) then error(10);position:=iend; { position }b1:=a+ b
第34页：PL语言的中间代码
PL语言的中间代码
- 指令格式
- opcod l a
- l
- 第一操作数，程序体层数
- a
- 第一操作数，相对地址
- Opcod：操作码
- 编译是如何确定变量的层数(地址)？
- 运行时如何根据指令中变量的层数和相对地址确定变量的存储单元？
