第5讲--中间代码翻译.ppt

CompilerPrinciples 第五讲 语义分析和中间代码产生 语义分析概述 中间语言 几种常用语句的翻译 符号表 静态语义检查和中间代码产生在编译程序中的位置如图所示： ◇ 虽然源程序可以直接翻译为目标语言代码，但是通常编译程序还是采用了独立于机器的、复杂性介于源语言与机器语言之间的中间语言。这样做的好处是： （1）便于进行与机器无关的代码优化； （2）使编译程序改变目标机更容易； （3）使编译程序的结构在逻辑上更为简单明确，以中间语言为界面，编译前端和后端的接口更清晰。 §1. 语义分析概述 一、语义分析的任务 审查每一个语法结构的静态语义，即验证语法正确的结构是否有意义。 如：赋值语句：x:=x+y,左边变量类型与右边变量类型是否一致。 在语义正确的基础上生成一种中间代码或目标代码。 二、语义分析的范围 1.确定类型：确定标识符所关联的数据类型。 2.类型检查：按语言的类型规则，检查运算的合法性与运算分量类型的一致性，必要时作类型转换。 3.识别含义：根据语言的语义定义（形式或非形式），识别程序中各构造成分组合到一起的含义，并作相应的语义处理（生成中间代码或目标代码）。 4.控制流检查：控制流语句必须转移到合法的地方。 如C中，break语句规定跳出最内层的循环或switch语句。 5.一致性检查：在很多场合要求对象只能被说明一次。如：pascal语言规定同一个标识符在一个分程序中只能被说明一次等。 6.相关名字检查：如：Ada，循环或块可以有一个名字，它出现在这些结构的开头或结尾。编译程序必须检查这两个地方用的名字是否相同。 其它：如名字的作用域分析等也是语义分析的工作。 三、语义描述工具和语义分析方法 语义描述工具 目前流行：用属性文法作为描述语义的工具。 语义分析方法 根据描述属性文法的语义规则的方式不同分为： 语法制导定义 翻译方案 属性文法形式定义：一个属性文法是一个三元组A=(G,V,F) 其中：G为一个上下文无关文法； V 表示属性的有穷集合； F表示属性的断言或谓词的有穷集。 语义规则 在对文法符号属性处理过程中，为文法的每一产生式定义一组属性的计算规则，称为语义规则。 3.语法制导翻译 所谓语法制导翻译是指：对文法中的每个产生式都附加上一个语义动作或语义子程序。伴随着语法分析，每当使用一条产生式进行推导或归约时，就执行相应产生式的语义动作（包括：查填表格，改变变量的求值，诊察与报告错误，生成中间代码等），从而完成预定的翻译工作。 §2.几种常用的中间语言形式 一、逆波兰表示法 波兰表示是波兰逻辑学家J·卢卡西维奇于1929年提出的一种既不须考虑优先关系、又不用括号的一种表示表达式的方法（前缀式），在计算机出现以后，这种表示方法显出了巨大的优越性。后人为了纪念他，就用其祖国名字来命名这种表示方法。现在我们要介绍的刚好是另一种波兰表示形式，称为后缀式，即运算符在后。 例： a+b → ab+ a*(b+c) → abc+* -a+b*c → a@bc*+ 二、图表示法 这里要介绍的图表示包括DAG与我们前面介绍过的抽象语法树。 1. 无循环有向图（DAG） DAG与抽象语法树基本上一样，对表达式中的每个子表达式，DAG中都有一个结点。一个内部结点表示一个操作符，它的孩子表示操作数。 两者所不同的是，在一个DAG中代表公共子表达式的结点具有多个父结点，而在一棵抽象语法树中公共子表达式被表示为重复的子树。如下例： 2.再来看A*B+C*D的树、后缀式 3.树表示的翻译法： 例： 产生式 语义动作 (1)E→E1 op E2 {E.val:=NODE(op,E1.val,E2.val)} (2)E→(E1) {E.val:=E1.val} (3)E→-E1 {E.val:=UNARY(@E1.val)} (4)E→i {E.val:=LEAF(i)} 三、三元式 1.三元式由三个部分组成： 算符：OP 第一运算分量：ARG1 第二运算分量：ARG2 2.各种语句都可表示成一组三元式 例1： OP ARG1 ARG2 x+y*z (1) * y z