语义分析中间代码与符号表

1、语义分析、中间代码与符号表语义分析、中间代码与符号表 学习目标：学习目标：v掌握：掌握： 常见语法成分的中间代码形式；常见语法成分的中间代码形式；符号表的组织管理符号表的组织管理v理解：理解：语义分析的内容语义分析的内容目标程序目标程序源程序源程序词法分析词法分析语法分析语法分析语义分析语义分析中间代码生成中间代码生成代码优化代码优化目标代码生成目标代码生成表格管理表格管理出错处理出错处理语义分析基础语义分析基础语义分析的内容语义分析的内容 主要是类型相容检查，有以下几种：主要是类型相容检查，有以下几种：1) 各种条件表达式的类型是不是各种条件表达式的类型是不是boolean型？型？2) 运算

2、符的分量类型是否相容？运算符的分量类型是否相容？3) 赋值语句的左右部的类型是否相容？赋值语句的左右部的类型是否相容？4) 形参和实参的类型是否相容形参和实参的类型是否相容?5) 下标表达式的类型是否为所允许的类型？下标表达式的类型是否为所允许的类型？6) 函数说明中的函数类型和返回值的类型是否一函数说明中的函数类型和返回值的类型是否一致？致？其它语义检查：其它语义检查：1)VE中的中的V是不是变量，而且是数组类型？是不是变量，而且是数组类型？2)V.i中的中的V是不是变量，而且是记录类型？是不是变量，而且是记录类型？i是不是不是该记录的域名？是该记录的域名？3)x+f()中的中的f是不是函数

3、名？形参个数和实参个是不是函数名？形参个数和实参个数是否一致？数是否一致？4)每个使用性标识符是否都有声明？有无标识符每个使用性标识符是否都有声明？有无标识符的重复声明？的重复声明？q在语义分析同时产生中间代码，在这种模式下，在语义分析同时产生中间代码，在这种模式下，语义分析的主要功能如下：语义分析的主要功能如下：语义审查语义审查在扫描声明部分时构造标识符的符号表在扫描声明部分时构造标识符的符号表在扫描语句部分时产生中间代码在扫描语句部分时产生中间代码8.3 中间代码的形式中间代码的形式定义：定义：中间代码是一种复杂性介于源程序语言和机器中间代码是一种复杂性介于源程序语言和机器语言之间的一种表

4、示形式。语言之间的一种表示形式。使用中间代码的好处：使用中间代码的好处：中间代码与具体机器无关中间代码与具体机器无关对中间代码进行与机器无关的优化对中间代码进行与机器无关的优化形式：形式：逆波兰记号、三元式、四元式和树形表示逆波兰记号、三元式、四元式和树形表示8.3.1 逆波兰记号逆波兰记号 逆波兰表示法逆波兰表示法将运算对象写在前面，把运算符写在后面，将运算对象写在前面，把运算符写在后面，因而也称后缀式。因而也称后缀式。例如：例如：程序设计语言中的表示程序设计语言中的表示 逆波兰表示逆波兰表示a+bab+a+b*c abc * +(a+b)*cab+c *后缀式的计算机处理后缀式的计算机处理

5、后缀式的最大优点是易于计算机处理后缀式的最大优点是易于计算机处理处理过程：处理过程：从左到右扫描后缀式，每碰到运算对象就推进栈；从左到右扫描后缀式，每碰到运算对象就推进栈；碰到运算符就从栈顶弹出相应目数的运算对象施碰到运算符就从栈顶弹出相应目数的运算对象施加运算，并把结果推进栈。最后的结果留在栈加运算，并把结果推进栈。最后的结果留在栈顶。顶。 bt1dct1t2t1t3t1= - bt2= c*dt3= t1+t2例：表达式例：表达式bc*d的后缀式的后缀式 bcd*+的计值过程的计值过程8.3.2 三元式和树形表示三元式和树形表示三元式三元式(算符算符op，第一个运算对象第一个运算对象ARG

6、1,第二个运算对象第二个运算对象ARG2)说明：说明：三元式的某些运算对象是另一三元式的某些运算对象是另一个三元式的编号（代表其结果）个三元式的编号（代表其结果）一目算符只需选用一个运算对一目算符只需选用一个运算对象（象（ARG1）多目算符可用连续几个三元式多目算符可用连续几个三元式表示表示例：例： a :b*c+b*d表示为表示为 (1) (* ,b,c)(2) (* ,b,d)(3) (+ ,(1),(2)(4) (:,(3),a)树形表示树形表示二目运算对应二叉子树，多目运算对应多叉子二目运算对应二叉子树，多目运算对应多叉子树，但通常通过引入新结点表示成二叉子树。树，但通常通过引入新结点

7、表示成二叉子树。例如：例如：a:b*c+b*d 表示成表示成:=a+*bcbd8.3.3 四元式四元式四元式表示四元式表示四元式是一种比较普遍采用的中间代码形式四元式是一种比较普遍采用的中间代码形式(算符算符op，ARG1，ARG2，运算结果运算结果RESULT）例如：例如：a:b*c+b*d的四元式表示如下：的四元式表示如下： 1) (*,b,c,t1 )2) (*,b,d,t2 )3) (+,t1,t2,t3 )4) (:, t3 ,a ) 其中其中t i（i1,2,3）是编译程序引入的临时变量是编译程序引入的临时变量四元式的优点：四元式的优点：四元式比三元式更便于优化。四元式比三元式更便

8、于优化。优化要求改变运算顺序或删除某些运算，引起编号优化要求改变运算顺序或删除某些运算，引起编号的变化。的变化。三元式通过编号引用中间结果，编号的变化引起麻三元式通过编号引用中间结果，编号的变化引起麻烦；四元式通过临时变量引用中间结果，编号变化烦；四元式通过临时变量引用中间结果，编号变化无影响。无影响。四元式对生成目标代码有利。四元式对生成目标代码有利。四元式表示很类似于三地址指令，很容易转换成机四元式表示很类似于三地址指令，很容易转换成机器代码。器代码。 符号表符号表1.符号表及其作用符号表及其作用符号表符号表(Symbol Table)符号表是存放标识符信息的一种表，其中的信息符号表是存放

9、标识符信息的一种表，其中的信息表示的是标识符的属性表示的是标识符的属性(语义语义)。符号表的作用符号表的作用符号表是连接符号表是连接声明声明与与引用引用的桥梁。一个名字在声的桥梁。一个名字在声明时，相关信息被填写进符号表，而在引用时，明时，相关信息被填写进符号表，而在引用时，根据符号表中的信息生成相应的可执行语句。它根据符号表中的信息生成相应的可执行语句。它的作用主要有：的作用主要有： 辅助语义的正确性检查辅助语义的正确性检查 辅助代码生成辅助代码生成2. 符号表的设计符号表的设计如何有效记录各类符号的属性，以便在编译的各如何有效记录各类符号的属性，以便在编译的各个阶段对符号表进行快速、有效的

10、查找、插入、个阶段对符号表进行快速、有效的查找、插入、修改、删除等操作，是符号表设计的基本目标。修改、删除等操作，是符号表设计的基本目标。符号表的组成符号表的组成表项分两部分，其中前者是标识符的名字（或在表项分两部分，其中前者是标识符的名字（或在名表中的地址），而后者是属性部分（不同种类名表中的地址），而后者是属性部分（不同种类的标识符属性不同）。的标识符属性不同）。符号表的组织方式和查找方法符号表的组织方式和查找方法符号表的组织方式可以是数组也可以是链表等等，符号表的组织方式可以是数组也可以是链表等等，查找算法可以是顺序查表法、平分查表法、散列查找算法可以是顺序查表法、平分查表法、散列查表法

11、等查表法等合理的组织和查找，将使得符号表的操作更高效合理的组织和查找，将使得符号表的操作更高效3. 符号的主要属性符号的主要属性名字名字类型类型 存储类别存储类别 （静态、（静态、regist，公共、内部。）公共、内部。）作用域及可视性作用域及可视性 存储分配信息存储分配信息n两类存储区两类存储区l静态：生命周期是整个程序的运行过程静态：生命周期是整个程序的运行过程 l动态：适应局部变量的生存和消亡，提高程序运行的空间效率动态：适应局部变量的生存和消亡，提高程序运行的空间效率 n具体位置具体位置过程的说明部分：过程的说明部分：CONST A=35,B=49;CONST A=35,B=49;VA

12、R C,D,E;VAR C,D,E;PROCEDURE P;PROCEDURE P;VAR GVAR GTABLETABLE表中的信息表中的信息NAME:ANAME:BNAME:CNAME:D NAME:E NAME:PKind :CONSTANTKind :CONSTANTKind :VARIBALEKind :VARIBALE Kind :VARIBALEKind :PROCEDURVAL:35 VAL:49 LEVEL:LEV LEVEL:LEV LEVEL:LEV LEVEL:LEVADR: DX ADR: DX+1 ADR: DX+2ADR:SIZE:4NAME:G Kind :VA

13、RIBALE LEVEL:LEV+1 ADR: DX 变量相对本过程变量相对本过程基地址的偏移量基地址的偏移量4. 符号表的总体组织符号表的总体组织第一种：按属性完全相同的组织多张表，空间第一种：按属性完全相同的组织多张表，空间效率高，但管理复杂效率高，但管理复杂第二种：所有符号一张表，管理集中单一，但第二种：所有符号一张表，管理集中单一，但空间臃肿空间臃肿第三种：折衷方式是根据符号属性相似程度分第三种：折衷方式是根据符号属性相似程度分类组织成若干张表，每张表中记录的符号都有类组织成若干张表，每张表中记录的符号都有比较多的相同属性。比较多的相同属性。 5. 分程序结构的符号表分程序结构的符号表

14、对于具有分程序型结构的语言程序，不同层次分程序中对于具有分程序型结构的语言程序，不同层次分程序中定义的标识符号具有不同的作用域和不同的可视性规则。定义的标识符号具有不同的作用域和不同的可视性规则。各分程序独立组织（分表结构）：每当编译程序扫描到各分程序独立组织（分表结构）：每当编译程序扫描到一个分程序结构一个分程序结构开始开始时，为该分程序时，为该分程序建立建立一张符号表，一张符号表，在该分程序中定义的标识符，都被在该分程序中定义的标识符，都被登录登录在该符号表中。在该符号表中。而当编译程序扫描到一个分程序的而当编译程序扫描到一个分程序的结束结束时，编译程序时，编译程序释释放放为该分程序所建立的符号表。为该分程序所建立的符号表。统一组织（单表结构）：所有分程序中定义的标识符都统一组织（单表结构）：所有分程序中定义的标识符都集中在单张符号表中。为了实现分程序构造中标识符