编译原理第7章语法制导翻译和中间代码生成.doc

第七章 语法制导翻译和中间代码生成 编译程序的任务是把源程序翻译成目标程序，这个目标程序必须和源程序的语义等同，也就是说，尽管它们的语法结构完全不同，但它们所表达的结果应完全相同。通常，在词法分析程序和语法分析程序对源程序的语法结构进行分析之后，要么由语法分析程序直接调用相应的语义子程序进行语义处理，要么首先生成语法树或该结构的某种表示，再进行语义处理。 编译中的语义处理是指两个功能：第一，审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。第二，如果静态语义正确，语义处理则要执行真正的翻译，即，要么生成程序的一种中间表示形式（中间代码），要么生成实际的目标代码。 为什么有的编译程序直接生成目标代码，有的编译程序采用中间代码，所谓中间代码，也称中间语言，是复杂性介于源程序语言和机器语言的一种表示形式。一般，快速编译程序直接生成目标代码，没有将中间代码翻译成目标代码的额外开销。但是为了使编译程序结构在逻辑上更为简单明确，常采用中间代码，这样可以将与机器相关的某些实现细节置于代码生成阶段仔细处理，并且可以在中间代码一级进行优化工作使得代码优化比较容易实现。 本章重点：属性文法、语法制导翻译方法的基本思想、几种典型的中间代码形式、一些语法成分的翻译工作。 第一节 属性文法 →T1+T2|T1orT2 T→num|true|false 因为T在同一个产生式里出现了两次，使用上角标将它们区分开。 对输入串3+4的语法树如图7-1-1（a） 属性文法记号中常使用N.t的形式表示与非终结符N相联的属性t。比如可把完成对上面表达式的类型检查的属性文法写成图7-1-2的形式。与每个非终结符T相联的有属性t，t要么是int，要么是bool。与非终结符E的产生式相联的断言指明：两个T的属性必须相同。图7-1-1(b)是图7-1-1(a)语法树结点带有语义信息的表示。 属性文法最早出自克努特笔下。他把属性分成两类：继承属性和综合属性，我们不对属性文法进行理论上的研究而仅仅将它做为工具描述语义分析。在编译的许多实际应用中，属性和断言以多种形式出现，也就是说，与每个文法符号相联的可以是各种属性、断言、以及语义规则，或者某种程序设计语言的程序段等等。下面再给出一些例子。 例1： 简单算术表达式求值的语义描述。 产生式 语义规则 （0）L→E print(E.val) （1）E→E1+T E.val：=E1.val+T.val （2）E→T E.val：=T.val （3）T→T1*F T.val：=T1.val×F.val （4）T→F T.val：=F.val （5）F→(E) F.val：=E.val （6）F→digit F.val：=digit.lexval 在该描述中，每个非终结符都有一个属性：一个整数值的称作val的属性。按照语义规则对每个产生式来说，它的左部E，T，F的属性值的计算来自它右部的非终结符，这种属性称作综合属性。单词digit仅有综合属性，它的值是由词法分析程序提供的。和产生式L→E相联的语义规则是一个过程，打印由E产生的表达式的值。我们可以理解为L的属性是空的或是虚的。 第二节 语法制导翻译概论 在语法分析过程中，随着分析的步步进展，根据每个产生式所对应的语义子程序（或语义规则描述的语义动作）进行翻译的办法称作语法制导翻译。 假定我们现在要分析的语法成分是简单算术表达式，所完成的语义的处理不是将它翻译成中间代码或目标代码，而是计算表达式的值。采用的描述系统是上节的例1。假如语法分析方法是自下而上的。在用某一产生式进行归约的同时就执行相应的语义动作，在分析出一个句子时，这个句子的“值”也就同时产生了，例如输入串是2+3*5，其语法树如图7-2-1(a)，在第一步归约用到了产生式（6），执行的语义动作是置F.val的值为单词digit值，我们把语法树中每个结点的语义值括在该结点处。那么第一步归约并完成语义动作后的情形在图7-2-1(b)中指出。继续进行分析，第七次归约后的情形在图7-2-1(c)中指出归约至E时，它的值17也计算出来了。 语法制导翻译的具体实现途径不困难。假定有一个LR语法分析器，现在把它的分析栈扩充，使得每个文法符号都跟有语义值，即把栈的结构看成图7-2-2所示那样。 Sm y.Val Y Sm-1 x.Val X ┆ ┆ ┆ S0 — # 状态栈 语义值 符号栈 图7-2-2 扩充的分析栈 状态 ACTION（动作） GOTO（转换） d + * ( ) # E T F 0 s5 s4 1 2 3 1 s6 Acc 2 r2 s7 r2 r2 3 r4 r4 r4 r4 4 s5 s4 8