第六章-属性文法-2.0(1)

属性文法和语法制导翻译语义处理在编译程序中的逻辑位置词法分析语法分析中间代码生成中间代码优化（可选）目标代码优化（可选）目标代码生成静态语义分析语义处理两项工作：静态语义分析，中间代码生成静态语义分析：主要工作如类型检查、名字的作用域分析等中间代码生成：从语法分析的结果生成中间代码（个别编译程序可能直接生成目标代码）跨分析和综合两个阶段分析阶段：理解源程序，挖掘源程序的语义综合阶段：生成与源程序语义上等价的目标程序跨编译程序的前端和后端语义处理在编译程序中的逻辑位置编译程序的设计中，语义分析和中间（目标）代码生成的实现多采用语法制导的语义处理（许多时候直接称之为语法制导的翻译）语法制导语义处理技术的基础是应用属性文法语义处理技术本章我们应该掌握什么属性文法的一些基本概念基于属性文法的几种处理方法S-属性文法的自上而下计算L-属性文法和自顶向下翻译自下而上计算继承属性一属性文法的基本概念①属性文法（也称属性翻译文法）：Kunth在1968年首先提出的。它是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。识别语言L={aibjcki,j,k1}但显示anbncn(n1)是合法的产生式SABCAA1aAaBB1bBbCC1cCc语义规则{if(A.num==B.num)and(B.num==C.num)thenprint(“Accepted!”)elseprint(“Refused!”)}{A.num:=A1.num+1}{A.num:=1}{B.num:=B1.num+1}{B.num:=1}{C.num:=C1.num+1}{C.num:=1}②语义规则：在一个属性文法中，对应于每个产生式A－α都有一套与之相关语义规则，每条规则的形式为b:=f(c1,c2,…,ck)这里，f是一个函数b是A的一个综合属性并且c1,c2,…,ck是产生式右边文法符号的属性；或者b是产生式右边某个文法符号的一个继承属性并且c1,c2,…,ck是A或产生式右边任何文法符号的属性。在这两种情况下，我们都说属性b依赖于属性c1,c2,…,ck。对于文法的每个产生式都配备的一组属性的计算规则。※例一※产生式A－BC可能有规则C.d:=B.c+1A.b:=A.a+B.c这些属性是什么类型？A.a和B.c在什么地方计算？强调终结符只有综合属性，它们由词法分析器提供；非终结符既可以有综合属性也可有继承属性文法开始符号的所有继承属性作为属性计算前的初始值对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其他产生式的属性计算规则或者由属性计算器的参数提供③综合属性综合属性在实际中被广泛应用。在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因为，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S-属性文法。下面的简单例子说明综合属性的使用和计算过程。说明：非终结符E，T，F都有一个综合属性val的整数值。符号digit有一个综合属性lexval，由词法分析器提供。产生式LEn对应的语法规则为打印由E产生的算术表达式的值的过程。产生式语义规则LEnEE1+TETTT1*FTFF(E)FdigitPrint(E.val)E.val:=E1.val+T.valE.val:=T.valT.val:=T1.val*F.valT.val:=F.valF.val:=E.valF.val:=digit.lexval表一一个简单计算器的属性文法假设表达式是3×5＋4，后跟换行符n画出语法树，并根据语义规则加注释Digit.lexval=3F.val=3T.val=3Digit.lexval=5T.val=15*F.val=5E.val=15E.val=19T.val=4F.val=4Digit.vexval=4Ln+※例二※语法分析树中各结点属性值的计算过程被称为对语法分析树的标注（annotating）或修饰（decorating），用带标注（annotated）的语法分析树表示属性值的计算结果④继承属性语法树中，一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定。用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。给出句子realid1,id2,id3,看看它的带注释的语法树※例三※产生式语义规则DTLTintTrealLL1,idLidL.in:=T.typeT.type:=integerT.type:=realL1.in:=L.inAddtype(id.entry,L.in)Addtype(id.entry,L.in)realT.type=realDL.in=realL.in=realL.in=real,,id1id2id3此例为继承属性在说明中为各种标识符提供类型信息非终结符T有一个综合属性type，它的值由说明中的关键字确定.与产生式DTL相应的语义规L.in:=T.type把说明中的类型赋值给继承属性L.in.利用语义规则把继承属性L.in沿着语法树往下传.Addtype把每个标志符的类型填入符号表的相应项中.二基于属性文法的处理方法基于属性文法的处理过程这种由源程序的语法结构所驱动的处理办法就是语法制导翻译。语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其他动作。对输入符号串的翻译也就是根据语义规则进行计算的结果。输入串语法树依赖图语义规则计算次序依赖图如果在一颗语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的语义规则必须在确定c的语义规则之后使用。在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述。强调：在为一颗语法树构造依赖图以前，为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成b:=f(c1,c2,…,ck)的形式。依赖图中为每一个属性设置一个结点，如果属性b依赖于属性c，则从属性c的结点有一条有向边连到属性b的结点。※举例四※当下面的产生式应用于语法树时，产生的依赖图如图。产生式语义规则E1－E1+E2E.val:=E1.val+E2.val图中虚线表示的是语法树，它不是依赖图中的一部分。E1EE2＋画出语法树根据规则，画出依赖图.val.val.val句子realid1，id2，id3的带注释的语法树的依赖图id1L,id2L,id3LrealTD4type5in6-addtype(id.entry,L.in)7in8addtype9in10addtype1entry2entry3entry产生式语义规则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)※举例五※属性的计算次序循环依赖关系例如：p,c1,c2都是属性，有如下求值规则p:=f1(c1),c1:=f2(c2),c2:=f3(p)，此时无法对p求值良定义属性文法如果一属性文法不存在属性之间的循环依赖关系，那么该属性文法为良定义的。（我们只处理良定义的属性文法）拓扑序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,…,mk，使得边必须是从序列中前面的结点指向后面的结点。也就是说mi－mj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。句子realid1，id2，id3的带注释的语法树的依赖图属性计算顺序id1L,id2L,id3LrealTD4type5in67in89in101entry2entry3entrya4:=real;a5:=a4addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7);a9:=a7addtype(id1.entry,a9);②树遍历的属性计算方法通过树遍历的方法计算属性的值假设语法树已建立，且树中已带有开始符号的继承属性和终结符的综合属性以某种次序遍历语法树，直至计算出所有属性深度优先，从左到右的遍历最常用的遍历方法是深度优先，从左到右的遍历的方法。可使用多次遍历（或称遍）。While还有未被计算的属性doVisitVode(S)/*S是开始符号*/procedureVisitNode(N:Node);beginifN是一个非终结符then/*假设它的产生式为N－X1…Xm*/fori:=1tomdoifXiVNthen/*即Xi是非终结符*/begin计算Xi的所有能够计算的继承属性VisitNode(Xi）end计算N的所有能够计算的综合属性end②树遍历的属性计算方法S有继承属性a，综合属性bX有继承属性c，综合属性dY有继承属性e，综合属性fZ有继承属性h，综合属性g※举例六※产生式语义规则S→XYZX→xY→yZ→zZ.h:=S.aX.c:=Z.gS.b:=X.d–2Y.e:=S.bX.d:=2*X.cY.f:=Y.e*3Z.g:=Z.h+1参照树遍历的算法,对其计算属性VisitNode(S)首先,画出语法树S.a=0XYZxyz然后执行第一次遍历,如左图所示X.c不能计算VisitNode(X)X.d不能计算Y.e不能计算VisitNode(Y)Y.f不能计算Z.h:=0VisitNode(Z)Z.g:=1S.b不能计算:h=0g=1第一遍计算了Z..h和Z.g,下面进行第二遍遍历VisitNode(S)X.c:=1VisitNode(X)X.d:=2Y.e不能计算VisitNode(Y)Y.f不能计算Z.h:=0VisitNode(Z)Z.g:=1S.b不能计算:c=1d=2第二遍计算出了X.c和X.d,继续第三遍遍历VisitNode(S)X.c:=1VisitNode(X)X.d:=2Y.e:=0VisitNode(Y)Y.f:=0Z.h:=0VisitNode(Z)Z.g:=1S.b不能计算:e=0f=0经过三次遍历,完成了属性的计算假设S.a的初始值为0，输入串为xyz产生式语义规则S→XYZZ.h:=S.aX.c:=Z.gS.b:=X.d-2Y.e:=S.bX→xX.d:=2*X.cY→yY.f:=Y.e*3Z→zZ.g:=Z.h+1一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算。一遍扫描处理方法与下面两个因素密切相关所采用的语法分析方法属性的计算次序L-属性文法可用于一遍扫描的自上而下分析，S-属性文法适合于一遍扫描的自下而上分析③一遍扫描的处理方法在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树（AbstractSyntaxTree)。在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点。问表达式3*5+4的抽象语法树？④抽象语法树BS1S2if_then_elseS→ifBthenS1elseS23*5+4*54+3Digit.lexval=3F.val=3T.val=3Digit.lexval=5T.val=15*F.val=5E.val=15E.val=19T.val=4F.val=4Digit.vexval=4Ln+这是3*5+4的带注释语法树这是它的抽象语法树35*+4如何建立表达式的抽象语法树mknode(op,left,right)建立一个运算符号结点，标号是op，两个域left和right分别