第6讲--属性文法

1、1第第六六讲讲 属性文法和属性文法和语法制导翻译语法制导翻译u属性文法属性文法u基于属性文法的处理基于属性文法的处理u属性的计算属性的计算uS S属性文法的自下而上计算属性文法的自下而上计算uL L属性文法的自上而下计算属性文法的自上而下计算21. 1. 属性文法属性文法 属性文法是在上下文无关文法的基础上为每个文属性文法是在上下文无关文法的基础上为每个文法符号（终结符或非终结符）配备若干个相关的法符号（终结符或非终结符）配备若干个相关的“值值”（称为（称为属性属性）。这些属性代表与文法符号相）。这些属性代表与文法符号相关的信息，例如它的类型、值、代码序列关的信息，例如它的类型、值、代码序列

2、、符号表、符号表内容等等。属性和变量一样，可以进行计算和传递。内容等等。属性和变量一样，可以进行计算和传递。 属性一般分为两类：属性一般分为两类：综合属性：综合属性：用于用于“自下而上自下而上”传递信息，传递信息，继承属性：继承属性：用于用于“自上而下自上而下”传递信息。传递信息。 属性加工的过程即是语义处理的过程，对于文属性加工的过程即是语义处理的过程，对于文法的每一个产生式都配备了一组属性的计算规则，法的每一个产生式都配备了一组属性的计算规则，称为语义规则。称为语义规则。3属性的类型 综合属性综合属性： 在语法树中，一个结点的综合属性的值由其子在语法树中，一个结点的综合属性的值由其子结点的

3、属性值确定。通常使用结点的属性值确定。通常使用自底向上自底向上的方法在每的方法在每一个结点处使用语义规则计算综合属性的值。仅仅一个结点处使用语义规则计算综合属性的值。仅仅使用综合属性的属性文法称使用综合属性的属性文法称S-S-属性文法。属性文法。 继承属性继承属性： 在语法树中，一个结点的继承属性由此结点的在语法树中，一个结点的继承属性由此结点的父结点父结点和和/ /或或兄弟结点的某些属性确定。可用继承兄弟结点的某些属性确定。可用继承属性来表示程序语言结构中的上下文依赖关系。属性来表示程序语言结构中的上下文依赖关系。4 注意：注意：（1 1）终结符只有综合属性，由词法分析器提供；）终结符只有综

4、合属性，由词法分析器提供；（2 2）非终结符既可以有综合属性也可以有继承属性。）非终结符既可以有综合属性也可以有继承属性。文法开始符号的所有继承属性作为属性计算前的初文法开始符号的所有继承属性作为属性计算前的初始值。始值。出现在产生式右边的继承属性和出现在产生式出现在产生式右边的继承属性和出现在产生式左边的综合属性都必须提供一个计算规则。一左边的综合属性都必须提供一个计算规则。一般地，属性计算规则中只能使用相应产生式的般地，属性计算规则中只能使用相应产生式的文法符号的属性，这有利于产生式范围内文法符号的属性，这有利于产生式范围内“封封装装”属性的依赖性。属性的依赖性。出现在产生式左边的继承属性

5、和出现在产生式出现在产生式左边的继承属性和出现在产生式右边的综合属性不由所给的产生式的属性计算右边的综合属性不由所给的产生式的属性计算规则进行计算，它们由其它产生式的属性规则规则进行计算，它们由其它产生式的属性规则计算或由属性计算器的参数提供。计算或由属性计算器的参数提供。5 在一个属性文法中，对应于每个产生式在一个属性文法中，对应于每个产生式A A都有一套与之相关联的都有一套与之相关联的语义规则语义规则，每条语义规，每条语义规则的形式为：则的形式为： b:=f(c b:=f(c1 1,c,c2 2,c,ck k) ) 其中其中f f是一个函数，并是一个函数，并且满足下面两种情况之一：且满足下

6、面两种情况之一： （1 1）b b是是A A的一个综合属性并且的一个综合属性并且c c1 1,c,c2 2,c,ck k是是产生式右边文法符号的属性；产生式右边文法符号的属性； （2 2）b b是产生式右边某个文法符号的一个继是产生式右边某个文法符号的一个继承属性并且承属性并且c c1 1,c,c2 2,c,ck k是是A A或产生式右边任何文或产生式右边任何文法符号的属性。法符号的属性。 对这两种情况都称为属性对这两种情况都称为属性b b依赖于依赖于属性属性c c1 1,c,c2 2, , , c ck k。6语义规则语义规则 描述属性计算、静态语义检查、符号表描述属性计算、静态语义检查、符

7、号表操作、代码生成等。语义规则可能产生操作、代码生成等。语义规则可能产生副作副作用用（如产生代码），也可能不是变元的严格（如产生代码），也可能不是变元的严格函数（即函数中还有其它没有列出的自变量函数（即函数中还有其它没有列出的自变量如变量地址等），比如说某个规则可能给出如变量地址等），比如说某个规则可能给出可用的下一个数据单元的地址。这样的语义可用的下一个数据单元的地址。这样的语义规则通常写成过程调用或过程段。规则通常写成过程调用或过程段。7 下表是一个台式计算器程序的属性文法。该计算器读入下表是一个台式计算器程序的属性文法。该计算器读入一个算术表达式，计算并打印它的值，每个输入行以一个算术表

8、达式，计算并打印它的值，每个输入行以n n作为结作为结束。束。 在这些语义规则中，一个整数综合属性在这些语义规则中，一个整数综合属性valval把每个非终结把每个非终结符符E,T,FE,T,F联系起来。记号联系起来。记号digitdigit具有综合属性具有综合属性lexvallexval，其值由，其值由词法分析器提供。词法分析器提供。8LnE.val=19E.val=15T.val=4T.val=15F.val=4T.val=3F.val=5digit.lexval=4F.val=3digit.lexval=5digit.lexval=3+*句子句子3 3* *5+45+4n n的带注释的语法

9、树的带注释的语法树这是个带综合属性文法的例子，下面再来看一这是个带综合属性文法的例子，下面再来看一个继承属性的例子。个继承属性的例子。9变量声明语句中，通过继承属性把类型信息传变量声明语句中，通过继承属性把类型信息传递给每个标识符。递给每个标识符。问题：给出句子问题：给出句子real a,b,c 的带注释的语法树的带注释的语法树？10112. 2. 基于属性文法的处理方法基于属性文法的处理方法 对单词符号串进行语法分析，构造语法分析树，对单词符号串进行语法分析，构造语法分析树，然后根据需要遍历语法树，并在语法树的各结点处然后根据需要遍历语法树，并在语法树的各结点处按语义规则进行计算。按语义规则

10、进行计算。 输入串输入串语法树语法树依赖图依赖图按按次序计算语义规则次序计算语义规则 这种由源程序的语法结构所驱动的处理办法就这种由源程序的语法结构所驱动的处理办法就是是语法制导翻译语法制导翻译。 语义规则的计算可能语义规则的计算可能产生代码产生代码、在、在符号表符号表中存中存放信息、给出放信息、给出错误信息错误信息或执行任何或执行任何其它动作其它动作。对输入串的翻译对输入串的翻译=根据语义规则进行计算得出结果根据语义规则进行计算得出结果12依赖图依赖图 语法树中结点属性之间的相互依赖关系用语法树中结点属性之间的相互依赖关系用依赖图依赖图描述描述 为每一个包含过程调用的语义规则引入一为每一个包

11、含过程调用的语义规则引入一个个虚综合属性虚综合属性b b，这样把每一个语义规则都写，这样把每一个语义规则都写成成 b:= f(c b:= f(c1 1,c,c2 2, c, ck k) ) 的形式。的形式。 依赖图是一个有向图，为每一个属性设置依赖图是一个有向图，为每一个属性设置一个结点：如果属性一个结点：如果属性b b依赖属性依赖属性c c，则从属性，则从属性c c的结点有一条有向边连到属性的结点有一条有向边连到属性b b的结点。的结点。13依赖图依赖图的画法的画法 例：属性例：属性 A.a:=f( X.x, Y.y )A.a:=f( X.x, Y.y ) 对应于产生式对应于产生式 A AX

12、Y XY 的语义规则。的语义规则。 在依赖图中有三个相关结点：在依赖图中有三个相关结点： A.a,X.x,Y.yA.a,X.x,Y.y。 由于由于A.aA.a依赖于依赖于X.xX.x， Y.yY.y，所以，所以有两条有向边从有两条有向边从X.xX.x到到A.aA.a，从，从Y.yY.y连到连到A.a.A.a. 如果与产生式如果与产生式A AXYXY对应的语义规对应的语义规则还有：则还有： X.i:=g(A.a,Y.y)X.i:=g(A.a,Y.y) 图中再增加两条有向边：从图中再增加两条有向边：从A.aA.a连到连到X.iX.i，从，从Y.yY.y连到连到X.i,X.i,因为因为X.iX.i依

13、赖于依赖于A.aA.a和和Y.y.Y.y.14例依赖图当下面的产生式应用于语法树时，我们就像下当下面的产生式应用于语法树时，我们就像下图所示的那样把有向边加到依赖图中。图所示的那样把有向边加到依赖图中。 产生式产生式 语义规则语义规则 EE1+E2 E.val:=E1.val+E2.val15所以有两条向所以有两条向下的边分别进入结点下的边分别进入结点7 7 和和9 9。每一个与每一个与L L产生式有关的语义规则产生式有关的语义规则addtype(id.entry,L.in)addtype(id.entry,L.in)都都产生一个虚属性，结点产生一个虚属性，结点6 6、8 8和和1010都是为

14、这些虚属性构造的。都是为这些虚属性构造的。16良定义文法和属性的计算次序良定义文法和属性的计算次序 定义：属性之间定义：属性之间不存在循环依赖关系不存在循环依赖关系的属性文法。的属性文法。 一个有向非循环图的一个有向非循环图的拓扑序拓扑序是图中结点的任何顺是图中结点的任何顺序序m1,m2, mk,使得边必须是从序列中前面的结点使得边必须是从序列中前面的结点指向后面的结点。也就是说，如果指向后面的结点。也就是说，如果mimj是是mi到到mj的一条边，那么在序列中的一条边，那么在序列中mi必须出现在必须出现在mj之前。之前。 一个依赖图的任何拓扑排序都给出一个语法树中一个依赖图的任何拓扑排序都给出

15、一个语法树中结点的语义规则计算的有效顺序。结点的语义规则计算的有效顺序。 属性文法说明的翻译是很精确的：基础文法用于属性文法说明的翻译是很精确的：基础文法用于构造输入符号串的语法分析树，在此基础之上可以构造输入符号串的语法分析树，在此基础之上可以建立依赖图。按照图的某一种拓扑排序，就可以根建立依赖图。按照图的某一种拓扑排序，就可以根据语义规则进行翻译。据语义规则进行翻译。17树遍历的属性计算方法树遍历的属性计算方法 以某种次序遍历语法树，直至计算出所有的以某种次序遍历语法树，直至计算出所有的属性。最常用的遍历方法是属性。最常用的遍历方法是深度优先，从左深度优先，从左到右到右的遍历方法。这种方法

16、最简单，适应面的遍历方法。这种方法最简单，适应面最广。（算法略）最广。（算法略） 缺点：缺点：v必须在语法树建立之后才能使用必须在语法树建立之后才能使用v效率不高效率不高对每个非终结符号：对每个非终结符号：多次重复计算所有能够计算的继承属性多次重复计算所有能够计算的继承属性最后计算所有能够计算的综合属性最后计算所有能够计算的综合属性18一遍扫描的处理方法一遍扫描的处理方法 在语法分析的同时计算属性值，因而无需构造在语法分析的同时计算属性值，因而无需构造实际的语法树。实际的语法树。 语法制导翻译法就是为文法中每个产生式配上语法制导翻译法就是为文法中每个产生式配上一组语义规则，并且，在一组语义规则

17、，并且，在语法分析的同时语法分析的同时执行这执行这些语义规则。些语义规则。计算语义规则，完成有关语义分析和代码生成动作计算语义规则，完成有关语义分析和代码生成动作的时机：的时机：自上而下分析中一个产生式匹配输入串成功时；自上而下分析中一个产生式匹配输入串成功时；自下而上分析中一个产生式被用于进行归约时。自下而上分析中一个产生式被用于进行归约时。19抽象语法树抽象语法树v 在语法分析期间完成翻译工作可大幅提高编译的时在语法分析期间完成翻译工作可大幅提高编译的时空效率，但也存在一些问题：空效率，但也存在一些问题：适合于语法分析的文法可能并不反映语言成分的自然层适合于语法分析的文法可能并不反映语言成

18、分的自然层次结构；次结构；特定的语法分析方法也可能限制了语法分析树的节点考特定的语法分析方法也可能限制了语法分析树的节点考察顺序察顺序v 因此，现代编译器通用的做法是：通过语法分析因此，现代编译器通用的做法是：通过语法分析构造语法树，再对语法树进行遍历完成属性的计算。构造语法树，再对语法树进行遍历完成属性的计算。也就是使用中间表示也就是使用中间表示(Intermediate (Intermediate Representation)Representation)把翻译从语法分析中分离出来。把翻译从语法分析中分离出来。v这样做可以使编译器更好地模块化，也方便了移植这样做可以使编译器更好地模块化，

19、也方便了移植和优化。和优化。20 为每个运算分量或为每个运算分量或运算符号都建立一个运算符号都建立一个结点来为子表达式建结点来为子表达式建立子树。运算符号结立子树。运算符号结点的各子结点分别是点的各子结点分别是表示该运算符号的各表示该运算符号的各个运算分量的子表达个运算分量的子表达式组成的子树的根。式组成的子树的根。 抽象语法树中的每一个结点可以抽象语法树中的每一个结点可以由包含几个域的记录来实现。由包含几个域的记录来实现。 在在一个运算符号对应的结点中一个运算符号对应的结点中, ,一个一个域标识运算符号域标识运算符号, ,其它域包含指向其它域包含指向运算分量的结点的指针。运算分量的结点的指针

20、。 通常，运算符号叫做这个结点的通常，运算符号叫做这个结点的标号。进行翻译时，抽象语法树中标号。进行翻译时，抽象语法树中的结点可能会用附加域来存放结点的结点可能会用附加域来存放结点的属性值的属性值( (或指向属性的指针）。或指向属性的指针）。表达式表达式3*5+4的抽象语法树的抽象语法树抽象语法树抽象语法树(AST)(AST)：语法分析树的压缩形式。：语法分析树的压缩形式。叶子结点：终结符的综合属性、文法开始符号的继承属性叶子结点：终结符的综合属性、文法开始符号的继承属性以下以表达式为例，说明如何构造以下以表达式为例，说明如何构造ASTAST。21综合属性综合属性nptr表示函数调用返回的指针

21、。表示函数调用返回的指针。22a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口23a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口24a+5* *b的语法树的构造的语法树的构造E.

22、nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口25a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口26a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+

23、F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口27a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口28a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向

24、符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口29a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口30a+5* *b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口313.3. S

25、-属性文法的自下而上计算S-属性文法：只含有综合属性的属性文法。属性文法：只含有综合属性的属性文法。 在自底向上的分析法如在自底向上的分析法如LR分析法中，我分析法中，我们使用一个栈来存放已经分析过的子树的们使用一个栈来存放已经分析过的子树的信息，现在可以在分析栈中使用一个附加信息，现在可以在分析栈中使用一个附加的域来存放综合属性值。的域来存放综合属性值。 如果一个属性文法是如果一个属性文法是S-属性文法，那么属性文法，那么在计算每个语义规则时，分析栈中栈顶在计算每个语义规则时，分析栈中栈顶处正好就是计算语义规则时需要用到的处正好就是计算语义规则时需要用到的其它属性值。其它属性值。32 假设图

26、中的栈是由一对数组假设图中的栈是由一对数组state和和val来实现的。每一个来实现的。每一个state元素都是元素都是一个指向一个指向LR(1)分析表的指针（或索引）。（注意，文法符号隐含在分析表的指针（或索引）。（注意，文法符号隐含在state中中而不需要存储在栈中）。然而，如果像而不需要存储在栈中）。然而，如果像前面前面LR分析时分析时的那样把文法符号存入的那样把文法符号存入栈中时，那么当第栈中时，那么当第i个个state对应的符号为对应的符号为A时，时，vali中就存放语法树中与结中就存放语法树中与结点点A对应的属性值。对应的属性值。 设当前栈顶由指针设当前栈顶由指针top指示。我们假

27、设综合属性是刚好在每次归约前计指示。我们假设综合属性是刚好在每次归约前计算的。假设语义规则算的。假设语义规则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的位置）综合

28、属性的位置）综合属性A.a的值存放在的值存放在valtop中。中。33边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？v属性的计算次序一定受分析方法所限定的分析树结属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制点建立次序的限制v分析树的结点是自左向右生成分析树的结点是自左向右生成v如果属性信息是自左向右流动，那么就有可能在分如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算析的同时完成属性计算344.4. L- L-属性文法和自顶向下翻译属性文法和自顶向下翻译L-属性文法属性文法：如果对于每个产生式：如果对于每个产生式AX1X2Xn的每个的每个

29、语义规则中，每个属性或者是综合属性，或者是语义规则中，每个属性或者是综合属性，或者是Xj(1=j=n)的一个继承属性且这个继承属性仅依赖的一个继承属性且这个继承属性仅依赖于：于： （1）产生式）产生式Xj的左边符号的左边符号X1,X2,Xj-1的属性的属性 （2）A的继承属性。的继承属性。L-属性文法也就是属性文法也就是“左属性左属性”文法，计算每一个继承属文法，计算每一个继承属性时不能引用右边符号的属性性时不能引用右边符号的属性(继承属性和综合属性继承属性和综合属性)。由此定义可知，由此定义可知，S属性文法一定是属性文法一定是L属性文法。属性文法。35 翻译模式翻译模式 属性文法可以看成是关

30、于语言翻译的高级规属性文法可以看成是关于语言翻译的高级规范说明，其中隐去实现细节，使用户从明确说明翻范说明，其中隐去实现细节，使用户从明确说明翻译顺序的工作中解脱出来。下面我们讨论一种适合译顺序的工作中解脱出来。下面我们讨论一种适合语法制导翻译的另一种描述形式，称为语法制导翻译的另一种描述形式，称为翻译模式翻译模式。翻译模式给出了使用语义规则进行计算的次序，这翻译模式给出了使用语义规则进行计算的次序，这样就可以把某些实现细节表示出来。在翻译模式中，样就可以把某些实现细节表示出来。在翻译模式中，和文法符号相关的属性和语义规则（这里我们也称和文法符号相关的属性和语义规则（这里我们也称语义动作），用

31、花括号语义动作），用花括号 括起来，插入到产生式右括起来，插入到产生式右部的合适位置上。这样翻译模式给出了使用语义规部的合适位置上。这样翻译模式给出了使用语义规则进行计算的顺序。则进行计算的顺序。36对继承属性出现位置的限制对继承属性出现位置的限制为了计算出继承属性，为了计算出继承属性，翻译模式翻译模式必须满足三个条件：必须满足三个条件： （1）产生式右边的符号的继承属性必须在这个符）产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。号以前的动作中计算出来。 （2）一个动作不能引用这个动作右边符号的综合）一个动作不能引用这个动作右边符号的综合属性。属性。 （3）产生式左边非终结符的

32、综合属性只有在它所）产生式左边非终结符的综合属性只有在它所引用的所有属性都计算出来后才能计算。计算这种引用的所有属性都计算出来后才能计算。计算这种属性的动作通常可放在产生式右端的末尾。属性的动作通常可放在产生式右端的末尾。37不满足条件的例子SA1A2 A1.in := 1; A2.in := 2;A a print(A.in) 应该改为：S A1.in := 1; A1 A2.in := 2; A2 A a print(A.in) 通常写成：S A1.in := 1; A1 A2.in := 2; A2 A a print(A.in) 38自顶向下翻译自顶向下翻译 在第四在第四讲讲我们知道，

33、为了构造不带回溯我们知道，为了构造不带回溯的自顶向下语法分析，必须消除文法中的左的自顶向下语法分析，必须消除文法中的左递归。现在我们把前面消除左递归的方法加递归。现在我们把前面消除左递归的方法加以扩充以扩充,当消除一个翻译模式的基本语法的左当消除一个翻译模式的基本语法的左递归时同时考虑属性。这种方法适合带综合递归时同时考虑属性。这种方法适合带综合属性的翻译模式。这样许多文法可以使用自属性的翻译模式。这样许多文法可以使用自顶向下分析来实现。顶向下分析来实现。39消除左递归消除左递归推广转换左递规翻译模式的方法，以便进行自顶向下分析：推广转换左递规翻译模式的方法，以便进行自顶向下分析： 假设我们有

34、下面的翻译模式：假设我们有下面的翻译模式： AA1Y A.a:=g(A1.a,Y.y) AX A.a:=f(X.x) 其每个文法符号都有一个综合属性，用小写字母表示，其每个文法符号都有一个综合属性，用小写字母表示，g和和f是任意函数。是任意函数。利用第四章消除左递归的算法，可将其转换成下面文法：利用第四章消除左递归的算法，可将其转换成下面文法： AXR R YR|40 翻译模式变为：翻译模式变为： AX R.i:=f(X.x) AX R.i:=f(X.x) R A.a:=R.s R A.a:=R.s RY R RY R1 1.i:=g(R.i,Y.y) .i:=g(R.i,Y.y) R R1

35、1 R.s:= R R.s:= R1 1.s .s R R.s:= R.i R R.s:= R.i 经过转换的翻译模式，使用了经过转换的翻译模式，使用了R R的继承属性的继承属性i i和综合和综合属性属性s.s. 考虑产生算术表达式的文法，它的翻译模式如何考虑产生算术表达式的文法，它的翻译模式如何? ?考虑语义动作考虑语义动作41 求值翻译模式：求值翻译模式： 使用属性使用属性valval来保存计算结果来保存计算结果 ET R.i:=T.val ET R.i:=T.val R E.val:=R.s R E.val:=R.s R+ R+ T R T R1 1.i:=R.i+T.val.i:=R.

36、i+T.val R R1 1 R.s:= R R.s:= R1 1.s .s R R.s:= R.i R R.s:= R.i T( T( E E ) T.val:= E.val ) T.val:= E.val Tnum T.val:= num.val Tnum T.val:= num.val42 构造语法树的翻译模式：构造语法树的翻译模式： 使用属性使用属性p p来保存语法子树的根结点指针来保存语法子树的根结点指针 ET R.i:=T.p ET R.i:=T.p R E.p:=R.s R E.p:=R.s R+ R+ T T RR1 1.i:=mknod(+,R.i,T.p).i:=mknod

37、(+,R.i,T.p) R R1 1 R.s:= R R.s:= R1 1.s .s R R.s:= R.i R R.s:= R.i T( T( E E ) T.p:= E.p ) T.p:= E.p Tnum T.p:=mkleaf(num,num.val) Tnum T.p:=mkleaf(num,num.val)43递归下降翻译器的构造递归下降翻译器的构造v思想：对递归下降的语法分析器进行扩展（在适当的位置加入语义子程序），使之能够实现翻译模式。v方法：为每个非终结符A构造一个函数，A的继承属性对应该函数的形式参数，其返回值为A的综合属性。函数体内，对出现在A的产生式右部的每个文法符号的

38、每个属性都设置一个局部变量。控制流程依然由递归下降分析方法确定。44在每个产生式对应的程序代码中，按照从左到右的次序，对于终结符、非终结符及其语义动作分别作以下工作：v对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续输入。v对于每个非终结符B，产生一个右部带有函数调用的赋值语句 c=B(b1,b2,.,bn)，其中b1,b2,.,bn是为B的继承属性设置的变量， c是为B的综合属性设置的变量。v对于语义动作，把动作的代码抄进语法分析器中，并把对属性的引用改为对相应变量的引用。思考：实现上述算术表达式文法的翻译模式，产生语法树。45 预测翻译器的设

39、计：示例预测翻译器的设计：示例把预测分析器的构造方法推广到翻译方案的实现把预测分析器的构造方法推广到翻译方案的实现产生式产生式R +TR | 的分析过程的分析过程procedure R;beginif lookahead = + then beginmatch ( + ); T ; Rendelse begin / 什么也不做什么也不做 /endend 46function R (i : syntax_tree_node ) : syntax_tree_node;var nptr , i1, s1, s : syntax_tree_node; addoplexeme : char;begin

40、if lookahead = + then begin / 产生式产生式 R +T R /addoplexeme = lexval;match( + );nptr = T; i1 = mknode(addoplexme, i , nptr) ; s1 = R (i1 ); s = s1endelse s = i; / 产生式产生式 R /return send;R : i, sT : nptr+ : addoplexeme47 5.5. 自下而上计算继承属性自下而上计算继承属性v自下而上地计算L-属性。可以基于所有LL(1)文法和许多LR(1)的L-属性文法。v从翻译模式中去掉嵌入在产生式中间

41、的动作v分析栈中的继承属性 复写规则：能够预知属性值在栈中的存放位置v模拟继承属性的计算 不能预知属性值在栈中的存放位置时，通过模拟非终结符、修改翻译模式归结为2中的情形v用综合属性代替继承属性 改变基础文法以避免继承属性 详见参考书详见参考书48习题一v下列文法由开始符号S产生一个二进制数，令综合属性val给出该数的值：SL . L|LL LB|BB 0|1 试设计求S.val的属性文法。其中，已知B的综合属性c，给出由B产生的二进位的结果值。49方法1:使用L.val、L.len属性SL S.val = L.val SL1.L2 S.val = L1.val + L2.val/2L2.le

42、nL BL.val = B.c, L.len = 1L L1BL.val = 2*L1.val + B.c, L.len = L1.len + 1B 0B.c = 0B 1B.c = 150方法2：使用L.lval、L.w属性SL S.val = L.lval SL1.L2 S.val = L1.lval + L2.lval / L2.wL BL.lval = B.c, L.w = 2L L1BL.lval = 2*L1.lval + B.c, L.w = 2 * L1.w B 0B.c = 0B 1B.c = 151为下面文法写一个语法制导的定义，用为下面文法写一个语法制导的定义，用S S的

43、综合属性的综合属性valval给出下面文法中给出下面文法中S S产生的二进制数的值。例如，输入产生的二进制数的值。例如，输入101.101101.101时，时，S. S. valval = 5.625 = 5.625。不得修改文法，但属性不得修改文法，但属性使用没有限制使用没有限制S L . R | LL L B | BR B R | BB 0 | 1S.LLBLBBRRBRBB习题二52S L . RS. val = L. val + R. valS LS. val = L. valL L1 BL. val = L1. val 2 + B. valL BL. val = B. valR B

44、R1R. val = R1. val / 2 + B. val / 2R BR. val = B. val / 2B 0B. val = 0B 1B. val = 153给出把中缀表达式翻译成没有冗余括号的中缀表给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。例如达式的语法制导定义。例如, ,因为因为 和和 是左结合是左结合, ,(a (b + c ) (d )可以重写成可以重写成a (b + c ) dv先把表达式的括号都去掉，然后在必要的地方先把表达式的括号都去掉，然后在必要的地方再加括号再加括号v去掉表达式中的冗余括号，保留必要的括号去掉表达式中的冗余括号，保留必要的括号 习题三54 第一种方法第一种方法S E print ( E. code )E E1 + T if T. op = plus thenE.code =E1.code|“+”|“(”|T.code|“)”elseE