1、编译原理编译原理第1页属性文法和语法制导翻译属性文法和语法制导翻译介绍有关语义分析及翻译的问题。介绍有关语义分析及翻译的问题。语义描述和语义处理的方法主要是属性文法和语语义描述和语义处理的方法主要是属性文法和语法制导翻译方法。法制导翻译方法。本章中，将首先介绍属性文法的基本概念，然后本章中，将首先介绍属性文法的基本概念，然后介绍基于属性文法的处理方法，讨论如何在自上介绍基于属性文法的处理方法，讨论如何在自上而下分析和自下而上分析中实现属性的计算。而下分析和自下而上分析中实现属性的计算。编译原理编译原理第2页属性文法和语法制导翻译属性文法和语法制导翻译本章内容概要本章内容概要属性文法属性文法综合
2、属性综合属性继承属性继承属性基于属性文法的处理方法基于属性文法的处理方法依赖图依赖图属性的计算次序属性的计算次序树遍历的属性计算方法树遍历的属性计算方法一遍扫描的处理方法一遍扫描的处理方法抽象语法树抽象语法树S-S-属性文法的自下而上计算属性文法的自下而上计算分析栈中的综合属性分析栈中的综合属性编译原理编译原理第3页属性文法和语法制导翻译属性文法和语法制导翻译L L属性文法和自顶向下翻译属性文法和自顶向下翻译翻译模式翻译模式自顶向下翻译自顶向下翻译递归下降翻译器的设计递归下降翻译器的设计自下而上计算继承属性自下而上计算继承属性从翻译模式中去掉嵌入在产生式中间的动作从翻译模式中去掉嵌入在产生式中
3、间的动作分析栈中的继承属性分析栈中的继承属性模拟继承属性的计算模拟继承属性的计算用综合属性代替继承属性用综合属性代替继承属性编译原理编译原理第4页属性文法和语法制导翻译属性文法和语法制导翻译属性文法属性文法 属性翻译文法是在上下文无关文法的基础上，为每个属性翻译文法是在上下文无关文法的基础上，为每个文法符号（终结符或非终结符）配备若干相关的文法符号（终结符或非终结符）配备若干相关的“值值”（称为属性）。（称为属性）。这些属性代表与文法符号相关信息，例如它的类型、这些属性代表与文法符号相关信息，例如它的类型、值、代码序列、符号表内容等等。值、代码序列、符号表内容等等。属性与变量一样，可以进行计算
4、和传递。属性与变量一样，可以进行计算和传递。属性加工的过程即是语义处理的过程。对于文法的每属性加工的过程即是语义处理的过程。对于文法的每个产生式都配备了一组属性的计算规则，称为语义规个产生式都配备了一组属性的计算规则，称为语义规则。则。编译原理编译原理第5页属性文法和语法制导翻译属性文法和语法制导翻译属性通常分为两类：属性通常分为两类：综合属性和继承属性。综合属性和继承属性。综合属性用于综合属性用于“自下而上自下而上”传递信息，而继承属性用于传递信息，而继承属性用于“自上自上而下而下”传递信息。传递信息。在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A都有一套与之相都有一
5、套与之相关联的语义规则，每条规则的形式为关联的语义规则，每条规则的形式为 b:f(c1，c2，ck)这里，这里，f是一个函数，而且或者是一个函数，而且或者（1）b是是A的一个综合属性并且的一个综合属性并且c1，c2，ck 是产生式右边是产生式右边文法符号的属性；或者文法符号的属性；或者 (2)b是产生式右边某个文法符号的一个继承属性并且是产生式右边某个文法符号的一个继承属性并且c1，c2，ck 是是A或产生式右边任何文法符号的属性。或产生式右边任何文法符号的属性。在两种情况下，我们都说属性在两种情况下，我们都说属性b依赖于属性依赖于属性 c1，c2，ck 编译原理编译原理第6页属性文法和语法制
6、导翻译属性文法和语法制导翻译(1)终结符只有综合属性，它们由词法分析器提供；终结符只有综合属性，它们由词法分析器提供；(2）非终结符既可有综合属性也可有继承属性，文法开始符）非终结符既可有综合属性也可有继承属性，文法开始符号的所有继承属性作为属性计算前的初始值。号的所有继承属性作为属性计算前的初始值。对出现在产生式右边的继承属性和出现在产生式左边的综对出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。合属性都必须提供一个计算规则。属性计算规则中只能使用相应产生式中的文法符号的属性，属性计算规则中只能使用相应产生式中的文法符号的属性，这有助于在产生式范围内这有助于在产
7、生式范围内“封装封装”属性的依赖性。然而，属性的依赖性。然而，出现在产生式左边的继承属性和出现在产生式右边的综合出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则计算或者由属性计算器的参数提供。其它产生式的属性规则计算或者由属性计算器的参数提供。编译原理编译原理第7页属性文法和语法制导翻译属性文法和语法制导翻译语义规则所描述的工作可以包括属性计算、静态语义检查、语义规则所描述的工作可以包括属性计算、静态语义检查、符号表操作、代码生成等等。符号表操作、代码生成等等。编译原理编译
8、原理第8页属性文法和语法制导翻译属性文法和语法制导翻译例如，考虑非终结符例如，考虑非终结符A，B和和C，其中，其中，A有一个继承有一个继承属性属性a和一个综合属性和一个综合属性b，B有综合属性有综合属性c，C有继承属有继承属性性d。产生式。产生式ABC可能有规则可能有规则 C.d：=B.c1 A.b：=A.aB.c而属性而属性A.a和和B.c在其它地方计算。在其它地方计算。编译原理编译原理第9页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第10页属性文法和语法制导翻译属性文法和语法制导翻译综合属性综合属性在语法树中，一个结点的综合属性的值由其子结点的在语法树中，一个结点的综合属
9、性的值由其子结点的属性值确定。因此，通常使用自底向上的方法在每一属性值确定。因此，通常使用自底向上的方法在每一个结点处使用语义规则计算综合属性的值。仅仅使用个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称综合属性的属性文法称S-属性文法属性文法 编译原理编译原理第11页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第12页属性文法和语法制导翻译属性文法和语法制导翻译继承属性继承属性在语法树中，一个结点的继承属性由此结点的父结点在语法树中，一个结点的继承属性由此结点的父结点和或兄弟结点的某些属性确定。和或兄弟结点的某些属性确定。用继承属性来表示程序设计语言结构中的
10、上下文依赖用继承属性来表示程序设计语言结构中的上下文依赖关系很方便。在下面的例子中，继承属性在说明中为关系很方便。在下面的例子中，继承属性在说明中为各种标识符提供类型信息。各种标识符提供类型信息。编译原理编译原理第13页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第14页属性文法和语法制导翻译属性文法和语法制导翻译句子句子real id1，id2，id3的带注释的语法树。的带注释的语法树。编译原理编译原理第15页属性文法和语法制导翻译属性文法和语法制导翻译基于属性文法的处理方法基于属性文法的处理方法 基于属性文法的处理过程通常是基于属性文法的处理过程通常是:对单词符号串进行语法
11、分析，构造语法分析树，对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树并在语法树的各结点处然后根据需要遍历语法树并在语法树的各结点处按语义规则进行计算。按语义规则进行计算。这种由源程序的语法结构所驱动的处理办法就是这种由源程序的语法结构所驱动的处理办法就是语法制导翻译法。语法制导翻译法。语义规则的计算可能产生代码、在符号表中存放语义规则的计算可能产生代码、在符号表中存放信息、给出错误信息或执行任何其他动作。对输信息、给出错误信息或执行任何其他动作。对输入符号串的翻译也就是根据语义规则进行计算的入符号串的翻译也就是根据语义规则进行计算的结果。结果。输入串输入串 语法树语法树 依赖
12、图依赖图 语义计算次序语义计算次序编译原理编译原理第16页属性文法和语法制导翻译属性文法和语法制导翻译依赖图依赖图如果在一棵语法树中一个结点的属性如果在一棵语法树中一个结点的属性b依赖于属性依赖于属性c，那，那么这个结点处计算么这个结点处计算b的语义规则必须在确定的语义规则必须在确定c的语义规则的语义规则之后使用。之后使用。在一棵语法树中的结点的继承属性和综合属性之间的相在一棵语法树中的结点的继承属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描述。互依赖关系可以由称作依赖图的一个有向图来描述。编译原理编译原理第17页属性文法和语法制导翻译属性文法和语法制导翻译在为一棵语法树构造
13、依赖图以前，我们为每一个包含过在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规则引入一个虚综合属性程调用的语义规则引入一个虚综合属性b，这样把每一，这样把每一个语义规则都写成个语义规则都写成 b：f(c1，c2，ck)的形式。依赖图中为每一个属性设置一个结点，如果属的形式。依赖图中为每一个属性设置一个结点，如果属性性b依赖于属性依赖于属性c，则从属性，则从属性c的结点有一条有向边连到的结点有一条有向边连到属性属性b的结点。更详细地说，对于给定的一棵语法分析的结点。更详细地说，对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的：树、依赖图是按下面步骤构造出来的：编译原理编译原理
14、第18页属性文法和语法制导翻译属性文法和语法制导翻译 for 语法树中每一结点语法树中每一结点n do for 结点结点n的文法符号的每一个属性的文法符号的每一个属性a do 为为a在依赖图中建立一个结点；在依赖图中建立一个结点；for 语法树中每一个结点语法树中每一个结点n do for 结点结点n所用产生式对应的每一个语义规则所用产生式对应的每一个语义规则 b:f(c1，c2，ck)do for i:=1 to k do 从从ci结点到结点到b结点构造一条有向边；结点构造一条有向边；编译原理编译原理第19页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第20页属性文法和语法制
15、导翻译属性文法和语法制导翻译属性的计算次序属性的计算次序一个有向非循环图的拓扑序是图中结点的任何顺序一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,mk,使得边必须是从序列中前面的结点指向使得边必须是从序列中前面的结点指向后面的结点。后面的结点。如果如果mimjmj是是mi到到mj的一条边，那么在序列中的一条边，那么在序列中mi必必须出现在须出现在mj之前。之前。编译原理编译原理第21页属性文法和语法制导翻译属性文法和语法制导翻译一个依赖图的任何拓扑排序都给出一个语法树中结点的语一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规则计算的有效顺序。义规则计算的有效顺序。在拓扑排序中，
16、在一个结点上，语义规则在拓扑排序中，在一个结点上，语义规则 b:=f(c1，c2，ck）中的属性中的属性 cl，c2,ck 在计算在计算b以前都是可用的。以前都是可用的。属性文法说明的翻译是很精确的。基础文法用于建立输入属性文法说明的翻译是很精确的。基础文法用于建立输入符号串的语法分析树。依赖图如上面讨论的那样建立。从符号串的语法分析树。依赖图如上面讨论的那样建立。从依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。依赖图的拓扑排序中，我们可以得到计算语义规则的顺序。用这个顺序来计算语义规则就得到输入符号串的翻译。用这个顺序来计算语义规则就得到输入符号串的翻译。编译原理编译原理第22页属性文
17、法和语法制导翻译属性文法和语法制导翻译在上图的依赖图中，每一条边都是从序号较低的结点在上图的依赖图中，每一条边都是从序号较低的结点指向序号较高的结点。因此，指向序号较高的结点。因此，依赖图的一个拓扑排序可以从低序号到高序号顺序写出。从这个拓扑排序中从这个拓扑排序中我们可以得到下列程序，用我们可以得到下列程序，用an来代表依赖图中与序号来代表依赖图中与序号n的结点有关的属性的结点有关的属性.这些语法规则的计算将把这些语法规则的计算将把real类类型填入到每个标识符对应的符号表项中。型填入到每个标识符对应的符号表项中。a4:=real a5:=a4 addtype(id3.entry,a5)a7:
18、=a5 addtype(id2.entry,a7)a9:=a7 addtype(id1.entry,a9)编译原理编译原理第23页属性文法和语法制导翻译属性文法和语法制导翻译树遍历的属性计算方法树遍历的属性计算方法 假设语法树已经建立好了，并且树中已带有开始符号的继假设语法树已经建立好了，并且树中已带有开始符号的继承属性和终结符的综合属性。承属性和终结符的综合属性。然后以某种次序遍历语法树，直至计算出所有属性。最常然后以某种次序遍历语法树，直至计算出所有属性。最常用的遍历方法是深度优先，从左到右的遍历方法。如果需用的遍历方法是深度优先，从左到右的遍历方法。如果需要的话，可使用多次遍历（或称遍）
19、。要的话，可使用多次遍历（或称遍）。编译原理编译原理第24页属性文法和语法制导翻译属性文法和语法制导翻译下面算法可对任何无循环的属性文法进行计算下面算法可对任何无循环的属性文法进行计算 While 还有未被计算的属性还有未被计算的属性 do VisittNode(S)*S是开始符号是开始符号*procedure VisitNode（N:Node）；）；begin if N是一个非终结符是一个非终结符 then *假设它的产生式为假设它的产生式为NX1,X2,Xm *for i:=1 to m do if not XiVt then*即即Xi 是非终结符是非终结符 *begin 计算计算 Xi
20、的所有能够计算的继承属性；的所有能够计算的继承属性；VisitNode(X;)end；计算计算 N 的所有能够计算的综合属性的所有能够计算的综合属性 end编译原理编译原理第25页属性文法和语法制导翻译属性文法和语法制导翻译只要文法的属性是非循环定义的，则每一次扫描至少只要文法的属性是非循环定义的，则每一次扫描至少有一个属性值被计算出来。有一个属性值被计算出来。如果语法树有如果语法树有n个结点（因此最多有个结点（因此最多有O(n)个属性），个属性），最坏的情况整个遍历需最坏的情况整个遍历需O(n)时间。时间。编译原理编译原理第26页属性文法和语法制导翻译属性文法和语法制导翻译例：例：S有继承属
21、性有继承属性a，综合属性，综合属性b；X有继承属性有继承属性c,综合属性综合属性d；Y有继承属性有继承属性e、综合属性、综合属性f；z有继承属性有继承属性h、综合属性、综合属性g。编译原理编译原理第27页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第28页属性文法和语法制导翻译属性文法和语法制导翻译一遍扫描的处理方法一遍扫描的处理方法 一遍扫描的处理方法是在语法分析的同时计算属性值，而一遍扫描的处理方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进行属性的计算，而且无需不是语法分析构造语法树之后进行属性的计算，而且无需构造实际的语法树（如果有必须，当然也可以实际构
22、造）。构造实际的语法树（如果有必须，当然也可以实际构造）。编译原理编译原理第29页属性文法和语法制导翻译属性文法和语法制导翻译因为一遍扫描的处理方法与语法分析器的相互作用，它与因为一遍扫描的处理方法与语法分析器的相互作用，它与下面两个因素密切相关：下面两个因素密切相关：（1)所采用的语法分析方法；所采用的语法分析方法；(2)属性的计算次序。属性的计算次序。L-属性文法可用于一遍扫描的自上而下分析，而属性文法可用于一遍扫描的自上而下分析，而S-属性文属性文法适合于一遍扫描的自下而上分析。法适合于一遍扫描的自下而上分析。编译原理编译原理第30页属性文法和语法制导翻译属性文法和语法制导翻译如果按这种
23、一遍扫描的编译程序模型来理解语法制导翻译如果按这种一遍扫描的编译程序模型来理解语法制导翻译方法的话，方法的话，语法制导翻译就是为文法中每个产生式配上一组语义规则，语法制导翻译就是为文法中每个产生式配上一组语义规则，并且在语法分析的同时执行这些语义规则。并且在语法分析的同时执行这些语义规则。在自上而下语法分析中，若一个产生式匹配输入串成功，在自上而下语法分析中，若一个产生式匹配输入串成功，或者，在自下而上分析中，当一个产生式被用于进行归约或者，在自下而上分析中，当一个产生式被用于进行归约时，此产生式相应的语义规则就被计算，完成有关的语义时，此产生式相应的语义规则就被计算，完成有关的语义分析和代码
24、产生的工作。分析和代码产生的工作。在这种情况下，语法分析工作和语义规则的计算是穿插进在这种情况下，语法分析工作和语义规则的计算是穿插进行的。行的。编译原理编译原理第31页属性文法和语法制导翻译属性文法和语法制导翻译抽象语法树抽象语法树 通过语法分析可以很容易构造出语法分析树，然后对语通过语法分析可以很容易构造出语法分析树，然后对语法树进行遍历完成属性的计算。法树进行遍历完成属性的计算。因此，语法树可以作为一种合适的中间语言形式。因此，语法树可以作为一种合适的中间语言形式。在语法树中去掉那些对翻译不必要的信息，从而获得更在语法树中去掉那些对翻译不必要的信息，从而获得更有效的源程序中间表示。这种经
25、变换后的语法树称之为有效的源程序中间表示。这种经变换后的语法树称之为抽象语法树抽象语法树 编译原理编译原理第32页属性文法和语法制导翻译属性文法和语法制导翻译在抽象语法树中，操作符和关键字都不作为叶结点出现，而在抽象语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点。是把它们作为内部结点，即这些叶结点的父结点。如产生式如产生式S if B then S1 else S2 If_then_elseBS1S2编译原理编译原理第33页属性文法和语法制导翻译属性文法和语法制导翻译下面是表达式下面是表达式354的抽象语法树：的抽象语法树：+*435编译原理编译原理第
26、34页属性文法和语法制导翻译属性文法和语法制导翻译语法制导翻译既可以基于语法分析树，也可以基于抽象语语法制导翻译既可以基于语法分析树，也可以基于抽象语法树进行。法树进行。两种情况所采用的基本方法是一样的。像在语法分析树一两种情况所采用的基本方法是一样的。像在语法分析树一样，在抽象语法树的每个结点上都可带上一定的属性。样，在抽象语法树的每个结点上都可带上一定的属性。建立表达式的抽象语法树与把表达式翻译成后缀形式类似。建立表达式的抽象语法树与把表达式翻译成后缀形式类似。我们通过为每一个运算分量或运算符号都建立一个结点来我们通过为每一个运算分量或运算符号都建立一个结点来为子表达式建立子树。运算符号结
27、点的各子结点分别是表为子表达式建立子树。运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根。示该运算符号的各个运算分量的子表达式组成的子树的根。编译原理编译原理第35页属性文法和语法制导翻译属性文法和语法制导翻译抽象语法树中的每一个结点可以由包含几个域的记录来实抽象语法树中的每一个结点可以由包含几个域的记录来实现的。现的。在一个运算符号对应的结点中，一个域标识运算符号，其在一个运算符号对应的结点中，一个域标识运算符号，其它域包含指向运算分量的结点的指针。运算符号通常叫作它域包含指向运算分量的结点的指针。运算符号通常叫作这个结点的标号。这个结点的标号。当我们进行翻译
28、时，抽象语法树中的结点可能会用附加的当我们进行翻译时，抽象语法树中的结点可能会用附加的域来存放结点的属性值（或指向属性值的指针）。域来存放结点的属性值（或指向属性值的指针）。编译原理编译原理第36页属性文法和语法制导翻译属性文法和语法制导翻译 下面的一些函数来建立表示带有二目算符的表达式的抽象语法下面的一些函数来建立表示带有二目算符的表达式的抽象语法树中的结点。每一个函数都返回一个指向新建立结点的指针。树中的结点。每一个函数都返回一个指向新建立结点的指针。(1)mknode（op,left,right）建立一个运算符号结点，标号）建立一个运算符号结点，标号是是op，两个域，两个域left和和r
29、ight分别指向左子树和右子树。分别指向左子树和右子树。(2）mkleaf（id,entry）建立一个标识符结点，标号为）建立一个标识符结点，标号为id,一一个域个域entry指向标识符在符号表中的入口。指向标识符在符号表中的入口。（3)mkleaf（num，ral)建立一个数结点，标号为建立一个数结点，标号为num，一个，一个域域ral用于存放数的值。用于存放数的值。编译原理编译原理第37页属性文法和语法制导翻译属性文法和语法制导翻译下面一系列函数调用建立了表达式下面一系列函数调用建立了表达式a-4c的抽象语法树。在的抽象语法树。在这个序列中这个序列中P1,P2,，P5是指向结点的指针是指向
30、结点的指针entrya和和entryc分别是指向符号表中的标识符分别是指向符号表中的标识符a和和c的指针。的指针。（1）P1：mkleaf（id，entrya)；(2）P2：=mkleaf（num，4）；）；(3）P3：=mknode（-，Pt，P2）；）；(4)P4：mkleaf（id，entryc)；(5）P5：=mknode（，P3，P4）；）；编译原理编译原理第38页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第39页属性文法和语法制导翻译属性文法和语法制导翻译 S-S-属性文法的自下而上计算属性文法的自下而上计算 综合属性可以在分析输入符号串的同时由自下而上的分析综合
31、属性可以在分析输入符号串的同时由自下而上的分析器来计算。器来计算。分析器可以保存与栈中文法符号有关的综合属性值，每当分析器可以保存与栈中文法符号有关的综合属性值，每当进行归约时，新的属性值就由栈中正在归约的产生式右边进行归约时，新的属性值就由栈中正在归约的产生式右边符号的属性值来计算。符号的属性值来计算。S-属性文法的翻译器通常可借助于属性文法的翻译器通常可借助于LR分析器实现。在分析器实现。在S-属属性文法的基础上，性文法的基础上，LR分析器可以改造为一个翻译器，在对分析器可以改造为一个翻译器，在对输入串进行语法分析的同时对属性进行计算。输入串进行语法分析的同时对属性进行计算。编译原理编译原
32、理第40页属性文法和语法制导翻译属性文法和语法制导翻译分析栈中的综合属性分析栈中的综合属性 在自底向上的分析方法在自底向上的分析方法中，我们使用一个栈来中，我们使用一个栈来存放已经分析过的子树存放已经分析过的子树的信息。现在我们可以的信息。现在我们可以在分析栈中使用一个附在分析栈中使用一个附加的域来存放综合属性加的域来存放综合属性值值。编译原理编译原理第41页属性文法和语法制导翻译属性文法和语法制导翻译设当前的栈顶由指针设当前的栈顶由指针top指示。我们假设综合属性是刚好在指示。我们假设综合属性是刚好在每次归约前计算的。每次归约前计算的。假设语义规则假设语义规则A.a:f(X.x,Y.y,Z.
33、z)是对应于产生式是对应于产生式AXYZ的。的。在把在把XYZ归约成归约成A以前，属性以前，属性Z z的值放在的值放在valtop中，中，Yy的值放在的值放在valtop-1中，中，X.x的值放在的值放在valtop-2中。如中。如果一个符号没有综合属性，那么数组果一个符号没有综合属性，那么数组val中相应的元素就不定中相应的元素就不定义。义。归约以后，归约以后，top值减值减2，A的状态存放在的状态存放在statetop中（也就是中（也就是X的位置），综合属性的位置），综合属性A.a的值存放在的值存放在valtop中。中。编译原理编译原理第42页属性文法和语法制导翻译属性文法和语法制导翻译编
34、译原理编译原理第43页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第44页属性文法和语法制导翻译属性文法和语法制导翻译在上面描述的实现中，代码段刚好在归约以前执行。归约在上面描述的实现中，代码段刚好在归约以前执行。归约提供了一个提供了一个“挂钩挂钩”，使得代码段中的动作能够与之相联。，使得代码段中的动作能够与之相联。可以允许用户把一个语义动作与一个产生式联系起来，这可以允许用户把一个语义动作与一个产生式联系起来，这个动作是当利用该产生式进行归约时要被执行的。个动作是当利用该产生式进行归约时要被执行的。编译原理编译原理第45页属性文法和语法制导翻译属性文法和语法制导翻译 L-L-
35、属性文法和自顶向下翻译属性文法和自顶向下翻译 在在6.2节中我们知道，可以通过深度优先的方法对语法树节中我们知道，可以通过深度优先的方法对语法树进行遍历，从而计算属性文法的所有属性值。在本节中我进行遍历，从而计算属性文法的所有属性值。在本节中我们讨论一类属性文法，叫做们讨论一类属性文法，叫做L-属性文法，这类属性文法允属性文法，这类属性文法允许我们通过一次遍历就计算出所有属性值。诸如许我们通过一次遍历就计算出所有属性值。诸如LL(1)这这种自上而下分析方法的分析过程，从概念上说可以看成是种自上而下分析方法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下深度优先
36、建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现语法分析的同时实现L属性文法的计算。属性文法的计算。编译原理编译原理第46页属性文法和语法制导翻译属性文法和语法制导翻译一个属性文法称为一个属性文法称为L-属性文法如果对于每个产生式属性文法如果对于每个产生式AX1X2Xn,其每个语义规则中的每个属性或者是综合属其每个语义规则中的每个属性或者是综合属性，或者是性，或者是Xj(1=j=n)的一个继承属性且这个继承属性仅的一个继承属性且这个继承属性仅依赖于：依赖于：(1）产生式）产生式Xi的左边符号的左边符号X1，X2，Xi-l的属性；的属性；(2)A的继承属性。的继承属性。可见，可见，S
37、-属性文法一定是属性文法一定是L-属性文法，因为（属性文法，因为（1),(2)限制只用限制只用于继承属性。于继承属性。编译原理编译原理第47页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第48页属性文法和语法制导翻译属性文法和语法制导翻译翻译摸式翻译摸式 属性文法可以看作是关于语言翻译的高级规范说明，其属性文法可以看作是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。解脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形式，下面我们讨论一种适合语法制导翻译的另一种描述形式，称为翻译模式（称
38、为翻译模式（Translation schemes）。）。翻译模式给出了使用语义规则进行计算的次序，这样就翻译模式给出了使用语义规则进行计算的次序，这样就可把某些实现细节表示出来。可把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称语义动作），用花括号括起来，插入到里我们也称语义动作），用花括号括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语产生式右部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。义规则进行计算的顺序。编译原理编译原理第49页属性文法和语法制导翻译属性文法和语法制导翻译下
39、面是一个简单的翻译模式例子，它把带加号和减号的中缀表达式翻译成相应的后缀表达式E TRR addop T print(addop.lexeme)R1|T num print(num.val)编译原理编译原理第50页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第51页属性文法和语法制导翻译属性文法和语法制导翻译例中每个语义动作都作为相应产生式左部符号的结点的儿子。例中每个语义动作都作为相应产生式左部符号的结点的儿子。这样，把语义动作看作是终结符号，表示在什么时候应该执这样，把语义动作看作是终结符号，表示在什么时候应该执行哪些动作。行哪些动作。为了便于说明，图中用实际的数字和加法运
40、算符代替了单词为了便于说明，图中用实际的数字和加法运算符代替了单词num和和addop。当按深度优先次序执行图中的动作后，打印。当按深度优先次序执行图中的动作后，打印输出输出95-2。编译原理编译原理第52页属性文法和语法制导翻译属性文法和语法制导翻译设计翻译模式时，必须注意某些限制以保证当某个动作引用设计翻译模式时，必须注意某些限制以保证当某个动作引用一个属性时它必须是有定义的。一个属性时它必须是有定义的。L-属性文法本身就能确保每个动作不会引用尚未计算出来的属性文法本身就能确保每个动作不会引用尚未计算出来的属性。属性。当只需要综合属性时，情况最为简单。在这种情况下，可以当只需要综合属性时，
41、情况最为简单。在这种情况下，可以这样来建立翻译模式：为每一个语义规则建立一个包含赋值这样来建立翻译模式：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。的动作，并把这个动作放在相应的产生式右边的末尾。编译原理编译原理第53页属性文法和语法制导翻译属性文法和语法制导翻译例如，假设有下面的产生式和语义规则：例如，假设有下面的产生式和语义规则：产生式产生式 语义规则语义规则T T1*F T.val：=T1val*F.val建立产生式和语义动作：建立产生式和语义动作：T T1*F T.val：T1.val*F.val编译原理编译原理第54页属性文法和语法制导翻译属性文法
42、和语法制导翻译如果既有综合属性又有继承属性，在建立翻译模式时就必须如果既有综合属性又有继承属性，在建立翻译模式时就必须特别小心特别小心(1)产生式右边的符号的继承属性必须在这个符号以前的动产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。作中计算出来。(2)一个动作不能引用这个动作右边的符号的综合属性。一个动作不能引用这个动作右边的符号的综合属性。(3）产生式左边非终结符的综合属性只有在它所引用的所有）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。放在产生
43、式右端的末尾。编译原理编译原理第55页属性文法和语法制导翻译属性文法和语法制导翻译下面的翻译模式不满足上述三个条件中的第一个条件：下面的翻译模式不满足上述三个条件中的第一个条件：SA1 A2 A1.in:1;A2in:=2 Aa print(A.in)可以看出，按深度优先遍历输入串可以看出，按深度优先遍历输入串aa的语法树，当要打印第的语法树，当要打印第二个产生式里继承属性二个产生式里继承属性A.in时的值时，该属性还没有定义。时的值时，该属性还没有定义。也就是说，从也就是说，从s开始按深度优先遍历开始按深度优先遍历A1和和A2子树之前，子树之前，A1.in和和A2in还未赋值。还未赋值。如果
44、计算如果计算A1in和和A2 in的值的动作分别被嵌入在产生式的值的动作分别被嵌入在产生式SA1A2的右部的右部A1和和A2之前而不是后面，那么之前而不是后面，那么A.in在每次在每次执行执行Print(A in)时已有定义。时已有定义。编译原理编译原理第56页属性文法和语法制导翻译属性文法和语法制导翻译自顶向下翻译自顶向下翻译讨论讨论L-属性文法在自顶向下分析中的实现。为了便于说明动属性文法在自顶向下分析中的实现。为了便于说明动作的顺序和属性计算的顺序，我们用翻译模式进行描述。作的顺序和属性计算的顺序，我们用翻译模式进行描述。在第四章我们知道，为了构造不带回溯的自顶向下语法分析，在第四章我们
45、知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左递归。必须消除文法中的左递归。现在我们把前面讨论过的消除左递归的算法加以扩充，当消现在我们把前面讨论过的消除左递归的算法加以扩充，当消除一个翻译模式的基本文法的左递归时同时考虑属性。这种除一个翻译模式的基本文法的左递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样，许多属性文法可以方法适合带综合属性的翻译模式。这样，许多属性文法可以使用自顶向下分析来实现。使用自顶向下分析来实现。编译原理编译原理第57页属性文法和语法制导翻译属性文法和语法制导翻译由于大多数算术运算符号都是左递归的，因此，我们很自由于大多数算术运算符号都是左递归
46、的，因此，我们很自然地用左递归文法来产生算术表达式。关于算术表达式的然地用左递归文法来产生算术表达式。关于算术表达式的左递归文法相应的翻译模式形式如图所示。左递归文法相应的翻译模式形式如图所示。编译原理编译原理第58页属性文法和语法制导翻译属性文法和语法制导翻译消除左递归，构造新的翻译模式如图消除左递归，构造新的翻译模式如图6.14所示。新的翻译所示。新的翻译模式产生的表达式模式产生的表达式9-5十十2的带注释的语法树如图的带注释的语法树如图6.15所示。所示。图中箭头指明了对表达式计算的顺序。图中箭头指明了对表达式计算的顺序。编译原理编译原理第59页属性文法和语法制导翻译属性文法和语法制导翻
47、译编译原理编译原理第60页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第61页属性文法和语法制导翻译属性文法和语法制导翻译下面我们把转换左递归翻译模式的方法推广到一般，以便下面我们把转换左递归翻译模式的方法推广到一般，以便进行自顶向下分析。进行自顶向下分析。假设我们有下面的翻译模式，它的每个文法符号都有一个假设我们有下面的翻译模式，它的每个文法符号都有一个综合属性，用小写字母表示，综合属性，用小写字母表示，g和和f是任意函数。是任意函数。A A1Y A.a=g(A1.a,Y.y)A X X A.aA.a=f(X.xf(X.x)编译原理编译原理第62页属性文法和语法制导翻译属性文
48、法和语法制导翻译利用第四章消除左递归的算法，可将其转换成下面的文法A XRR YR|再考虑语义动作，翻译模式变为A X R.i:=f(X.x)R A.a:=R.sR Y R1.i:=g(R.i,Y.y)R1 R.s:=R1.sR R.s:=R.i编译原理编译原理第63页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第64页属性文法和语法制导翻译属性文法和语法制导翻译例例611如果把构造抽象语法树的属性文法定义（见表如果把构造抽象语法树的属性文法定义（见表64)转化成翻译模式，那么关于转化成翻译模式，那么关于E的产生式和语义动作就变为：的产生式和语义动作就变为：E E1+T E.nptr:=mknode(+,E1.nptr,T.nptr)E E1-T E.nptr:=mknode(-,E1.nptr,T.nptr)E T E.nptr:=T.nptr编译原理编译原理第65页属性文法和语法制导翻译属性文法和语法制导翻译编译原理编译原理第66页属性文法和语法制导翻译属性文法和语法制导翻译
