编译原理符号表的原理及典型实例

编译原理第九章符号表在编译程序工作的过程中,需要不断收集、记录和使用源程序中一些语法符号的类型和特征等相关信息。这些信息一般以表格形式存储于系统中。如常数表、变量名表、数组名表、过程名表、标号表等等，统称为符号表。对于符号表组织、构造和管理方法的好坏会直接影响编译系统的运行效率。第九章符号表一、符号表的作用和功能收集符号属性上下文语义的合法性检查的依据作为目标代码生成阶段地址分配的依据例：C语言程序段：inta;a=1;MOV#1,R0MOVR0,mema词法分析：a是一个单词；语法分析：a出现在一条变量声明语句和一条赋值语句中；语义分析：a是一个整形变量，并分配地址。二、符号表的内容标识符的名字与标识符有关的信息类型信息（包括种类和属性）地址码层次信息行号信息……二、符号表的内容例：Pascal语言的名字信息表nametabnamekindlevtypnormalrefadr/val/sizelink01tx→名字标识符名字种类，可以是常量(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二、符号表的内容例：Pascal语言的名字信息表nametabtypea=array[1..10,1..10]ofinteger;namekindtyprefkatypearraysntx→nametab例：Pascal语言的数组信息表atabinxtypeltypelreflowhighelsizesize12ax→数组的下标类型数组元素类型当元素为数组时，它指向该元素数组信息在atab表中的位置，其他情况为0数组下限数组上限数组元素的体积数组本身的体积二、符号表的内容typea=array[1..10,1..10]ofinteger;namekindtyprefkatypearraysntx→nametabinxtypeltypelreflowhighelsizesizenintsarraysm11010100mintsints0110110ax→atab三、符号表的组织按照属性种类完全相同的那些符号组织在一起；把所有语言中的符号都组织在一张符号表中；根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有比较多的相同属性。三、符号表的组织假设有下列三类符号及其所需属性第一类符号属性1属性2属性3第二类符号属性1属性2属性4第三类符号属性2属性5属性6第一种组织法：按属性分类优点：管理一致，空间效率高缺点：管理复杂三、符号表的组织假设有下列三类符号及其所需属性第一类符号属性1属性2属性3第二类符号属性1属性2属性4第三类符号属性2属性5属性6第二种组织法：单一组织优点：管理一致，集中单一缺点：管理复杂三、符号表的组织假设有下列三类符号及其所需属性第一类符号属性1属性2属性3第二类符号属性1属性2属性4第三类符号属性2属性5属性6第三种组织法：折中方法四、符号表的数据结构线性表——符号表项按照符号被扫描到的先后顺序登录……………………a………………………b………a………………………d………c………………………b…………四、符号表的数据结构有序表——符号表项按照符号的字符代码串的值的大小排列……………………a………………………b………a………………………d………c………………………b…………四、符号表的数据结构散列表——符号表项的位置由对该符号进行某种函数操作所得到的函数值来确定……………………a………………………b………a………………………d………c………………………b…………五、符号表与作用域intmain(){inta=0;intb=0;{intb=1;{inta=2;printf(“%d,%d\n”,a,b);}{intb=3;printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}B2B3B1B0intmain(){inta=0;intb=0;{intb=1;{inta=2;printf(“%d,%d\n”,a,b);}{intb=3;printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}printf(“%d,%d\n”,a,b);}NULLabbabB0的符号表B1的符号表B2的符号表B3的符号表