编译原理-第六章习题答案.ppt

* 4.2 翻译模式 1）翻译模式的概念： 翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号｛ ｝括起来，可以被插入到产生式右部的任何合适的位置上。 这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。 翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。 翻译模式保证了按深度优先次序一次扫描就能完成属性的计算。 例 一个简单的翻译模式 E→TR R→addop T {print(addop.lexeme)} R1|ε T→num {print(num.val)} E T 9 print(‘9’) R - T 5 print(‘5’) print(‘-’) R + T print(‘2’) print(‘+’) 2 R ε 9-5+2翻译成后缀式95-2+ * 2）翻译模式的构造 条件：属性文法是L-属性文法； 保证语义动作不会引用还没有计算的属性值。 a. 只需要综合属性的情况： 为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。 例如： T→T1*F T?val = T1 ?val*F ?val T→T1*F { T?val = T1 ?val*F ?val} b. 既有综合属性又有继承属性: 产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。 一个动作不能引用这个动作右边符号的综合属性。( 因为综合属性是在该符号所有分析动作结束后计算） 产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。 * 4.3 自顶向下的翻译 用翻译模式构造自顶向下翻译。 从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取公共左因子，在改写基本文法时考虑属性值的计算。 例 图6.13的带左递归的文法的翻译模式被转换成图6.14的带右递归的文法的翻译模式。 E?E1+T ｛E ? val:=E1?val+T ? val} E ? E1-T ｛E ? val:=E1 ? val-T ?val｝ E ? T {E.val:=T ? val} T ? (E) ｛T ? val:=E ?val｝ T ? num ｛T ? val:=num ?val} 图6.13 带左递归的文法的翻译模式 上一页 下一页 * 编译原理电子教案 第六章 属性文法和语法制导翻译 * 本章的主要内容 属性文法和语法制导的翻译的概念 综合属性和继承属性的概念、特点 S-属性文法与L-属性文法的概念及分析方法 翻译模式 递归下降翻译器的设计 * 本章要求 知识点：语法制导定义，S-属性定义及其自底向上计算属性，L-属性定义，自顶向下的翻译，自底向上计算继承属性。 深刻理解：属性，综合属性，继承属性，依赖图，计算顺序，语法树，语法制导定义，S-属性文法定义，L-属性文法定义，翻译模式。 熟练掌握：对于已知文法G和翻译任务，构造其L-属性定义，将其改造成适于自顶向下分析或自底向上分析的翻译模式。 * 本章教学线索 1 属性文法（属性翻译文法） 1.1 属性文法的概念 1.2 属性的分类 1.3 属性的计算规则 2 基于属性文法的处理办法 3 S-属性文法的自下而上计算 4 L-属性文法和自顶向下翻译 5 自下而上计算继承属性 * 1 属性文法（属性翻译文法） 语法制导翻译：通过给语法树上各个符号赋予一定的含义 并且将各个符号进行有结构的连接，可以形成语言的具 体语句的含义。这给予我们以启示：可以通过扩充文法， 在文法符号上附着某些语义信息，并在这些语义信息间建 立相互计算关系，从而在语法分析的同时进行语义分析。 由于这种分析是在语法分析的控制下进行的，故称为语法 制导翻译。 * 1.1 属性文法的概念 （1）属性文法的定义 在上下文无关文法的基础上，为每个文法符号（终结符和非终结符）配备若干相关的“值”（也称：“属性”），对于文法的每个产生式都配备了一组属性的计算规则（语义规则），这种文法称为属性文法。1968年，Knuth首先提出。 说明：在一般情况下，整个