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

第六章 属性文法和语法制导翻译,6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S-属性文法的自下而上计算 6.4 L-属性文法和自顶向下翻译 6.5 自下而上计算继承属性,语义分析,静态语义分析 类型检查、控制流检查 、一致性检查 名字的作用域分析 动态语义分析 栈溢出 数组越界 ai,编译中的语义处理,静态语义分析或静态审查 执行真正的翻译 翻译成中间表示形式 翻译成目标代码,语义形式形式化,词法分析正规式，正规文法，有穷自动机 语法分析上下文无关文法 语义分析难于形式化描述 属性文法,6.1 属性文法,属性文法（属性翻译文法） 是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。 属性：类型、值、代码序列、符号表内容,表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或产生式右边任何文法符号的属性。,注意,终结符 只有综合属性，它们由词法分析器提供 非终结符 既可有综合属性也可有继承属性,例: 产生式ABC有规则,C.d := B.c1 A.b := A.aB.c,继承属性,综合属性,S-属性文法,仅仅使用综合属性的属性文法称 S-属性文法 在语法树中，一个结点的综合属性的值由其 子结点的属性值确定。 通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。, 表6.1 一个简单台式计算器的属性文法,8+5*2n,digit,L,E,n,T,E,T,F,digit,T,+,*,F,F,digit,.lexval = 8,.val = 8,带注释的语法树 (结点带有语义信息 ),.val = 8,.val = 8,.val = 18,.lexval = 5,.val = 5,.val = 5,.val = 10,.lexval = 2,.val = 2,继承属性,在语法树中，一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定。 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。,表6.2 带继承属性L.in的属性文法,real id1, id2, id3 的带注释的语法树,图6.2 在每个L结点都带有继承属性的语法树,D,real,T,id3,L,L,L,id2,id1,.type = real,.in = real,.in = real,.in = real,继承属性,综合属性,终结符 只有综合属性,语义规则,属性计算 类型说明 符号表操作 代码生成 ,补充例 1,为文法 S ( L ) | a L L , S | S 写一个语义规则，输出括号的对数。,S S print (S. num) S ( L ) S. num := L.num + 1 S a S. num := 0 L L1 , S L. num := L1. num + S. num L S L. num := S.num,为下面文法配备语义规则，使得语义处理结果是将中缀表达式变为后缀表达式,如: 输入是3+4*5 输出是345*+,补充例 2,G: E ET | T T T*F | F F (E) | i,E ET print + E T T T*F print * T F F (E) F i print i,F,3,4,5,E,E,T,+,*,T,3,F,3,4,5,+,*,3,T,F,F,3 4 5,E,T,E,T,F,3,4,5,+,*,T,F,F,34 * 5,(a),(b),(c),(d),4,5,*,+,E ET print + T T*F print * F i print i,G: NS.S S SB S B B 0 B 1,给文法配备语义规则, 完成二进制到十进制的转换 输入 11.01 输出 3.25,补充例 3,11.01= 1*21+1*21+0*2-1+1*2-2,NS1.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 ,方案1:只引入综合属性 .v : value .L: length 例如: S为11, 则S.v=3, S.L=2,11.01=11+01*2-2,NS1.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 ,N,S,.,S,S,B,S,B,B,B,1,1,0,1,2,1,1,2,计算S.L,N,S,.,S,S,B,S,B,B,B,1,1,0,1,1,1,3,1,0,0,1,1,3.25,计算N.v,S.L=2,NS1.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-2,方案2:引入综合属性.v , .L 和继承属性 .f .f ：最右边一位的权值 如: S=11 , S.f=1 S=0.01 , S.f=2-2,NS1.S N.v=S1.v+S.v， S1.f1， S.f2-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-2,NS1.S N.v=S1.v+S.v， S1.f1， S.f2-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.L,N,S,.,S,S,B,S,B,B,B,1,1,0,1,2,1,1,2,11.01= 1*21+1*21+0*2-1+1*2-2,计算继承属性 .f,N,S,.,S,S,B,S,B,B,B,1,1,0,1,1,2-2,1,2,2-2,2-1,2-1,2,NS1.S N.v=S1.v+S.v， S1.f1， S.f2-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-2,计算 .v,N,S,.,S,S,B,S,B,B,B,1,1,0,1,1,2-2,1,2,2-2,2-1,2-1,2,3.25,NS1.S N.v=