《编译原理》课程简介 (44).pdf

《《编译原理》课程简介 (44).pdf》由会员分享，可在线阅读，更多相关《《编译原理》课程简介 (44).pdf（15页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、编 译 原 理 C O M P I L A T I O N P RIN C IP LE 第六章 属性文法和语法制导翻译6.2 语法制导翻译6.2 语法制导翻译什么是语法制导的翻译n编译阶段p词法分析p语法分析p语义分析 p中间代码生成p代码优化p目标代码生成 语义翻译语法制导翻译6.2 语法制导翻译n语法制导定义(Syntax-Directed Definitions,SDD）p将每个文法符号和一个语义属性集合相关联p将每个产生式和一组语义规则相关联，这些规则用于计算该产生式中各文法符号的属性值n一个语法制导翻译的基础是一个文法，其中翻译成分依附在每一产生式上。产产 生生 式式语语 义义 规规

2、 则则(1)D TL L.in:=T.type(2)Tint T.type:=integer(3)T real T.type:=real.6.2 语法制导翻译n语法制导翻译方案(Syntax-Directed Translation，SDT)pSDT是在产生式右部嵌入了程序片段的上下文无关文法，这些程序片段称为语义动作。按照惯例，语义动作放在大括号内。D T L.inh=T.type L Tint T.type=int T real T.type=real L L1.inh=L.inh L1,id.6.2 语法制导翻译语法制导翻译实现n从概念上讲，语法制导翻译即基于属性文法的处理过程通常是这样

3、的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。分析树属性依赖图语义规则的计算顺序输入符号串6.2 语法制导翻译n分析树中的继承属性和综合属性之间的相互依赖关系，可以由称为依赖图的一个有向图来描述。n为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b：=f（c1,c2,.,ck）的形式。n依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。v依赖图6.2 语法制导翻译v依赖图 产生式语义规则D TL T intT realL L1,idL idL.in:

4、=T.type T.type=integer T.type:=realL1.in:=L.in addtype(id.entry,L.in)addtype(id.entry,L.in)v例 Real id1,id2,id3分析树的依赖图.in54id31678910TDLLLRealtypeinin3 entry2 entryentryid2id16.2 语法制导翻译良定义的属性文法n很显然，一条求值规则只有在其各变元值均已求得的情况下才可以使用。但有时候可能会出现一个属性对另一个属性的循环依赖关系。n如，p、c1、c2都是属性，若有如下求值规则：p:=f1(c1)、c1:=f2(c2)、c2:

5、=f3(p)时，就无法对p求值。n如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。6.2 语法制导翻译属性的计算顺序n一个有向非循环图的拓扑排序是图中结点的任何顺序m1,m2,mk，使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。n一个依赖图的任何拓扑排序都给出一个分析树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点，语义规则b:=f(c1,c2,ck)中的属性c1,c2,ck在计算b以前都是可用的。6.2 语法制导翻译n一个依赖图

6、的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。n属性文法说明的翻译是很精确的。p用这个顺序来计算语义规则就得到输入符号串的翻译。分析树属性依赖图语义规则的计算顺序输入符号串1最基本的文法用于建立输入符号串的分析树。2依赖图根据语法规则建立。3从依赖图的拓扑排序中，可以得到计算语义规则的顺序。6.2 语法制导翻译n例 Real id1,id2,id3分析树的依赖图p每一条边都是从序号较低的结点指向序号较高的结点。因此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到下列程序，用an来代表依赖图中与序号n的结点有关的属性：a4:=reala5:=a4

7、addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7)a9:=a7 addtype(id1.entry,a9)p这些语义规则的计算就把real类型填入到每个标识符对应的符号表项中。.in54id31678910TDLLLRealtypeinin3 entry2 entryentryid2id16.2 语法制导翻译属性计算方法n树遍历的属性计算方法p设语法树已经建立起来，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍

8、）。n一遍扫描的处理方法p与树遍历的属性计算文法不同，一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。p因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：（1）所采用的语法分析方法（2）属性的计算次序。6.2 语法制导翻译n在某些情况下可用一遍扫描实现属性文法的语义规则计算。也就是说在语法分析的同时完成语义规则的计算，无须明显地构造语法树或构造属性之间的依赖图。因为单遍实现对于编译效率非常重要。n研究怎样实现这种翻译器？pS-属性 适用于自底向上的计算pL-属性 适用于自顶向下的分析，也可用于自底向上。|编译原理谢 谢Thanks