编译原理-第六章习题答案.ppt

编译原理电子教案,第六章属性文法和语法制导翻译,2,本章的主要内容,属性文法和语法制导的翻译的概念综合属性和继承属性的概念、特点S-属性文法与L-属性文法的概念及分析方法翻译模式递归下降翻译器的设计,3,本章要求,知识点：语法制导定义，S-属性定义及其自底向上计算属性，L-属性定义，自顶向下的翻译，自底向上计算继承属性。深刻理解：属性，综合属性，继承属性，依赖图，计算顺序，语法树，语法制导定义，S-属性文法定义，L-属性文法定义，翻译模式。熟练掌握：对于已知文法G和翻译任务，构造其L-属性定义，将其改造成适于自顶向下分析或自底向上分析的翻译模式。,4,本章教学线索,1属性文法（属性翻译文法）1.1属性文法的概念1.2属性的分类1.3属性的计算规则2基于属性文法的处理办法3S-属性文法的自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性,5,1属性文法（属性翻译文法）,语法制导翻译：通过给语法树上各个符号赋予一定的含义并且将各个符号进行有结构的连接，可以形成语言的具体语句的含义。这给予我们以启示：可以通过扩充文法，在文法符号上附着某些语义信息，并在这些语义信息间建立相互计算关系，从而在语法分析的同时进行语义分析。由于这种分析是在语法分析的控制下进行的，故称为语法制导翻译。,6,1.1属性文法的概念,（1）属性文法的定义在上下文无关文法的基础上，为每个文法符号（终结符和非终结符）配备若干相关的“值”（也称：“属性”），对于文法的每个产生式都配备了一组属性的计算规则（语义规则），这种文法称为属性文法。1968年，Knuth首先提出。说明：在一般情况下，整个属性文法是非常复杂的。但属性的函数关系却通常非常简单。属性也很少依赖于大量的其它属性，因此可以将相互依赖的属性分割成较小的独立属性集，然后单独对每一属性集写出一个属性文法。,7,（2）属性（Attribute）是编程语言结构的任意特性。属性在其包含的信息和复杂性等方面变化很大。属性的典型例子有：变量的数据类型表达式的值存储器中变量的位置程序的目标代码数的有效位数（3）属性文法一般表示方法：,8,例6.1一个简单台式计算器的属性文法,9,例6.2：无符号整数的属性文法,10,1.2属性的分类,例6.3属性文法为例6.1中的属性文法，输入：3*5+4n,综合属性：用于自下而上传递信息；在语法树中，一个结点的综合属性由其子结点的属性值确定，因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。继承属性：用于自上而下传递信息；在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。,11,例6.4继承属性的类型说明文法,realid1，id2，id3,12,1.3属性的计算规则,属性的计算规则：设有产生式A定义b=f（c1，c2，ck）f是一个计算函数，并且（1）b是A的一个综合属性，并且c1，c2，ck是产生式右边文法符号的属性。或者：（2）b是产生式右边某文法符号的一个继承属性，并且c1，c2，ck是A或产生式右边任何文法符号的属性。,13,注意：如果同一文法符号在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来。终结符只有综合属性，它们由词法分析器提供。非终结符既可有综合属性也可有继承属性，文法开始符的所有继承属性为属性计算前的初始值。属性计算规则中仅能使用相应产生式中文法符号的属性（封装性）。产生式左边的继承属性和产生式右边的文法符号的综合属性由其它产生式的属性规则计算。一个句型的语法树可以加以扩充，用来表示句型分析中得到的各个符号的属性间的关系：语法树中，一个结点的综合属性的值由其子结点的属性值确定语法树中，一个结点的继承属性的值由该结点的父结点和（或）兄弟结点的某些属性值确定,14,本章教学线索,1属性文法（属性翻译文法）2基于属性文法的处理办法2.1语法制导翻译2.2依赖图2.3树遍历的属性计算方法2.4一遍扫描的处理办法2.5抽象语法树(AbstractSyntaxtree)3S-属性文法的自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性,15,2.1语法制导翻译,基于属性文法的处理过程通常是：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。,在具体实现时，一般都是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。也就是语义分析是伴随语法分析的过程进行。,16,2.2依赖图,a依赖图：一种有向图，在一颗语法树中表示结点的继承属性和综合属性之间的相互依赖关系（这种属性之间的依赖关系由文法的语义规则确定）。b依赖图的构造方法：for语法树中每一结点ndofor结点n的文法符号的每一个属性ado为a在依赖图中建立一个结点；for语法树中每一个结点ndofor结点n所有产生式对应的每一条语义规则bf（c1，c2，ck)dofori1tokdo从结点ci到结点b构造一条有向边；注意：如果属性文法不存在属性之间循环的依赖关系，那么称该文法为良定义。,17,例6.5EE1+E2E.val=E1.val+E2.val,例6.4中带继承属性文法对于realid1，id2，id3,18,c属性的计算顺序拓扑排序一个有向非循环图的拓扑排序是图中结点的任何顺序m1，m2，mk，使得边必须是从序列中前面的结点指向后面的结点，也就是说,如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj前面。若依赖图中无环（属性之间没有循环依赖关系），则存在一个拓扑排序，它就是属性值的计算顺序。计算语义规则的方法1）分析树法：输入串分析树依赖图计算次序2）基于规则的方法：在构造编译器时，用手工或专门的工具来分析语义规则，确定属性值的计算顺序。3）忽略语义规则的方法：在语法分析过程中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。实际上，要求限制语法制导定义，使属性值的计算顺序能和语法分析过程同步进行。,19,2.3树遍历的属性计算方法,前提：1）假设语法树已经建立2）且树中已带有开始符号的继承属性和终结符的综合属性；方法：深度优先，从左到右进行（也是一种分析树的方法）具体算法：While还有未被计算的属性doVisitNode(S)/S是开始符号ProcedureVisitNode(N：Node)；beginifNVNthen/假设它的产生式NX1Xmfori=1tomdoifXiVNthenbegin计算Xi的所有能够计算的继承属性；VisitNode（Xi）；end；计算N的所有能够计算的综合属性；end例子：6.6P143,20,2.4一遍扫描的处理办法,在语法分析的同时计算属性值，无需构造实际的语法树；这种方法同下面两个因素有关：,所采用的语法分析方法属性的计算次序使用一遍扫描的语义分析方法，就是为文法中的每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。在自上而下的分析中就是在产生式匹配输入串成功，或者在自下而上的分析中，当一个产生式被用于进行规约时，此产生式相应的语义规则就被计算，完成有关的语义分析和代码产生的工作。语法分析过程中完成翻译有许多优点，但也有一些不足：适于语法分析的文法可能不完全反映语言成分的自然层次结构；语法分析方法限制，对语法树结点的访问次序和翻译需要的访问次序不一致。,21,2.5抽象语法树(AbstractSyntaxtree),（1）表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是语法树的抽象形式，也称作语法结构树，或结构树。抽象语法树是常用的一种中间表示形式。（2）在抽象语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。产生式SifBthenS1elseS2赋值语句的语法树if-then-elseassignment|BS1S2variableexpression（3）建立表达式的抽象语法树建立表达式的抽象语法树使用的函数1）mknode（op，left，right）建立一个运算符号结点，标号是op，两个域left和right指向运算分量结点的指针。2）mkleaf(id，entry)建立一个标识符结点，由标号id标识，一个域entry指向标识符符号表中相应的项。3）mkleaf（num，val）建立一个数结点，标号为num，域val用于存放数的值。返回新建立结点的指针。,22,产生式语义规则EE1+TE.nptr:=mknode(+,E1.nptr,T.nptr)EE1-TE.nptr:=mknode(-,E1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val),23,本章教学线索,1属性文法（属性翻译文法）2基于属性文法的处理办法3S-属性文法的自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性,24,3S-属性文法的自下而上计算,s-属性文法：只含有综合属性s-属性文法通常借助于LR分析器来实现，在分析栈中使用一个附加的域来存放文法符号的综合属性值。,Ab=f（c1，c2，ck）b是A的综合属性，ci(1ik)是中符号的属性。综合属性的值在自底向上的分析过程中，每步归约时，计算相应的属性值。,25,例如：AXYZAaf(Xx，Yy，Zz)AaXxYyZz,定义式A.a=f（X.x，Y.y，Z.z）（抽象）变成：valntopf（valtop-2，valtop-1，valtop）（具体可执行代码）。在执行代码段之前执行：ntoptop-r+1（r是句柄的长度）执行代码段后执行：topntop；总结：采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程序,完成翻译的任务。,26,例6.9用LR分析器实现台式计算器产生式代码段LEnprintf(valntop)EE+Tvalntop:=valtop-2+valtopETTT*Fvalntop:=valtop-2*valtopTFF(E)valntop:=valtop-1Fdigit,输入stateval产生式3*5+4n-*5+4n33*5+4nF3Fdigit*5+4nT3TF5+4nT*3-+4nT*53-5+4nT*F3-5Fdigit+4nT15TT*F+4nE15ET4nE+15-nE+415-4nE+F15-4FdigitnE+T15-4TFnE19EE+TEn19L19LEn,27,本章教学线索,1属性文法（属性翻译文法）2基于属性文法的处理办法3S-属性文法的自下而上计算4L-属性文法和自顶向下翻译4.1L-属性文法的定义4.2翻译模式4.3自顶向下的翻译4.4递归下降翻译器的设计5自下而上计算继承属性,28,4L-属性文法和自顶向下翻译,在语法分析过程中进行语义分析和翻译，属性的计算顺序受到语法分析建立分析树结点顺序的限制。一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。L-属性文法可用按深度优先顺序计算属性值。,29,4.1L-属性文法的定义,如果AX1X2XnP，其每一个语义规则中的每一个属性都是一个综合属性，或是Xj(1jn)的一个继承属性，这个继承属性仅依赖于：a产生式中Xj的左边符号X1，X2，Xj-1的属性；bA的继承属性。每一个S-属性文法都是L-属性文法,30,4.2翻译模式,1）翻译模式的概念：翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号括起来，可以被插入到产生式右部的任何合适的位置上。这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。,翻译模式保证了按深度优先次序一次扫描就能完成属性的计算。,例一个简单的翻译模式ETRRaddopTprint(addop.lexeme)R1|Tnumprint(num.val),9-5+2翻译成后缀式95-2+,31,2）翻译模式的构造条件：属性文法是L-属性文法；保证语义动作不会引用还没有计算的属性值。a.只需要综合属性的情况：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：TT1*FTval=T1val*FvalTT1*FTval=T1val*Fvalb.既有综合属性又有继承属性:产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。一个动作不能引用这个动作右边符号的综合属性。(因为综合属性是在该符号所有分析动作结束后计算）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。,32,4.3自顶向下的翻译,用翻译模式构造自顶向下翻译。从翻译模式中消除左递归对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取公共左因子，在改写基本文法时考虑属性值的计算。例图6.13的带左递归的文法的翻译模式被转换成图6.14的带右递归的文法的翻译模式。EE1+TEval:=E1val+TvalEE1-TEval:=E1val-TvalETE.val:=TvalT(E)Tval:=EvalTnumTval:=numval图6.13带左递归的文法的翻译模式,33,ETR.i:=T.valRE.val:=R.sRTR1.i:=R.i+T.valR1R.s:=R1.sR-TR1.i:=R.i-T.valR1R.s:=R1.sRR.s:=R.iT（E）T.val:=E.valTnumT.val:=num.val图6.14经过转换的带有右递归文法的翻译模式,R.s=R.i,34,关于左递归翻译模式更一般化的讨论左递归翻译模式AA1YA.a:=g(A1.a，Y.y)AXA.a:=f(X.x)（6.2）每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。消除左递归，文法转换成AXRRYR|（6.3）再考虑语义动作，翻译模式变为：AXR.i:=f(X.x)RA.a:=R.sRYR1.i:=g（R.i，Y.y）R1R.s:=R1.sRR.s:=R.i（6.4）经过转换的翻译模式与图6.14中一样,使用R的继承属性i和综合属性s。（6.2）和（6.4）的结果是一样的,35,输入：XY1Y2,AA1YA.a:=g(A1.a,Y.y)AXA.a:=f(X.x)（6.2）,AXRi:=f(Xx)RA.a:=R.sRYR1i:=g（Ri，Yy）R1Rs:=R1sRRs:=Ri（6.4）,36,建立表达式的抽象语法树的翻译模式：EE1+TEnptr:=mknode(+,E1nptr,Tnptr)EE1-TEnptr:=mknode(-,E1nptr,Tnptr)ETEnptr:=Tnptr从翻译模式中消除左递归，变成以下翻译模式：ETRi:=TnptrREnptr:=RsRTR1i:=mknode(+,Ri,Tnptr)R1Rs:=R1sR-TR1i:=mknode(-,Ri,Tnptr)R1Rs:=R1sRRs:=RiT(E)Tnptr:=EnptrTidTnptr:=mkleaf(id,identry)TnumTnptr:=mkleaf(num,numval),37,使用继承属性构造a-4+5的语法树,E,T,id,nptr,id,toentryfora,R,-,T,num,nptr,num4,i,-,R,+,T,id,nptr,id,toentryforc,+,i,R,s,i,38,4.4递归下降翻译器的设计,算法6.1预测语法制导翻译器的建立输入：一个带有适合预测分析的基础文法的语法制导翻译模式。输出：一个语法制导翻译器的代码。方法：在预测分析器中加入语义动作代码。AVN,建立一个可递归调用的函数过程A。为A的每一个继承属性都设置一个形式参数，函数的返回值是A的综合属性值。函数过程A的代码（指用符号形式表示的数据和程序）要根据当前的输入符号来决定使用哪一个产生式。与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、非终结符号还是语义动作，分别是：（a）对于带有综合属性x的单词符号X，x存放在X.x中，Match(X)。（b）对于BVN，编写一个赋值语句c:=B（b1,b2,，bk)其中，b1，b2，bk是继承属性，c是综合属性。（c）对于每个动作，动作的代码抄进翻译器中，用代表属性的变量来代替对属性的每一次引用。,39,例:RaddopTR1i:=mknode（addoplexeme，Ri，Tnptr）R1R.s:=R1.sRR.s:=R.i递归下降构造语法树functionR(in:AST-node):AST-node;varnptr,i1,s1,s:AST-node;addoplexeme:char;beginifsym=addopthenbeginaddoplexeme=lexval;advance;/