网制作技巧chapter5语法制导翻译ppt课件

1、第五章第五章 语法制导翻译语法制导翻译 本章内容本章内容 引见一种方式化的语义描画方法：语法引见一种方式化的语义描画方法：语法制导的翻译，包括它的两种详细方式：制导的翻译，包括它的两种详细方式：语法制导的定义和翻译方案语法制导的定义和翻译方案 。 引见语法制导的翻译的实现方法。引见语法制导的翻译的实现方法。第五章第五章 语法制导翻译语法制导翻译v 翻译的义务：语义分析和正确性检查，翻译的义务：语义分析和正确性检查，假设正确，那么翻译成中间代码或目的假设正确，那么翻译成中间代码或目的代码。代码。v 运用的方法运用的方法: :称作语法制导翻译。称作语法制导翻译。v 根本思想根本思想: :根据翻译的

2、需求设置文法符根据翻译的需求设置文法符号的属性，以描画语法构造的语义。号的属性，以描画语法构造的语义。第五章第五章 语法制导翻译语法制导翻译 属性属性 1、定义：代表与文法符号、定义：代表与文法符号(Vt或或Vn )相关的信相关的信息。息。 属性可以为任何特性。属性可以为任何特性。 例如：变量的例如：变量的类型、层次，存储地址；表达式类型，值；程类型、层次，存储地址；表达式类型，值；程序的目的代码等。序的目的代码等。 2、属性值：是指与属性相关的信息，可以在、属性值：是指与属性相关的信息，可以在语法分析过程中计算和传送。语法分析过程中计算和传送。 3、属性的表示：、属性的表示： X.属性值。属

3、性值。 留意：留意： 产生式的左、右部有一样的符号时用产生式的左、右部有一样的符号时用下标或上标来区别。下标或上标来区别。 例：例： EE1+T E.val:=E1.val+T.val 第五章第五章 语法制导翻译语法制导翻译 1、语义规那么(属性等式)为文法的每一个产生式(规那么)配备的计算属性的计算规那么。2、属性文法为文法的每个符号引入一组属性，且让该文法附加上语义规那么时，构成了属性文法。表示：文法规那么(产生式)语义规那么规那么1相关的属性等式.规那么n相关的属性等式一个结点的承继属性值是由该结点一个结点的承继属性值是由该结点兄弟结点和父结点的属性值计算出兄弟结点和父结点的属性值计算出

4、来的。来的。普通来说，语义翻译可按图的流程处置。普通来说，语义翻译可按图的流程处置。实践上，编译中语义翻译的实现并不是按图实践上，编译中语义翻译的实现并不是按图6.1 的流的流程处置的；而是随语法分析的进展，识别出一个语法程处置的；而是随语法分析的进展，识别出一个语法构造，就对它的语义进展分析和翻译。构造，就对它的语义进展分析和翻译。4.1 语法制导的定义语法制导的定义例例简单台式计算器的语法制导定义简单台式计算器的语法制导定义产产 生生 式式语语 义义 规规 则则 L E n print (E.val)E E1 + TE.val := E1 .val + T.valE TE.val := T

5、.valT T1 * * FT.val := T1.val * * F.valT FT.val := F.valF (E)F.val := E.valF digitF.val := digit.lexval5.1.1 语法制导定义的方式语法制导定义的方式属性属性b依赖于属性依赖于属性c1，c2，ck5.1.2 综合属性综合属性S属性定义：仅仅运用综合属性的语法制导定义属性定义：仅仅运用综合属性的语法制导定义产产 生生 式式语语 义义 规规 则则 L E n print (E.val)E E1 + TE.val := E1 .val + T.valE TE.val := T.valT T1 *

6、* 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.val = 5+*F.val = 5F.va

7、l = 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 =

8、 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 综合属性综合属性分析树各结点属性的计算可以自下而上地完成分析树各结

9、点属性的计算可以自下而上地完成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.va

10、l = 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 =

11、 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.va

13、l = 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

14、l = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+*F.val = 5F.val = 2digit.lexval = 55.1.3 承继属性承继属性一结点的承继属性是由该结点的父结点和一结点的承继属性是由该结点的父结点和/或或兄弟结点的属性来定义的兄弟结点的属性来定义的 ,int id, id, id产产 生生 式式语语 义义 规规 则则 D TLL.in := T.typeTintT. type := integerTrealT. type := realL L1,idL1.in := L.in; addtype (id.entry, L.in

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

16、 entry102entry3 entryin 98in 76in 54 type for i:=1 to k do 从结点从结点ci到结点到结点b构造一条有向边；构造一条有向边；5.1.4 属性计算次序属性计算次序 拓扑排序是无环有向图的结点的一种排序拓扑排序是无环有向图的结点的一种排序m1, m2, , mk，它使得边只会从这个次序中先出，它使得边只会从这个次序中先出现的结点到后出现的结点，也就是假设现的结点到后出现的结点，也就是假设mi mj是从是从mi到到mj的边，那么在此排序中的边，那么在此排序中mi先先于于mj。 显然，依赖图的任何拓扑排序都是分析树中结显然，依赖图的任何拓扑排序都

17、是分析树中结点属性计算的一个正确次序，即按拓扑排序进点属性计算的一个正确次序，即按拓扑排序进展计算的话，用语义规那么展计算的话，用语义规那么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 76

18、in 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 属性计算次序属性计算次序属性计算次序属性计算次序 构造输入的分析树，构造属性依赖图，对结点构造输入的

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

20、析树方法：前面引见的方法。分析树方法：前面引见的方法。基于规那么的方法：在构造编译器时，用基于规那么的方法：在构造编译器时，用 手工或专门的工具来分析语义规那么手工或专门的工具来分析语义规那么, ,静态确定语义规那么的计算次序。静态确定语义规那么的计算次序。忽略规那么的方法：事先确定属性的计算战略忽略规那么的方法：事先确定属性的计算战略如边分析边计算，那么语义规那么的设如边分析边计算，那么语义规那么的设计必需符合所选分析方法的限制计必需符合所选分析方法的限制. .5.2 语法树的构造语法树的构造5.2.1 语法树语法树语法树是分析树的浓缩表示：算符和关键字是语法树是分析树的浓缩表示：算符和关键

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

22、分析方法限制，对分析树结点的访问序和翻译需求的访问序不一致。序和翻译需求的访问序不一致。5.2 语法树的构造语法树的构造前往新建立结点的指针。前往新建立结点的指针。idto entry anum 4 idto entry c +5.2 语法树的构造语法树的构造产产 生生 式式语语 义义 规规 则则 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.np

23、trF idF.nptr := mkleaf (id, id.entry)F numF.nptr := mkleaf (num, num.val)idto entry anum 4 idto entry c +5.2 语法树的构造语法树的构造a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum 5* *+ +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口 而语法制导定义中语义规那么的执行受输入的语法的制导，当识别出输入串的一个语法构造时可以看成发生一个

24、事件，执行其相应的动作，因此这是一种事件驱动的程序设计。 方法：执行方法：执行mknode和和mkleaf时，时，检查能否已有一样的结点，检查能否已有一样的结点，假设有，那么前往相应结点的假设有，那么前往相应结点的指针。指针。+*d+*acb5.3 S属性定义的自下而上计属性定义的自下而上计算算 综合属性可以由自下而上的分析器在分析输入时完成计算。分析器可以把文法符号的综合属性值放在它的栈里，每当归约时，根据出如今栈顶的产生式右部符号的属性来计算左部符号的综合属性。我们阐明如何扩展分析器的栈使之可以保管综合属性 S属性定义的翻译器可以借助LR分析器的生成器来实现 5.3 S属性定义的自下而上计

25、算属性定义的自下而上计算将将LR分析器分析栈中添加一个域来保管综合属性值分析器分析栈中添加一个域来保管综合属性值。. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop假设产生式假设产生式A XYZA XYZ的语义规那么是的语义规那么是A.a := f (X.x, Y.y, Z.z)A.a := f (X.x, Y.y, Z.z)，那么归约后：那么归约后：. . . . . .AA.a. . . . . .top4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. .

26、 . . . .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.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . .

27、. . .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-5+4nT*F3-5Fdigit+4nT15TT*F+4nE15ET4nE+15-nE+4

28、15-4nE+F15-4FdigitnE+T15-4TFnE19EE+TEn19-L19LEn在语法分析过程中进展语义分析和翻译，属性的计算顺序遭到语法分析建立分析树结点顺序的限制。一种自然的计算属性的顺序是按深度优先访问分析树结点的顺序，它顺应多种自底向上和自顶向下的翻译方法。L-属性定义可用于按深度优先顺序计算属性值。计算计算mm的承继属性；的承继属性；dfvisit(m) dfvisit(m) END; END; 计算计算n n的综合的综合属性属性 END; END; 2A的承继属性。的承继属性。每一个每一个S-属性定义都是属性定义都是L-属性定义。属性定义。12变量类型声明的语法制导定

29、义是变量类型声明的语法制导定义是一个一个L 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)的过程中何时执行语义动作。的过程中何时执行语义动作。翻译方式给出了运用语义规那么进

30、翻译方式给出了运用语义规那么进展计算的顺序。可看成是分析过程中翻译展计算的顺序。可看成是分析过程中翻译的注释。的注释。它是输入表达式它是输入表达式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 num

31、print(5)print (+)R print(8)print(5)print(+)addop Tprint() R print(8)print(5)print(+)print(2)print()ET9TRR-5+T2R 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 E1.val例例 数学排版言语数学排版言语EQN例例 数学排版言语数学排版言语EQN E sub 1

32、.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:=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

33、 := 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 出其翻译方式：出其翻译方式： TT1*F T val:=T1 val*F val解：解：TT1*F T val:=T1 val*F valSA AaAa边分析边翻译的方式能否用于承继属性？边分析边翻译的方式能否用于承继属性？属性的计算次序一定受分析方法所限定的分析属性的计算次序一定受分析方

34、法所限定的分析树结点建立次序的限制。树结点建立次序的限制。分析树的结点是自左向右生成。分析树的结点是自左向右生成。假设属性信息是自左向右流动，那么就有能够假设属性信息是自左向右流动，那么就有能够在分析的同时完成属性计算。在分析的同时完成属性计算。用翻译方式构造自顶向下翻译。用翻译方式构造自顶向下翻译。5.5.1 从翻译方式中消除左递归从翻译方式中消除左递归 对于一个翻译方式，假设采用自顶向下分析，必需对于一个翻译方式，假设采用自顶向下分析，必需消除左递归和提取左公因子，在改写根本文法时思索消除左递归和提取左公因子，在改写根本文法时思索属性值的计算。属性值的计算。例例6.14 带左递归的文法的翻

35、译方式构造方法？带左递归的文法的翻译方式构造方法？EE1+TEval:=E1val+TvalEE1-TEval:=E1val-TvalETE.val:=TvalT(E)Tval:=EvalTnumTval:=numval图6.13带左递归的文法的翻译方式例例6.14 图图6.13的带左递归的文法的翻译方式的带左递归的文法的翻译方式被转换成图被转换成图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

36、RR s:=R i T E T val:=E. val Tnum T val:=num val 承继属性承继属性i综合属性综合属性sE val=6Tval=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=5 R i=4T val=2 R i=6R s= 6R s= 6R s= 6E val=6关于左递归翻译方式更普通化的讨论关于左递归翻译方式更普通化的讨论左递归翻译方式左递归翻译方式 AA1Y AA1YA.a:=g(A1.a,Y.y) A.a:=g(A1.a,Y.y) AX AX A.a

37、:=f(X.x) A.a:=f(X.x) 6.26.2 每一个文法符号都有一个综合属性，用相应的小写字每一个文法符号都有一个综合属性，用相应的小写字母表示，母表示，g g和和f f是恣意函数。是恣意函数。 消除左递归，文法转换成消除左递归，文法转换成 AX R AX R RY R| RY R| 6.36.3 再思索语义动作，翻译方式变为：再思索语义动作，翻译方式变为： AX R i:=f(X x) R A. a:=R. s RY R1 i:=gR i,Y y R1 R s:=R1 s RR s:=R i 6.4 经过转换的翻译方式，运用经过转换的翻译方式，运用R的承继属性的承继属性i和综合属性

38、和综合属性s。Y2Y1XAAAA a=g(g(f(X x),Y1 y),Y2 y)A a=g(f(X x),Y1 y)A a=f(X x)AY2Y1Y1X XRRRR i=f(X x)R i=g(f(X x),Y1 y)R i=g(g(f(X x),Y1 y),Y2 y)例例 左递归的消除引起承继属性左递归的消除引起承继属性例例 左递归的消除引起承继属性左递归的消除引起承继属性产产 生生 式式语语 义义 规规 则则 E E1 + T E.nptr := mknode( +, E1.nptr, T.nptr)E TE.nptr := T.nptrT T1* *FT.nptr := mknode(

39、 * *, 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 E T T R.i := T.nptrR.i := T.nptrRRE.nptr := R.sE.nptr := R.sR R + +TTR1.i := mknod ( R1.i := mknod ( +, R.i, T.nptr), R.i, T.nptr)R1R1R.s

40、:= R1.sR.s := R1.sR R R.s := R.i R.s := R.i T T F F W.i := F.nptrW.i := F.nptrW WT.nptr := W.sT.nptr := W.sW W *FFW1.i := mknod ( W1.i := mknod ( *, W.i, F.nptr), W.i, F.nptr)W1W1W.s := W1.sW.s := W1.sW W W.s := W.i W.s := W.i 例例 左递归的消除引起承继属性左递归的消除引起承继属性E T R.i := T.nptr T + T + T + RE.nptr := R.sR

41、+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 例例 左递归的消除引起承继属性左递归的消除引起承继属性TF.nptrF.nptridi W*F.nptridnumididnum 5* * *指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分5.5.2 预测翻译器的

42、设计预测翻译器的设计把预测分析器的构造方法推行到翻译方案的实现把预测分析器的构造方法推行到翻译方案的实现产生式产生式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, s1, s : syntax_tree_node; addoplexeme

43、: 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属性定义的自上而下计属性定义的自上而下计算算4.3.4 用综合属性替代承继属性用综合属性替代承继属性Pascal的声

44、明，如的声明，如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 用综合属性替代承继属性用综合属性替代承继属性Pascal的声明，如的声明，如

45、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

46、. type := realD:L,idLidintegerT4.4 L属性的自下而上计算属性的自下而上计算 在自下而上分析的框架中实现在自下而上分析的框架中实现L L属性定义的方法属性定义的方法它能实现任何基于它能实现任何基于LL(1)LL(1)文法的文法的L L属性定义。属性定义。也能实现许多但不是一切的基于也能实现许多但不是一切的基于LR(1) LR(1) 的的L L属性定义。属性定义。4.4 L属性的自下而上计算属性的自下而上计算 4.4.1 删除翻译方案中嵌入的动作删除翻译方案中嵌入的动作E T RR + T print (+)R1 | T print ()R1 | T num pr

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

48、(+)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 () 4.4 L属性的自下而上计算属性的自下而上计算 4.4.2 分析栈上的承继属性分析栈上的承继属性例例 int p, q, r D T L.in := T.type LT

49、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 addtype (id.

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

51、 aACC.i := A.sC.i := A.sS S bABC bABCC.i := A.sC.i := A.sC C c cC.s := g(C.i)C.s := g(C.i)4.4 L属性的自下而上计算属性的自下而上计算 属性的位置不能预测属性的位置不能预测S S aAC aACC.i := A.sC.i := A.sS S bABC bABCC.i := A.sC.i := A.sC C c cC.s := g(C.i)C.s := g(C.i)添加标志非终结符添加标志非终结符S S aAC aACC.i := A.sC.i := A.sS S bABMC bABMCM.i := A.

52、s; C.i := M.sM.i := A.s; C.i := M.sC C c cC.s := g(C.i)C.s := g(C.i)M M M.s := M.iM.s := M.i4.4 L属性的自下而上计算属性的自下而上计算 4.4.3 模拟承继属性的计算模拟承继属性的计算承继属性是某个综合属性的一个函数承继属性是某个综合属性的一个函数S aACC.i := f (A.s)C cC.s := g(C.i)4.4 L属性的自下而上计算属性的自下而上计算 4.4.3 模拟承继属性的计算模拟承继属性的计算承继属性是某个综合属性的一个函数承继属性是某个综合属性的一个函数S aACC.i := f

53、 (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.ps :=B.ps B1sub B2.ps

54、 := shrink(B.ps) B2B.ht := disp (B1.ht, B2.ht ) B text B.ht := text.h B.ps 4.4 L属性的自下而上计算属性的自下而上计算 产产 生生 式式语语 义义 规规 则则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.

55、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 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 :=

56、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;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

57、.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 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.h

58、t := 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, B2.ht ) N N.s :=

59、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 :=

60、 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:= disp (valtop 3, valtop )N N.s := shrink(N.i) B text B.ht := text.h B.ps 4.4 L属性的自下而上计算属性的自下而上计算 产产 生生 式式代代 码码 段段S LB va