《编译原理第五章.》由会员分享，可在线阅读，更多相关《编译原理第五章.（193页珍藏版）》请在金锄头文库上搜索。
1、编 译 原 理 Compiler Principles 徐佳 xujia 教学网站：http:/10.20.79.1 南京邮电大学.计算机学院 第五章 语法制导翻译及中间代码生成 compilingcompiling runningrunning programmingprogramming 教材：教材：编译技术原理及其实现方法编译技术原理及其实现方法王汝传王汝传 编著编著 1 第五章 语法制导翻译及中间代码生成 本章内容本章内容 5.1 5.1 语语语语法制法制导导导导翻翻译译译译概述概述 一、一、语语语语法制法制导导导导翻翻译译译译定定义义义义 二、二、语语语语法制法制导导导导翻翻译译译译
2、原理原理 三、三、语语语语法制法制导导导导翻翻译实现译实现译实现译实现 5.2 5.2 中中间语间语间语间语 言言 一、引言一、引言 二、逆波二、逆波兰兰兰兰表示表示 三、三元式三、三元式 四、四、树树树树形表示形表示 五、四元式五、四元式 2 第五章 语法制导翻译及中间代码生成 本章内容本章内容 5.3 5.3 自底向上自底向上语语语语法制法制导导导导翻翻译译译译 一、一、简单简单简单简单 算算术术术术表达式和表达式和赋值语赋值语赋值语赋值语 句的翻句的翻译译译译 二、布二、布尔尔表达式的翻表达式的翻译译译译 三、控制三、控制语语语语句翻句翻译译译译 * 四、数四、数组组组组元素的翻元素的翻
3、译译译译 五、五、过过过过程程语语语语句的翻句的翻译译译译 六、六、说说说说明明语语语语句的翻句的翻译译译译 5.4 5.4 自自顶顶顶顶向下向下语语语语法制法制导导导导翻翻译译译译 一、一、递归递归递归递归 下降的下降的语语语语法制法制导导导导翻翻译译译译 二、二、LL(1)LL(1)语语语语法制法制导导导导翻翻译译译译 5.5 5.5 属性文法与属性翻属性文法与属性翻译译译译 一、属性文法与一、属性文法与L L属性文法属性文法 二、属性翻二、属性翻译译译译 3 第五章 语法制导翻译及中间代码生成 本节内容本节内容 5.1 5.1 语法制导翻译概述语法制导翻译概述 一、语法制导翻译定义一、语
4、法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现 5.2 5.2 中间语言中间语言 一、引言一、引言 二、逆波兰表示二、逆波兰表示 三、三元式三、三元式 四、树形表示四、树形表示 五、四元式五、四元式 4 5.1 5.1 语法制导翻译概述语法制导翻译概述 本节内容本节内容 一、语法制导翻译定义一、语法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现 5 第五章 语法制导翻译及中间代码生成 5.1 5.1 语法制导翻译概述语法制导翻译概述 在前面我们已经讨论了词法分析和语法分析，一个程序成功地通在前
5、面我们已经讨论了词法分析和语法分析，一个程序成功地通 过词法分析和语法分析，只能说明它是一个合法程序，但是对程序内过词法分析和语法分析，只能说明它是一个合法程序，但是对程序内 部的部的逻辑含义逻辑含义并未加以考虑，从整个编译程序来看，词法分析和语法并未加以考虑，从整个编译程序来看，词法分析和语法 分析仅仅是编译程序的一部分，编译程序最终的目的是将源程序翻译分析仅仅是编译程序的一部分，编译程序最终的目的是将源程序翻译 成可供计算机直接执行的目标程序。成可供计算机直接执行的目标程序。 在某些在某些编译编译编译编译 程序中，是直接生成程序中，是直接生成机器机器语语语语言言或或汇编语汇编语汇编语汇编语
6、 言言形式的目形式的目标标标标 代码；有些编译程序是把源程序翻译为某种形式代码；有些编译程序是把源程序翻译为某种形式中间语言代码中间语言代码，然后，然后 再把中间语言代码翻译为目标代码。再把中间语言代码翻译为目标代码。 下面就来介绍一种语法制导翻译方法，这种方法先将源程序单词下面就来介绍一种语法制导翻译方法，这种方法先将源程序单词 序列翻译成中间语言，然后再将中间语言翻译成目标程序。那么，什序列翻译成中间语言，然后再将中间语言翻译成目标程序。那么，什 么叫语法制导翻译呢？么叫语法制导翻译呢？ 6 第五章第五章 语法制导翻译及中间代码语法制导翻译及中间代码 5.1 5.1 语法制导翻译概述语法制
7、导翻译概述 一、语法制导翻译定义一、语法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现 7 第五章第五章 语法制导翻译及中间代码语法制导翻译及中间代码 5.1 5.1 语法制导翻译概述语法制导翻译概述 一、语法制导翻译定义一、语法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现 8 5.1 语法制导翻译概述 一、语法制导翻译定义 语法制导翻译就是以语法分析为主导的语义处理。语法分析过程中嵌 入语义动作，即调用对应的语义子程序。 例如在前面语法分析时分析a+b*c表达式，其分析语法树如下： E E
8、+ + E E E E * * E E E E a a b b c c 语法分析是将语法分析是将a a归约归约E E，再将再将b b归约归约E E，将，将c c归约为归约为E E，然后再将然后再将E*EE*E归约成归约成E E，再将再将 E+EE+E归约成归约成E E，所以所以a+b*ca+b*c是一个合法的句子。如果考虑语义，在归约过程中加上是一个合法的句子。如果考虑语义，在归约过程中加上 语义动作，先将语义动作，先将a a归约为归约为E E，将，将a a值赋给值赋给E E后，后，b b归约成归约成E E，同时将同时将b b值赋给值赋给E E，在将在将c c 值赋给值赋给E E，然后再将然后
9、再将b*cb*c（E*EE*E）给给E E，最后再将左右两个，最后再将左右两个E E值相加就是最终结果，值相加就是最终结果， 这就是语法制导翻译的基本思想，在语法分析同时进行语义分析。这就是语法制导翻译的基本思想，在语法分析同时进行语义分析。 9 第五章第五章 语法制导翻译及中间代码语法制导翻译及中间代码 5.1 5.1 语法制导翻译概述语法制导翻译概述 一、语法制导翻译定义一、语法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现 10 第五章第五章 语法制导翻译及中间代码语法制导翻译及中间代码 5.1 5.1 语法制导翻译概述语法制导翻译概述
10、一、语法制导翻译定义一、语法制导翻译定义 二、语法制导翻译原理二、语法制导翻译原理 三、语法制导翻译实现三、语法制导翻译实现 11 5.1 语法制导翻译概述 二、语法制导翻译原理 语法制导翻译的原理就是先为每个文法规定相应的语义，即编写出 相应语义处理子程序，整个分析是以语法分析为主导。在自顶向下 语法分析时，若某一个规则右部与输入串相匹配时，或者，在自底 向上语法分析时，当一个规则被用于归约时，此时该规则对应的语 义子程序就进入工作，完成既定翻译任务，产生与语义相应的中间 代码或目标代码。 语义动作：给每个文法符号X赋以各种不同的语义值 这里的语义值不一定指具体数值，可以是“类型”、“种属”
11、、“地址” 或“代码”等，我们用记号XTYPE、XCAT或XVAL来表示这些值 。如果某规则的右部有若干个同一符号出现，那么我们就用上角标 来区别这些符号。例如，假定有如下规则和语义动作 ： 12 例如，假定有如下规则和语义动作例如，假定有如下规则和语义动作 ： E E =E=E(1) (1)+E +E(2) (2) EVAL:=E EVAL:=E(1) (1)VAL+E VAL+E(2) (2)VAL VAL 语义动作写在规则之后的花括号里，这里语义动作是表明与规则左部语义动作写在规则之后的花括号里，这里语义动作是表明与规则左部 文法符号文法符号E E相关的语义值相关的语义值EVALEVAL
12、，它是通过把规则右部文法符号的语义它是通过把规则右部文法符号的语义 值值E E(1) (1)VAL VAL和和E E(2) (2)VAL VAL加在一起来决定的，规则中终结符号加在一起来决定的，规则中终结符号“ “+”+”按语义按语义 规则被解释成通常规则被解释成通常“ “加加” ”的意思。各规则的的意思。各规则的语义动作可以对表达式计算，也语义动作可以对表达式计算，也 可以生成中间代码，甚至还可以来产生目标指令。可以生成中间代码，甚至还可以来产生目标指令。 例例5.1 5.1 设有文法设有文法 E E =E+E=E+E E E =digit=digit 这里这里digitdigit代表代表0
13、 0和和9 9之间任一数字，如果我们的目的仅是为了求值，则之间任一数字，如果我们的目的仅是为了求值，则 语义动作如下语义动作如下 (1) E(1) E =E=E(1) (1)+E +E( ( ) ) EVAL:=EEVAL:=E(1) (1)VAL+E VAL+E(2) (2)VAL VAL (2) E(2) E =digit EVAL:=digit=digit EVAL:=digit 假定语义动作中的假定语义动作中的“ “+”+”代表是整型加算术运算。代表是整型加算术运算。 规则规则(1)(1)的语义动作为的语义动作为: : E E的语义值的语义值EVALEVAL等于等于E E(1) (1)
14、 和 和E E(2) (2)的语义值 的语义值E E(1) (1) VAL VAL和和E E(2) (2)VAL VAL之和之和. . 规则规则(2)(2)的语义动作为的语义动作为: E: E的语义值为的语义值为0 09 9之间任一个数之间任一个数. . 这样，按照它们的语义动作，我们在分析每个句子的同时一步一步地算出这样，按照它们的语义动作，我们在分析每个句子的同时一步一步地算出 每个句子的值每个句子的值 。 13 例如，假定有输入串1+2+3，我们通过语法树的分析来看如何进行语法 制导翻译，来求出该句子最后值。 输入串1+2+3的语法树如下图所示： 下面我们采用自底向上归约过程。首先考虑底
15、层最左下面我们采用自底向上归约过程。首先考虑底层最左E E的结点，这个的结点，这个 结点对应于规则结点对应于规则E E =1=1和语义动作和语义动作EVALEVAL：=1=1。这样，底层最左的这样，底层最左的E E的的 值值1 1与语义值与语义值EVALEVAL相关。类似地，值相关。类似地，值2 2与该结点的右兄弟的语义值与该结点的右兄弟的语义值EVALEVAL 相关。如下图所示：相关。如下图所示： E E + + E E E E + + E E E E 1 1 2 2 3 3 14 在图所示子树中，子树根处EVAL的语义值是3，这可用语义动作 EVAL:=E(1)VAL+E(2)VAL算出。使用这个语义动作时，以底部最左的E的 EVAL的值来代替E(1)VAL ，而以右边E的EVAL的值代替E(2)VAL 。 以这种方法继续下去，我们就推出如下
