编译原理6-2-基于属性文法的处理方法课件.ppt

《编译原理6-2-基于属性文法的处理方法课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章属性文法和语法制导翻译6.1属性文法6.2基于属性文法的处理方法6.3S-属性文法的自下而上计算6.4L-属性文法和自顶向下翻译6.5自下而上计算继承属性6.2基于属性文法的处理方法6.2.1依赖图6.2.2树遍历的属性计算方法6.2.3一遍扫描的处理方法6.2.4抽象语法树语法制导翻译法(syntax-directedtranslation)由源程序的语法结构驱动翻译过程输入串语法树依赖图语义规则计算次序图6.3语法制导翻译概观描述一棵语法树中结点的属性之间的相互依赖关系也可在语法分析的同时完成语义规则的计算(一遍扫描)语义规则的形式

2、b:=f(c1，c2，…，ck)可以为每一个包含过程调用的语义规则引入一个虚综合属性b，依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。6.2.1依赖图LEnprint(E.val)b…c1ckfor语法树中每一结点ndofor结点n的文法符号的每一个属性ado为a在依赖图中建立一个结点；for语法树中每一个结点ndofor结点n所用产生式对应的每一个语义规则b:＝f(c1，c2，…，ck)dofori:=1tokdo从ci结点到b结点构造一条有向边；依赖图的构造步骤产生式语义规则E

3、E1+E2E.val:=E1.val+E2.valEE1E2valvalval虚线表示语法树实线表示依赖图realid1,id2,id3的语法分析树的依赖图DrealT,id3LLLid2id1,1entry102entry3entryin98in76in54type☆图6.5图6.2中语法分析树的依赖图虚结点TrealT.type:=realDTLL.in:=T.typeLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)属性的计算次序一个依赖图的任何拓扑

4、排序都给出一个语法树中结点的语义规则计算的有效顺序。例6.5在☆图6.5的依赖图中，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。用an来代表依赖图中与序号n的结点有关的属性。a4:=real;a5:=a4;addtype(id3.entry,a5)a7:=a5;addtype(id2.entry,a7)a9:=a7;addtype(id1.entry,a9)6.2.2树遍历的属性计算方法以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历。*下面算法可对任何无循环的属性文

5、法进行计算While还有未被计算的属性doVisitNode(S)/*S是开始符号*/procedureVisitNode(N:Node)；beginifN∈VNthen/*假设它的产生式为N→X1X2…Xm*/fori:=1tomdoifXi∈VNthen/*即Xi是非终结符*/begin计算Xi的所有能够计算的继承属性；VisitNode(Xi)end；计算N的所有能够计算的综合属性end(a)初始状态(b)VisitNode(S)第一次调用后(c)VisitNode(S)第二次调用后(d)VisitNode(S)第三次调用后的最终状态初

6、值S.a=0,输入串xyz的语法树如下产生式语义规则SXYZS.b:=X.d-2X.c=Z.gY.e:=S.bZ.h:=S.aXxX.d:=2*X.cYyY.f:=Y.e*3ZzZ.g:=Z.h+1例6.6:S有继承属性a,综合属性bX有继承属性c,综合属性dY有继承属性e,综合属性fZ有继承属性h,综合属性gS:a=0XYZxyz.h=0.g=1.c=1.d=2.e=0.f=0,b=06.2.3一遍扫描的处理方法一遍扫描的处理方法:在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树

7、。如果采用一遍扫描的编译程序模型，语法制导翻译就是为文法中每个产生式配上一组语义规则,并且在语法分析的同时执行这些语义规则。一遍扫描处理方法与两个因素有关语法分析方法属性的计算次序在什么时候计算一个产生式的语义规则在自上而下分析中，当一个产生式匹配输入串成功在自下而上分析中，当一个产生式被用于进行归约时L-属性文法可用于一遍扫描的自上而下分析S-属性文法适合于一遍扫描的自下而上分析6.2.4抽象语法树在抽象语法树中,操作符和关键字都不作为叶结点出现,而是把它们作为内部结点SifBthenS1elseS2if-then-elseBS1S2Si

8、fBthenS1elseS2抽象语法树语法分析树语法制导翻译可以基于语法分析树，也可以基于抽象语法树a:=b*-c+b*-c:=EEE+E*EbE@Ea赋值语句cE