《编译原理-第七章讲述》由会员分享，可在线阅读，更多相关《编译原理-第七章讲述（85页珍藏版）》请在金锄头文库上搜索。
1、编译原理 第七章 语义分析和中间代码产生 王金伟 计算机与信息工程学院 天津师范大学 *1TJNU-COCIE-WJW 第七章 语义分析和中间代码产生 l在词法分析和语法分析之后的阶段就是语义分析 和中间代码生成 l本章把第六章介绍的有关语法制导翻译的相关方 法和技术用在中间代码生成和语义分析上 l主要工作 l静态语义检查 l翻译 Date 2TJNU-COCIE-WJW l静态语义检查 l类型检查:如果操作符作用于不相容的操作数 ，编译程序必须报告出错信息。 l l 例如例如，在C语言中”.”因该作用与结构体变量 ，若作用于指针变量应用“-” l控制流检查:控制流语句必须使控制转移到合 法的
2、地方。 l l 例如例如，在C语言中break语句使控制跳离包括语 句的最小while、for或switch语句。如果不存 在包括它的这样的语句应该报错。 Date 3TJNU-COCIE-WJW l静态语义检查 l一致性检查:很多场合要求对象只能被定义一次 l l 例如例如，Pascal语言规定同一标识符在一个分程序 中只能被说明一次，同一case语句的标号不能相 同，枚举类型的元素不能重复出现等等。 l相关名字检查:有时，同一名字必须出现两次或 多次。 l l 例如例如，Ada语言程序中，循环或程序块可以有一 个名字，它出现在这些结构的开头和结尾，编译 程序必须检查这两个地方用的名字是相同
3、的。 l其他:如名字的作用域分析等。 Date 4TJNU-COCIE-WJW l翻译（产生中间代码） l采用独立于机器的中间代码的好处： l便于进行与机器无关的代码优化工作 l使编译程序改变目标机更容易 l使编译程序的结构在逻辑上更为简单明确。以中间语 言为界面，编译前端和后端的接口更清晰 静态语义检查态语义检查 和中间间代码码生成器的位 置 语语法 分析器 静 态态 检查检查 器 中间间代 码码 生成器 中 间间 代 码码 符号流 中间间代码码 优优化器 Date 5TJNU-COCIE-WJW 第七章 语义分析和中间代码产生 n7.1 中间语言 n7.2 说明语句 n7.3 赋值语句的翻
4、译 n7.4 分情况语句 n7.5 回填技术 n7.6 类型检查 Date 6TJNU-COCIE-WJW 7.1中间语言 n中间语言 源程序的中间表示方法 n中间语言的形式 后缀式 图表示法 三地址代码 Date 7TJNU-COCIE-WJW 把运算量(操作数)写在前面，把算符写在后面。 例如例如： 原式后缀式 a+b，ab+ a*b，ab* 一、后缀式 Date 8TJNU-COCIE-WJW 1.表达式E的后缀表示递归定义 n如果E是变量和常数，则E的后缀表示是E本身 n如果E是形如E1 op E2的表达式，其中op是任 意的二元算符，则E的后缀表示是E1 E2 op， 其中E1和E2
5、分别是E1和E2的后缀表示 n如果E是形如op E1的表达式，其中op是一元 算符，则E的后缀表示是E1 op，其中E1 是E1 的后缀表示 n如果E是形如(E1)的表达式，则E1的后缀表示 也是E的后缀表示 注意注意：后缀式不需要括号 Date 9TJNU-COCIE-WJW 例例：赋值语句 a := b *（- c）+ b *（ - 34） 的后缀式： a b c- * b 34- * + := Date 10TJNU-COCIE-WJW 1.特点和形式 描述了源程序的自然层次结构 n语法树(抽象语法树) n有向无环图(DAG) 二、图表示法 Date 11TJNU-COCIE-WJW 例
6、例：a := b * - c + b * - c 后缀式是抽象语法树的线性表示 后根序遍历 a b c uminus * b c uminus * + := assign a + * b c uminus (a)抽象语法树 * uminus c b Date 12TJNU-COCIE-WJW assign a + * b c uminus (b) DAG 例例：a:=b * - c+b * -c其中，b*-c是公共子表达式 Date 13TJNU-COCIE-WJW 2.产生赋值语句抽象语法树的属性文法 产生式语义规则 S id := E S.nptr := mknode(:=, mkleaf
7、(id, id.place), E.nptr ) E E1 + E2E.nptr := mknode(+, E1.nptr, E2.nptr ) E E1 * E2E.nptr := mknode(*, E1.nptr, E2.nptr ) E -E1E.nptr := mknode(uminus, E1.nptr ) E ( E1 ) E.nptr := E1.nptr E idE.nptr := mkleaf(id , id.place ) Date 14TJNU-COCIE-WJW 例例：赋值语句：a:=b*-c+b*-c 抽象语法树的表示方法 后缀式：a b c uminus * b
8、c uminus * + assign assign + * uminus id a id c id b * uminus id c id b id b id c unimus 1 * 0 2 id b id c unimus 5 * 4 6 + 3 7 id a assign 9 8 . 0 1 2 3 4 5 6 7 8 9 10 11 Date 15TJNU-COCIE-WJW 1.一般形式 包含三个地址：两个操作数，一个结果 x := y op z 一系列的上述形式 x, y, z是名字、常数和编译器产生的临时变量 op是算符，定点、浮点、逻辑，只能有一个 例例：x + y * z翻译
9、成 t1 := y * z t2 := x + t1 三、三地址代码 Date 16TJNU-COCIE-WJW 1.一般形式（续） 三地址代码是AST或DAG的线性化表示 nDAG图对应的三地址代码可能比相应的AST对 应的三地址代码要优化，因为可以复用中间 结果 Date 17TJNU-COCIE-WJW 例子例子： 相应于a:=b * - c+b * -c的AST和DAG的三地址代码 t1 ： -c t2 ： b* t1 t3 ： -c t4 ： b* t3 t5 ： t2+t4 a ： t5 （a）对于AST的代码 t1：-c t2：b*t1 t5：t2+t2 a：= t5 （b）对于
10、DAG的代码 Date 18TJNU-COCIE-WJW 2.三地址代码的种类 (1)赋值语句： x := y op z，op是二元算术算符或逻辑算符 (2)赋值语句： x := op z，op是一元算符，如：负号，逻辑非 not等 (3)复写语句： x := y Date 19TJNU-COCIE-WJW 2.三地址代码的种类(续1) (4)无条件转移： goto L，L是下一步要执行的三地址语句的标号 (5)条件转移语句： if x relop y goto L 根据逻辑运算的结果决定是否执行转移 if a goto L a为真跳到L执行，否则执行if后边的语句 Date 20TJNU-C
11、OCIE-WJW 2.三地址代码的种类(续2) (6)过程调用语句： param x和call p, n n表示实参个数 例如例如：call p(x1 , x2 , , xn )，表示成三地址语句： param x1 param x2 param xn call p , n 过程返回：return y y表示返回值 Date 21TJNU-COCIE-WJW 2.三地址代码的种类(续3) (7)数组引用赋值 x := y i x i := y (8)地址和指针的使用 x := E.code:=E1.codeE2.code gen(E.place:=E1.place +E2.place) EE1
12、*E2E.place:=newtemp; E.code:=E1.codeE2.code gen(E.place:=E1.place*E2.place) E-E1E.place:=newtemp; E.code:=E1.codegen(E.place:=uminusE1.place) E(E1)E.place:=E1.place; E.code:=E1.code EidE.place:=id.place; E.code:= Date 23TJNU-COCIE-WJW 其中： (1)E.place表示存放E值的名字。 (2)E.code表示对E求值的三地址语句序列。 (3)newtemp是个函数，
13、对它的调用将产生一个新的 临时变量 注意注意： 三地址语句序列是语法树的线性表示，用临时变 量代替语法树中的结点 实际实现中，三地址语句序列往往是被存放到一个 输出文件中，而不是将三地址语句序列置入code属性 之中 Date 24TJNU-COCIE-WJW 4. 三地址代码的具体实现 三地址代码是一种抽象形式，其具体实现可用结构 体来表示，有以下几种表示方法： 四元式 ：op, arg1, arg2, result 三元式 ：op, arg1, arg2 间接三元式：间接码表+三元式表 Date 25TJNU-COCIE-WJW (1)四元式 op, arg1, arg2, result
14、nop：算符的内部编码 narg1和arg2分别表示两个操作数 nresult表示计算结果 narg1、arg2和result的内容通常是符号表条目指针 注意注意： n一元运算不需要使用arg2的域 nparam不使用arg2和result域 n条件和无条件转移把目标语句的标号放在result中 Date 26TJNU-COCIE-WJW 例子例子：语句a:=b*-c+b*-c 的四元式表示 arg1arg2resultop (0)uminusct1 (1)*bt1t2 (2)uminusct3 (3)*bt3t4 (4)+t2t4t5 (5)Assignt5a Date 27TJNU-COC
15、IE-WJW (2)三元式 op, arg1, arg2 避免四元式引入临时变量，可以用三地址语句的 序号表示临时变量 有3个域的记录结构 nop：算符的内部编码 narg1和arg2分别表示操作数 n语句的结果通过语句的序号引用 narg1、arg2的内容通常是符号表条目指针或 三地址语句的序号(对于临时变量) Date 28TJNU-COCIE-WJW arg1arg2op 例子例子：语句a:=b*-c+b*-c 的三元式表示 (0)uminusc (1)*b(0) (2)uminusc (3)*b(2) (4)+ (1) (3) (5)Assigna(4) Date 29TJNU-COCIE-WJW 注意注意： 有些三地址语句要多个三元式表示 例子例子： xi := y op arg1 arg2 (0) = x i (1)
