编译原理第6章_属性文法和语法制导翻译2.ppt
第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译内容内容属性文法属性文法基于属性文法的处理方法基于属性文法的处理方法S-属性文法的自下而上计算属性文法的自下而上计算L-属性文法和自顶向下翻译属性文法和自顶向下翻译自下而上计算继承属性自下而上计算继承属性第六章第六章 属性文法和语法制导翻译属性文法和语法制导翻译语义语义：一组规则：一组规则，用它可以定义一个程序的意用它可以定义一个程序的意义义。描述方法：描述方法：自然语言描述：隐藏错误、二义性和不完整性自然语言描述：隐藏错误、二义性和不完整性形式描述：形式描述：F 操作语义操作语义(PL/1)(PL/1)F 指称语义指称语义(ADA)(ADA)F 代数语义代数语义(PASCAL)(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在其它地方计算在其它地方计算 n属性文法的例子：简单算术表达式求值的语义描述。属性文法的例子：简单算术表达式求值的语义描述。非终结符非终结符E、T及及F都有一个都有一个综合属性综合属性val，符号符号digit有一个综合属性有一个综合属性lexval，它的值由词法分析器提供。，它的值由词法分析器提供。与产生式与产生式LE对应的语义规则仅仅是打印由对应的语义规则仅仅是打印由E产生的算术表产生的算术表达式的值的一个过程，我们可认为这条规则定义了达式的值的一个过程，我们可认为这条规则定义了L的一个的一个虚属性虚属性。某些某些非终结符加下标非终结符加下标是为了区分一个产生式中同一非终结符是为了区分一个产生式中同一非终结符多次出现多次出现语语 义义 规规 则则 L EE E1+TE TT T1*FT FF (E)F digitPrint(E.val)E.val:=E1.val+T.val E.val:=T.val T.val:=T1.val F.val T.val:=F.valF.val:=E.valF.val:=digit.lexval产生式产生式6.1 属性文法属性文法综合属性综合属性在语法树中，一个结点的综合属性的值由其子在语法树中，一个结点的综合属性的值由其子结点的属性值确定。结点的属性值确定。使用自底向上的方法在每一个结点处使用语义使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值规则计算综合属性的值仅仅使用综合属性的属性文法称仅仅使用综合属性的属性文法称S属性文属性文法法结点属性值的计算正好和自底向上分析建立分析树结点同步进行。属性文法举例属性文法举例简单计算器简单计算器 用语义规则描述表达式求值该属性文法描述如下 产生式 语义规则(属性计算规则)1.LEn print(E.val)(虚属性)2.EE1+T E.val:=E1.val+T.val3.ET E.val:=T.val4.TT1*F T.val:=T1.val*F.val5.TF T.val:=F.val6.F(E)F.val:=E.val7.Fi F.val:=i.lexval非终结符设有非终结符设有综合属性，代综合属性，代表表达式的值表表达式的值终结符终结符i i设有设有综综合属性，合属性，其其值由值由词法分析器提供词法分析器提供简单计算器的设计简单计算器的设计 p138p138例 3*5+4n表达式的文法1.LEn 2.EE1+T3.ET4.TT1*F5.TF6.F(E)7.Fi E nE nE E1 1 +T +TT TT T1 1 *F*FF Fi i3 3i i5 5F Fi i4 4要解决的问题要解决的问题表达式求值表达式求值.valval 3 3.valval 3 3.valval 5 5.valval 15 15.valval 1515.valval 4 4.valval 4 4.valval 19 19L L显示显示1919.lexvallexval 3 3.lexvallexval 5 5.lexvallexval 4 4综合属性综合属性自下自下而上而上传递信息传递信息6.1 属性文法属性文法继承属性继承属性在语法树中，一个结点的继承属性由此结点的在语法树中，一个结点的继承属性由此结点的父结点和父结点和/或兄弟结点的某些属性确定或兄弟结点的某些属性确定用继承属性来表示程序设计语言结构中的上下用继承属性来表示程序设计语言结构中的上下文依赖关系很方便文依赖关系很方便1.DTL L.in:=T.type2.Tint T.type:=integer3.Treal T.type:=real4.LL1,id L1.in:=L.in addtype(id.entry,L.in)5.Lid addtype(id.entry,L.in)entry 单词 id 的属性，id在符号表的入口addtype 在符号表中为变量添加类型信息用语义规则描述变量说明该属性文法描述如下 产生式 语义规则(属性计算规则)说明语句的属性文法说明语句的属性文法 综合属性综合属性继承属性继承属性节节目录目录说明语句的设计说明语句的设计 例 real id1,id2,id3 说明语句的文法1.D T L2.T int3.T real 4.L L1,id5.L idD DT LT LrealrealL L1 1 ,id,id3 3L L2 2 ,id,id2 2idid1 1要解决的问题要解决的问题记录标识符的类型记录标识符的类型类型信息传递类型信息传递realrealrealrealrealreal.typetyperealreal.in.inrealreal.in.inrealreal.in.inrealreal继承属性继承属性自上自上而下而下传递信息传递信息类型类型描述描述变量变量表表6.2 基于属性文法的处理方法基于属性文法的处理方法语法制导翻译即基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。由由源源程程序序的的语语法法结结构构所所驱驱动动的的处处理理办办法法就就是是语语法制导翻译法法制导翻译法语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行其他动作。对输入符号串的翻译就是根据语义规则进行计算的结果。输入串输入串语法树语法树依赖图依赖图语义规则计算次序语义规则计算次序
