编译原理第6章属性文法和语法制导翻译2.ppt

第六章 属性文法和语法制导翻译,内容,属性文法 基于属性文法的处理方法 S-属性文法的自下而上计算 L-属性文法和自顶向下翻译 自下而上计算继承属性,第六章 属性文法和语法制导翻译,语义：一组规则，用它可以定义一个程序的意义。 描述方法： 自然语言描述：隐藏错误、二义性和不完整性 形式描述： 操作语义(PL/1) 指称语义(ADA) 代数语义(PASCAL) 属性文法,语义分析的任务,语义检查 例 类型、运算、维数、越界 语义处理 例 变量的存储分配 例 表达式的求值 例 语句的翻译(中间代码的生成) 问题 如何根据被识别出的语法单位进行语义处理?,章节目录,第六章 属性文法和语法制导翻译,编译中的语义处理包括两个功能： （1）审查每个语法结构的静态语义，即验证语法结构合法的程序是否真正有意义。也称为静态语义分析或静态审查； （2）如果静态语义正确，则执行真正的翻译，即生成中间代码或生成实际的目标代码。 以上工作普遍基于属性文法和语法制导翻译方法。,6.1 属性文法,属性文法（也称属性翻译文法） Knuth在1968年提出 在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。 属性代表与文法符号相关信息，如类型、值、代码序列、符号表内容等 属性可以进行计算和传递 语义规则：对于文法的每个产生式都配备了一组属性的计算规则,6.1 属性文法,属性 综合属性：“自下而上”传递信息 继承属性：“自上而下”传递信息 在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条规则的形式为： b:=f(c1, c2, , ck) 这里，f是一个函数，而且或者 1. b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性，或者 2. b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck 是A或产生式右边任何文法符号的属性。 在两种情况下，属性b依赖于属性c1,c2,ck。,6.1 属性文法,说明 终结符只有综合属性，由词法分析器提供 非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值 对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性 出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供,6.1 属性文法,语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。 例，考虑非终结符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在其它地方计算,属性文法的例子：简单算术表达式求值的语义描述。 非终结符E、T及F都有一个综合属性val， 符号digit有一个综合属性lexval，它的值由词法分析器提供。 与产生式LE对应的语义规则仅仅是打印由E产生的算术表达式的值的一个过程，我们可认为这条规则定义了L的一个虚属性。 某些非终结符加下标是为了区分一个产生式中同一非终结符多次出现,语 义 规 则,L E,E E1+T,E T,T T1 * F,T F,F (E),F digit,Print(E.val),E.val:=E1.val+T.val,E.val:=T.val,T.val:=T1.val F.val,T.val:=F.val,F.val:=E.val,F.val:=digit.lexval,产生式,6.1 属性文法,综合属性 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。 使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值 仅仅使用综合属性的属性文法称S属性文法 结点属性值的计算正好和自底向上分析建立分析树结点同步进行。,属性文法举例简单计算器,用语义规则描述表达式求值 该属性文法描述如下 产生式 语义规则(属性计算规则) 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.val:=F.val F(E) F.val:=E.val Fi F.val:=i.lexval,非终结符设有综合属性，代表表达式的值,终结符i设有综合属性，其值由词法分析器提供,简单计算器的设计 p138,例 3*5+4n 表达式的文法 LEn EE1+T ET TT1*F TF F(E) Fi,E n,E1 + T,T,T1 * F,F,i 3,i 5,F,i 4,要解决的问题 表达式求值,.val 3,.val 3,.val 5,.val 15,.val 15,.val 4,.val 4,.val 19,L,显示19,.lexval 3,.lexval 5,.lexval 4,综合属性自下 而上传递信息,6.1 属性文法,继承属性 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定 用继承属性来表示程序设计语言结构中的上下文依赖关系很方便,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 ) entry 单词 id 的属性，id在符号表的入口 addtype 在符号表中为变量添加类型信息,用语义规则描述变量说明 该属性文法描述如下 产生式 语义规则(属性计算规则),说明语句的属性文法,综合属性,继承属性,节目录,说明语句的设计,例 real id1,id2,id3 说明语句的文法 D T L T int T real L L1,id L id,D,T L,real,L1 , id3,L2 , id2,id1,要解决的问题 记录标识符的类型 类型信息传递,real,real,real,.type real,.in real,.in real,.in real,继承属性自上 而下传递信息,类型 描述,变量 表,6.2 基于属性文法的处理方法,语法制导翻译即基于属性文法的处理过程通常是这样的：对单