编译原理6-1-属性文法课件.ppt

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

第六章属性文法和语法制导翻译6.1属性文法6.2基于属性文法的处理方法6.3S-属性文法的自下而上计算6.4L-属性文法和自顶向下翻译6.5自下而上计算继承属性 语义分析静态语义分析类型检查、控制流检查、一致性检查名字的作用域分析动态语义分析栈溢出数组越界a[i] 编译中的语义处理静态语义分析或静态审查执行真正的翻译翻译成中间表示形式翻译成目标代码 语义形式形式化词法分析－正规式，正规文法，有穷自动机语法分析－上下文无关文法语义分析－难于形式化描述属性文法 6.1属性文法属性文法（属性翻译文法）是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。属性：类型、值、代码序列、符号表内容… 产生式语义规则LEnprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexval表6.1一个简单台式计算器的属性文法属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。属性的计算规则L的虚属性换行符 属性通常分为两类综合属性用于“自下而上”传递信息继承属性用于“自上而下”传递信息或者在兄弟之间传递信息 语义规则的形式在一个属性文法中，对应于每个产生式A→α都有一套与之相关联的语义规则，每条规则的形式为b:=f(c1，c2，…，ck)属性b依赖于属性c1，c2，…，ck（1）或者b是A的一个综合属性,并且c1，c2，…，ck是产生式右边文法符号的属性；（2）或者b是产生式右边某个文法符号的一个继承属性,并且c1，c2，…，ck是A或产生式右边任何文法符号的属性。 注意终结符只有综合属性，它们由词法分析器提供非终结符既可有综合属性也可有继承属性 例:产生式A→BC有规则C.d:=B.c＋1A.b:=A.a＋B.c继承属性综合属性ABC S-属性文法仅仅使用综合属性的属性文法称S-属性文法在语法树中，一个结点的综合属性的值由其子结点的属性值确定。通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。☆表6.1一个简单台式计算器的属性文法 8+5*2nLEnprint(E.val)EE1+TE.val:=E1.val+T.valETE.val:=T.valTT1*FT.val:=T1.val*F.valTFT.val:=F.valF(E)F.val:=E.valFdigitF.val:=digit.lexvaldigitLEnTETFdigitT+*FFdigit.lexval=8.val=8带注释的语法树(结点带有语义信息).val=8.val=8.val=18.lexval=5.val=5.val=5.val=10.lexval=2.val=2 继承属性在语法树中，一个结点的继承属性由此结点的父结点和／或兄弟结点的某些属性确定。用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。 产生式DTLTintTrealLL1,idLid表6.2带继承属性L.in的属性文法语义规则L.in:=T.typeT.type:=integerT.type:=realL1.in:=L.in;addtype(id.entry,L.in)addtype(id.entry,L.in) realid1,id2,id3的带注释的语法树图6.2在每个L结点都带有继承属性的语法树DTLL.in:=T.typeTintT.type:=integerTrealT.type:=realLL1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)DrealT,id3LLLid2id1,.type=real.in=real.in=real.in=real继承属性综合属性终结符只有综合属性 语义规则属性计算类型说明符号表操作代码生成…… 补充例1为文法S(L)|aLL,S|S写一个语义规则，输出括号的对数。SSprint(S.num)S(L)S.num:=L.num+1SaS.num:=0LL1,SL.num:=L1.num+S.numLSL.num:=S.num 为下面文法配备语义规则，使得语义处理结果是将中缀表达式变为后缀表达式如:输入是3+4*5输出是345*+补充例2G:EE＋T|TTT*F|FF(E)|iEE＋T{print‘+’}ETTT*F{print‘*’}TFF(E)Fi{print‘i’} F345EET+*T3F345+*3TFF*ETF345+TFF345ETETF345+*TFF3＋4*5(a)(b)(c)(d)45*+EE＋T{print‘+’}TT*F{print‘*’}Fi{print‘i’} G:NS.SSSBSBB0B1给文法配备语义规则,完成二进制到十进制的转换输入－11.01输出－3.25补充例3 11.01=1*21+1*21+0*2-1+1*2-2NS1.S{N.v=S1.v+S.v*2-S.L}SS1B{S.v=S1.v*2+B.v,S.L=S1.L+1}SB{S.v=B.v,S.L=1}B0{B.v=0}B1{B.v=1}NS.SSBSBBB1101方案1:只引入综合属性.v:value.L:length例如:S为11,则S.v=3,S.L=211.01=11+01*2-2 NS1.S{N.v=S1.v+S.v*2-S.L}SS1B{S.v=S1.v*2+B.v,S.L=S1.L+1}SB{S.v=B.v,S.L=1}B0{B.v=0}B1{B.v=1}NS.SSBSBBB11012112计算S.L NS.SSBSBBB1101113100113.25计算N.vS.L=2NS1.S{N.v=S1.v+S.v*2-S.L}SS1B{S.v=S1.v*2+B.v,S.L=S1.L+1}SB{S.v=B.v,S.L=1}B0{B.v=0}B1{B.v=1}S.L=2 11.01=1*21+1*21+0*2-1+1*2-2NS.SSBSBBB1101方案2:引入综合属性.v,.L和继承属性.f.f：最右边一位的权值如:S=11,S.f=1S=0.01,S.f=2-2NS1.S{N.v=S1.v+S.v，S1.f＝1，S.f＝2-S.L}SS1B{S.L=S1.L+1，S1.f=S.f*2，B.f=S.f,S.v=S1.v+B.v}SB{S.L=1，B.f=S.f，S.v=B.v}B0{B.v=0}B1{B.v=B.f} 11.01=1*21+1*21+0*2-1+1*2-2NS1.S{N.v=S1.v+S.v，S1.f＝1，S.f＝2-S.L}SS1B{S.L=S1.L+1，S1.f=S.f*2，B.f=S.f,S.v=S1.v+B.v}SB{S.L=1，B.f=S.f，S.v=B.v}B0{B.v=0}B1{B.v=B.f}计算S.LNS.SSBSBBB11012112 11.01=1*21+1*21+0*2-1+1*2-2计算继承属性.fNS.SSBSBBB110112-2122-22-12-12NS1.S{N.v=S1.v+S.v，S1.f＝1，S.f＝2-S.L}SS1B{S.L=S1.L+1，S1.f=S.f*2B.f=S.f,S.v=S1.v+B.v}SB{S.L=1，B.f=S.f，S.v=B.v}B0{B.v=0}B1{B.v=B.f} 11.01=1*21+1*21+0*2-1+1*2-2计算.vNS.SSBSBBB110112-2122-22-12-123.25NS1.S{N.v=S1.v+S.v，S1.f＝1，S.f＝2-S.L}SS1B{S.L=S1.L+1，S1.f=S.f*2，B.f=S.f,S.v=S1.v+B.v}SB{S.L=1，B.f=S.f，S.v=B.v}B0{B.v=0}B1{B.v=B.f},2-2,2-2,3,2,1,2,0,0蓝色:.v红色:.f