第08章、语法制导翻译讲解.ppt

S.P O.P 表 格 管 理 程 序 错 误 处 理 程 序 第8章 语法制导翻译和中间代码生成 2 8.1　属性文法 8.2　语法制导翻译 8.3　常用中间代码 8.4 简单赋值语句的翻译 第8章 语法制导翻译和中间代码生成 教学要求： 理解语法制导翻译的基本思想 会写出语句的逆波兰表示、三元式、四元式和树形结构 3 4 编译中的语义处理是指两个功能： 第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义，也称为静态语义检查或静态审查。动态语义检查需要生成相应的目标代码，在运行时进行。 第二，如果静态语义正确，语义处理的工作是要执行真正的翻译，即生成程序的一种中间表示形式（中间代码），或者直接生成实际的目标代码。 语义处理 5 静态语义检查 （1）类型检查。根据类型相容性要求，验证程序中执行的每个操作是否遵守语言的类型系统的过程，编译程序必须报告不符合类型系统的信息。 （2）控制流检查。控制流语句必须使控制转移到合法的地方。如C语言中不允许goto转入case语句流；break语句需要寻找包含它的最小switch、while或for语句方可找到转向点，否则出错。 （3）上下文相关性检查。比如，变量名字必须先声明后引用。 （4）一致性检查。如在相同作用域中标识符只能说明一次、case语句的标号不能相同等。 6 语义的形式化描述要远比语法的形式化困难得多。目前较为常见的是用属性文法作为描述程序语言语义的工具，并采用语法制导翻译的方法完成对语法成分的翻译工作。 在语法分析过程中，每当一个产生式获得匹配（自上而下分析）或用于归约（自下而上分析）时，就执行相应于该产生式的语义子程序进行语义处理，这个过程就是语法制导翻译。 7 8 8.1 属性文法 属性文法是Knuth在1968年首先提出的。它是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）附加若干相关的“值”（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等。属性与变量一样，可以进行计算和传递。属性的加工过程即是语义处理的过程。 对于文法的每个产生式附加一组属性的计算规则，称为语义规则。 这样一来，属性文法实际上就是附加了一组属性和语义规则的文法。 9 一、属性文法的形式 属性文法(AG，Attribute Grammar)是一个三元组：A=(G,V, F)， 其中， G: 是一个上下文无关文法； V: 有穷的属性集，每个属性与一个文法符号相连； F：语义规则，每条与一个产生式相联，只引用该产生式左端或右端的终结符或非终结符相联的属性。 文法符号X的属性t常用X.t来表示。 10 附加了一组属性和运算（语义）规则的文法 属性文法 文法符号X的属性t常用X.t来表示 语义规则是根据产生式所蕴涵的语义操作建立起来的，并与语义分析的目标有关 不同的产生式对应不同的语义规则 不同的分析目标也对应不同的语义规则 静态语义检查、符号表操作、代码生成及打印各种错误信息 11 二、属性的分类-- 继承的和综合的属性 综合属性：在语法树中，一个结点的综合属性由该结点的子结点的属性值确定。它的计算规则由底向上. 继承属性：在语法树中，一个结点的继承属性由该结点的父结点/兄弟结点的属性确定。即它 的计算规则由顶向下。 简单地说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。 12 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给定的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由参数提供。 (1) 非终结符既可以有综合属性，也可以有继承属性。 (2) 终结符只有综合属性,它们是由词法分析器提供的。 (3) 文法开始符号的所有继承属性，作为属性计算前的初始值是已知的。 书上错：文法开始符号没有继承属性（×）。 13 [例1] （综合属性）可用作台式计算器的简单算术表达式求值的语义描述 非终结符E、T及F都有一个综合属性val，符号 i 有一个综合属性，它的值由词法分析器提供。与产生式L→E对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。某些非终结符加上标（也有的参考书加下标）是为了区分一个产生式中同一非终结符多次出现。 语 义 规 则 L E E E1+T E T T T1 * F T F F (E) F i Print(E.val) E.val:=E1.val+T.val E.val:=