《编译原理》ppt课件Chapt8符合表.ppt

《《编译原理》ppt课件Chapt8符合表.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第八章符号表符号表的作用:一致性检查和作用域分析;辅助代码生成.8.1符号表的组织与作用符号表的每一项(入口)包含两大栏:名字栏，也称主栏，关键字栏信息栏，记录相应的不同属性，分为若干子栏.对符号表的操作:填入名称查找名字访问信息填写修改信息删除对符号表进行操作的时机：定义性出现使用性出现按名字的不同种属建立多张符号表，如常数表、变量名表、过程名表、…符号的组织方式:1.安排各项各栏的存储单元为固定长度2.用间接方式安排各栏存储单元符号表的存放次序:1.把每一项置于连续K存储单元中，构成一张K*N的表

2、2.把整个符号表分成m个子表，如T1,T2,…Tm，每个子表含有N项.例:PASCAL程序段：PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LAB

3、ELSTART;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDUREINCWAP(M，N:INTEGER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.PROCEDUREINCWAP(M，N:INTE

4、GER);LABELSTART;VARK:INTEGER;BEGINSTART:K:=M+1;M:=N+4;N:=K;END.8.2整理和查找1.线性查找按关键字出现的顺序填写各项。填表快，查找慢。结构简单，节省空间，效率低，查找时间复杂度：O(n)。改进：自适应线性表2.二分查找表格中的项按名字的“大小”顺序整理排列。填表慢,查找快。查找时间复杂度:O(Log2n)改进：组织成二叉树。3.杂凑查找(HASH技术)杂凑函数H(SYM)：0~N-1N：符号表的项数。要求：1.计算简单高效2.函数值分布均

5、匀填表快，查找快8.4符号表的内容符号表的信息栏中登记了每个名字的有关性质类型：整、实或布尔等种属：简单变量、数组、过程等大小：长度，即所需的存储单元字数相对数：指分配给该名字的存储单元的相对地址PL语言编译程序的符号表1.表格的定义名字表(nametab)程序体表(btab)层次显示表(display)数组信息表(atab)中间代码表(code)1)名字表(nametab)名字表nametab：登记程序中出现的各种名字及其属性名字标识符名字种类，可以是常量(constant)、变量(variable

6、)、类型(type)、过程(procedure)名字所在的程序体的静态层次。规定主程序的层次为1，主程序中定义的层次为2，依次类推名字的类型，类型有整型(ints)、字符型(chars)、布尔型(bool)、数组(arrays)，对于无类型的名字填入notype一个布尔量，用于标明名字是否为变量形参名，当名字是否为变量形参名时填入false，其他情况填入true或不填当名字为数组类型或数组变量名时，ref指向该数组在数组信息表中的位置；当名字为过程名时，ref指向该过程在程序体表(btab)中的位置；

7、其他情况ref为0adr,当名字为变量名时(包括形参，存入该变量(或形参)在相应活动记录中分类的存贮单元的相对地址；对于过程名，填入他们相应代码的入口地址val,当名字为变量名时，填入他们的相应值size,当名字为类型名时，填入该类型数据所需存贮单元的数目指向同一程序体中定义的上一个名字在nametab中的位置，每个程序体在nametab中登记的第一个名字的link为0(2)程序体表btab和层次显示表display程序体表btab：记录个程序体的总信息，用于对源程序中定义的名字的作用域进行分析；对名

8、字表进行管理指向本程序体中最后一个形式参在nametab中的位置指向本程序体中最后一个名字在nametab中的位置本程序体所有形参所需体积、包括连接数据所占空间本程序体所有局部数据所需空间大小层次显示表display：描述正在处理的各嵌套层，对程序体表进行管理btab(3)数组信息表atab数组的下标类型数组元素类型当元素为数组时，它指向该元素数组信息在atab表中的位置，其他情况为0数组下限数组上限数组元素的体积数组本身的体积typea=array[1