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

1、上一页下一页2本章的主要内容本章的主要内容 属性文法和语法制导的翻译的概念 综合属性和继承属性的概念、特点 S-属性文法与L-属性文法的概念及分析方法 翻译模式 递归下降翻译器的设计上一页下一页3本章要求本章要求 知识点：语法制导定义，S-属性定义及其自底向上计算属性，L-属性定义，自顶向下的翻译，自底向上计算继承属性。深刻理解：属性，综合属性，继承属性，依赖图，计算顺序，语法树，语法制导定义，S-属性文法定义，L-属性文法定义，翻译模式。熟练掌握：对于已知文法G和翻译任务，构造其L-属性定义，将其改造成适于自顶向下分析或自底向上分析的翻译模式。上一页下一页4本章教学线索本章教学线索1 属性文

2、法（属性翻译文法）属性文法（属性翻译文法）1.1 属性文法的概念 1.2 属性的分类 1.3 属性的计算规则2 基于属性文法的处理办法基于属性文法的处理办法3 S-S-属性文法的自下而上计算属性文法的自下而上计算4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译5 自下而上计算继承属性自下而上计算继承属性上一页下一页51 属性文法（属性翻译文法）属性文法（属性翻译文法）语法制导翻译：通过给语法树上各个符号赋予一定的含义并且将各个符号进行有结构的连接，可以形成语言的具体语句的含义。这给予我们以启示：可以通过扩充文法，在文法符号上附着某些语义信息，并在这些语义信息间建立相互计算关系，从而在语

3、法分析的同时进行语义分析。由于这种分析是在语法分析的控制下进行的，故称为语法制导翻译。上一页下一页61.1 属性文法的概念属性文法的概念（1）属性文法的定义 在上下文无关文法的基础上，为每个文法符号（终结符和非终结符）配备若干相关的“值”（也称：“属性”），对于文法的每个产生式都配备了一组属性的计算规则（语义规则），这种文法称为属性文法。1968年，Knuth首先提出。说明：在一般情况下，整个属性文法是非常复杂的。但属性的函数关系却通常非常简单。属性也很少依赖于大量的其它属性，因此可以将相互依赖的属性分割成较小的独立属性集，然后单独对每一属性集写出一个属性文法。上一页下一页7（2）属性（Att

4、ribute）是编程语言结构的任意特性。属性在其包含的信息和复杂性等方面变化很大。属性的典型例子有：变量的数据类型 表达式的值 存储器中变量的位置 程序的目标代码 数的有效位数（3）属性文法一般表示方法：上一页下一页8例6.1 一个简单台式计算器的属性文法上一页下一页9例：无符号整数的属性文法上一页下一页101.2 属性的分类属性的分类例6.3 属性文法为例中的属性文法，输入：3*5+4ndigitlexval:=3Fval:=3Tval:=3digitlexval:=5Fval:=5Tval:=15*Eval:=15+digitlexval:=4Fval:=4Tval:=4Eval:=19L

5、n 综合属性：用于自下而上传递信息；在语法树中，一个结点的综合属性由其子结点的属性值确定，因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。继承属性：用于自上而下传递信息；在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。上一页下一页11例6.4 继承属性的类型说明文法DT.type=realrealL.in=realL.in=real,id3L.in=real,id2id1real id1，id2，id3上一页下一页121.3 属性的计算规则属性的计算规则属性的计算规则：设有产生式A定义 b=f（c1，

6、c2，ck）f是一个计算函数，并且（1）b是A的一个综合属性，并且c1，c2，ck是产生式右边文法符号的属性。或者：（2）b是产生式右边某文法符号的一个继承属性，并且c1，c2，ck是A或产生式右边任何文法符号的属性。上一页下一页13注意：如果同一文法符号在文法规则中出现不止一次，那么每次必须用合适的下标与在其他地方出现的符号区分开来。终结符只有综合属性，它们由词法分析器提供。非终结符既可有综合属性也可有继承属性，文法开始符的所有继承属性为属性计算前的初始值。属性计算规则中仅能使用相应产生式中文法符号的属性（封装性）。产生式左边的继承属性和产生式右边的文法符号的综合属性由其它产生式的属性规则计

7、算。一个句型的语法树可以加以扩充，用来表示句型分析中得到的各个符号的属性间的关系：u语法树中，一个结点的综合属性的值由其子结点的属性值确定u语法树中，一个结点的继承属性的值由该结点的父结点和（或）兄弟结点的某些属性值确定上一页下一页14本章教学线索本章教学线索1 属性文法（属性翻译文法）属性文法（属性翻译文法）2 基于属性文法的处理办法基于属性文法的处理办法 2.1 语法制导翻译 依赖图 2.3 树遍历的属性计算方法 一一遍扫描的处理办法 2.5 抽象语法树(Abstract Syntax tree)3 S-S-属性文法的自下而上计算属性文法的自下而上计算4 L-L-属性文法和自顶向下翻译属性

8、文法和自顶向下翻译5 自下而上计算继承属性自下而上计算继承属性上一页下一页15 语法制导翻译语法制导翻译 基于属性文法的处理过程通常是：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。输入串分析树依赖图语义规则的计算图6.1 语法制导翻译的概观 在具体实现时，一般都是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。也就是语义分析是伴随语法分析的过程进行。上一页下一页162.2 依赖图依赖图a依赖图：一种有向图，在一颗语法树中表示结点的继承属性和综合属性之间的相互依赖关系（这种属性之间的依赖关系由文法的语义规则确定）。b

9、依赖图的构造方法：for 语法树中每一结点n do for 结点n的文法符号的每一个属性a do 为a在依赖图中建立一个结点；for 语法树中每一个结点n do for 结点n所有产生式对应的每一条语义规则 bf（c1，c2，ck)do for i1 to k do 从结点ci到结点b构造一条有向边；注意：如果属性文法不存在属性之间循环的依赖关系，那么称该文法为良定义。bC1C2Ck-1Ck上一页下一页17例6.5 EE1+E2 E.val=E1.val+E2.val E.valE1.valE2.valDTrealLL,id3L,id2id14typein 5in 7in 910861 ent

10、ry3 entry2 entry例中带继承属性文法对于real id1，id2，id3上一页下一页18c属性的计算顺序l拓扑排序一个有向非循环图的拓扑排序是图中结点的任何顺序m1，m2，mk，使得边必须是从序列中前面的结点指向后面的结点，也就是说,如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj前面。若依赖图中无环（属性之间没有循环依赖关系），则存在一个拓扑排序，它就是属性值的计算顺序。l计算语义规则的方法 1）分析树法：输入串分析树依赖图计算次序 2）基于规则的方法：在构造编译器时，用手工或专门的工具来分析语义规则，确定属性值的计算顺序。3）忽略语义规则的方法：在语法分析过程

11、中翻译，那么计算顺序由分析方法来确定而表面上与语义规则无关。实际上，要求限制语法制导定义，使属性值的计算顺序能和语法分析过程同步进行。上一页下一页192.3 树遍历的属性计算方法树遍历的属性计算方法前提：1）假设语法树已经建立 2）且树中已带有开始符号的继承属性和终结符的综合属性；方法：深度优先，从左到右进行（也是一种分析树的方法）具体算法：While 还有未被计算的属性 do VisitNode(S)/S是开始符号Procedure VisitNode(N：Node)；begin if NVN then /假设它的产生式NX1Xmfor i=1 to m do if XiVN then be

12、gin 计算计算Xi的所有能够计算的继承属性；的所有能够计算的继承属性；VisitNode（Xi）；end；计算计算N的所有能够计算的综合属性；的所有能够计算的综合属性；end例子：6.6 P143 上一页下一页202.4 一遍扫描的处理办法一遍扫描的处理办法 在语法分析的同时计算属性值，无需构造实际的语法树；这种方法同下面两个因素有关：所采用的语法分析方法 属性的计算次序 使用一遍扫描的语义分析方法，就是为文法中的每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。在自上而下的分析中就是在产生式匹配输入串成功，或者在自下而上的分析中，当一个产生式被用于进行规约时，此产生式相应的

13、语义规则就被计算，完成有关的语义分析和代码产生的工作。语法分析过程中完成翻译有许多优点，但也有一些不足：u适于语法分析的文法可能不完全反映语言成分的自然层次结构；u语法分析方法限制，对语法树结点的访问次序和翻译需要的访问次序不一致。上一页下一页212.5 抽象语法树抽象语法树(Abstract Syntax tree)（1）表示程序层次结构的树，它把分析树中对语义无关紧要的成分去掉，是语法树的抽象形式，也称作语法结构树，或结构树。抽象语法树是常用的一种中间表示形式。（2）在抽象语法树中，运算符号和关键字都不在叶结点，而是在内部结点中出现。产生式Sif B then S1 else S2 赋值语

14、句的语法树if-then-else assignment|B S1 S2 variable expression （3）建立表达式的抽象语法树 建立表达式的抽象语法树使用的函数 1）mknode（op，left，right）建立一个运算符号结点，标号是op，两个域left和right指向运算分量结点的指针。2）mkleaf(id，entry)建立一个标识符结点，由标号id标识，一个域entry指向标识符符号表中相应的项。3）mkleaf（num，val）建立一个数结点，标号为num，域val用于存放数的值。返回新建立结点的指针。上一页下一页22 产生式 语义规则 EE1+T E.nptr:=m

15、knode(+,E1.nptr,T.nptr)E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr)E T T id T.nptr:=mkleaf(id,id.entry)T num T.nptr:=mkleaf(num,num.val)idto entry anum 4 idto entry c +a-4+c的语法树上一页下一页23本章教学线索本章教学线索1 属性文法（属性翻译文法）属性文法（属性翻译文法）2 基于属性文法的处理办法基于属性文法的处理办法3 S-S-属性文法的自下而上计算属性文法的自下而上计算4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译5

16、自下而上计算继承属性自下而上计算继承属性上一页下一页243 S-属性文法的自下而上计算属性文法的自下而上计算s-属性文法：只含有综合属性s-属性文法通常借助于LR分析器来实现，在分析栈中使用一个附加的域来存放文法符号的综合属性值。stateval.ZZ.zY.Y.y.XX.ztop一个带有综合属性值域的分析栈A b=f（c1，c2，ck）b是A的综合属性，ci(1 ik)是中符号的属性。综合属性的值在自底向上的分析过程中，每步归约时，计算相应的属性值。上一页下一页25例如：AXYZ Aa f(Xx，Yy，Zz)Aa X x Y y Z z X X.xY Y.yZ Z.z A A.astate

17、valtoptopstate val 定义式 A.a=f（，）（抽象）变成：valntopf（valtop-2，valtop-1，valtop）（具体可执行代码）。在执行代码段之前执行：ntoptop-r+1（r是句柄的长度）执行代码段后执行：topntop；总总 结：结：采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。象一座建筑，语法分析是构架，归约处有一个“挂钩”，语义分析和翻译的代码段（语义子程序）就挂在这个钩子上。这样，随着语法分析的进行，归约前调用相应的语义子程序,完成翻译的任务。上一页下一页26例6.9 用LR分析器

18、实现台式计算器产生式 代码段 LEn printf(valntop)E E+T valntop:=valtop-2+valtopE TT T*F valntop:=valtop-2*valtopT FF(E)valntop:=valtop-1F digit输入 state val 产生式3*5+4n -*5+4n 3 3*5+4n F 3 Fdigit*5+4n T 3 TF 5+4n T*3-+4n T*5 3-5+4n T*F 3-5 F digit+4n T 15 TT*F+4n E 15 ET4n E+15-n E+4 15-4 n E+F 15-4 Fdigitn E+T 15-4

19、T Fn E 19 EE+T En 19 L 19 L En上一页下一页27本章教学线索本章教学线索1 属性文法（属性翻译文法）属性文法（属性翻译文法）2 基于属性文法的处理办法基于属性文法的处理办法3 S-S-属性文法的自下而上计算属性文法的自下而上计算4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译4.1 L-属性文法的定义4.2 翻译模式4.3 自顶向下的翻译4.4 递归下降翻译器的设计5 自下而上计算继承属性自下而上计算继承属性上一页下一页284 L-属性文法和自顶向下翻译属性文法和自顶向下翻译 在语法分析过程中进行语义分析和翻译，属性的计算顺序受到语法分析建立分析树结点顺序的

20、限制。一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。L-属性文法可用按深度优先顺序计算属性值。上一页下一页294.1 L-属性文法的定义属性文法的定义 如果AX1X2XnP，其每一个语义规则中的每一个属性都是一个综合属性，或是Xj(1j n)的一个继承属性，这个继承属性仅依赖于：a产生式中Xj的左边符号X1，X2，Xj-1的属性；bA的继承属性。每一个每一个S-属性文法都是属性文法都是L-属性文法属性文法上一页下一页304.2 翻译模式翻译模式1）翻译模式的概念：翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规

21、则或语义动作用花括号 括起来，可以被插入到产生式右部的任何合适的位置上。这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。翻译模式保证了按深度优先次序一次扫描就能完成属性的计算。翻译模式保证了按深度优先次序一次扫描就能完成属性的计算。例 一个简单的翻译模式 ETR Raddop T print(addop.lexeme)R1|Tnum print(num.val)ET9print(9)R-T5print(5)print(-)R+Tprint(2)print(+)2R9-5+2翻译

22、成后缀式95-2+上一页下一页312）翻译模式的构造条件：属性文法是L-属性文法；保证语义动作不会引用还没有计算的属性值。a.只需要综合属性的情况：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：TT1*F Tval=T1 val*F val TT1*F Tval=T1 val*F valb.既有综合属性又有继承属性:产生式右边符号的继承属性必须在这个符号以前的动作中计算出来。一个动作不能引用这个动作右边符号的综合属性。(因为综合属性是在该符号所有分析动作结束后计算）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的

23、动作通常可放在产生式右端的末尾。上一页下一页324.3 自顶向下的翻译自顶向下的翻译用翻译模式构造自顶向下翻译。从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取公共左因子，在改写基本文法时考虑属性值的计算。例例 图的带左递归的文法的翻译模式被转换成图的带右递归的文法的翻译模式。EE1+T E val:=E1val+T val E E1-T E val:=E1 val-T val E T E.val:=T val T (E)T val:=E val T num T val:=num val 图6.13 带左递归的文法的翻译模式 上一页下一页33 ET R.i:=

24、T.val RE.R T R1.i:=R.i+T.val R1R.s:=R1.s R-T R1.i:=R.i-T.val R1R.s:=R1.s RR.s:=R.i T（E）T.val:=E.val Tnum T.val:=num.val 图经过转换的带有右递归文法的翻译模式ET.val=9num.val=9R.i=9-T.val=5num.val=5R.i=4+T.val=2num.val=2R.i=6R.s=R1.sR.s=R1.sE.val=R.s计算表达式计算表达式9-5+2上一页下一页34关于左递归翻译模式更一般化的讨论关于左递归翻译模式更一般化的讨论左递归翻译模式 AA1YA.a:

25、=g(A1.a，Y.y)AX A.a:=f(X.x)（）每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。消除左递归，文法转换成 AX R RY R|（）再考虑语义动作，翻译模式变为：AX R.i:=f(X.x)R A.a:=R.s RY R1.i:=g（R.i，Y.y）R1 R.s:=R1.s R R.s:=R.i （）经过转换的翻译模式与图中一样,使用R的继承属性i和综合属性s。（）和（）的结果是一样的 上一页下一页35A.a=g(g(f(X.x),Y1.y),Y2.y)A.a=g(g(f(X.x),Y1.y),Y2.y)Y2A.a=g(f(X.x),Y1.y)A.a

26、=g(f(X.x),Y1.y)A.a=f(X.x)A.a=f(X.x)Y1X XAX XR.i=f(X.x)R.i=f(X.x)Y1R.i=g(f(X.x),Y1.y)R.i=g(f(X.x),Y1.y)Y2R.i=g(g(f(X.x),Y1.y),Y2.y)R.i=g(g(f(X.x),Y1.y),Y2.y)输入：XY1Y2AA1YA.a:=g(A1.a,Y.y)AX A.a:=f(X.x)（）AX Ri:=f(X x)R A.a:=R.s RY R1 i:=g（R i，Y y）R1 R s:=R1 s R R s:=R i （）上一页下一页36建立表达式的抽象语法树的翻译模式：建立表达式的

27、抽象语法树的翻译模式：EE1+T E nptr:=mknode(+,E1 nptr,T nptr)EE1-T E nptr:=mknode(-,E1 nptr,T nptr)ET E nptr:=T nptr 从从翻译模式中消除左递归，变成以下翻译模式：翻译模式中消除左递归，变成以下翻译模式：ET R i:=T nptr R E nptr:=R s R T R1 i:=mknode(+,R i,T nptr)R1 R s:=R1 s R-T R1 i:=mknode(-,R i,T nptr)R1 R s:=R1 s R R s:=R i T(E)T nptr:=E nptr Tid T np

28、tr:=mkleaf(id,id entry)Tnum T nptr:=mkleaf(num,num val)上一页下一页37使用继承属性构造a-4+5的语法树ETidnptridto entry for aR-Tnumnptrnum 4i-R+Tidnptridto entry for c+iRsi上一页下一页384.4 递归下降翻译器的设计递归下降翻译器的设计算法6.1 预测语法制导翻译器的建立 输入：一个带有适合预测分析的基础文法的语法制导翻译模式。输出：一个语法制导翻译器的代码。方法：在预测分析器中加入语义动作代码。A VN,建立一个可递归调用的函数过程建立一个可递归调用的函数过程 A

29、。为。为A的每一个继承属性都的每一个继承属性都设置设置 一个形式参数，函数的返回值是一个形式参数，函数的返回值是A的综合属性值。的综合属性值。函数过程函数过程A的代码（指用符号形式表示的数据和程序）要根据当前的的代码（指用符号形式表示的数据和程序）要根据当前的输入符号来决定使用哪一个产生式。输入符号来决定使用哪一个产生式。与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、与每一个产生式有关的代码，从左到右根椐产生式右部是单词符号、非终结符号还是语义动作，分别是：非终结符号还是语义动作，分别是：（a）对于带有综合属性）对于带有综合属性x的单词符号的单词符号X，x存放在中，存放在中，Ma

30、tch(X)。（b）对于）对于B VN，编写一个赋值语句，编写一个赋值语句c:=B（b1,b2,，bk)其中，其中，b1，b2，bk是继承属性，是继承属性，c是综合属性。是综合属性。（c）对于每个动作，动作的代码抄进翻译器中，用代表属性的变量来代替）对于每个动作，动作的代码抄进翻译器中，用代表属性的变量来代替对属性的每一次引用。对属性的每一次引用。上一页下一页39例例:Raddop T R1i:=mknode（addop lexeme，R i，T nptr）R1 R.s:=R1.s R R.s:=R.i递归下降构造语法树递归下降构造语法树 function R(in:AST-node):AST

31、-node;var nptr,i1,s1,s:AST-node;addoplexeme:char;begin if sym=addop then begin addoplexeme=lexval;advance;/执行一个匹配执行一个匹配 nptr=T;/调用调用T的函数，返回的函数，返回T的综合属性的综合属性 i1=mknode(addoplexeme,in,nptr);/返回返回R1的继承属性的继承属性 s1=R(i1)/调用调用R过程形参为过程形参为R的继承属性，返回的继承属性，返回R的综合属性的综合属性 s=s1 /执行执行R.s=R1.s end else s=in /如果如果sym

32、不是不是addop，则，则R-自动匹配，执行自动匹配，执行R return s end上一页下一页40本章教学线索本章教学线索1 属性文法（属性翻译文法）属性文法（属性翻译文法）2 基于属性文法的处理办法基于属性文法的处理办法3 S-S-属性文法的自下而上计算属性文法的自下而上计算4 L-L-属性文法和自顶向下翻译属性文法和自顶向下翻译5 自下而上计算继承属性自下而上计算继承属性5.1 从翻译模式中去掉嵌入在产生式中间的动作5.2 分析栈中的继承属性5.3 模拟继承属性的计算5.4 用综合属性代替继承属性上一页下一页415.1 从翻译模式中去掉嵌入在产生式中间的动作从翻译模式中去掉嵌入在产生式

33、中间的动作 在自下而上的翻译方法中要求把所有的语义动作都放在产生式的末尾，而在前面讲到的递归下降翻译方法中，需要在产生式右部的不同地方嵌入语义动作。等价转换的方法如下：在基础文法中加入新的产生式，这种产生式的形式为：M，其中M为新引入的一个标记非终结符，把嵌入在产生式中的每个语义动作用不同的标记非终结符M代替，并把这个动作放在产生式M的末尾。例如：ETR R+T print(+)R|-T print(-)|Tnumprint(num.val)等价转换为：ETRR+TMR|-TNR|Tnum print(num.val)Mprint(+)Nprint(-)上一页下一页425.2 分析栈中的继承属性分析栈中的继承属性（前面已经讲解了）参见P159对类型说明语句的翻译模式。上一页下一页435.3 模拟继承属性的计算模拟继承属性的计算 思想：通过引进新的非终结符和相应的产生式，将新的文法符号插入到某些产生式中去，使得在文法在翻译过程中可以按继承属性的计算方法来处理。也就是在分析过程中文法符号的属性值在分析栈是确定的。上一页下一页445.4 用综合属性代替继承属性用综合属性代替继承属性 对基础文法进行等价改变，避免使用文法符号的继承属性。结结 语语The End谢谢您的聆听！期待您的指正！