ch05--语法制导翻译技术.

LIWensheng,SCST,BUPT第5章语法制导翻译技术知识点：语法制导定义、翻译方案S-属性定义、L-属性定义S-属性定义的翻译L-属性定义的翻译WenshengLiBUPT@20082/84语法制导翻译技术语义分析涉及到语言的语义形式语义学的研究开始于20世纪60年代初形式语义学可以分为三类–操作语义学：通过说明程序在一个机器中是如何执行的来定义程序的语义，着重模拟数据加工过程中计算机系统的操作–指称语义学：使用数学函数来描述程序和程序的构成，函数通过把语义值联系到正确的语法结构来描述程序的语义，主要描述数据加工的结果–公理语义学：把数理逻辑应用于语言的语义，语言结构与谓词转换器联系在一起，语言结构的行为以命题刻画，通过描述程序执行对程序断言的影响来定义程序、语句或语言结构的语义，主要用于程序正确性证明语法制导翻译技术–多数编译程序普遍采用的一种技术–比较接近形式化WenshengLiBUPT@20083/84语法制导翻译技术–根据翻译目标的要求确定每个产生式所包含的语义；–根据产生式包含的语义，分析文法中每个符号的语义；–把这些语义以属性的形式附加到相应的文法符号上；–根据产生式的语义，给出符号属性的求值规则(即语义规则)，从而形成语法制导定义。–在语法分析过程中，当使用该产生式时，根据语义规则对相应的属性进行求值，从而完成翻译。例如：考虑算术表达式文法–总目标：计算表达式的值–产生式EE1+T的语义：表达式的值由两个子表达式的值相加得到–分析每个符号的语义，并以属性的形式记录：E.val、E1.val、T.val–求值规则：E.val=E1.val+T.val–语法制导定义：产生式语义规则EE1+TETTT1*FTFF(E)FdigitE.val=E1.val+T.valE.val=T.valT.val=T1.val*F.valT.val=F.valF.val=E.valF.val=digit.valWenshengLiBUPT@20084/84语法制导翻译技术（续）例如：考虑算术表达式文法–总目标：检查表达式的类型–产生式EE1+T的语义：表达式的类型由两个子表达式的类型综合得到–分析每个符号的语义，并以属性的形式记录：E.type、E1.type、T.type–求值规则：if(E1.type==integer)&&(T.type==integer)E.type=integer;else…WenshengLiBUPT@20085/84翻译结果—取决于翻译目标生成代码–可以为源程序产生中间代码–可以直接生成目标机指令对输入符号串进行解释执行向符号表中存放信息给出错误信息翻译的结果依赖于语义规则–使用语义规则进行计算所得到的结果就是对输入符号串进行翻译的结果。–如：EE+T的翻译结果可以是：计算表达式的值、检查表达式的类型是否合法、为表达式创建语法树、生成代码等等。WenshengLiBUPT@20086/84语法制导翻译技术（续）进一步：–用一个或多个子程序（称为语义动作）所要完成的功能描述产生式的语义；–把语义动作插入到产生式中相应位置，从而形成翻译方案。–在语法分析过程中使用该产生式时，在适当的时机调用这些动作，完成所需要的翻译。语法制导定义是对翻译的高层次的说明，它隐蔽了一些实现细节，无须指明翻译时语义规则的计算次序。翻译方案指明了语义规则的计算次序，规定了语义动作的执行时机。WenshengLiBUPT@20087/84语法制导翻译的一般步骤输入符号串分析树依赖图语义规则的计算顺序计算结果WenshengLiBUPT@20088/84语法制导翻译技术5.1语法制导定义及翻译方案5.2S-属性定义的自底向上翻译5.3L-属性定义的自顶向下翻译5.4L-属性定义的自底向上翻译小结WenshengLiBUPT@20089/845.1语法制导定义及翻译方案对上下文无关文法的推广每个文法符号都可以有一个属性集，其中可以包括两类属性：综合属性和继承属性。–左部符号的综合属性是从该产生式右部文法符号的属性值计算出来的；在分析树中，一个内部结点的综合属性是从其子结点的属性值计算出来的。–出现在产生式右部的某文法符号的继承属性是从其所在产生式的左部非终结符号和/或右部文法符号的属性值计算出来的；在分析树中，一个结点的继承属性是从其兄弟结点和/或父结点的属性值计算出来的。–分析树中某个结点的属性值是由与在这个结点上所用产生式相应的语义规则决定的。和产生式相联系的语义规则建立了属性之间的关系，这些关系可用有向图（即：依赖图）来表示。WenshengLiBUPT@200810/84本节内容安排一、语法制导定义二、依赖图三、计算次序四、S属性定义和L属性定义五、翻译方案WenshengLiBUPT@200811/84一、语法制导定义在一个语法制导定义中，对应于每一个文法产生式A，都有与之相联系的一组语义规则，其形式为：b=(c1,c2,…,ck)这里，是一个函数，而且或者(1)b是A的一个综合属性，且c1、c2、…、ck是产生式右部文法符号的属性，或者(2)b是产生式右部某个文法符号的一个继承属性，且c1、c2、…、ck是A或产生式右部任何文法符号的属性。属性b依赖于属性c1、c2、…、ck。语义规则函数都不具有副作用的语法制导定义称为属性文法WenshengLiBUPT@200812/84语义规则一般情况：–语义规则函数可写成表达式的形式。某些情况下：–一个语义规则的唯一目的就是产生某个副作用，如打印一个值、向符号表中插入一条记录等；–这样的语义规则通常写成过程调用或程序段。–看成是相应产生式左部非终结符号的虚拟综合属性。–虚属性和符号‘=’都没有表示出来。WenshengLiBUPT@200813/84简单算术表达式求值的语法制导定义综合属性val与每一个非终结符号E、T、F相联系表示相应非终结符号所代表的子表达式的整数值LE的语义规则是一个过程，打印出由E产生的算术表达式的值，可以认为是非终结符号L的一个虚拟综合属性。产生式LEEE1+TETTT1*FTFF(E)Fdigit语义规则print(E.val)E.val=E1.val+T.valE.val=T.valT.val=T1.val*F.valT.val=F.valF.val=E.valF.val=digit.lexvalWenshengLiBUPT@200814/84综合属性分析树中，如果一个结点的某一属性由其子结点的属性确定，则这种属性为该结点的综合属性。如果一个语法制导定义仅仅使用综合属性，则称这种语法制导定义为S-属性定义。对于S-属性定义，通常采用自底向上的方法对其分析树加注释，即从树叶到树根，按照语义规则计算每个结点的属性值。简单台式计算机的语法制导定义是S-属性定义WenshengLiBUPT@200815/843*5+4的分析树加注释的过程属性值的计算可以在语法分析过程中进行。LEE+TTFT*FdigitFdigitdigit.lexval=3.val=3.val=3.lexval=5.val=5.val=15.val=15.lexval=4.val=4.val=4.val=19Print(19)WenshengLiBUPT@200816/84继承属性分析树中，一个结点的继承属性值由该结点的父结点和/或它的兄弟结点的属性值决定。可用继承属性表示程序设计语言结构中上下文之间的依赖关系–可以跟踪一个标识符的类型–可以跟踪一个标识符，了解它是出现在赋值号的右边还是左边，以确定是需要该标识符的值还是地址。WenshengLiBUPT@200817/84用继承属性L.in传递类型信息的语法制导定义D产生的声明语句包含了类型关键字int或real，后跟一个标识符表。T有综合属性type，其值由声明中的关键字确定。L的继承属性L.in，–产生式DTL,L.in表示从其兄弟结点T继承下来的类型信息。–产生式LL1,id，L1.in表示从其父结点L继承下来的类型信息产生式DTLTintTrealLL1,idLid语义规则L.in=T.typeT.type=integerT.type=realL1.in=L.inaddtype(id.entry,L.in)addtype(id.entry,L.in)WenshengLiBUPT@200818/84语句realid1,id2,id3的注释分析树L产生式的语义规则使用继承属性L.in把类型信息在分析树中向下传递；并通过调用过程addtype，把类型信息填入标识符在符号表中相应的表项中。DTLL,id2L,id3id1real.type=real.in=real.in=real.in=realaddtype(id3.entry,L.in)addtype(id1.entry,L.in)addtype(id2.entry,L.in)WenshengLiBUPT@200819/84二、依赖图分析树中，结点的继承属性和综合属性之间的相互依赖关系可以由依赖图表示。为每个包含过程调用的语义规则引入一个虚拟综合属性b，以便把语义规则统一为b=(c1,c2,…,ck)的形式。依赖图中：–为每个属性设置一个结点–如果属性b依赖于c，那么从属性c的结点有一条有向边连到属性b的结点。WenshengLiBUPT@200820/84算法5.1构造依赖图输入：一棵分析树输出：一张依赖图方法：for(分析树中每一个结点n)for(结点n处的文法符号的每一个属性a)为a在依赖图中建立一个结点;for(分析树中每一个结点n)for(结点n处所用产生式对应的每一个语义规则b=(c1,c2,…,ck))for(i=1;i=k;i++)从ci结点到b结点构造一条有向边;WenshengLiBUPT@200821/84依赖图构造举例产生式依赖规则AXYA.a=(X.x,Y.y)X.i=g(A.a,Y.y)AXY.a.x.i.yDTLL,id2L,id3id1real4type9in10addtype7in8addtype5in6addtype1entry2entry3entryWenshengLiBUPT@200822/84三、计算次序有向非循环图的拓扑排序–图中结点的一种排序m1,m2,…,mk–有向边只能从这个序列中前边的结点指向后面的结点–如果mimj是从mi指向mj的一条边，那么在序列中mi必须出现在mj之前。依赖图的任何拓扑排序–给出了分析树中结点的语义规则计算的有效顺序–在拓扑排序中，一个结点上语义规则b=(c1,c2,…,ck)中的属性c1,c2,…,ck在计算b时都是可用的。拓扑排序：–1、2、3、4、5、6、7、8、9、10–4、5、3、6、7、2、8、9、1、10WenshengLiBUPT@200823/84计算顺序从拓扑排序中可以得到下面的程序，an代表依赖图中与序号n的结点有关的属性：type=real；in5=type；addtype(id3.entry,in5)；in7=in5；addtype(id2.entry,in7)；in9=in7；addtype(id1.entry,in9)；WenshengLiBUPT@200824/84语法制导翻译过程最基本的文法用于建立输入符号串的分析树；为分析树构造依赖图；对依赖图进行拓扑排序；从这个序列得到语义规则的计算顺序；照此计算顺序进行求值，得到对输入符号串的翻译。输入符号串分析树依赖图语义规则的计算顺序计算结果WenshengLiBUPT@200825/84四、S属性定义和L属性定义S属性定义：仅涉及综合属性的语法制导定义L属性定义：一个语法制导定义是L属性定义，如果–与每个产生式AX1X2…Xn相应的每条语义规则计算的属性都是A的综合属性，或是Xj（1jn）的继承属性，而该继承属性仅依赖于：•A的继承属性；•