《编译6属性文法和语法制导翻译(zss)》由会员分享，可在线阅读，更多相关《编译6属性文法和语法制导翻译(zss)（76页珍藏版）》请在金锄头文库上搜索。
1、编译原理(第三版) 陈火旺等编著,（2012年9月-12月）主讲：朱世松计算机学院,2,2017/9/9,第六章 属性文法和语法制导翻译,属性 属性常用来描述事物或人的特征。如：人的姓名，性别等，商品的颜色、重量、单位等。,3,2017/9/9,6.1 属性文法,属性文法（也称属性翻译文法）Knuth在1968年提出在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等属性可以进行计算和传递语义规则：对于文法的每个产生式都配备了一组属性的计算规则,4,2017/9/9,属性综合属性：“自下而上
2、”传递信息继承属性：“自上而下”传递信息在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为：b:=f(c1,c2,ck)这里，f是一个函数，而且或者1. b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性，或者2. b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck 是A或产生式右边任何文法符号的属性。属性b依赖于属性c1,c2,ck。,5,2017/9/9,说明终结符只有综合属性，由词法分析器提供非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值 对出现在产生式右边的继承属性和出现在产生式左边的综合
3、属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性,6,2017/9/9,语义规则所描述的工作可以包括: 属性计算、静态语义检查、符号表操作、代码生成等等。例，考虑非终结符A，B和C，其中，A有一个继承属性a和一个综合属性b，B有综合属性c，C有继承属性d。产生式ABC可能有规则 C.d:=B.c+1 A.b:=A.a+B.c而属性A.a和B.c在其它地方计算,7,2017/9/9,产 生 式 LEn EE1+T ETTT1*FTFF (E)Fdigit,语 义 规 则print(E.val) E.val := E1.val+T.val E.val :=T.val
4、T.val :=T1.val* F.val T.val :=F.val F.val :=E.val F.val :=digit.lexval表6.1,8,2017/9/9,综合属性在语法树中，一个结点的综合属性的值由其子结点的属性值确定。使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值仅仅使用综合属性的属性文法称S属性文法,9,2017/9/9,产 生 式 LEn EE1+T ETTT1*FTFF (E)Fdigit,语 义 规 则print(E.val) E.val := E1.val+T.val E.val :=T.val T.val :=T1.val* F.val T.val
5、 :=F.val F.val :=E.val F.val :=digit.lexval,10,2017/9/9,3*5+4n的带注释的语法树,digit.lexval=3,F.val=3,T.val=3,*,digit.lexval=5,F.val=5,T.val=15,E.val=15,+,digit.lexval=4,F.val=4,T.val=4,E.val=19,n,L,产 生 式 语 义 规 则 LEn print(E.val) EE1+T E.val := E1.val+T.val ET E.val :=T.val TT1*F T.val :=T1.val* F.val TF T.
6、val :=F.val F (E) F.val :=E.val Fdigit F.val :=digit.lexval,11,2017/9/9,继承属性在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下文依赖关系很方便,12,2017/9/9,产 生 式 语 义 规 则 DTLL.in := T.type TintT.type := integer TrealT.type := real LL1, idL1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),
7、13,2017/9/9,句子real id1，id2，id3的带注释的语法树,id1,L,id2,L,id3,L,real,T,D,T.type=real,L.in=real,L.in=real,L.in=real,产 生 式 语 义 规 则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),14,2017/9/9,6.2 基于属性文法的的处理方法,由源程序的语法结构所驱动的
8、处理办法就是语法制导翻译法语义规则的计算产生代码在符号表中存放信息给出错误信息执行任何其它动作对输入符号串的翻译也就是根据语义规则进行计算的结果。,输入串,语法树,依赖图,语义规则计算次序,15,2017/9/9,6.2 基于属性文法的的处理方法,依赖图树遍历一遍扫描,16,2017/9/9,6.2.1 依赖图,在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b:=f(c1,c2,ck)的形式依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有
9、向边连到属性b的结点。,17,2017/9/9,for 语法树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for语法树中每一个结点n do for 结点n所用产生式对应的每一个语义规则b:=f(c1,c2,ck ) dofor i:=1 to k do 从ci结点到b结点构造一条有向边；,18,2017/9/9,EE1E2 E.val:=E1.val+E2.val,E1,+,E2,E,val,val,val,19,2017/9/9,句子real id1，id2，id3的带注释的语法树的依赖图,id1,L,id2,L,id3,L,real,T,D
10、,4type,5in,6 - addtype(id.entry, L.in),7in,8 addtype,9in,10 addtype,1entry,2entry,3entry,产 生 式 语 义 规 则 DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in :=L.in addtype(id.entry, L.in) Lid addtype(id.entry, L.in),20,2017/9/9,如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的,只处理良定义的属性文法,21,
11、2017/9/9,属性的计算次序,一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序属性文法说明的翻译是很精确的基础文法用于建立输入符号串的语法分析树根据语义规则建立依赖图从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序,输入串,语法树,依赖图,语义规则计算次序,22,2017/9/9,句子real id1，id2，id3的带注释的语法树的依赖图,a4:=real;a5:=a4addtype (id3.entry,a5);a7:=a5;addtype (id2.entry,a7);a9:=a7addtype (id1.entry,a9);,23,2017/9/9,6.2
12、 基于属性文法的的处理方法,依赖图树遍历一遍扫描,24,2017/9/9,6.2.2 树遍历的属性计算方法,通过树遍历的方法计算属性的值 假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性 以某种次序遍历语法树，直至计算出所有属性深度优先，从左到右的遍历,25,2017/9/9,While 还有未被计算的属性 doVisitNode(S) /*S是开始符号*/procedure VisitNode (N:Node) ;begin if N是一个非终结符 then /*假设它的产生式为NX1Xm*/ for i :=1 to m do if XiVN then /*即Xi是非终结
13、符*/ begin 计算Xi的所有能够计算的继承属性； VisitNode (Xi) end; 计算N的所有能够计算的综合属性end,26,2017/9/9,产 生 式语 义 规 则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1,例 考虑属性文法G。其中，S有继承属性a，综合属性b；X有继承属性c、综合属性d；Y有继承属性e、综合属性f；Z有继承属性h、综合属性g,27,2017/9/9,假设S.a的初始值为0，输入串为xyz,S:a=0,X,Y,Z,
14、x,y,z,Z:h=0 g=1,X:c=1 d=2,S:a=0, b=0,Y:e=0 f=0,产 生 式语 义 规 则 SXYZ Z.h := S.a X.c := Z.g S.b := X.d -2 Y.e := S.bXx X.d :=2*X.cYy Y.f := Y.e*3Zz Z.g :=Z.h+1,28,2017/9/9,6.2 基于属性文法的的处理方法,依赖图树遍历一遍扫描,29,2017/9/9,6.2.3 一遍扫描的处理方法,一遍扫描的处理方法是在语法分析的同时计算属性值 所采用的语法分析方法属性的计算次序L属性文法适合于一遍扫描的自上而下分析S属性文法适合于一遍扫描的自下而上分析,
