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

《编译原理6-2-基于属性文法的处理方法.ppt》由会员分享，可在线阅读，更多相关《编译原理6-2-基于属性文法的处理方法.ppt（20页珍藏版）》请在三一办公上搜索。

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

2、b:=f(c1，c2，ck)可以为每一个包含过程调用的语义规则引入一个虚综合属性 b，依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点 有一条有向边连到属性b的结点。,6.2.1 依赖图,b,c1,ck,for 语法树中每一结点n dofor 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for 语法树中每一个结点n dofor 结点n所用产生式对应的每一个语义规则 b:f(c1，c2，ck)do for i:=1 to k do 从ci结点到b结点构造一条有向边；,依赖图的构造步骤,val,val,val,虚线表示语法树,实线表示依赖图,real

3、 id1,id2,id3 的语法分析树的依赖图,D,real,T,id3,L,L,L,id2,id1,1 entry,10,2 entry,3 entry,in 9,8,in 7,6,in 5,4 type,图 6.5 图6.2中语法分析树的依赖图,虚结点,属性的计算次序,一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。例6.5 在图6.5的依赖图中，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。用an来代表依赖图中与序号n的结点有关的属性。,a4:=real;a5:=a4;addtype(id3.entry,a5)a7:=a5;addtype(id2.entry,

4、a7)a9:=a7;addtype(id1.entry,a9),6.2.2 树遍历的属性计算方法,以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历。,*下面算法可对任何无循环的属性文法进行计算,While 还有未被计算的属性 doVisitNode(S)/*S是开始符号*/procedure VisitNode(N:Node)；begin if N VN then/*假设它的产生式为NX1 X2Xm*/for i:=1 to m do if XiVN then/*即Xi 是非终结符*/begin 计算 Xi 的所有能够计算的

5、继承属性；VisitNode(Xi)end；计算 N 的所有能够计算的综合属性 end,(a)初始状态(b)VisitNode(S)第一次调用后(c)VisitNode(S)第二次调用后(d)VisitNode(S)第三次调用后的最终状态,初值 S.a=0,输入串 xyz 的语法树如下,例6.6:S有继承属性a,综合属性bX有继承属性c,综合属性dY有继承属性e,综合属性fZ有继承属性h,综合属性g,.h=0.g=1,.c=1.d=2,.e=0.f=0,b=0,6.2.3 一遍扫描的处理方法,一遍扫描的处理方法:在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构

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

7、法分析树，也可以基于抽象语法树,a:=b*-c+b*-c,抽象语法树,语法分析树,如何建立表达式的抽象语法树,抽象语法树中的每一个结点可以由包含几个域的记录来实现的。,运算符号（结点标号）,运算分量的指针,标识符在符号表中的入口,用一些函数来建立表达式的抽象语法树中的结点。(1)mknode(op,left,right)建立一个 运算符号结点，标号是op,两个域left和right分别指向左子树和右子树.(2)mkleaf(id,entry)建立一个 标识符结点，标号为id,一个域entry指向标识符在符号表中的入口。(3)mkleaf(num，val)建立一个 数结点，标号为num，一个域v

8、al用于存放数的值。,每一个函数都返回一个指向新建立结点的指针。,to entry for a,to entry for c,图6.7 a 4+c 的抽象语法树,建立表达式a4c 的抽象语法树(1)P1:=mkleaf(id，entrya)；(2)P2:=mkleaf(num，4)；(3)P3:=mknode(，P1，P2)；(4)P4:=mkleaf(id，entryc)；(5)P5:=mknode(，P3，P4)；,P1,P2,P3,P4,P5,建立抽象语法树的语义规则,表6.4 为表达式建立抽象语法树的属性文法,nptr：函数调用返回的指针,虚线:带注释的语法分析树(象征性存在)实线:抽象语法树(真正存在),to entry for a,图6.8 a 4+c 的抽象语法树的构造 表6.4,T,E,id,.nptr,.nptr,.nptr,.nptr,.nptr,to entry for C,E,E,T,num,T,id,.nptr,