编译原理_07中间代码及其他详解.ppt

主要内容 概述 属性文法 语法制导翻译概述 中间语言 概 述 编译程序的任务是把源程序翻译成语义上等价的目标程序。通常，在编译过程中，经过词法分析和语法分析之后， 接下来将进行语义分析与处理。 编译中的语义处理包括两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。有时把这个工作称为静态语义分析或静态审查。第二，如果静态语义正确，语义处理则要执行真正的翻译，即生成某种中间代码或者实际的目标代码。 本章引入属性文法和语法制导翻译方法的基本思想，介绍几种典型的中间代码形式和一些常见语法成分的翻译方法。 8.1 属性文法 属性，通常用来描述事物的特征、性质、品质等。 属性文法的形式定义：一个属性文法形式上可定义为一个三元组A，A=（G，V，F）。其中G表示一个上下文无关文法；V表示属性的有穷集；F表示有关属性的断言或谓词的有穷集。 在属性文法中: （1）每个属性t都与某个文法符号N相关联，用N.t来表示。例如N.type表示与N关联的属性type。 （2）每个断言与文法的某个规则相关联。 （3）如果对G中的某一输入串（句子）而言， A中的所有断言对该输入串的语法树结点的属性全为真，则该串也是A语言中的句子。 编译程序的静态语义审查工作就是验证关于所编译的程序的断言是否全部为真。 如文法G[S]： E→F1＋F2｜F1 or F2 F→num｜true ｜false 与每个非终结符F相联的属性有type，type为int或者bool。关于类型检验的属性文法可以表示为：? E→Fl＋F2 {F1.type := int AND F2.type := int} E→F1 or F2 {F1.type := bool AND F2.type := bool} F→num {F.type := int} F→true {F.ype := bool} F→false {F.ype := bool} 由上可知，与非终结符E的产生式相联的断言指明：两个F的属性必须相同。 属性可以分为综合属性和继承属性两类。综合属性一般用于自下而上传递信息，而继承属性常常用于自上而下传递信息。下述为简单算术表达式求值的属性文法： 规则 语义规则 1. S→E print（E.val） 2. E→E1＋T E.val := E1.val＋T.val 3. E→T E.va1 := T.valv 4. T→T1 ? F T.val := T1.val ? F.val 5. T→T1 T.val := T1.val 6. F→（E） F.val := E.val 7. F→digit F.val := digit.lexval? 每一个非终结符都有一个表示整数值的属性val。规则左部符号E、T、F的属性值取决于各自规则的右部，称为综合属性；对于文法符号S，其属性是虚的或空的。 8.3 中间语言 所谓中间语言，也称中间代码，是复杂性介于源程序语言和机器语言的一种记号系统。一般来说，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，使生成的的目标代码更为高效，通常采用中间语言。 编译程序所使用的中间语言形式较多。常见的有逆波兰式、三元式、四元式和树形表示等等。 8.3.1 逆波兰式 逆波兰式是最简单的一种中间语言形式，也称做后缀式。它的特点是将运算对象写在前面，把运算符号写在后面。对于简单表达式E，相应的逆波兰式E’遵循下面的转换规则： 表达式 逆波兰式 E E’ (E) E’ －E E@ （负号“－”是一元运算符，为了区别于减号“－”，通常写成@） E1 op E2 E1’ E2’ op 用逆波兰式表示表达