编译原理 第六章――属性文法和语法制导翻译ppt课件.ppt

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

1、第六章属性文法和语法制导翻译语义分析的功能审查静态语义，验证语法结构合法的程序是否真正有意义静态语义正确，翻译为中间语言或实际的目标代码属性文法：也称属性翻译文法，是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为“属性”）。综合属性属性继承属性对一个属性文法，每个产生式A→α都有一套与之相关的语义规则，每条规则的形式为：b:=f(c1，c2，...，ck)其中：f是一个函数，而且：或者（1）b是A的一个综合属性且c1，c2，...，ck是产生式右边文法符号的属性；或者（2）b是产生式右部某个文法符号

2、的一个继承属性并且c1，c2，...，ck是A或产生式右部任何文法符号的属性。这两种情况均称属性b依赖于属性c1，c2，...，ck。（1）终结符只有综合属性，它们由词法分析器提供。（2）非终结符既可有综合属性也可有继承属性。文法开始符号的所有继承属性作为属性计算前的初始值。语义规则LEEE1+TETTT1*FTFF(E)FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.valF.valT.val:=F.valF.val:=E.valF.val:=digit.lexval

3、产生式综合属性val一个简单台式计算器的语法制导定义LE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=3F.val=5digit.lexval=4digit.lexval=5digit.lexval=3+*3*5+4的带注释的分析树语法制导翻译实现从概念上讲，语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算输入符号串分析树属性依赖图语义规则的计算顺序依赖图由称为依赖图的一个有向图

4、描述分析树中的继承属性和属性中间的相互依赖关系。依赖图的构造算法：for分析树中每一个结点ndofor结点的文法符号的每一个属性ado为a在依赖图中建立一个结点；for分析树中每一个结点ndofor结点n所用产生式对应的每一个语义规则b:=f(c1,c2,…ck)dofori:=1tokdo从ci结点到b结点构造一条有向边带有继承属性L.in的语法树DL.in=realL.in=realL.in=realT.type=realrealid2id1id3，，Realid1,id2,id3产生式语义规则DTLTintTrealLL1,i

5、dLidL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)Realid1,id2,id3分析树的依赖图5678910T4LLLRealtypeininin3entry2entryentryid3id2id1，，1D每一个与L产生式有关的语义规则addtype(id.Entry,L.in)都产生一个虚属性，结点6、8和10都是为这些虚属性构造的。每次过程调用产生一个虚属性的结点。Realid1,id2,id

6、3分析树的依赖图5678910T4LLLRealtypeininin3entry2entryentryid3id2id1，，1D如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的。产生式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type=integerT.type:=realL1.in:=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)属性的计算顺序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,…,mk，使得边必须是从序列

7、中前面的结点指向后面的结点。也就是说，如果mi→mj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。在拓扑排序中，在一个结点，语义规则b:=f(c1,c2,…ck)中的属性c1,c2,…ck在计算b以前都是可用的。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。属性计算方法树遍历的属性计算方法设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使

8、用多次遍历（或称遍）。对无循环的属性文法进行属性计算的算法While还有未被计算的属性doVisitNode(S)/*S为开始符号*/ProcedureVisitNode(N:N