编译原理-第五章 语法制导翻译

《编译原理-第五章 语法制导翻译》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、编译原理CompilerPrinciples徐小龙xuxl@njupt.edu.cn南京邮电大学.计算机学院第五章语法制导翻译comPilingrunningProgramming教材：《编译技术原理及其实现方法》王汝传编著第五章语法制导翻译本章内容§5.1语法制导翻译概述一、语法制导翻译定义二、语法制导翻译原理三、语法制导翻译实现§5.2中间语言一、简介二、逆波兰表示三、三元式四、树形表示五、四元式§5.3自底向上语法制导翻译一、简单算术表达式和赋值语句的翻译二、布尔表达式的翻译三、控制语句翻译

2、§5.1语法制导翻译概述一、语法制导翻译定义1、问题的引入一个程序成功地通过词法分析和语法分析，只能说明它是一个合适程序，但是对程序内部的逻辑含义并未加以考虑，从整个编译程序来看,词法分析和语法分析仅仅是编译程序一部分,编译程序最终的目的是将源程序翻译成可供计算机直接执行的目标程序。某些编译程序是直接生成机器语言或汇编语言形式的目标代码，而有些则并非如此。语法制导翻译方法先将源程序单词序列翻译成中间语言，然后再将中间语言翻译成目标程序。§5.1语法制导翻译概述一、语法制导翻译定义2、定义语法制导翻

3、译就是以语法分析为主导的语义处理。在语法分析过程中嵌入语义动作，即调用对应的语义子程序。E+EE*EEabc例如在前面语法分析时分析a+b*c表达式。语法分析是将a归约E，再将b归约E，将c归约为E，然后再将E*E归约成E，再将E+E归约成E，所以a+b*c是一个合法的句子。如果考虑语义，在归约过程中加上语义动作，先将a归约为E，将a值赋给E后，b归约成E，同时将b值赋给E，在将c值赋给E，然后再将b*c（E*E）给右E，再将a给E，最后再将两个E值相加就是最终结果。这就是语法制导翻译的基本思想，

4、在语法分析同时进行语义分析。§5.1语法制导翻译概述二、语法制导翻译原理1、语法制导翻译的原理语法制导翻译的原理就是先为每个文法规确定相应的语义，即编写出相应语义处理子程序，整个分析是以语法分析为主导。在自顶向下语法分析时，若某一个规则右部与输入串相匹配时，或者，在自底向上语法分析时，当一个规则被用于进行归约时，此时该规则对应的语义子程序就进入工作，完成既定翻译任务，产生与语义相应的中间代码或目标代码。§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作语义动作：给每个文法符号X赋以各种不同的

5、语义值这里的语义值不一定指具体数值，可以是“类型”、“种属”、“地址”或“代码”等，我们用记号X·TYPE、X·CAT或X·VAL来表示这些值。如果某规则的右部有同一符号若干个出现，那么我们就用上角标来区别这些符号§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：假定有如下规则和语义动作：E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}语义动作写在规则之后的花括号里，这里语义动作是表明与规则左部文法符号E相关的语义值E·VAL，它是通过把规则右部文法符号的语

6、义值E(1)·VAL和E(2)·VAL加在一起来决定的，规则中终结符号“+”按语义规则被解释成通常“加”的意思。各规则的语义动作可以对表达式计算，也可以生成中间代码，甚至还可以来产生目标指令。§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：设有文法E∷=E+EE∷=digitdigit代表0和9之间任一数字，如果仅是为了求值，则语义动作：(1)E∷=E(1)+E(2){E·VAL:=E(1)·VAL+E(2)·VAL}(2)E∷=digit{E·VAL:=digit}假定

7、语义动作中的“+”代表是整型加算术运算。规则(1)的语义动作为:E的语义值E·VAL等于E(1)和E(2)的语义值E(1)·VAL和E(2)·VAL之“和.规则(2)的语义动作为:E的语义值为0～9之间任一个数.这样，按照它们的语义动作，我们在分析每个句子的同时一步一步地算出每个句子的值.§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：设有文法E∷=E+EE∷=digit如果采用自底向上归约过程。首先考虑底层最左E的结点，这个结点对应于规则E∷=1和语义动作E·VAL:=1。这

8、样，在底层最左的E处值1与语义值E·VAL相关。E+EE+EE123输入串1+2+3，通过语法树来看如何进行语法制导翻译，来求出该句子最后值：§5.1语法制导翻译概述二、语法制导翻译原理2、语义动作举例：设有文法E∷=E+EE∷=digit输入串1+2+3，通过语法树来看如何进行语法制导翻译，来求出该句子最后值：在图所示子树中，子树根处E·VAL的语义值是3，这可用语义动作E·VAL:=E(1)·VAL+E(2)·VAL算出。使用这个语义动作时，以底部最左的E的E·VAL的值