网页制作技巧chapter5语法制导翻译.ppt

《网页制作技巧chapter5语法制导翻译.ppt》由会员分享，可在线阅读，更多相关《网页制作技巧chapter5语法制导翻译.ppt（133页珍藏版）》请在三一办公上搜索。

1、第五章 语法制导翻译,本章内容介绍一种形式化的语义描述方法：语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案。介绍语法制导的翻译的实现方法。,第五章 语法制导翻译,翻译的任务：语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。使用的方法:称作语法制导翻译。基本思想:根据翻译的需要设置文法符号的属性，以描述语法结构的语义。,例如，一个变量的属性有类型，层次，存储地址等。表达式的属性有类型，值等。属性值的计算和产生式相联系。随着语法分析的进行，执行属性值的计算，完成语义分析和翻译的任务。,第五章 语法制导翻译,属性1、定义：代表与文法符号(Vt或Vn)相关的信息。属性可以为任

2、何特性。例如：变量的类型、层次，存储地址；表达式类型，值；程序的目标代码等。2、属性值：是指与属性相关的信息，可以在语法分析过程中计算和传递。3、属性的表示：X.属性值。注意：产生式的左、右部有相同的符号时用下标或上标来区别。例：EE1+T E.val:=E1.val+T.val,第五章 语法制导翻译,1、语义规则(属性等式)为文法的每一个产生式(规则)配备的计算属性的计算规则。2、属性文法为文法的每个符号引入一组属性，且让该文法附加上语义规则时，构成了属性文法。表示：文法规则(产生式)语义规则 规则1 相关的属性等式.规则n 相关的属性等式,属性值分类据计算的依赖关系分成不相交的两类：综合属

3、性(synthesized attribute)在分析树中，一个结点的综合属性值是从其子结点的属性值计算出来的继承属性(inherited attribute)一个结点的继承属性值是由该结点兄弟结点和父结点的属性值计算出来的。,特例：开始符号没有继承属性，在开始时要确定；终极符则只能有综合属性，而不能有继承属性。非终结符既可有综合属性也可有继承属性,输入符号串,图语法制导翻译的概观,分析树,依赖图,语义规则的计算,一般来说，语义翻译可按图的流程处理。实际上，编译中语义翻译的实现并不是按图6.1 的流程处理的；而是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。,4.1 语法制

4、导的定义,例简单台式计算器的语法制导定义,5.1.1 语法制导定义的形式,语法制导定义是对上下文无关文法的推广每个文法符号有一组属性每个文法产生式A 有一组形式为b:=f(c1,c2,ck)的语义规则，其中f 是函数，b和c1,c2,ck 是该产生式文法符号的属性。综合属性：如果b是A的属性，c1,c2,ck 是产生式右部文法符号的属性或A的其它属性。继承属性：如果b是产生式右部某个文法符号X的属性。属性b依赖于属性c1，c2，ck,5.1.2 综合属性,S属性定义：仅仅使用综合属性的语法制导定义,5.1.2 综合属性,每个结点的属性值都标注出来的分析树叫做注释分析树（annotated pa

5、rse tree)8+5*2 n的注释 分析树,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的

6、计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,分析树各结点属性的计算可以自下而上地完成,5.1.2 综合属性,注释分析树:结点的属性值都标注出来的分析树,继承属性,一结点的继承属性是由该结点的父结点和/或兄弟结点的属性来定义的,int id,id,id,继承属性,int id1,id2,id3的注释分析树,属性依赖图,属性依赖图,语义规则建立了属性之间的依赖关系，这些关系可以用图来表示，这样的图称为依赖图int id1,id2,id3 的分析树的依赖图,依赖图的构造方法 for 分析树中每一结点n do for 结点n的文法符号的

7、每一个属性a do 为a在依赖图中建立一个结点；for 分析树中每一个结点n do for 结点n所用产生式对应的每一条 语义规则 b:f（c1，c2，ck)do for i:=1 to k do 从结点ci到结点b构造一条有向边；,5.1.4 属性计算次序,拓扑排序是无环有向图的结点的一种排序m1,m2,mk，它使得边只会从这个次序中先出现的结点到后出现的结点，也就是若mi mj是从mi到mj的边，那么在此排序中mi先于mj。显然，依赖图的任何拓扑排序都是分析树中结点属性计算的一个正确次序，即按拓扑排序进行计算的话，用语义规则b:=f(c1,c2,ck)计算b时，属性c1,c2,ck 已经计

8、算过了。,5.1.4 属性计算次序,拓扑排序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。例：1，2，3，4，5，6，7，8，9，10,5.1.4 属性计算次序,属性计算次序 构造输入的分析树,5.1.4 属性计算次序,属性计算次序 构造输入的分析树，构造属性依赖图,5.1.4 属性计算次序,属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行拓扑排序,5.1.4 属性计算次序,属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性。,5.1.4 属性计算次序,语义规则的计算方法分析树方法：前面介绍的方法。基于规则的方法：在构造编

9、译器时，用 手工或专门的工具来分析语义规则,静态确定语义规则的计算次序。忽略规则的方法：事先确定属性的计算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制.,5.2 语法树的构造,语法树语法树是分析树的浓缩表示：算符和关键字是作为内部结点。语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：,5.2 语法树的构造,语法树是常用的一种中间表示形式，把语法分析和翻译分开。语法分析过程中完成翻译有许多优点，但也有一些不足：1.适于语法分析的文法可能不完全反映语言成分的自然层次结构；2.语法分析方法限制，对分析树结点的访问序和翻译需要的访问序不一致。,5.2 语法树的构造,5

10、.2.2 建立表达式的语法树使用的函数 1.mknode(op,left,right)建立一个运算符号结点，标号是op,两个域left和right指向运算分量结点的指针。2mkleaf(id,entry)建立一个标识符结点,由标号id标识，一个域entry指向标识符符号表中相应的项。3.mkleaf(num,val)建立一个数结点，标号为num，域val用于存放数的值。返回新建立结点的指针。,id,to entry a,num 4,id,to entry c,+,a-4+c的语法树,5.2 语法树的构造,5.2.3建立语法树的语法制导定义,id,to entry a,num 4,id,to e

11、ntry c,+,a-4+c的语法树,1.每个非终结符号有一个语法树结点的指针属性。2.非终结符号归约未建立结点。,5.2 语法树的构造,a+5*b的语法树的构造,而语法制导定义中语义规则的执行受输入的语法的制导，当识别出输入串的一个语法结构时（可以看成发生一个事件），执行其相应的动作，因此这是一种事件驱动的程序设计。,5.2.4 关于表达式的有向非循环图 有向非循环图（Directed Acyclic Graph，简称DAG)用途：提取表达式中的公共子表达式，以取 得目标程序的局部优化。方法：执行mknode和mkleaf时，检查是否已有相同的结点，若有，则返回相应结点的指针。,例6.9 表

12、达式 aa*(b-c)+(b-c)*d 的DAG,+,*,d,+,*,a,c,b,5.3 S属性定义的自下而上计算,综合属性可以由自下而上的分析器在分析输入时完成计算。分析器可以把文法符号的综合属性值放在它的栈里，每当归约时，根据出现在栈顶的产生式右部符号的属性来计算左部符号的综合属性。我们说明如何扩展分析器的栈使之能够保存综合属性 S属性定义的翻译器可以借助LR分析器的生成器来实现,5.3 S属性定义的自下而上计算,将LR分析器分析栈中增加一个域来保存综合属性值。,栈 state val,top,若产生式A XYZ的语义规则是A.a:=f(X.x,Y.y,Z.z)，那么归约后：,top,4.

13、2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,4.2 S属性定义的自下而上计算,台式计算器的语法制导定义改成栈操作代码,栈 state val,top,例 输入串3*5+4n的语义分析过程,输入 state val 使用的产生式,3*5+4n-,*5+4n 3 3,*5+4n F 3 Fdigit,*5+4n T 3 TF,5+4n T*3-,+4n T*5 3-5,+4n T*F 3-5 F digit,产生式 代码段LEn printf(valntop)E E+T valntop:=valtop-2+valtopE TT T*F va

14、lntop:=valtop-2*valtopT FF(E)valntop:=valtop-1F digit,+4n T 15 T T*F,+4n E 15 E T,4n E+15-,n E+4 15-4,n E+F 15-4 F digit,n E+T 15-4 T F,n E 19 E E+T,En 19-,L 19 L En,输入 state val 使用的产生式,产生式 代码段LEn printf(valntop)E E+T valntop:=valtop-2+valtopE TT T*F valntop:=valtop-2*valtopT FF(E)valntop:=valtop-1F

15、 digit,S-属性小结 采用自底向上分析，例如LR分析，首先给出S-属性定义，然后，把S-属性定义变成可执行的代码段，这就构成了翻译程序。,在语法分析过程中进行语义分析和翻译，属性的计算顺序受到语法分析建立分析树结点顺序的限制。一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。L-属性定义 可用于按深度优先顺序计算属性值。,5.4 L-属性定义,深度优先顺序计算属性PROCEDURE dfvisit(n:node);BEGIN FOR n 的每个子结点m,从左至右 DO BEGIN 计算m的继承属性；dfvisit(m)END;计算n的综合属

16、性 END;,5.4.1 L-属性定义 定义 一个语法制导定义是L-属性定义，如果AX1X2XnP,其每一个语义规则中的每一个属性都是一个综合属性，或是Xj(1j n)的一个继承属性，这个继承属性仅依赖于 1.产生式中Xj的左边符号X1，X2，Xj-1 的属性；2A的继承属性。每一个S-属性定义都是L-属性定义。,1,2,变量类型声明的语法制导定义是一个L属性定义,表是否为L-属性的语法制导定义？,产生式,语义规则,ALMA QR,L.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),解：表语法制导定义不是L-属性

17、定义文法符号Q的继承属性依赖于它右边文法符号R的属性,5.4.2 翻译模式 定义 翻译模式是语法制导定义的一种便于翻译的书写形式。其中属性与文法符号相对应，语义规则或语义动作用花括号 括起来，可被插入到产生式右部的任何合适的位置上。这是一种语法分析和语义动作交错的表示法，它表达在按深度优先遍历分析树的过程中何时执行语义动作。翻译模式给出了使用语义规则进行计算的顺序。可看成是分析过程中翻译的注释。,例：一个简单的翻译模式 ETR Raddop T print(addop.lexeme)R1|Tnumprint(num.val)把语义动作看成终结符号，输入9-5+2,其分析树如图6.10，当按深度

18、优先遍历它，执行遍历中访问的语义动作，将输出 9 5-2+它是输入表达式9-5+2的后缀式。,一个简单的翻译模式,例 把有加和减的中缀表达式翻译成后缀表达式如果输入是8+5 2，则输出是8 5+2。E T RR addop T print(addop.lexeme)R1|T num print(num.val)E T R num print(8)R numprint(8)addop Tprint(+)R numprint(8)addop numprint(5)print(+)R print(8)print(5)print(+)addop Tprint()R print(8)print(5)pr

19、int(+)print(2)print(),E,T,9,T,Pt(9),R,Pt(-),Pt(+),R,-,5,Pt(5),+,T,2,Pt(2),R,图6.10 9-5+2的带语义动作的分析树,ETR Raddop T print(addop.lexeme)R1|Tnum print(num.val),例 数学排版语言EQN,例 数学排版语言EQN E sub 1.val S B B B1 B2 B B1 sub B2 B text,例 数学排版语言EQN,例 数学排版语言EQN E sub 1.val,例 数学排版语言EQN,例 数学排版语言EQN S B.ps:=10 BS.ht:=B.

20、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 textB.ht:=text.h B.ps,5.5.2设计翻译模式（根据语法制导定义）条件：语法制导定义是L-属性定义保证语义动作不会引用还没有计算的属性值。1.只需要综合属性的情况：为每一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式右边的末尾。例如：语法和语义规则如下，请写出其翻译模式：TT1*F Tval:=T1 val*F val,

21、解：TT1*F Tval:=T1 val*F val,2.既有综合属性又有继承属性 产生式右边的符号的继承属性必须在这个符号以前的动作中计算出来。一个动作不能引用这个动作右边符号的综合属性。产生式左边非终结符号的综合属性只有在它所引用的所有属性都计算出来以后才能计算。计算这种属性的动作通常可放在产生式右端的未尾。,例：下面的翻译模式满足要求吗？SA1A2 A1.in:=1;A2.in:=2 A a print(A.in,Print(A.in),Print(A.in),A1.in:=1;A2.in:=2,解：不满足,输入文法和翻译文法的概念,输入文法：未插入动作符号时的文法由输入文法可以通过推导

22、产生输入序列翻译文法：插入动作符号的文法由翻译文法可以通过推导产生活动序列,输入序列动作序列,5.5 自顶向下的翻译,边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制。分析树的结点是自左向右生成。如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算。,5.5 自顶向下的翻译,用翻译模式构造自顶向下翻译。5.5.1 从翻译模式中消除左递归 对于一个翻译模式，若采用自顶向下分析，必须消除左递归和提取左公因子，在改写基本文法时考虑属性值的计算。例6.14 带左递归的文法的翻译模式构造方法？,E E1+TE val:=E1val+T val

23、E E1-T E val:=E1 val-T val E T E.val:=T val T(E)T val:=E val T num T val:=num val 图6.13 带左递归的文法的翻译模式,例6.14 图6.13的带左递归的文法的翻译模式被转换成图6.14的带右递归的文法的翻译模式。,ET Ri:=T val RE val:=R s R TR1i:=R.i+T.val R1R.s:=R1 s R-TR1 i:=R i-Tval R1R s:=R1 s RR s:=R i T（E）T val:=E.val Tnum T val:=num val,EE1+T E E1-T E T T(

24、E)T num,继承属性i综合属性s,E TRR(+T|-T)R|T(E)T num,图6.14经过转换的带有右递归文法的翻译模式,E val=6,Tval=9,R i=9;R s=6,9,T val=5,5,R i=4;R s=6,+,T val=2,R i=6;R s=6,2,图6.15 表达式9-5+2的计算,ET Ri:=T val RE val:=R s R+TR1i:=R.i+T.val R1R.s:=R1 s R-TR1 i:=R i-Tval R1R s:=R1 s RR s:=R i T(E)T val:=E.val Tnum Tval:=num val,Tval=9,R i

25、=9,T val=5,R i=4,T val=2,R i=6,R s=6,R s=6,R s=6,E val=6,关于左递归翻译模式更一般化的讨论左递归翻译模式 AA1YA.a:=g(A1.a,Y.y)AX A.a:=f(X.x)（6.2）每一个文法符号都有一个综合属性，用相应的小写字母表示，g和f是任意函数。消除左递归，文法转换成 AX R RY R|（6.3）,再考虑语义动作，翻译模式变为：AX Ri:=f(X x)R A.a:=R.s RY R1 i:=g（R i,Y y）R1 R s:=R1 s RR s:=R i（6.4）经过转换的翻译模式，使用R的继承属性i和综合属性s。,Y2,Y

26、1,X,(a),例输入：XY1Y2采用左递归翻译模式,AA1YA.a:=g(A1.a,Y.y)AX A.a:=f(X.x),A,A,A,A a=g(g(f(X x),Y1 y),Y2 y),A a=g(f(X x),Y1 y),A a=f(X x),A,Y2,Y1,X,(b),AX Ri:=f(X x)R A.a:=R.s RY R1 i:=g(R i,Y y)R1R s:=R1 s RR s:=R i,R,R,R,Ri=f(X x),R i=g(f(X x),Y1 y),R i=g(g(f(X x),Y1 y),Y2 y),例输入：XY1Y2 消除左递归后翻译模式,例 左递归的消除引起继承属

27、性,例 左递归的消除引起继承属性,例 左递归的消除引起继承属性,E T R.i:=T.nptrRE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sR R.s:=R.i T F W.i:=F.nptrWT.nptr:=W.sW*FW1.i:=mknode(*,W.i,F.nptr)W1W.s:=W1.sW W.s:=W.i,例 左递归的消除引起继承属性,E T R.i:=T.nptr T+T+T+RE.nptr:=R.sR+TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sR R.s:=R.i T F W.i:=F.n

28、ptrWT.nptr:=W.sW*FW1.i:=mknode(*,W.i,F.nptr)W1W.s:=W1.sW W.s:=W.i,例 左递归的消除引起继承属性,略去了E TR T 部分,5.5.2 预测翻译器的设计,把预测分析器的构造方法推广到翻译方案的实现产生式R+TR|的分析过程procdure R;beginif lookahead=+then beginmatch(+);T;Rendelse begin/*什么也不做*/endend,5.5.2 预测翻译器的设计,function R(i:syntax_tree_node):syntax_tree_node;var nptr,i1,s

29、1,s:syntax_tree_node;addoplexeme:char;begin 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+:addoplexeme,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性Pascal的声明，如m,n:integerD L:TT integer|charL

30、L,id|id,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性Pascal的声明，如m,n:integerD L:TT integer|charL L,id|id改成从右向左归约D id LL,id L|:TT integer|char,4.3 L属性定义的自上而下计算,4.3.4 用综合属性代替继承属性Pascal的声明，如m,n:integerD L:TT integer|charL L,id|id改成从右向左归约D id LL,id L|:TT integer|char,4.3 L属性定义的自上而下计算,D id L addtype(id.entry,L.type)

31、L,id L1 L.type:=L1.Type;addtype(id.entry,L1.type)L:T L.type:=T.typeT integer T.type:=integerT real T.type:=real,4.4 L属性的自下而上计算,在自下而上分析的框架中实现L属性定义的方法它能实现任何基于LL(1)文法的L属性定义。也能实现许多（但不是所有的）基于LR(1)的L属性定义。,4.4 L属性的自下而上计算,删除翻译方案中嵌入的动作E T RR+T print(+)R1|T print()R1|T num print(num.val),4.4 L属性的自下而上计算,删除翻译方案

32、中嵌入的动作E T RR+T print(+)R1|T print()R1|T num print(num.val)在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端。,4.4 L属性的自下而上计算,删除翻译方案中嵌入的动作E T RR+T print(+)R1|T print()R1|T num print(num.val)在文法中加入产生的标记非终结符，让每个嵌入动作由不同标记非终结符M代表，并把该动作放在产生式M 的右端。E T RR+T M R1|T N R1|T num print(num.val)M print(+)N print

33、(),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性例 int p,q,r 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),4.4 L属性的自下而上计算,4.4.2 分析栈上的继承属性属性位置能预测例 int p,q,r D T L.in:=T.type LT int T.type:=integerT real T.type:=realL L1.in:=L.in L1,id

34、addtype(id.entry,L.in)L id addtype(id.entry,L.in),4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,属性的位置不能预测S aACC.i:=A.sS bABCC.i:=A.sC cC.s:=g(C.i),4.4 L属性的自下而上计算,属性的位置不能预测S aACC.i:=A.sS bABCC.i:=A.sC cC.s:=g(C.i)增加标记非终结符S aACC.i:=A.sS bABMCM.i:=A.s;C.i:=M.sC cC.s:=g(C.i)M M.s:=M.i,4.4 L属性的自下而上计算,模拟继承属性的计算继承属性是某个综合属

35、性的一个函数S aACC.i:=f(A.s)C cC.s:=g(C.i),4.4 L属性的自下而上计算,模拟继承属性的计算继承属性是某个综合属性的一个函数S aACC.i:=f(A.s)C cC.s:=g(C.i)增加标记非终结符，把f(A.s)的计算移到对标记非终结符归约时进行。S aANCN.i:=A.s;C.i:=N.sN N.s:=f(N.i)C cC.s:=g(C.i),4.4 L属性的自下而上计算,例 数学排版语言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.p

36、s:=B.ps B1sub B2.ps:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)B textB.ht:=text.h B.ps,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.4 L属性的自下而上计算,4.5 递 归 计 算,回顾：语法制导定义的实现分析树方法。,4.5 递 归 计 算,回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽

37、略规则的方法）。,4.5 递 归 计 算,回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）。本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）。,4.5 递 归 计 算,回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）。本节介绍先分析后计算的方法，不局限于L属性计算（基于规则的方法）。为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分。,4.5 递 归 计 算,回顾：语法制导定义的实现分析树方法。边分析边进行属性计算，只能完成L属性计算（忽略规则的方法）。本节介绍先分析后计算的

38、方法，不局限于L属性计算（基于规则的方法）。为每个非终结符构造一个属性计算函数，但是该函数不含语法分析部分。为非终结符的不同综合属性构造不同的函数。,4.5 递 归 计 算,4.5.1 自左向右遍历为B构造一个属性计算函数 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:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht)B textB.ht:=text.h B.ps,4.5 递 归 计 算,function B(n,

39、ps);var ps1,ps2,ht1,ht2;begincase 在结点n的产生式 ofB B1 B2:ps1:=ps;ht1:=B(child(n,1),ps1);ps2:=ps;ht2:=B(child(n,2),ps2);return max(ht1,ht2);,B B1.ps:=B.ps B1B2.ps:=B.ps B2B.ht:=max(B1.ht,B2.ht),4.5 递 归 计 算,function B(n,ps);var ps1,ps2,ht1,ht2;begincase 在结点n的产生式 ofB B1 sub B2:ps1:=ps;ht1:=B(child(n,1),ps1

40、);ps2:=shrink(ps);ht2:=B(child(n,3),ps2);return disp(ht1,ht2);,B B1.ps:=B.ps B1subB2.ps:=shrink(B.ps)B2B.ht:=disp(B1.ht,B2.ht),4.5 递 归 计 算,function B(n,ps);var ps1,ps2,ht1,ht2;begincase 在结点n的产生式 ofB text:return ps text.h;default:errorend,B textB.ht:=text.h B.ps,4.5 递 归 计 算,4.5.2 其它遍历方法按所需次序访问结点的子结点，

41、可用于非L属性定义。A LM L.i:=l(A.i);M.i:=m(L.s);A.s:=f(M.s)A QR R.i:=r(A.i);Q.i:=q(R.s);A.s:=f(Q.s),4.5 递 归 计 算,A LM:/*从左到右的次序*/li:=l(ai);ls:=L(child(n,1),li);mi:=m(ls);ms:=M(child(n,2),mi);return f(ms);,4.5 递 归 计 算,A QR:/*从右到左的次序*/ri:=r(ai);rs:=R(child(n,2),ri);qi:=q(rs);qs:=Q(child(n,1),qi);return f(qs);,4

42、.5 递 归 计 算,4.5.3 多次遍历 S E E.i:=g(E.s);S.r:=E.tE E1E2 E.s:=fs(E1.s,E2.s);E1.i:=fi1(E.i);E2.i:=fi2(E.i);E.t:=ft(E1.t,E2.t)E id E.s:=id.s;E.t:=h(E.i),4.5 递 归 计 算,综合属性t不可能和s在同一遍扫描中完成计算,4.5 递 归 计 算,function Sr(n);begins:=Es(child(n,1);i:=g(s);t:=Et(child(n,1),i);return tend;,4.5 递 归 计 算,function Es(n);|f

43、unction Et(n,i);begin|begincase 在结点n的产生式 of|case 在结点n的产生式 ofE E1 E2:|E E1 E2:s1:=Es(child(n,1);|i1:=fi1(i);s2:=Es(child(n,2);|t1:=Et(child(n,1),i1);return fs(s1,s2);|i2:=fi2(i);E id:|t2:=Et(child(n,2),i2);return id.s;|return ft(t1,t2);default:|E id:error|return h(i);end|default:end;|error|end|end;,本

44、 章 要 点,语义规则的两种描述方法：语法制导的定义和翻译方案。设计简单问题的语法制导定义和翻译方案，这是本章的重点和难点。语义规则的三种计算方法：分析树方法、基于规则的方法和忽略规则的方法。S属性的自下而上计算（边分析边计算）。L属性的自上而下计算（边分析边计算）。L属性的自下而上计算（边分析边计算）。递归计算（先分析后计算）。,例 题 1,为文法S(L)|aL L,S|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,例 题 2,为

45、文法S(L)|aL L,S|S写一个翻译方案，它输出每个a的嵌套深度。例如，对于(a,(a,a)，输出的结果是1 2 2。S S.depth:=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,为文法S(L)|aL L,S|S写一个翻译方案，它打印出每个a在句子中是第几个字符。例如，当句子是(a,(a,(a,a),(a)时，打印的结果是2 5 8 10 14。S S.in:=0 SS L.in:=S.in+1(L)S.ou

46、t:=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.in S L.out:=S.out,例 题 4,给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。例如，因为和是左结合，(a(b+c)(d)可以重写成a(b+c)d。先把表达式的括号都去掉，然后在必要的地方再加括号。去掉表达式中的冗余括号，保留必要的括号。,例 题 4,第一种方法S E print(E.code)E E1+T if T.op=plus thenE.code:=E1.code

47、|“+”|“(”|T.code|“)”elseE.code:=E1.code|“+”|T.code;E.op:=plusE TE.code:=T.code;E.op:=T.op,例 题 4,T T1 Fif(F.op=plus)or(F.op=times)thenif T1.op:=plus thenT.code:=“(”|T1.code|“)”|“”|“(”|F.code|“)”elseT.code:=T1.code|“”|“(”|F.code|“)”else if T1.op:=plus thenT.code:=“(”|T1.code|“)”|“”|F.codeelseT.code:=T1

48、.code|“”|F.code;T.op:=times,例 题 4,T FT.code:=F.code;T.op:=F.opF idF.code:=id.lexeme;F.op:=idF(E)F.code:=E.code;F.op:=E.op,例 题 4,第二种方法给E，T和F两个继承属性left_op和right_op分别表示左右两个运算对象的主算符的优先级给它们一个综合属性self_op表示自身主算符的优先级再给一个综合属性code表示没有冗余括号的代码。分别用1和2表示加和乘的优先级，用3表示id和(E)的优先级，用0表示左侧或右侧没有运算对象的情况。,例 题 4,S EE.left_o

49、p:=0;E.right_op:=0;print(E.code)E E1+TE1.left_op:=E.left_op;E1.right_op:=1;T.left_op:=1;T.right_op:=E.right_op;E.code:=E1.code|“+”|T.code;E.self_op:=1;E TT.left_op:=E.left_op;T.right_op:=E.right_op;E.code:=T.code;E.self_op:=T.self_op,例 题 4,T T1 F.T F.F idF.code:=id.lexeme;F.self_op:=3,例 题 4,F(E)E.left_op:=0;E.right_op:=0;F.self_op:=if(F.left_op=F.right_op)thenE.self_op else 3F.code:=if(F.left_op=F.right_op)thenE.code else“(”|E.code|“)”,习 题,第一次 4.1,4.3第二次4.4,4.7第三次 4.13,4.14,