天津大学编译原理讲义-Part6属性文法和语法制导翻译

属性文法和语法制导翻译授课：胡静属性文法目录虽然形式语义学的研究已经取得了许多重大进展，但目前在实际应用中比较流行的语义描述和语义处理的方法主要还是属性文法和语法制导翻译。本章研究内容：上下文无关文法所产生的语言的翻译。把属性附加到代表语法结构的文法符号上，可以将语义信息和程序设计语言的结构联系起来。属性的值是用与文法产生式相关联的“语义规则”来计算的。涉及的概念属性文法：关于语言翻译的高层次规格说明，隐蔽了具体实现细节，不显式的说明翻译发生的顺序(属性文法)语法制导翻译：指明了语义规则的计算顺序，说明实现细节。语义规则计算可完成的工作生成代码在符号表中保存信息发出错误信息对输入符号串翻译的过程就是对语义规则求值的过程属性文法是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的“值”。属性代表与文法符号相关的信息，如类型、值、代码序列、符号表内容属性可以代表任何对象：字符串，数组，类型，内存单元或其他对象语法制导定义=文法+符号的相关属性集属性分为两个子集：综合属性、继承属性如果把文法符号的结点看成记录，包含若干存储信息的域，那么属性就相当于域的名字属性文法分析树节点上属性值由产生式的语义规则来定义综合属性值：通过分析树中其子节点的属性值计算出来的继承属性值：由该节点的兄弟节点及父节点的属性值计算出来的依赖图语义规则建立了属性间的依赖关系，这种关系用图来表示就是依赖图依赖图表示了语义规则的计算顺序注释分析数每个节点都有属性值的分析树叫做注释分析树计算节点属性的过程称为注释或者装饰分析树属性文法在语法制导定义中，每个产生式A→α都有一个形如b=f(c1,c2,...,ck)的语义规则集合与之相关联，其中f是函数，并且满足下面条件之一b是A的一个综合属性，且c1,c2,...,ck是该产生式文法符号的属性b是产生式右部某个文法符号的一个继承属性，且c1,c2,...,ck是A或者产生式右边任何文法符号的属性在这两种情况下，我们说属性b依赖于c1,c2,...,ck。特别要强调的是：终结符只有综合属性，它们由词法分析器提供；非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。关于属性文法的说明通常，这种函数的被写为表达式。其他的语义规则被写为过程调用或者程序段——定义产生式左部非终结符的虚综合属性值一般说来，对于出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装”属性的依赖性。出现在产生式左边的继承属性和出现在产生式右部的综合属性不由所给产生式的属性计算规则进行计算，它们由其他产生式的属性规则计算或由属性计算器的参数提供。继承属性和综合属性的计算举例对于产生式A→BC来讲直观上来讲，这个产生式可以计算A的综合属性、B和C的继承属性。那么对于A的继承属性，可能需要根据某个类似于X→…A…的产生式求的。同样的B和C的综合属性可能需要根据某个类似于B→β，以及C→γ的产生式求的。属性文法举例产生式语义规则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.lexvalS-属性文法S-属性文法在语法树中，一个结点的综合属性的值由其子结点的属性值决定。仅使用综合属性的属性文法称为S-属性定义S属性定义的分析树的分析方法——自底向上的在每个节点用语义规则来计算综合属性值。综合属性举例LnE产生式语义规则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.lexval3*5+4ET+TF*TFFdigitdigitdigit.lexval=3.val=5.val=4.val=3.val=3.val=15.val=4.val=4.val=15.val=19.val=5继承属性在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。继承属性在程序设计语言中的作用表示程序设计语言上下文结构的依赖性对于赋值号，其左边和右边的标识符在操作的时候需要提供的属性不同，这时候就要跟踪标识符的继承属性。如果在赋值号左边，则需要地址，右边则需要值。虽然我们总是可以只用综合属性来改写语法制导定义，但是使用带有继承属性的属性文法有时更为自然。继承属性的例子DLT产生式语义规则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)realid1,id2,id3realid3,L.in=real.in=real.type=realid2,L.in=realid1语法制导翻译基于属性文法的处理过程通常是：对符号串进行语法分析，构造语法分析树根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。这种由源程序的语法结构驱动的处理办法就是语法制导翻译法。在某些情况下，在进行语法分析的同时完成语义规则的计算而无须明显地构造语法树或构造属性之间的依赖图。（一遍处理，L-属性文法）输入符号串分析树依赖图语义规格的计算顺序依赖图依赖图是有向图表示了分析树中各节点属性间的依赖关系。其中属性包括继承属性和综合属性表示了节点属性的计算先后顺序。如果分析树中某个节点的属性b依赖于属性c，那么在该节点处b的语义规则必须在c的语义规则之后计算。依赖图的构造方法为每个包括过程调用的语义规则引入一个虚综合属性b，把每条语义规则都变成b=f(c1,c2,...,ck)的形式依赖图的每个结点表示一个属性边表示属性间的依赖关系。如果属性b依赖于属性c，那么从c到b就有一条有向边依赖图举例DLTrealid3,L.in=real.in=real.type=realid2,L.in=realid1DLTrealid3,Lid2,Lid1typeinyinyinyentryentryentry12345678910如果一属性文法不存在属性之间的循环依赖关系，那么称该文法为良定义的产生式语义规则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)属性的计算顺序无环有向图的拓扑排序无环有向图中节点m1,m2,…,mk的拓扑排序是：若mi→mj是从mi到mj的边，那么在此排序中mi先于mj依赖图的任何拓扑排序都给出了一个分析树中各节点语义规则计算的正确顺序，即在计算f之前，语义规则b=f(c1,c2,...,ck)中的依赖属性c1,c2,...,ck都是已知的属性文法所说明的翻译可以按照下面的步骤进行最基本的文法用于构造输入串的分析树用前面的方法构造依赖图从依赖图的拓扑排序可以得到语义规则的计算顺序按该顺序计算语义规则即可得到输入串的翻译属性文法计算顺序举例a4:=reala5:=a4addtype(id3.entry,a5)a7:=a5addtype(id2.entry,a7)a9:=a7addtype(id1.entry,a9)DLTrealid3,Lid2,Lid1typeinyinyinyentryentryentry12345678910计算语义规则的方法分析树法：在编译时，这种方法从分析树所构成的依赖图的拓扑排序中得到语义规则的计算顺序。如果分析树的依赖图中有环路，这种方法将失败基于规则的方法对于每一个产生式，计算该产生式所关联的属性的顺序在编译器构造时已经预先确定好了忽略规则的方法选择计算顺序时不考虑语义规则。如果翻译是在语法分析过程中进行的，那么计算顺序的选择就由语法分析方法来确定。后两种方法在编译时都不必显式的构造依赖图树遍历的属性计算方法通过树遍历计算属性值的方法都假设语法树已经建立，并且数中已带有开始符号的继承属性和终结符的综合属性。最常用的遍历方法是深度优先，从左到右的遍历方法只要文法的属性是非循环定义的，则每次扫描至少有一个属性值被计算出来。如果语法树有n个结点（因此最多有O(n)个属性），最坏的情况整个遍历需要O(n2)时间。树遍历的举例产生式语义规则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+1S有继承属性a，综合属性bX有继承属性c，综合属性dY有继承属性e，综合属性fZ有继承属性h，综合属性g假设S.a的初始值为0SZYXxyza=0初始状态SZYXxyza=0第一遍扫描h=0g=1SZYXxyza=0第二遍扫描h=0g=1c=1d=2SZYXxyza=0第三遍扫描h=0g=1b=0e=0f=0c=1d=2一遍扫描的处理方法在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树。一遍扫描的处理方法与语法分析器密切相关的因素：所采用的语法分析方法属性的计算顺序L-属性文法可用于一遍扫描的自顶向下分析，而S-属性文法适合于一遍扫描的自底向上分析。此时的语法制导翻译可理解为：直观上说为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则在自顶向下语法分析中，若一个产生式匹配输入串成功在自底向上语法分析中，当一个产生式被用于进行归约时抽象语法树的构造用抽象语法树作为中间表示，可以把翻译从语法分析中分离出来语法树是分析树的压缩形式，去掉了那些对翻译不必要的信息，对表示语言的结构很有用。表达式的抽象语法树的构造为每个运算符和运算对象建立节点来为子表达式构造子树。运算符节点的字节点分别是表示该运算符各运算对象的子表达式组成的子树的根表达式语法树的构造方法运算符节点（用记录实现，也可以用对象实现）一个域标识运算符，其余域包含指向运算对象的指针将运算符称为该节点的标记构造的过程（方法）mknode(op,left,right)：建立一个标记为op的运算符节点，其中两个域left和right是指向其左右运算对象的指针mkleaf(id,entry)：建立标记为id的标识符节点，entry是指向该标识符在标识符表中的相应表项的指针mkleaf(num,value)：建立标记为num的数节点，域val保存该数的值。抽象语法树的例子产生式语义规则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)表达式的无环有向图表达式的无环有向图（dag）可以识别表达式中的公共子表达式无环有向图的组成叶子节点：表达式中的操作数（操作符的运算对象）内部节点：表达式中的操作符（运算符）子树：表达式中的每一个子表达式和抽象语法树的区别：代表公共子表达式的节点具有多个“父结点”在省城抽象语法树时，mknode和mkleaf之前先查看是否已经存在需要创建的节点，如果存在，则返回以创建的节点而不是新创建一个节点S属性文法的自底向上计算S-属性文法的特点S-属性文法，只有综合属性也就是说产生式左边的文法的综合属性要根据产生式右边符号的综合属性来进行计算。适用于那些需要类似于表达式，需