属性文法与语法制导翻译ppt课件

1、属性文法和语法属性文法和语法制导翻译制导翻译w 引见有关语义分析及翻译的问题。w 语义描画和语义处置的方法主要是属性文法和语法制导翻译方法。w 本章中，将首先引见属性文法的根本概念，然后引见基于属性文法的处置方法，讨论如何在自上而下分析和自下而上分析中实现属性的计算。第六章 属性文法和语法制导翻译w 属性文法属性文法w 综合属性综合属性w 承继属性承继属性w 基于属性文法的处置方法基于属性文法的处置方法w 依赖图依赖图w 属性的计算次序属性的计算次序w 树遍历的属性计算方法树遍历的属性计算方法w 一遍扫描的处置方法一遍扫描的处置方法w 笼统语法树笼统语法树w S-S-属性文法的自下而上计算属性

2、文法的自下而上计算w 分析栈中的综合属性分析栈中的综合属性w L L属性文法和自顶向下翻译属性文法和自顶向下翻译w 翻译方式翻译方式w 自顶向下翻译自顶向下翻译w 递归下降翻译器的设计递归下降翻译器的设计w 自下而上计算承继属性自下而上计算承继属性w 从翻译方式中去掉嵌入在产生式中间的动作从翻译方式中去掉嵌入在产生式中间的动作w 分析栈中的承继属性分析栈中的承继属性w 模拟承继属性的计算模拟承继属性的计算w 用综合属性替代承继属性用综合属性替代承继属性属性文法 w 属性翻译文法是在上下文无关文法的根底上，为每个文法符号终结符或非终结符配备假设干相关的“值称为属性。w 这些属性代表与文法符号相关

3、信息，例如它的类型、值、代码序列、符号表内容等等。w 属性与变量一样，可以进展计算和传送。w 属性加工的过程即是语义处置的过程。对于文法的每个产生式都配备了一组属性的计算规那么，称为语义规那么。 w 属性通常分为两类：w 综合属性和承继属性。综合属性用于“自下而上传送信息，而承继属性用于“自上而下传送信息。w 在一个属性文法中，对应于每个产生式A都有一套与之相关联的语义规那么，每条规那么的方式为 b:f(c1，c2，ck) ，这里，f是一个函数，而且或者w 1b是A的一个综合属性并且c1，c2，ck 是产生式右边文法符号的属性；或者w 2b是产生式右边某个文法符号的一个承继属性并且c1，c2，

4、ck 是A或产生式右边任何文法符号的属性。w 在两种情况下，我们都说属性b依赖于属性 c1，c2，ckw 1终结符只需综合属性，它们由词法分析器提供；w 2非终结符既可有综合属性也可有承继属性，文法开场符号的一切承继属性作为属性计算前的初始值。w 对出如今产生式右边的承继属性和出如今产生式左边的综合属性都必需提供一个计算规那么。w 属性计算规那么中只能运用相应产生式中的文法符号的属性，这有助于在产生式范围内“封装属性的依赖性。w 然而，出如今产生式左边的承继属性和出如今产生式右边的综合属性不由所给的产生式的属性计算规那么进展计算，它们由其它产生式的属性规那么计算或者由属性计算器的参数提供。w

5、语义规那么所描画的任务可以包括属性计算、静态语义检查、符号表操作、代码生成等等。w 语义规那么能够产生副作用如产生代码，也能够不是变元的严厉函数如某个规那么给出可用的下一个数据单元的地址。这样的语义规那么通常写成过程调用或过程段。 w 例如，思索非终结符A，B和C，其中，A有一个承继属性a和一个综合属性b，B有综合属性c，C有承继属性d。产生式ABC能够有规那么w Cd：=Bc1w Ab：=AaBcw 而属性Aa和Bc在其它地方计算。 产产 生生 式式 语语 义义 规规 则则 L E n print (E.val) E E1 + T E.val := E1 .val + T.val E T E

6、.val := T.val T T1 * * F T.val := T1.val * * F.val T F T.val := F.val F (E) F.val := E.val F digit F.val := digit.lexval表表6.1 一个简单台式计算器的属性文法一个简单台式计算器的属性文法综合属性w 在语法树中，一个结点的综合属性的值由其子结点的属性值确定。因此，通常运用自底向上的方法在每一个结点处运用语义规那么计算综合属性的值。w 仅仅运用综合属性的属性文法称S-属性文法 digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.va

7、l = 8F.val = 8digit.lexval = 8T.val = 5+*F.val = 5F.val = 2digit.lexval = 5图图6.1 8+5*2 n的注释分析树的注释分析树承继属性w 在语法树中，一个结点的承继属性由此结点的父结点和或兄弟结点的某些属性确定。w 用承继属性来表示程序设计言语构造中的上下文依赖关系很方便。在下面的例子中，承继属性在阐明中为各种标识符提供类型信息。 产产 生生 式式 语语 义义 规规 则则 D TL L.in := T.type T int T. type := integer T real T. type := real L L1, i

8、d L1.in := L.in; addtype (id.entry, L.in ) L id addtype (id.entry, L.in ) 表表6.2 带承继属性带承继属性L.in的属性文法的属性文法w 句子real id1，id2，id3的带注释的语法树 DrealT.type = real,id3L.in = realL.in = realL.in = realid2id1,图图6.2 在每个在每个L结点都带有承继属性的语法树结点都带有承继属性的语法树基于属性文法的处置方法 w 基于属性文法的处置过程通常是:w 对单词符号串进展语法分析，构造语法分析树，然后根据需求遍历语法树并在语

9、法树的各结点处按语义规那么进展计算。w 这种由源程序的语法构造所驱动的处置方法就是语法制导翻译法。输入串语法树依赖图语义规那么计算次序图6.3 语法制导翻译概观依赖图w 假设在一棵语法树中一个结点的属性b依赖于属性c，那么这个结点处计算b的语义规那么必需在确定c的语义规那么之后运用。w 在一棵语法树中的结点的承继属性和综合属性之间的相互依赖关系可以由称作依赖图的一个有向图来描画。 w 在为一棵语法树构造依赖图以前，我们为每一个包含过程调用的语义规那么引入一个虚综合属性b，这样把每一个语义规那么都写成w b：f( c1，c2，ck)w 的方式。依赖图中为每一个属性设置一个结点，假设属性b依赖于属

10、性c，那么从属性c的结点有一条有向边连到属性b的结点。cb 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结点构造一条有向边；对于给定的一棵语法分析树、依赖图是按下面步骤构造出来的： real id1, id2, id3的分析树的依赖图的分析树的依赖图D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54

11、type图图 6.5 图图6.2中语法分析树的依赖图中语法分析树的依赖图D TL L.in := T.typeL L1, id L1.in := L.in;addtype (id.entry, L.in ) T realT. type := real虚结点虚结点属性的计算次序w 一个有向非循环图的拓扑序是图中结点的任何顺序m1,m2,mk,使得边必需是从序列中前面的结点指向后面的结点。w 假设mimj是mi到mj的一条边，那么在序列中mi必需出如今mj之前。w 一个依赖图的任何拓扑排序都给出一个语法树中结点的语义规那么计算的有效顺序。w 例6.5 在图6.5的依赖图中，依赖图的一个拓扑排序可以

12、从低序号到高序号顺序写出。从这个拓扑排序中我们可以得到以下程序，用an来代表依赖图中与序号n的结点有关的属性。a4 := real;a5 := a4;addtype (id3.entry, a5 ) a7 := a5;addtype (id2.entry, a7 ) a9 := a7;addtype (id1.entry, a9 ) 树遍历的属性计算方法 w 假设语法树曾经建立好了，并且树中已带有开场符号的承继属性和终结符的综合属性。w 然后以某种次序遍历语法树，直至计算出一切属性。最常用的遍历方法是深度优先，从左到右的遍历方法。假设需求的话，可运用多次遍历或称遍。 下面算法可对任何无循环的属

13、性文法进展计算 While 还有未被计算的属性 do VisitNode(S) *S是开场符号* procedure VisitNodeN: Node； begin if N VN then * 假设它的产生式为NX1 X2Xm * for i:=1 to m do if XiVN then* 即Xi 是非终结符 * begin 计算 Xi 的一切可以计算的承继属性； VisitNode (Xi) end； 计算 N 的一切可以计算的综合属性 endw 只需文法的属性是非循环定义的，那么每一次扫描至少有一个属性值被计算出来。w 假设语法树有n个结点因此最多有O(n)个属性，最坏的情况整个遍历需

14、O(n)时间。例6.6： S有承继属性a，综合属性b； X有承继属性c, 综合属性d； Y有承继属性e , 综合属性f； Z有承继属性h , 综合属性g。产生式语义规则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=0XYZxyz(a)初始形状S:a=0XYZxyz(b)VisitNode(S)第一次调用后.h=0.g=1S:a=0,b=0XYZxyz(c)VisitNode(S)第二次调用后.h=0.g=1.c=1.d=2S:a=0,b=0XYZxyz(d)对文法G的属性计算步骤

15、.h=0.g=1.c=1.d=2.e=0.f=1图6.6 对文法G的属性计算步骤初值 a=0 Z.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没有值Z.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一遍扫描的处置方法 w 一遍扫描的处置方法是在语法分析的同时计算属性值，而不是语法分析构造语法树之后进展属性的计算，而且无需构造实践的语法树假设有必需，当然也可以实践构造。w 采用这种处置方法，当一个属性值不再用于计算其它属性值时，编译程序就不用再

16、保管这个属性值。当然，假设需求，也可以把这些语义值存到文件中。 w 由于一遍扫描的处置方法与语法分析器的相互作用，它与下面两个要素亲密相关：w 1所采用的语法分析方法；w 2属性的计算次序。w L-属性文法可用于一遍扫描的自上而下分析，而S-属性文法适宜于一遍扫描的自下而上分析。w 假设按这种一遍扫描的编译程序模型来了解语法制导翻译方法的话，w 所谓语法制导翻译就是为文法中每个产生式配上一组语义规那么，并且在语法分析的同时执行这些语义规那么。w 在自上而下语法分析中，假设一个产生式匹配输入串胜利，或者，在自下而上分析中，当一个产生式被用于进展归约时，此产生式相应的语义规那么就被计算，完成有关的

17、语义分析和代码产生的任务。笼统语法树 w 经过语法分析可以很容易构造出语法分析树，然后对语法树进展遍历完成属性的计算。w 在语法树中去掉那些对翻译不用要的信息，从而获得更有效的源程序中间表示。这种经变换后的语法树称之为笼统语法树 。w 语法树与分析树w 语法树可看作分析树的浓缩，也称笼统语法树。而分析树可看成详细语法树。w 在笼统语法树中，操作符和关键字都不作为叶结点出现，而是把它们作为内部结点，即这些叶结点的父结点。 S if B then S1 else S2if-then-elseBS1S2SifBthen S1else S2笼统语法树详细语法树a := b* -c + b * -cas

18、signEEE+E*EbEEa赋值语句cE*EbEcassigna+*bc*bc算符笼统语法树语法分析树建立表达式的笼统语法树w 语法制导翻译既可以基于语法分析树，也可以基于笼统语法树进展。w 建立表达式的笼统语法树与把表达式翻译成后缀方式类似。我们经过为每一个运算分量或运算符号都建立一个结点来为子表达式建立子树。运算符号结点的各子结点分别是表示该运算符号的各个运算分量的子表达式组成的子树的根。w 笼统语法树中的每一个结点可以由包含几个域的记录来实现的。w 当我们进展翻译时，笼统语法树中的结点能够会用附加的域来存放结点的属性值或指向属性值的指针。+ +num 5idto entry for a

19、 下面的一些函数来建立表示带有二目算符的表达式的笼统语法树中的结点。每一个函数都前往一个指向新建立结点的指针。 (1) mknodeop, left, right建立一个运算符号结点，标号是op，两个域left和right分别指向左子树和右子树。 (2) mkleafid, entry建立一个标识符结点，标号为id, 一个域entry指向标识符在符号表中的入口。 (3) mkleafnum，val建立一个数结点，标号为num，一个域val用于存放数的值。 w 建立表达式a - 4c的笼统语法树w 1P1： mkleafid，entrya)；w 2P2： mkleafnum，4；w 3P3： m

20、knode-，Pt，P2；w 4P4： mkleafid，entryc)；w 5P5： mknode，P3，P4；w 在这个序列中P1，P2，P5是指向结点的指针。entrya和entryc分别是指向符号表中的标识符a和c的指针。+num4ididto entry for ato entry for c图图6.7 a 4 + c的笼统语法树的笼统语法树产生式语义规则EE1 + TEE1 - TETT( E )TidTnumE.nptr := mknode(+,E1.nptr, E2.nptr)E.nptr := mknode(-,E1.nptr, E2.nptr)E.nptr := T.npt

21、rT.nptr := E.nptrT.nptr := mkleaf(ID,id.entry)T.nptr := mkleaf(NUM,num.lexval)表6.4 为表达式建立笼统语法树的属性文法to entry for a图图6.8 a 4 + c的笼统语法树的构造的笼统语法树的构造TEidnptrnptrnptrnptrnptridid4id-+to entry for CE+E-TnumTid S-属性文法的自下而上计算 w 综合属性可以在分析输入符号串的同时由自下而上的分析器来计算。w 分析器可以保管与栈中文法符号有关的综合属性值，每当进展归约时，新的属性值就由栈中正在归约的产生式右

22、边符号的属性值来计算。w S-属性文法的翻译器通常可借助于LR分析器实现。在S-属性文法的根底上，LR分析器可以改造为一个翻译器，在对输入串进展语法分析的同时对属性进展计算。 分析栈中的综合属性 w 在自底向上的分析方法中，我们运用一个栈来存放曾经分析过的子树的信息。如今我们可以在分析栈中运用一个附加的域来存放综合属性值。. . . . .Z. zZY. yYX.xX. . . . .state valtop图6.9 带有综合属性的分析栈w 设当前的栈顶由指针top指示。我们假设综合属性是刚好在每次归约前计算的。w 假设语义规那么 A. a:f( X.x, Y.y, Z.z)w 对应于产生式

23、AXYZ 。w 在把XYZ归约成A以前，w 属性Z.z的值放在valtop中，w Y.y的值放在valtop-1中，w X.x的值放在valtop-2中。w 归约以后，top值减2，w A的形状存放在statetop中原X的位置w 综合属性A. a的值存放在valtop中。. . . . .X.xXY. yYZ. zZ. . . . .栈栈 state valtop表6.5 用LR分析器实现台式计算器产产 生生 式式 代代 码码 段段 L E n print (val top ) E E1 + T val ntop :=val top 2+val top E T T T1 * * F val

24、ntop :=val top 2 val top T F F (E) val ntop :=val top 1 F digit 注: ntop = top r +1 ， r 产生式右边长度如 F (E) 应为 val top - 2 :=val top 1输入StateVal用到的产生式3*5+4n *5+4n 33*5+4n F3F dight*5+4n T3T F5+4n T*3+4n T*535+4n T*F35F dight+4n T15T T*F+4n E15E T4n E+15n E+4154n E+F154F dightn E+T154T Fn E19E E+TEn19L19L

25、En表6.6 翻译输入3*5+4n所作的动作L-属性文法和自顶向下翻译 w 在6.2节中我们知道，可以经过深度优先的方法对语法树进展遍历，从而计算属性文法的一切属性值。w 在本节中我们讨论一类属性文法，叫做L-属性文法，这类属性文法允许我们经过一次遍历就计算出一切属性值。诸如LL(1)这种自上而下分析方法的分析过程，从概念上说可以看成是深度优先建立语法树的过程，因此，我们可以在自上而下语法分析的同时实现L属性文法的计算。w 一个属性文法称为L-属性文法。假设对于每个产生式AX1X2Xn，其每个语义规那么中的每个属性或者是综合属性，或者是Xj(1=j= n)的一个承继属性且这个承继属性仅依赖于：

26、w 1产生式Xi的左边符号X1，X2，Xi-l的属性；w 2 A的承继属性。w 可见，S-属性文法一定是L-属性文法，由于(1)、(2)限制只用于承继属性。 产生式语义规则ALMAQRL.i := l(A.i)M.i := m(L.s)A.s := f(M.s)R.i := r(A.i)Q.i := q(R.s)A.s := f(Q.s)表6.7 非L-属性文法的例子由于 Q.i 依赖于右部符号R的综合属性R.s翻译摸式 w 属性文法可以看作是关于言语翻译的高级规范阐明，其中隐去实现细节。w 下面我们讨论一种适宜语法制导翻译的另一种描画方式，称为翻译方式Translation schemes。

27、w 翻译方式给出了运用语义规那么进展计算的次序，这样就可把某些实现细节表示出来。w 在翻译方式中，和文法符号相关的属性和语义规那么这里我们也称语义动作，用花括号括起来，插入到产生式右部的适宜位置上。这样翻译方式给出了运用语义规那么进展计算的顺序。 ET RR addop T print( addop.lexme) R | T num print( num. lexme) 例: 将含有+和-运算的中缀表达式翻译为后缀方式如 表达式 9+2 后缀表示为 9 2 +图6.10 9+2 的阐明动作的语法分析树ETR9print(9)-Tprint(-)R5print(5)+Tprint(+)2prin

28、t(2)R12345w 设计翻译方式时，必需留意某些限制以保证当某个动作援用一个属性时它必需是有定义的。w L-属性文法本身就能确保每个动作不会援用尚未计算出来的属性。w 当只需求综合属性时，情况最为简单。在这种情况下，可以这样来建立翻译方式：为每一个语义规那么建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。 w 例如，假设有下面的产生式和语义规那么：w 产生式 语义规那么w T T1* F T. val：=T1.val * F. valw 建立产生式和语义动作：w T T1* F T. val：T1. val * F. valw 假设既有综合属性又有承继属性，在建立翻译方式时

29、就必需w (1)产生式右边的符号的承继属性必需在这个符号以前的动作中计算出来。w (2)一个动作不能援用这个动作右边的符号的综合属性。w (3)产生式左边非终结符的综合属性只需在它所援用的一切属性都计算出来以后才干计算。计算这种属性的动作通常可放在产生式右端的末尾。w 下面的翻译方式不满足上述三个条件中的第一个条件：w SA1 A2 A1. in:1; A2. in:=2w Aa print(A. in)w可以改为w S A1. in:1 A1 A2. in:=2 A2SAaprint(A.in)1Aaprint(A.in)2A1. in:1; A2. in:=23该属性还没有定义w 通常，给

30、定一个L-属性文法，可以建立一个满足上述三个条件的翻译方式。w 下面例子阐明这种建立方法。它基于数学格式言语EQN。w 给定输人w E sub 1 valw EQN把E，1和val分别按不同的大小放在相关的位置上，如下图。 E1.val图6.11 盒子的语法制导安放产产 生生 式式 语语 义义 规规 则则 S B B.ps := 10; S.ht := B.ht B B1 B2 B1.ps := B.ps; B2.ps := B.ps; B.ht := max(B1.ht, B2.ht ) B B1 sub B2 B1.ps:=B.ps; B2.ps:= shrink(B.ps); B.ht

31、:= disp (B1.ht, B2.ht ) B text B.ht := text.h B.ps w文法中:w 非终结符B(表示盒子代表一个公式，产生式BBB 代表两个盒子并置， BB1 sub B2 代表B2的大小比B1的小，并且放在下角标的位置表6.8 盒子大小和高度的属性文法S ： S.ht，综合属性；待排公式的整体高度B ：B.ps，承继属性； 公式(文本)中字体“点的大小 B.ht，综合属性；公式排版高度text ：text.h，文本高度max ：求两个排版公式的最大高度shrink(B) ：将点大小减少为B的30disp(B1.ht，B2.ht)：向下调整B2的位置文字排版中的

32、符号属性E1Val例例 数学排版言语数学排版言语EQNS B.ps := 10 BS.ht := B.ht B B1.ps := B.ps B1B2.ps := B.ps B2B.ht := max(B1.ht, B2.ht ) B B1.ps :=B.ps B1sub B2.ps := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B text B.ht := text.h B.ps 图6.12 从表6.8构造出的翻译方式承继属性 ps自顶向下翻译w 在第四章我们知道，为了构造不带回溯的自顶向下语法分析，必需消除文法中的左递归。w 如今我们把前面讨论

33、过的消除左递归的算法加以扩展，当消除一个翻译方式的根本文法的左递归时同时思索属性。这种方法适宜带综合属性的翻译方式。这样，许多属性文法可以运用自顶向下分析来实现。 w 算术表达式的左递归文法相应的翻译方式E E1+T E. val：E1. val + T. valE E1-T E. val：E1. val - T. valE T E. val：T. val T (E) T. val：E. val T num T. val：num. val图6.13 带左递归的文法的翻译方式w 消除左递归，构造新的翻译方式E T R.i := T.valRE. val := R.sR +TR1.i := R.i

34、 + T. valR1R.s := R1.sR TR1.i := R.i T. valR1R.s := R1.sR R.s := R.i T )T.val := E. val T numT. val := num. val图6.14 消除左递归后的翻译方式图图6.15 计算表达式计算表达式 9 5 + 2w 对于自顶向下分析，我们假定动作是在处于一样位置上的符号被展开匹配胜利时执行的。 ET.val=9R.i=9num.val=9T.val=5R.i=4+T.val=2R.i=6 num.val=5num.val=2w 下面我们把转换左递归翻译方式的方法推行到普通，以便进展自顶向下分析。w 假

35、设我们有下面的翻译方式，它的每个文法符号都有一个综合属性，用小写字母表示，g和f是恣意函数。 A A1Y A.a：g(A1.a , Y.y)A X A.a：f(X.x)(6.1)w 消除左递归，转换为如下文法: A XRR YR | w 思索语义动作，翻译方式变为 A XR.i := f(X.x) RA.a := R.sR YR1.i := g(R.i , Y.y) R1 R.s := R1.sR R.s := R.i (6.2)(6.3)XA.a := f( X.x)A.a := g(f( X.x), Y1.y)Y1A.a := g(g(f( X.x), Y1.y), Y2.y)Y2(a)

36、按(6.1)自下而上计算A.aXR.i := f(X.x)Y1R.i := g(f(X.x),Y1.y)Y2R.i := g(g(f(X.x),Y1.y), Y2.y)R.sR.sR.s(b) 按(6.3)自上而下计算图图6.16 计算属性值的两种方法计算属性值的两种方法w 例6.11 假设把构造笼统语法树的属性文法定义见表6.4)转化成翻译方式，那么关于E的产生式和语义动作就变为：EE1 + T E.nptr := mknode(+,E1.nptr, E2.nptr)EE1 - T E.nptr := mknode(-,E1.nptr, E2.nptr)ET E.nptr := T.nptr

37、)T( E ) T.nptr := E.nptr Tnum T.nptr := mkleaf(NUM,num.val) Tid T.nptr := mkleaf(ID,id.entry) E T R.i := T.nptr R E.nptr := R.s R + T R1.i := mknode(+, R.i, T.nptr) R1 R.s := R1.s R - T R1.i := mknode(-, R.i, T.nptr) R1 R.s := R1.s R R.s := R.i /前往最终语法树其他不变，略删除左递归后：引入非终结符R图图6.17 构造笼统语法树的翻译方式构造笼统语法树的

38、翻译方式ET nptrT nptrid R-+T nptridnumididnum 4+ +- -to entry for ato entry for ci R s Ri 图图6.18 运用承继属性构造语法树运用承继属性构造语法树R.i 指向根结点指向根结点递归下降翻译器的设计 w 对给定的适宜于自顶向下翻译的翻译方式，下面给出设计递归下降翻译器的方法。w 1.对每个非终结符A构造一个函数过程，对A的每个承继属性设置一个方式参数，函数的前往值为A的综合属性作为记录，或指向记录的一个指针，记录中有假设干域，每个属性对应一个域。为了简单，我们假设每个非终结只需一个综合属性。A对应的函数过程中，为出

39、如今A的产生式中的每一个文法符号的每一个属性都设置一个部分变量。w 2.非终结符A对应的函数过程中，根据当前的输入符号决议运用哪个产生式候选。w 3.每个产生式对应的程序代码中，按照从左到右的次序，对于单词符号终结符、非终结符和语义动作分别作以下任务。w (1)对于带有综合属性x的终结符X，把x的值存入为X.x设置的变量中。然后产生一个匹配X的调用，并继续读入一个输入符号advance。w (2)对于每个非终结符B，产生一个右边带有函数调用的赋值语句cB (b1，b2，bk，其中，b1，bk是为B的承继属性设置的变量，c是为B的综合属性设置的变量。w (3)对于语义动作，把动作的代码抄进分析器

40、中，用代表属性的变量来替代对属性的每一次援用。w (4)函数结尾：return A的综合属性。w 例6.12 图6.17中的文法是LL(1)的,因此适宜于自顶向下分析。根据文法非终结符的属性，得到关于非终结符E，R，T的函数及其参数的类型，详细如下：w function E：AST-node；w function R(in：AST-node)：AST-node；w function T：AST-node；w R.in : 承继属性作为R的参数 w 把图6.17中的两个R产生式结合起来使翻译程序更小，新的产生式中用addop代表+和 -。w Raddopw T R1.i := mknode(ad

41、dop.lexme， R.i，T.nptrw R1 R.s:=R1.sw RR.s：R.i procedure R;beginif sym = addop then beginadvance; T; R endelse begin /* 什么也不做什么也不做 */ endend;图图6.19 产生式产生式R addop TR | 的分析过程的分析过程function R (in : AST-node) : AST-node;var nptr , i1, s1, s : AST-node; addoplexeme : char;begin if sym = addop then begin /*

42、 产生式 R addop T R */addoplexeme := lexval;advance;nptr := T; i1 := mknode(addoplexme, in , nptr) ; s1 := R (i1); s : = s1 endelse s := in; /* 产生式 R */return send;图图6.20 递归下降构造笼统语法树递归下降构造笼统语法树nptr: T.nptri1: R1.i s1: R1.ss : R.saddoplexeme: addop (+|-)自下而上计算承继属性w 讨论在自下而上的分析过程中实现L-属性文法的方法。w 这种方法可以实现任何基

43、于LL(1)文法的L-属性文法，它还可以实现许多不是一切基于LR(1)文法的L-属性文法。 从翻译方式中去掉嵌入在产生式中间的动作从翻译方式中去掉嵌入在产生式中间的动作 w 引见一种转换方法，它可以使一切嵌入的动作都出如今产生式的末尾，这样就可以自下而上处置承继属性。w 转换方法是，在根底文法中参与新的产生式，这种产生式的方式为M,其中M为新引入的一个标志非终结符。我们把嵌入在产生式中的每个语义动作用不同的标志非终结符M替代，并把这个动作放在产生式M的末尾。 例如，下面翻译方式例如，下面翻译方式 ET R R+T printR | -Tprint R | T numprintnum.val E

44、TR R+ TMR | TNR | T num printnum.val M print N print运用标志非终结符号M和N转换为w 两个翻译方式中的文法接受一样的言语。经过画出带有表示动作的附加结点的分析树，可以看到动作的执行程序也是一样的。w 在经过转换的翻译方式中，动作都在产生式右端的末尾，因此，可以在自下而上分析过程中产生式右部被归约时执行相应的动作。 分析栈中的承继属性 w 自下而上分析器对产生式AXY的右部是经过把X和Y从分析栈中移出并用A替代它们。w 假设X有一个综合属性X.s，按照6.3节所引见的方法我们把它与X一同放在分析栈中。w 由于X.s的值在Y以下的子树中的任何归约

45、之前曾经放在栈中，这个值可以被Y承继。w 也就是说，假设承继属性Y. i是由复写规那么Y. i := X.s定义的，那么可以在需求Y.i值的地方运用X.s的值。w 我们将会看到，在自下而上分析中计算属性值时复写规那么起非常重要的作用 下面例子阐明复写规那么的运用 w 假设某翻译方式为D T L.in := T.type LT int T. type := integerT real T. type := realL L1.in := L.in L1, id addtype (id.entry, L.in )L id addtype (id.entry, L.in )w 按照这个翻译方式标识符的

46、类型可以经过承继属性的复写规那么来传送。例如，对于输入串 int p, q, r 其属性的传送方向如图 DTLL,rL,qpint type ininin图图6.21 在每个在每个L结点结点L.in =T.type输 入 串状 态所 用 产 生 式int p, q, r p, q, r intp, q, r TT int, q, r Tp, q, r TLL id q, r TL，, r TL，q, r TLL L，id r TL，TL，rTLL L，idDD TL表6.9 int p, q, r的分析过程w 从表6.9可以看出，当L的右部被归约时，T恰好在这个右部的下面。 w 假设分析栈是由

47、一对数组state和val来实现的。w 假设statei代表符号X，那么val i存放X的综合属性X. s，那么表6.9中给出了state数组的内容。w 由于在表6.9中，每次L的右部被归约时，T恰好在这个右部的下面，因此这时可以方便地访问到T.type的值。 w 由于T. type在栈中相对于栈顶的位置是知的，我们可以翻译方式中语义动作的实现如下表所示。产产 生生 式式 代代 码码 段段 D TL T int valtop := integer T real valtop := real L L1, id addtype(valtop, valtop 3) L id addtype(valt

48、op, valtop 1) 表6.10 语义动作的实现模拟承继属性的计算w 属性的位置不能预测属性的位置不能预测w 产生式产生式语义规那么语义规那么w S S aAC aACC.i := A.sC.i := A.sw S S bABC bABCC.i := A.sC.i := A.sw C C c cC.s := g(C.i)C.s := g(C.i)w 属性C.i经过复写规那么承继综合属性A.s的值。留意在栈中A和C之间能够有B也能够没有B，当经过Cc进展归约时，C.i的值能够在valtop-1处也能够在valtop-2处，但我们不能确定终究在哪个位置。w 为理处理这个问题，我们在上述翻译方

49、式中的第二个产生式右部的C的前面插入一个新的标志非终结符M。 产生式产生式语义规那么语义规那么S S aAC aACC.i := A.sC.i := A.sS S bABMC bABMCM.i := A.s; C.i := M.i := A.s; C.i := M.sM.sC C c cC.s := g(C.i)C.s := g(C.i)M M M.s := M.iM.s := M.iS b A B CsiS b A B Msi C si图图6.22 经过标志经过标志M传送属性值传送属性值a修正前b修正后w 模拟不是复写规那么的语义规那么模拟不是复写规那么的语义规那么w 承继属性是某个综合属性

50、的一个函数承继属性是某个综合属性的一个函数w S aACC.i := f (A.s)w 添加标志非终结符，把添加标志非终结符，把f(A.s)的计算移到对的计算移到对标志非终结符归约时进展。标志非终结符归约时进展。wS aANCN.i := A.s; C.i := N.swN N.s := f (N.i)w(6.4)例例6.13 数学排版言语数学排版言语EQN S B.ps := 10 BS.ht := B.ht B B1.ps := B.ps B1B2.ps := B.ps B2B.ht := max(B1.ht, B2.ht ) B B1.ps :=B.ps B1sub B2.ps := s

51、hrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B text B.ht := text.h B.ps 文字排版中引入标志符号为了自底向上计算：B text B.ht := text.h B.ps 必需确定承继属性B.ps的“属性栈位置。为此引入标志非终结符L、M和N及其属性，包括相应的空产生式和有关属性规那么。这样B.ps即可在紧靠“句柄text下方的位置上找到。(L的综合属性置为B.ps的初值)SL BBB1M B2BB1 sub N B2texttext.hLL.s=10分析栈属性栈topbottom产产 生生 式式 代代 码码 段段S LB B.ps

52、 := L.s; S.ht := B.ht L L.s := 10 B B1 MB2 B1.ps := B.ps; M.i := B.ps;B2.ps := M.s; B.ht := max(B1.ht, B2.ht ) M M.s := M.i B B1 sub N B2 B1.ps :=B.ps; N.i := B.ps;B2.ps := N.s; B.ht := disp (B1.ht, B2.ht ) N N.s := shrink(N.i) B text B.ht := text.h B.ps 表6.11 一切承继属性都由复写规那么赋值L 用于初始化，M的用法同图6.22，N的用法同

53、式(6.4)w 按照前面例子的做法，在必要的时候引进标志非终结符，可以实如今LR分析过程中对L-属性文法进展计算。w 对于一个给定的LL(1)文法引入标志非终结符后，由于每个标志非终结符只需一个产生式，所以文法依然坚持是LL(1文法。任何LL(1)文法也是LR1)文法，因此，当标志非终结符参与到LL(1)文法时不会产生分析冲突。但对LR(1)文法引入标志非终结符之后，不能保证还是LR(1)的，因此能够引起分析冲突。w 下面，我们给出一种带承继属性的自下而上的分析和翻译方法。对于一个根底文法是LL(1)文法的L-属性文法定义，经过下面方法可以得到一个计算分析栈中一切属性值的分析程序。w 为了简单

54、起见，假设w 每一个非终结符A都有一个承继属性A.iw 每个文法符号X都有一个综合属性X.sw 假设X是一个终结符号，那么它的综合属性就是经过词法分析器前往的词法值，这个值将放在val栈中的顺应位置。w 对于每个产生式AX1X2Xn，引入n个新的标志非终结符M1，Mn，用产生式AM1X1MnXn替代上面的产生式。w 综合属性Xj.s将放在分析栈中与Xj相应的数组val的表项中。w 假设有承继属性Xj.i,把它也放在数组val中，但放在与Mj相应的项中。w 一个重要现实是，当我们进展分析时，假设承继属性A.i存在的话，它将在数组val中紧挨M1位置下面的位置中存放。 w 由于标志非终结符能够引起

55、分析冲突，进展下面的简化是有益的。w (1) 假设Xj没有承继属性，那么无需运用标志符Mj。当然，假设Mj被省略，栈中属性的位置会引起变化，但是这种变化可以经过对分析器稍加修正而顺应。w (2) 假设X1.i存在，但是由复写规那么X1.i:A.i计算，那么可省略M1。由于我们知道A.i曾经存放在栈中预定的位置，紧挨X1下面，因此这个值也可以作为X1.i运用。用综合属性替代承继属性 w 有时，改动根底文法能够防止承继属性。w 例如，一个Pascal的阐明由一标识符序列后跟类型组成，如w m, n: integerw 相应文法w D L: Tw T integer | charw L L，id |

56、 idw w 由于标识符由L产生而类型不在L的子树中，我们不能仅仅运用综合属性就把类型与标识符联络起来。w 现实上，假设非终结符L从第一个产生式中它的右边T中承继了类型，那么我们得到的属性文法就不是L-属性的，因此，基于这个属性文法的翻译任务不能在语法分析的同时进展。w 一个处理的方法是重新构造文法，使类型作为标识符表的最后一个元素。这样，类型可以经过综合属性L.type进展传送，当经过L产生每个标识符时，它的类型就可以填入到符号表中。w 相应文法w D id Lw L ，id L | : Tw T integer | char例例 题题 1 1为文法为文法S ( L ) | aL L , S

57、 | S写一个语法制导定义，它输出括号的对数。写一个语法制导定义，它输出括号的对数。S Sprint (S. num)S ( L )S. num := L.num + 1S aS. num := 0L L1 , SL. num := L1. num + S. numL SL. num := S.num 例例 题题 1 1例例 题题 2 2为文法为文法S ( L ) | aL L , S | S写一个翻译方案，它输出每个写一个翻译方案，它输出每个a的嵌套深度。的嵌套深度。例如例如:对于对于( a , ( a , a) )，输出的结果是，输出的结果是1 2 2。例例 题题 2 2S S. dept

58、h := 0 SS L. depth := S. depth + 1 ( L ) S a print (S. depth) L L1. depth := L. depth L1 , S. depth := L. depth SL S. depth := L. depth S例例 题题 3 3为文法为文法S ( L ) | aL L , S | S写一个翻译方案，它打印出每个写一个翻译方案，它打印出每个a在句子中是在句子中是第几个字符。第几个字符。例如，当句子是例如，当句子是( a , ( a , ( a , a ) , (a) ) )时，时，打印的结果是打印的结果是 2 5 8 10 14 。 例例 题题 3 3S S. in := 0 SS L. in := S. in + 1 ( L ) S. out := L. out + 1 S a S. out := S. in + 1; print (S. out) L L1. in := L. in L1 , S. in := L1. out + 1 S L. out := S. out L S. in := L.