属性文法和语法制导翻译1.ppt

第六章 属性文法和语法制导翻译,第六章 属性文法和语法制导翻译,从本章开始，我们介绍有关语义分析及翻译的问题。其处理的方法主要是属性文法和语法制导翻译方法。 本章中，我们将首先介绍属性文法的基本概念，然后介绍基于属性文法的处理方法，讨论如何自上而下分析和自下而上分析中实现属性计算。 本章重点掌握: 6.1 属性文法 6.2 基于属性文法的处理方法 6.3 S属性文法的自下而上计算 6.4 L属性文法和自顶向下翻译。,第六章 属性文法和语法制导翻译,6.1 属性文法 属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的“值”（称为属性）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列、符号表内容等等。属性和变量一样，可以进行计算和传递。 属性一般分为两类：综合属性和继承属性。简单的说，综合属性用于“自下而上”传递信息，而继承属性用于“自上而下”传递信息。 属性加工加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，则称为语义规则。 在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规则，每条语义规则的形式为：,第六章 属性文法和语法制导翻译,b:=f(c1,c2,ck) 这里f是一个函数，而且或者 （1）b是A的一个综合属性并且c1,c2,ck是产生式右边文法符号的属性；或者 （2）b是产生式右边某个文法符号的一个继承属性并且c1,c2,ck是A或产生式右边任何文法符号的属性 在这两种情况下，我们都说属性b依赖于属性c1,c2,ck. 要特别强掉的是： （1）终结符只有综合属性，它由词法分析器提供； （2）非终结符既可以有综合属性也可以有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。 一般来讲，对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内“封装”属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算,由属性计算器的参数提供,第六章 属性文法和语法制导翻译,语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等。语义规则可能产生副作用（如产生代码），也可能不是变元的严格函数（如某个规则给出可用的下一个数据单元的地址）。这样的语义规则通常写成过程调用，或过程段。 综合属性： 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称S属性文法。 继承属性： 在语法树中，一个结点的继承属性由此结点的父结点和/或兄弟结点的某些属性确定。用继承属性来表示程序语言结构中的上下文依赖关系很方便。,第六章 属性文法和语法制导翻译,6.2 基于属性文法的处理方法 从概念上讲，基于属性文法的处理过程通常是这样的：对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。 输入串语法树依赖图语义规则计算次序 这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其它动作。对输入串的翻译也就是根据语义规则进行计算得出结果。 6.2.1依赖图 如果在一棵语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的属性规则必须在确定c的语义规则之后使用。在一颗语法树中的结点的继承属性和综合属性之间的相互依赖关系可以用称作依赖图的一个有向图来描述。 在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性b，这样把每一个语义规则都写成 b:= f(c1,c2, ck) 的形式。依赖图中为每一个属性设置一个结点，如果属性b依赖属性c，则从属性c的结点有一条有向边连到属性b的结点。,第六章 属性文法和语法制导翻译,这里要掌握依赖图的画法。 例如，属性 A.a:=f( X.x, Y.y ) 对应于产生式 AXY的语义规则,这条语义规则确定了依赖于属性X.x和Y.y的综合属性A.a。 如果在语法树中应用这个产生式，那么在依赖图中会有三个结点A.a,X.x,和Y.y。由于A.a依赖X.x，所以有一条有向边从X.x到A.a.由于A.a也依赖于Y.y，所以还有一条有向边从Y.y连到A.a. 如果与产生式AXY对应的语义规则还有： X.i:=g(A.a,Y.y) 那么，图中还应有两条有向边，一条从A.a连到X.i，另一条从Y.y连到X.i ,因为X.i依赖于A.a和Y.y.,第六章 属性文法和语法制导翻译,例6.3当下面的产生式应用于语法树时，我们就像图6.4所示的那样把有向边加到依赖图中。 产生式 语义规则 EE1+E2 E.val:=E1.val+E2.val 例6.4下页的图是书中图6.2 （P139）带注释语法树的依赖图。依赖图中的结点由数字来标识，这些数字将在讨论属性的计算次序时用到。从代表T.type的结点4有一条边连到代表L.in的结点5，因为根据产生式DTL的语义规则L1.in=L.in,可知L1.in依赖于L.in,第六章 属性文法和语法制导翻译,所以有两条向下的边分别进入结点7 和9。每一个于L产生式有关的语义规则addtype(id.entry,L.in)都产生一个虚属性，结点6、8和10都为这些虚属性构造的。 如果一属性文法不存在属性之间的循环依赖关系，那么该文法为良定义的。为了设计编译程序，我们只处理良定义的属性文法。,第六章 属性文法和语法制导翻译,属性的计算次序 一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2, mk,使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果mimj是mi到mj的一条边，那么在序列中mi必须出现在mj之前。 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。这就是说，在拓扑排序中，在一个结点上，语义规则b:=f（c1,c2,ck)中的属性c1,c2ck在计算b以前都是可用的。 6.2.2树遍历的属性计算方法 通过树遍历计算属性值得方法很多种。这些方法都假设语法树已经建立起了，并且树中已带有开始符号的继承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有的属性。最常用的遍历方法是深度优先，从左到右的遍历方法。,第六章 属性文法和语法制导翻译,6.2.3一遍扫描的处理方法 与树遍历的属性计算方法不同，一遍扫描的方法是在语法分析的同时计算属性值。 如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话，所谓语法制导翻译法，直观上说是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则.在自上而下的语义分析中,若一个产生式匹配输入串成功,或者在自下而上分析中,当一个产生式被用于进行归约时,此产生式相应的语义规则就被计算,完成有关语义分析和代码生成的工作. 6.2.4 抽象语法树 建立表达式的抽象语法树,我们通过为每个运算分量或运算符号都建立一个结点来为子表达式建立子树. 运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根.,第六章 属性文法和语法制导翻译,抽象语法树中的每一个结点可以由包含几个域的记录来实现的. 在一个运算符号对应的结点中,一个域标识运算符号，其它域包含指向运算分量的结点的指针。运算符号通常叫做这个结点的标号。当我们进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的属性值(或指向属性的指针）。 6.3 S属性文法的自下而上计算 这一节我们考虑这样一类属性文法：S属性文法，它只含有综合属性。 下面我们讨论分析栈中的综合属性。 在自底向上的分析法中。我们使用一个栈来存放已经分析过的子树的信息。现在我们可以在分析栈中使用一个附域来存放综合属性值。图6.9表示的是一个带有一个属性值空间的分析栈的例子。,State val X X.x Y Y.y Z Z.z 图6.9,top,第六章 属性文法和语法制导翻译,我们假设图中的栈是由一对数组state和val来实现的。每一个state元素都是一个指向LR(1)分析表的指针（或索引）。（注意，文法符号隐含在state中而不需要存储在栈中）。然而，如果像第五章中的那样把文法符号存入栈中时，那么当第i个state对应的符号为A时，vali中就存放语法树中与结点A对应的属性值。 设当栈顶由指针top指示。我们假设综合属性是刚好在每次归约前计算的。假设语义规则A.a:=f(X.x,Y.y,Z.z)是对应于产生式AXYZ的。在把XYZ归约成A以前，属性Z.z的值放在valtop中，Y.y的值放在valtop-1中，X.x的值放在valtop-2中。如果一个符号没有综合属性，那么数组val中相应的元素就不定义。归约后，top值减2，A的状态存放在statetop中（也就是X的位置）综合属性A.a的值存放在valtop中。,第六章 属性文法和语法制导翻译,6.4 L属性文法和自顶向下翻译 一个属性文法称为L属性文法：如果对于每个产生式AX1X2Xn其每个语义规则中的每个属性或者是综合属性，或者是Xj(1=j=n)的一个继承属性且这个继承属性仅依赖于： （1）产生式Xj的左边符号X1,X2,Xj-1的属性 （2）A的继承属性。 6.4.1 翻译模式 属性文法可以看成是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形式，称为翻译模式。翻译模式给出了使用语义规则进行计算的次序，这样就可以把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号 括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。,第六章 属性文法和语法制导翻译,如果既有综合属性又有继承属性，在建立翻译模式时就必须特别小心： （1）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。 （2）一个动作不能引用这个动作右边符号的综合属性。 （3）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。 6.4.2 自顶向下翻译 在第四章我们知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。现在我们把前面消除左递归的方法加以扩充,当消除一个翻译模式的基本语法的左递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样许多文法可以使用自顶向下分析来实现。,第六章 属性文法和语法制导翻译,对于自顶向下的分析，我们假设动作是在处于相同位置上的符号被展开（匹配成功）时执行的。一个符号的继承属性必须由出现这个符号之前的动作来计算，产生式左边非终结符的综合属性必须在它的所依赖的所有属性都计算出来之后才能被计算。 下面我们把转换左递规翻译模式的方法推广到一般，以便进行自顶向下分析： 假设我们有下面的翻译模式： AA1Y A.a:=g(A1.a,Y.y) AX A.a:=f(X.x) 其每个文法符号都有一个综合属性，用小写字母表示，g和f是任意函数。 利用第四章消除左递归的算法，可将其转换成下面文法： AXR R YR|,第六章 属性文法和语法制导翻译,再考虑语义动作，翻译模式变为： 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. 6.4.3 递归下降翻译器的设计 6.5 自下而上计算继承属性,第六章 属性文法和语法制导翻译,例题与习题解答,例6.1 某程序设计语言说明部分的语法制导定义如下： DTL Tint Treal LL1, id Lid 给出语法制导定义及自底向上的翻译模式，并比较两者的不同。 解：语法制导定义为： DTL L.in := T.type Tint T.type := integer Treal T.type := real LL1, id L1.in := L.in, addtype(id.entry , L.in ) Lid addtype (id.entry, L.in) ,第六章 属性文法和语法制导翻译,自底向上分析的翻译模式为： DT L.in := T.type L Tint T.type := integer Treal T.type := real L L1.in := L.in L1, id addtype(id.entry , L.in ) Lid addtype (id.entry, L.in) 从上述定义看两者的区别仅在于在翻译模式中把语义动作插入在规则右部的任意位置。而语法制导中把语义动作都放在产生式的最后。 例6.2 在一个移入归约的分析中采用以下的语法制导的翻译模式，在某产生式归约时，立即执行括号中的动作。 AaB print “0” Ac