第六章(语义分析与中间代码生成).ppt

第六章语义分析与中间代码生成 贵州大学 计算机科学与技术学院 本章内容 介绍几种常用的中间表示：后缀表示、图形表示和三地址代码 用语法制导定义和翻译模式的方法来说明程序设计语言的典型语法结构怎样被翻译成中间形式 重点：三地址码，各种语句的目标代码结构、语法制导定义与翻译模式 难点：布尔表达式的翻译，对各种语句的目标代码结构、语法制导定义与翻译模式的理解 本章内容 6.1 中间代码的形式 6.2 声明语句的翻译 6.3 赋值语句的翻译 6.4 布尔表达式和控制流语句的翻译 6.1 中间代码的形式 中间语言(复杂性界于源语言和目标语言之间)的好处： 便于进行与机器无关的代码优化工作 易于移植 使编译程序的结构在逻辑上更为简单明确 6.1 中间代码的形式 常用的中间代码： 后缀式（逆波兰表示） 图表示： DAG、语法树 三地址代码 三元式 四元式 间接三元式 6.1.1 后缀式 中缀表达式的计算顺序不是运算符出现的自然顺序，而是根据运算符间的优先关系来确定的，因此，从中缀表达式直接生成目标代码一般比较麻烦。 后缀式表示法：Lukasiewicz发明的一种表示表达式的方法，又称逆波兰表示法。 一个表达式E的后缀形式可以如下定义： 1. 如果E是一个变量或常量，则E的后缀式是E自身。 2. 如果E是E1 op E2形式的表达式，其中op是任何二元操作符，则E的后缀式为E1? E2? op，其中E1? 和E2? 分别为E1 和E2的后缀式。 3. 如果E是(E1)形式的表达式，则E1 的后缀式就是E的后缀式。 6.1.1 后缀式 例6.1 下面给出的是一些表达式的中缀、前缀和后缀表示。 中缀表示 前缀表示 后缀表示 a+b +ab ab+ a*(b+c) *a+bc abc+* (a+b)*(c+d) *+ab+cd ab+cd+* a:=a*b+c*d :=a+*ab*cd aab*cd*+:= 6.1.2 图形表示 图表示法 语法树 DAG 图形表示 有向无环图(Directed Acyclic Graph，简称DAG) 对表达式中的每个子表达式，DAG中都有一个结点 一个内部结点代表一个操作符，它的孩子代表操作数 在一个DAG中代表公共子表达式的结点具有多个父结点 6.1.3 三地址代码 所谓三地址码，是指这种代码的每条指令最多只能包含三个地址，即两个操作数地址和一个结果地址。 一般形式： x := y op z 表达式x + y ? z 翻译成的三地址语句序列是 t1 := y ? z t2 := x + t1 常用的三地址语句 赋值语句x := y op z， x := op y， x := y 无条件转移goto L 条件转移if x relop y goto L 过程调用和返回使用如下的指令来实现： param x用来指明参数； call p, n和y=call p, n 用来表示过程调用和函数调用； return y表示过程返回； 索引赋值x := y[ i ]和 x[ i ] := y 地址和指针赋值x := y，x := ?y 和?x := y 三元式 形如x[i]:=y和x:=y[i]的三元运算符需要用两条三元式指令来表示 6.2 声明语句的翻译 分析过程或程序块的声明序列时： 为局部名字建立符号表条目 为它分配存储单元 符号表中包含了名字的类型和分配给它的存储单元的相对地址等信息 相对地址：对静态数据区基址的偏移或对活动记录中局部数据区基址的偏移。 6.2.1 过程中的说明 一个过程中的所有声明语句可集中处理。用一个全程变量offset来记录下一个可用的相对地址。 program main var A, B : real; … procedure P1 var B:boolean; … begin … end procedure P2 var A:integer; … begin … end begin … end 3.所讨论语言的文法(允许过程嵌套) P ? D S (1) D ? D ; D (2) | id : T (3) | proc id ; D ; S (4) 6.2.3 记录的域名 下述产生式中的非终结符T产生记录类型 T ? record D end 例：