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

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

1、第五章第五章 语法制导翻译语法制导翻译 本章内容本章内容 介绍一种形式化的语义描述方法：介绍一种形式化的语义描述方法：语法制导语法制导的翻译的翻译，包括它的两种具体形式：，包括它的两种具体形式：语法制导语法制导的定义和翻译方案的定义和翻译方案。介绍语法制导的翻译的实现方法。介绍语法制导的翻译的实现方法。第五章第五章 语法制导翻译语法制导翻译v 翻译的任务：翻译的任务：语义分析和正确性检查，若语义分析和正确性检查，若正确，则翻译成中间代码或目标代码。正确，则翻译成中间代码或目标代码。v 使用的方法使用的方法:称作语法制导翻译。称作语法制导翻译。v 基本思想基本思想:根据翻译的需要设置文法符号的根

2、据翻译的需要设置文法符号的属性属性，以描述语法结构的语义。，以描述语法结构的语义。第五章第五章 语法制导翻译语法制导翻译 属性属性1、定义：代表与文法符号(Vt或Vn)相关的信息。属性可以为任何特性。例如：变量的类型、层次，存储地址；表达式类型，值；程序的目标代码等。2、属性值：是指与属性相关的信息，可以在语法分析过程中计算和传递。3、属性的表示：X.属性值。注意：产生式的左、右部有相同的符号时用下标或上标来区别。例：EE1+TE.val:=E1.val+T.val第五章第五章 语法制导翻译语法制导翻译 1、语义规则(属性等式)为文法的每一个产生式(规则)配备的计算属性的计算规则。2、属性文法

3、为文法的每个符号引入一组属性，且让该文法附加上语义规则时，构成了属性文法。表示：文法规则(产生式)语义规则规则1相关的属性等式.规则n相关的属性等式据计算的依赖关系计算的依赖关系分成不相交不相交的两类：在分析树中，一个结点的综合属性值是从其的属性值计算出来的一个结点的继承属性值是由该结点和的属性值计算出来的。一般来说，语义翻译可按图的流程处理。一般来说，语义翻译可按图的流程处理。实际上，编译中语义翻译的实现并不是按图实际上，编译中语义翻译的实现并不是按图6.1 的流的流程处理的；而是随语法分析的进展，识别出一个语法程处理的；而是随语法分析的进展，识别出一个语法结构，就对它的语义进行分析和翻译。

4、结构，就对它的语义进行分析和翻译。4.1 语法制导的定义语法制导的定义例例简单台式计算器的语法制导定义简单台式计算器的语法制导定义产产 生生 式式语语 义义 规规 则则 L E n print(E.val)E E1+TE.val:=E1.val+T.valE TE.val:=T.valT T1*FT.val:=T1.val*F.valT FT.val:=F.valF(E)F.val:=E.valF digitF.val:=digit.lexval5.1.1 语法制导定义的形式语法制导定义的形式是对上下文无关文法的推广 每个文法符号有一组属性每个文法符号有一组属性 每个文法产生式每个文法产生式A

5、 有一组形式为有一组形式为b:=f(c1,c2,ck)的语义规则的语义规则，其中其中f 是函数，是函数，b和和c1,c2,ck 是该产生式文法符号的属性。是该产生式文法符号的属性。综合属性：综合属性：如果如果b是是A的属性，的属性，c1,c2,ck 是是产生式右部文法符号的属性或产生式右部文法符号的属性或A的其它属性。的其它属性。继承属性继承属性：如果：如果b是产生式右部某个文法符号是产生式右部某个文法符号X的属性。的属性。5.1.2 综合属性综合属性S属性定义属性定义：仅仅使用综合属性的语法制导定义仅仅使用综合属性的语法制导定义产产 生生 式式语语 义义 规规 则则 L E n print(

6、E.val)E E1+TE.val:=E1.val+T.valE TE.val:=T.valT T1*FT.val:=T1.val*F.valT FT.val:=F.valF(E)F.val:=E.valF digitF.val:=digit.lexval5.1.2 综合属性综合属性每个结点的属性值都标注出来的分析树叫做每个结点的属性值都标注出来的分析树叫做注注释分析树释分析树（annotated parse tree)8+5*2 n的注释的注释 分析树分析树digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T

7、.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=

8、8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.va

9、l=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val

10、=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digi

11、t.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性

12、的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=55.1.2 综合属性综合属性注释分析树注释分析树:结

13、点的属性值都标注出来的分析树结点的属性值都标注出来的分析树digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5 继承属性继承属性一结点的继承属性是由该结点的父结点和一结点的继承属性是由该结点的父结点和/或或兄弟结点的属性来定义的兄弟结点的属性来定义的,int id,id,id产产 生生 式式语语 义义 规规 则则 D TLL.in:=T.typeTintT.type:=integerTrealT.type:=realL L1,idL1.in

14、:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)继承属性继承属性int id1,id2,id3的注释分析树的注释分析树DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,属性依赖图属性依赖图属性依赖图属性依赖图,语义规则建立了属性之间的依赖关属性之间的依赖关系系，这些关系可以用图来表示，这样的图称为int id1,id2,id3 的分析树的依赖图的分析树的依赖图D intT,id3LLLid2id1,1 entry102entry3 entryin 98in

15、 76in 54 type 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构造一条有向边；构造一条有向边；5.1.4 属性计算次序属性计算次序 拓扑排序拓扑排序是无环有向图的结点的一种排序m1,m2,mk，它使得边只会从这个次序中先出现的

16、结点到后出现的结点，也就是若mimj是从mi到mj的边，那么在此排序中mi先于mj。显然，依赖图的任何拓扑排序都是分析树中结点属性计算的一个正确次序，即按拓扑排序进行计算的话，用语义规则b:=f(c1,c2,ck)计算b时，属性c1,c2,ck已经计算过了。5.1.4 属性计算次序属性计算次序拓扑排序拓扑排序：结点的一种排序，使得边只会从该次序中：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点。先出现的结点到后出现的结点。例：例：1，2，3，4，5，6，7，8，9，10D intT,id3LLLid2id1,1 entry102entry3 entryin 98in 76in

17、54 type5.1.4 属性计算次序属性计算次序属性计算次序属性计算次序 构造输入的分析树构造输入的分析树D intT,id3LLLid2id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 属性计算次序属性计算次序属性计算次序属性计算次序 构造输入的分析树，构造属性依赖图构造输入的分析树，构造属性依赖图D intT,id3LLLid2id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 属性计算次序属性计算次序属性计算次序属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行构造输入的分

18、析树，构造属性依赖图，对结点进行拓扑排序拓扑排序D intT,id3LLLid2id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 属性计算次序属性计算次序属性计算次序属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性。拓扑排序，按拓扑排序的次序计算属性。D intT,id3LLLid2id1,1 entry102entry3 entryin 98in 76in 54 type5.1.4 属性计算次序属性计算次序语义规则的计算方法语义规则的计算方法 分析树方

19、法：前面介绍的方法。分析树方法：前面介绍的方法。基于规则的方法：基于规则的方法：在构造编译器时，用在构造编译器时，用 手工或专门的工具来分析语义规则手工或专门的工具来分析语义规则,静态确定静态确定语语义规则的计算次序义规则的计算次序。忽略规则的方法：忽略规则的方法：事先确定属性的计算策略事先确定属性的计算策略（如边分析边计算），那么语义规则的设计（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制必须符合所选分析方法的限制.语法树的构造语法树的构造 语法树语法树 语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字是作为算符和关键字是作为内部结点。内部结点。语法制导翻译可

20、以基于分析树，也可以基于语法树语法制导翻译可以基于分析树，也可以基于语法树 语法树的例子：语法树的例子：if-then-elseBS1S2+*258 语法树的构造语法树的构造语法树是常用的一种中间表示形式，把语法分析语法树是常用的一种中间表示形式，把语法分析和翻译分开。语法分析过程中完成翻译有许多和翻译分开。语法分析过程中完成翻译有许多优点，但也有一些不足：优点，但也有一些不足：1.适于语法分析的文法可能不完全反映语言适于语法分析的文法可能不完全反映语言成分的自然层次结构；成分的自然层次结构；2.语法分析方法限制，对分析树结点的访问语法分析方法限制，对分析树结点的访问序和翻译需要的访问序不一致

21、。序和翻译需要的访问序不一致。语法树的构造语法树的构造 1.mknode(op,left,right)建立一个建立一个结点，标号结点，标号是是op,两个域两个域left和和right指向运算分量结点的指针。指向运算分量结点的指针。2mkleaf(id,entry)建立一个建立一个结点结点,由标号由标号id标识，标识，一个域一个域entry指向标识符符号表中相应的项。指向标识符符号表中相应的项。3.mkleaf(num,val)建立一个建立一个结点，标号为结点，标号为num，域域val用于存放数的值。用于存放数的值。idto entry anum 4 idto entry c +语法树的构造语法

22、树的构造产产 生生 式式语语 义义 规规 则则 E E1+T E.nptr:=mknode(+,E1.nptr,T.nptr)E TE.nptr:=T.nptrT T1*FT.nptr:=mknode(*,T1.nptr,F.nptr)T FT.nptr:=F.nptrF (E)F.nptr:=E.nptrF idF.nptr:=mkleaf(id,id.entry)F numF.nptr:=mkleaf(num,num.val)idto entry anum 4 idto entry c +语法树的构造语法树的构造a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.

23、nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口 而语法制导定义中语义规则的执行受输入的语法的制导，当识别出输入串的一个语法结构时（可以看成发生一个事件），执行其相应的动作，因此这是一种事件驱动的程序设计。（DirectedAcyclicGraph，简称DAG)提取表达式中的公共子表达式，以取提取表达式中的公共子表达式，以取 得目标程序的局部优化。得目标程序的局部优化。执行执行mknode和和mkleaf时，时，检查是否检查是否已有相同的结点已有相同的结点，若有，则返回相

24、应结点的指针。若有，则返回相应结点的指针。+*d+*acb5.3 S属性定义的自下而上计属性定义的自下而上计算算 综合属性可以由自下而上的分析器在分析输入时完成计算。分析器可以把文法符号的综合属性值放在它的栈里，每当归约时，根据出现在栈顶的产生式右部符号的属性来计算左部符号的综合属性。我们说明如何扩展分析器的栈使之能够保存综合属性 S属性定义的翻译器可以借助LR分析器的生成器来实现 S属性定义的自下而上计算属性定义的自下而上计算将将LR分析器分析器分析栈中增加分析栈中增加一个域来保存综合属性值一个域来保存综合属性值。.ZZ.zYY.yXX.x.栈栈 state valtop若产生式若产生式A

25、XYZ的语义规则是的语义规则是A.a:=f(X.x,Y.y,Z.z)，那么归约后：那么归约后：.AA.a.top4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈 state valtop产产 生生 式式代代 码码 段段 L E nprint(E.val)E E1+TE.val:=E1.val+T.valE TE.val:=T.valT T1*FT.val:=T1.val*F.valT FT.val:=F.valF(E)F.val:=E.valF digitF.val:=digit.

26、lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈 state valtop产产 生生 式式代代 码码 段段 L E nprint(val top 1)E E1+Tval top 2 :=val top 2+val top E TT T1*Fval top 2 :=val top 2 val top T FF(E)val top 2 :=val top 1F digit3*5+4n-*5+4n33*5+4nF3Fdigit*5+4nT3TF5+4nT*3-+4nT*53-

27、5+4nT*F3-5Fdigit+4nT15TT*F+4nE15ET4nE+15-nE+415-4nE+F15-4FdigitnE+T15-4TFnE19EE+TEn19-L19LEn 采用采用，例如，例如LR分析，首先分析，首先给出给出，然后，把，然后，把S-属性定义变成属性定义变成可执行的代码段可执行的代码段，这就构成了翻译程序。，这就构成了翻译程序。一种自然的计算属性的顺序是按深度优先一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它适应多种自底向上访问分析树结点的顺序，它适应多种自底向上和自顶向下的翻译方法。和自顶向下的翻译方法。L-属性定义属性定义 可用于按深度优先顺序计算

28、属可用于按深度优先顺序计算属性值。性值。PROCEDURE dfvisit(n:node);BEGIN FOR n 的每个子结点的每个子结点m,从左至右从左至右 DO BEGIN 计算计算m的的继承继承属性；属性；dfvisit(m)END;计算计算n的的综合综合属性属性 END;定义定义 一个语法制导定义是一个语法制导定义是，如果，如果 P,其每一个语义规则中的每其每一个语义规则中的每一个属性都是一个综合属性，或是一个属性都是一个综合属性，或是Xj(1 j n)的一个继承属性，这个继承属性仅依赖于的一个继承属性，这个继承属性仅依赖于 12变量类型声明的语法制导定义是变量类型声明的语法制导定义

29、是一个一个L属性定义属性定义产产 生生 式式语语 义义 规规 则则 D TLL.in:=T.typeTintT.type:=integerTrealT.type:=realL L1,idL1.in:=L.in;addtype(id.entry,L.in)Lidaddtype(id.entry,L.in)ALMA QRL.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)ETR Raddop T print(addop.lexeme)R1|Tnumprint(num.val)9 5-2+例例 把有加和减的中缀表达式翻译

30、成后缀表达式把有加和减的中缀表达式翻译成后缀表达式如果输入是如果输入是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)print(+)print(2)print()ET9TRR-5+T2R ETR Radd

31、op 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 E1.val例例 数学排版语言数学排版语言EQN例例 数学排版语言数学排版语言EQN E sub 1 .val 产产 生生 式式 语语 义义 规规 则则 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:

32、=B.ps;B2.ps:=shrink(B.ps);B.ht:=disp(B1.ht,B2.ht)B text B.ht:=text.h B.ps E1.val例例 数学排版语言数学排版语言EQN例例 数学排版语言数学排版语言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:=shrink(B.ps)B2:=disp(B1.ht,B2.ht)B text B.ht:=text.h B.ps 为每一个语义规则建立一个包含赋值的动作，并为每

33、一个语义规则建立一个包含赋值的动作，并把这个动作放在相应的产生式把这个动作放在相应的产生式的的。例如：语法和语义规则如下，请写出其翻译模式：例如：语法和语义规则如下，请写出其翻译模式：TT1*F T val:=T1 val*F val解：解：TT1*F T val:=T1 val*F valSAaAa边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制。点建立次序的限制。分析树的结点是自左向右生成。分析树的结点是自左向右生成。如果属性信息是自左向右流动，那么就有可能在分如果

34、属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算。析的同时完成属性计算。用翻译模式构造自顶向下翻译。用翻译模式构造自顶向下翻译。对于一个翻译模式，若采用自顶向下分析，对于一个翻译模式，若采用自顶向下分析，和和，在改写基本文法时考虑属，在改写基本文法时考虑属性值的计算。性值的计算。E E1+TE val:=E1 val+T val 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.14 图图6.13的带左递归的文法的翻译模式的带左递归的文法的翻译模式被转换成图被

35、转换成图6.14的带右递归的文法的翻译模式。的带右递归的文法的翻译模式。ET R i:=T val RE val:=R s R TR1 i:=R.i+T.val R1R.s:=R1 s R-TR1 i:=R i-T val R1R s:=R1 s RR s:=R i T（E）T val:=E.val Tnum T val:=num val 继承属性继承属性i综合属性综合属性sE val=6T val=9R i=9;R s=69T val=55R i=4;R s=6+T val=2R i=6;R s=62 T val=9R i=9T val=5R i=4T val=2R i=6R s=6R s=

36、6R s=6E 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 R i:=f(X x)R A.a:=R.s RY R1 i:=g（R i,Y y）R1 R s:=R1 s RR s:=

37、R i （6.4）经过转换的翻译模式，使用经过转换的翻译模式，使用R的继承属性的继承属性i和综合属性和综合属性s。Y2Y1X采用左递归翻译模式采用左递归翻译模式AAAA a=g(g(f(X x),Y1 y),Y2 y)A a=g(f(X x),Y1 y)A a=f(X x)AY Y2 2Y Y1 1X XRRRR i=f(X x)R i=g(f(X x),Y1 y)R i=g(g(f(X x),Y1 y),Y2 y)消除左递归后翻译模式消除左递归后翻译模式例例 左递归的消除引起继承属性左递归的消除引起继承属性例例 左递归的消除引起继承属性左递归的消除引起继承属性产产 生生 式式语语 义义 规规

38、 则则 E E1+T E.nptr:=mknode(+,E1.nptr,T.nptr)E TE.nptr:=T.nptrT T1*FT.nptr:=mknode(*,T1.nptr,F.nptr)T FT.nptr:=F.nptrF (E)F.nptr:=E.nptrF idF.nptr:=mkleaf(id,id.entry)F numF.nptr:=mkleaf(num,num.val)例例 左递归的消除引起继承属性左递归的消除引起继承属性E T R.i:=T.nptrRE.nptr:=R.sR +TR1.i:=mknode(+,R.i,T.nptr)R1R.s:=R1.sR R.s:=R

39、.i T F W.i:=F.nptrWT.nptr:=W *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.nptrWT.nptr:=W *FW1.i:=mknode(*,W.i,F.nptr)W1W.s:=W1.sW W.s:=W.i 例例 左递归的消除引起继承属性左递归的消除引起继承属性TF.np

40、trF.nptridi W*F.nptridnumididnum 5*指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i Wsi W 略去了略去了E TR T 部分部分5.5.2 预测翻译器的设计预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现把预测分析器的构造方法推广到翻译方案的实现产生式产生式R +TR|的分析过程的分析过程procdure R;beginif lookahead=+then beginmatch(+);T;Rendelse begin /*什么也不做什么也不做*/endend 5.5.2 预测翻译器的设计预测翻译器的设计functio

41、n R(i:syntax_tree_node):syntax_tree_node;var nptr,i1,s1,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+:addoplexeme4.3 L属性定义的自上而下计

42、算属性定义的自上而下计算4.3.4 用综合属性代替继承属性用综合属性代替继承属性Pascal的声明，如的声明，如m,n:integerD L:TT integer|charL L,id|id4.3 L属性定义的自上而下计算属性定义的自上而下计算4.3.4 用综合属性代替继承属性用综合属性代替继承属性Pascal的声明，如的声明，如m,n:integerD L:TT integer|charL L,id|id改成从右向左归约改成从右向左归约D id LL ,id L|:TT integer|char4.3 L属性定义的自上而下计算属性定义的自上而下计算4.3.4 用综合属性代替继承属性用综合属性

43、代替继承属性Pascal的声明，如的声明，如m,n:integerD L:TT integer|charL L,id|id改成从右向左归约改成从右向左归约D id LL ,id L|:TT integer|charD:L,idLidintegerT4.3 L属性定义的自上而下计算属性定义的自上而下计算D id L addtype(id.entry,L.type)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:=realD:L,i

44、dLidintegerT4.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属性的自下而上计算属性的自下而上计算 删除翻译方案中嵌入

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

46、每个嵌入动，让每个嵌入动作由不同标记非终结符作由不同标记非终结符M代表，并把该动作放在产代表，并把该动作放在产生式生式M 的右端。的右端。E T RR +T M R1|T N R1|T num print(num.val)M print(+)N print()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 addt

47、ype(id.entry,L.in)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)DTLL,rL,qpint type ininin L属性的自下而上计算属性的自下而上计算 DTLL,rL,qpint type ininin产产 生生 式式 代代 码

48、码 段段D TL T int valtop:=integer T real valtop:=real L L1,id addtype(valtop,valtop 3)L id addtype(valtop,valtop 1)4.4 L属性的自下而上计算属性的自下而上计算 属性的位置不能预测属性的位置不能预测S aACC.i:=A.sS bABCC.i:=A.sC cC.s:=g(C.i)L属性的自下而上计算属性的自下而上计算 属性的位置不能预测属性的位置不能预测S aACC.i:=A.sS bABCC.i:=A.sC cC.s:=g(C.i)增加标记非终结符增加标记非终结符S aACC.i:=

49、A.sS bABMCM.i:=A.s;C.i:=M.sC cC.s:=g(C.i)M M.s:=M.i4.4 L属性的自下而上计算属性的自下而上计算 模拟继承属性的计算模拟继承属性的计算继承属性是某个综合属性的一个函数继承属性是某个综合属性的一个函数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)的计算移到对标的计算移到对标记

50、非终结符归约时进行记非终结符归约时进行。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.ps:=B.ps B1sub B2.ps:=shrink(B.ps)B2:=disp(B1.ht,B2.ht)B text B.ht:=text.h B.ps 4.4 L属性的自下而上计算属性的自下而上计算 产产 生

51、生 式式语语 义义 规规 则则S LB B.ps:=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 NB2 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 L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB B.ps:=L.s;S.ht:=B.ht

52、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 NB2 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 4.4 L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB valtop 1:=valtopL L.s:=10 B B1 MB2 B1.ps:=B.ps;M.i:=B.ps;B

53、2.ps:=M.s;B.ht:=max(B1.ht,B2.ht)M M.s:=M.i B B1 sub NB2 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 L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB valtop 1:=valtopL valtop+1:=10B 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

54、 B B1 sub NB2 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 4.4 L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB valtop 1:=valtopL valtop+1:=10B B1 MB2 valtop 2:=max(valtop 2,valtop)M M.s:=M.i B B1 sub NB2 B1.ps:=B.ps;N.i:=B.ps;B2.ps:=N.s;B.ht:=disp(B1.ht

55、,B2.ht)N N.s:=shrink(N.i)B text B.ht:=text.h B.ps 4.4 L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB valtop 1:=valtopL valtop+1:=10B B1 MB2 valtop 2:=max(valtop 2,valtop)M valtop+1:=valtop 1B B1 sub NB2 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 4.4

56、L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB valtop 1:=valtopL valtop+1:=10B B1 MB2 valtop 2:=max(valtop 2,valtop)M valtop+1:=valtop 1B B1 sub NB2 valtop 3:=disp(valtop 3,valtop)N N.s:=shrink(N.i)B text B.ht:=text.h B.ps L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB valtop 1:=valtopL valtop+1:=10B B1 MB2 val

57、top 2:=max(valtop 2,valtop)M valtop+1:=valtop 1B B1 sub NB2 valtop 3:=disp(valtop 3,valtop)N valtop+1:=shrink(valtop 2)B text B.ht:=text.h B.ps 4.4 L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB valtop 1:=valtopL valtop+1:=10B B1 MB2 valtop 2:=max(valtop 2,valtop)M valtop+1:=valtop 1B B1 sub NB2 valtop 3:

58、=disp(valtop 3,valtop)N valtop+1:=shrink(valtop 2)B text valtop:=valtop valtop 14.5 递递 归归 计计 算算 回顾：语法制导定义的实现回顾：语法制导定义的实现 分析树方法。分析树方法。4.5 递递 归归 计计 算算 回顾：语法制导定义的实现回顾：语法制导定义的实现 分析树方法。分析树方法。边分析边进行属性计算边分析边进行属性计算，只能完成只能完成L L属性计算属性计算（忽略规则的方法）。（忽略规则的方法）。4.5 递递 归归 计计 算算 回顾：语法制导定义的实现回顾：语法制导定义的实现 分析树方法。分析树方法。边

59、分析边进行属性计算边分析边进行属性计算，只能完成只能完成L L属性计算属性计算（忽略规则的方法）。（忽略规则的方法）。本节介绍本节介绍先分析后计算的方法，不局限于先分析后计算的方法，不局限于L L属属性计算（基于规则的方法）。性计算（基于规则的方法）。4.5 递递 归归 计计 算算 回顾：语法制导定义的实现回顾：语法制导定义的实现 分析树方法。分析树方法。边分析边进行属性计算边分析边进行属性计算，只能完成只能完成L L属性计算属性计算（忽略规则的方法）。（忽略规则的方法）。本节介绍本节介绍先分析后计算的方法，不局限于先分析后计算的方法，不局限于L L属属性计算（基于规则的方法）。性计算（基于规

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

61、分函数不含语法分析部分。为非终结符的不同综合属性构造不同的函数。为非终结符的不同综合属性构造不同的函数。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)B2:=disp(B1.ht,B2.ht)B text B.ht:=text.h B.ps 4.5 递递 归归 计计 算算function B(n,ps)

62、;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(ch

63、ild(n,1),ps1);ps2:=shrink(ps);ht2:=B(child(n,3),ps2);return disp(ht1,ht2);B B1.ps:=B.ps B1subB2.ps:=shrink(B.ps)B2:=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:errorendB text B.ht:=text.h B.ps 4.5 递递 归归 计计 算算4.5.2 其

64、它遍历方法其它遍历方法按所需次序访问结点的子结点，可用于非按所需次序访问结点的子结点，可用于非L 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)i A si M si L s i A si R si 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);i A si M si L s

65、 i A si R si Q s 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);i A si M si L s i A si R si Q s 4.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:=

66、id.s;E.t:=h(E.i)S ri E s t i E1 s ti E s ti E2 s t i E s t id s 4.5 递递 归归 计计 算算综合属性综合属性t不可能和不可能和s在同一遍扫描中完成计算在同一遍扫描中完成计算 i E s t S ri E s tid s i E s tid 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);|function 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);re