编译原理第6章属性文法和语法制导翻译.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.valET E.val:=T.valTT1*F T.val:=T1.val*F.valTF T.val:=F.valF(E)F.val:=E.valFi F.val:=i.lexval,非终结符设有综合属性，代表表达式的值,终结符i设有综合属性，其值由词法分析器提供,简单计算器的设计 p138,例 3*5+4n表达式的文法LEn EE1+TETTT1*FTFF(E)Fi,E n,E1+T,T,T1*F,F,i3,i5,F,i4,要解决的问题表达式求值,.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.typeTint T.type:=integerTreal T.type:=realLL1,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 LT intT real L L1,idL id,D,T L,real,L1,id3,L2,id2,id1,要解决的问题记录标识符的类型类型信息传递,real,real,real,.typereal,.inreal,.inreal,.inreal,继承属性自上而下传递信息,类型描述,变量表,6.2 基于属性文法的处理方法,语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。由源程序的语法结构所驱动的处理办法就是语法制导翻译法语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行其他动作。对输入符号串的翻译就是根据语义规则进行计算的结果。,
