编译原理第六章习题答案

编译原理电子教案第六章属性文法和语法制导翻译谢强计算机科学与技术学院13851481944[e-mail]上一页下一页2本章的主要内容属性文法和语法制导的翻译的概念综合属性和继承属性的概念、特点S-属性文法与L-属性文法的概念及分析方法翻译模式递归下降翻译器的设计上一页下一页3本章要求知识点：语法制导定义，S-属性定义及其自底向上计算属性，L-属性定义，自顶向下的翻译，自底向上计算继承属性。深刻理解：属性，综合属性，继承属性，依赖图，计算顺序，语法树，语法制导定义，S-属性文法定义，L-属性文法定义，翻译模式。熟练掌握：对于已知文法G和翻译任务，构造其L-属性定义，将其改造成适于自顶向下分析或自底向上分析的翻译模式。上一页下一页4本章教学线索1属性文法（属性翻译文法）1.1属性文法的概念1.2属性的分类1.3属性的计算规则2基于属性文法的处理办法3S-属性文法的自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性上一页下一页51属性文法（属性翻译文法）语法制导翻译：通过给语法树上各个符号赋予一定的含义并且将各个符号进行有结构的连接，可以形成语言的具体语句的含义。这给予我们以启示：可以通过扩充文法，在文法符号上附着某些语义信息，并在这些语义信息间建立相互计算关系，从而在语法分析的同时进行语义分析。由于这种分析是在语法分析的控制下进行的，故称为语法制导翻译。上一页下一页61.1属性文法的概念（1）属性文法的定义在上下文无关文法的基础上，为每个文法符号（终结符和非终结符）配备若干相关的“值”（也称：“属性”），对于文法的每个产生式都配备了一组属性的计算规则（语义规则），这种文法称为属性文法。1968年，Knuth首先提出。说明：在一般情况下，整个属性文法是非常复杂的。但属性的函数关系却通常非常简单。属性也很少依赖于大量的其它属性，因此可以将相互依赖的属性分割成较小的独立属性集，然后单独对每一属性集写出一个属性文法。上一页下一页7（2）属性（Attribute）是编程语言结构的任意特性。属性在其包含的信息和复杂性等方面变化很大。属性的典型例子有：•变量的数据类型•表达式的值•存储器中变量的位置•程序的目标代码•数的有效位数（3）属性文法一般表示方法：文法规则语义规则规则1规则2…规则n相关的属性等式/语义规则相关的属性等式/语义规则…相关的属性等式/语义规则上一页下一页8例6.1一个简单台式计算器的属性文法产生式语义规则L→EnPrint(E.val)E→E1+TE.val=E1.val+T.valE→TE.val=T.valT→T1*FT.val=T1.val*F.valT→FT.val=F.valF→(E)F.val=E.valF→digitF.val=digit.lexval上一页下一页9例6.2：无符号整数的属性文法文法规则语义规则Number1→Number2digitNumber→digitdigit→0digit→1digit→2digit→3digit→4digit→5digit→6digit→7digit→8digit→9Number1.val=number2.val*10+digit.valNumber.val=digit.valdigit.val=0digit.val=1digit.val=2digit.val=3digit.val=4digit.val=5digit.val=6digit.val=7digit.val=8digit.val=9上一页下一页101.2属性的分类例6.3属性文法为例6.1中的属性文法，输入：3*5+4ndigitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19Ln•综合属性：用于自下而上传递信息；在语法树中，一个结点的综合属性由其子结点的属性值确定，因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。•继承属性：用于自上而下传递信息；在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。上一页下一页11例6.4继承属性的类型说明文法产生式语义规则D→TLL.in=T.typeT→intT.type=integerT→realT.type=realL→L1,idL1.in=L.inAddtype(id.entry,L.in)L→idAddtype(id.entry,L.in)DT.type=realrealL.in=realL.in=real,id3L.in=real,id2id1realid1，id2，id3上一页下一页121.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自下而上计算继承属性上一页下一页152.1语法制导翻译基于属性文法的处理过程通常是：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。输入串分析树依赖图语义规则的计算图6.1语法制导翻译的概观在具体实现时，一般都是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。也就是语义分析是伴随语法分析的过程进行。上一页下一页162.2依赖图a．依赖图：一种有向图，在一颗语法树中表示结点的继承属性和综合属性之间的相互依赖关系（这种属性之间的依赖关系由文法的语义规则确定）。b．依赖图的构造方法：for语法树中每一结点ndofor结点n的文法符号的每一个属性ado为a在依赖图中建立一个结点；for语法树中每一个结点ndofor结点n所有产生式对应的每一条语义规则b＝f（c1，c2，…，ck)dofori＝1tokdo从结点ci到结点b构造一条有向边；注意：如果属性文法不存在属性之间循环的依赖关系，那么称该文法为良定义。bC1C2…Ck-1Ck上一页下一页17例6.5E→E1+E2E.val=E1.val+E2.valE.valE1.valE2.valDTrealLL,id3L,id2id14typein5in7in910861entry3entry2entry例6.4中带继承属性文法对于realid1，id2，id3产生式语义规则D→TLL.in=T.typeT→intT.type=integerT→realT.type=realL→L1,idL1.in=L.inAddtype(id.entry,L.in)L→idAddtype(id.entry,L.in)上一页下一页18c．属性的计算顺序拓扑排序一个有向非循环图的拓扑排序是图中结点的任何顺序m1，m2，…，mk，使得边必须是从序列中前面的结点指向后面的结点，也就是说,如果mi→mj是mi到mj的一条边，那么在序列中mi必须出现在mj前面。若依赖图中无环（属性之间没有循环依赖关系），则存在一个拓扑排序，它就是属性值的计算顺序。计算语义规则的方法1）分析树法：输入串→分析树→依赖图→计算次序2）基于规则的方法：在构造编译器时，用手工或专门的工具来分析语义规则，确定属性值的计算顺序。3）忽略语义规则的方法：在语法分析过程中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。实际上，要求限制语法制导定义，使属性值的计算顺序能和语法分析过程同步进行。上一页下一页192.3树遍历的属性计算方法前提：1）假设语法树已经建立2）且树中已带有开始符号的继承属性和终结符的综合属性；方法：深度优先，从左到右进行（也是一种分析树的方法）具体算法：While还有未被计算的属性doVisitNode(S)//S是开始符号ProcedureVisitNode(N：Node)；beginifN∈VNthen//假设它的产生式N→X1…Xmfori=1tomdoifXi∈VNthenbegin计算Xi的所有能够计算的继承属性；VisitNode（Xi）；end；计算N的所有能够计算的综合属性；end例子：6.6P143上一页下一页202.4一遍扫描的处理办法在语法分析的同时计算属性值，无需构造实际的语法树；这种方法同下面两个因素有关：1.所采用的语法分析方法2.属性的计算次序使用一遍扫描的语义分析方法，就是为文法中的每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。在自上而下的分析中就是在产生式匹配输入串成功，或者在自下而上的分析中，当一个产生式被用于进行规约时，此产生式相应的语义规则就被计算，完成有关的语义分析和代码产生的工作。语法分析过程中完成翻译有许多优点，但也有一些不足：适于语法分析的文法可能不完全反映语言成分的自然层次结构；语法分析方法限制，对语法树结点的访问次序和翻译需要的访问次序不一致。上一页下一页212.5抽象语法树(AbstractSyntaxtree)（1）表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是语法树的抽象形式，也称作语法结构树，或结构树。抽象语法树是常用的一种中间表示形式。（2）在抽象语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。产生式S→ifBthenS1elseS2赋值语句的语法树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产生式语义规则EE1+TE.nptr:=mknode('+',E1.nptr,T.nptr)EE1-TE.nptr:=mknode('-',E1.nptr,T.nptr)ETE.nptr:=T.nptrT(E)T.nptr:=E.nptrTidT.nptr:=mkleaf(id,id.entry)TnumT.nptr:=mkleaf(num,num.val)idtoentryanum4–idtoentryc+a-4+c的语法树上一页下一页23本章教学线索1属性文法（属性翻译文法）2基于属性文法的处理办法3S-属性文法的自下而上计算4L-属性文法和自顶向下翻译5自下而上计算继承属性上一页下一页2