第四章 语法制导的翻译

1、第四章第四章 语法制导的翻译语法制导的翻译 本章内容本章内容1、介绍一种形式化的语义描述方法：、介绍一种形式化的语义描述方法：语法制导的语法制导的翻译翻译，它包括两种具体形式，它包括两种具体形式语法制导的定义语法制导的定义翻译方案翻译方案2、介绍语法制导翻译的实现方法、介绍语法制导翻译的实现方法4.1 语法制导的定义语法制导的定义 例例 简单台式计算器的语法制导定义简单台式计算器的语法制导定义产产 生生 式式 语语 义义 规规 则则 L E n print (E.val) E E1 + T E.val = E1 .val + T.val E T E.val = T.val T T1 F T.v

2、al = T1.val F.val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval4.1 语法制导的定义语法制导的定义4.1.1 语法制导定义的形式语法制导定义的形式 基础文法基础文法 每个文法符号有一组属性每个文法符号有一组属性 每个文法产生式每个文法产生式A 有有一组形式为一组形式为b=f(c1, c2, , ck )的语义规则的语义规则，其中其中b和和c1, c2, , ck 是该产生式文法符号的属性，是该产生式文法符号的属性，f 是函数是函数 综合属性：综合属性：如果如果b是是A的属性，的属性，c1

3、, c2 , , ck 是产生式右部文法符号的属性或是产生式右部文法符号的属性或A的其它属性的其它属性 继承属性继承属性：如果：如果b是右部某文法符号是右部某文法符号X的属性的属性4.1 语法制导的定义语法制导的定义4.1.2 综合属性综合属性S属性定义属性定义：仅使用综合属性的语法制导定义仅使用综合属性的语法制导定义产产 生生 式式 语语 义义 规规 则则 L E n print (E.val) E E1 + T E.val = E1 .val + T.val E T E.val = T.val T T1 F T.val = T1.val F.val T F T.val = F.val F

4、(E) F.val = E.val F digit F.val = digit.lexval4.1 语法制导的定义语法制导的定义 例例 8+5* *2 n的注释分析树的注释分析树digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18

5、nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定

6、义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexv

7、al = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.l

8、exval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval

9、= 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val =

10、8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属

11、性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.

12、val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义注释分析树注释分析树: :结点的属性值都标注出来的分析树结点的属性值都标注出来的分析树digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 54.1 语法制导的定义语法制导的定义4.1.3 继承属性继承属性int id, id, id产产 生生 式式 语语 义义 规规 则则 D TL L.in = T.type T in

13、t T. type = integer T real T. type = real L L1, id L1.in = L.in; addType(id.entry, L.in) L id addType(id.entry, L.in) 4.1 语法制导的定义语法制导的定义 例例 int id1, id2, id3的注释分析树的注释分析树DintT.type = integer,id3L.in = integerL.in = integerL.in = integerid2id1,4.1 语法制导的定义语法制导的定义4.1.4 属性依赖图属性依赖图 例例 int id1, id2, id3的分析

14、树的依赖图的分析树的依赖图 D TL L.in = T.typeD intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 语法制导的定义语法制导的定义4.1.4 属性依赖图属性依赖图 例例 int id1, id2, id3的分析树的依赖图的分析树的依赖图L L1, id L1.in = L.in; addType (id.entry, L.in) D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 语法制导的定义语法制导的定义4.1.4

15、 属性依赖图属性依赖图 例例 int id1, id2, id3的分析树的依赖图的分析树的依赖图L id addType (id.entry, L.in) D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 语法制导的定义语法制导的定义4.1.5 属性计算次序属性计算次序1、拓扑排序、拓扑排序：结点的一种排序，使得边只会从该次：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点序中先出现的结点到后出现的结点 例例 1，2，3，4，5，6，7，8，9，10D intT,id3LLLid2id1,1 en

16、try102 entry3 entryin 98in 76in 54 type4.1 语法制导的定义语法制导的定义4.1.5 属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树构造输入的分析树D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 语法制导的定义语法制导的定义4.1.5 属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树，构造属性依构造输入的分析树，构造属性依赖图赖图D intT,id3LLLid2id1,1 entry102 entry3 entryi

17、n 98in 76in 54 type4.1 语法制导的定义语法制导的定义4.1.5 属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树，构造属性依构造输入的分析树，构造属性依赖图，对结点进行拓扑排序赖图，对结点进行拓扑排序D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 语法制导的定义语法制导的定义4.1.5 属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树，构造属性依构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计赖图，对结点进行拓扑

18、排序，按拓扑排序的次序计算属性算属性D intT,id3LLLid2id1,1 entry102 entry3 entryin 98in 76in 54 type4.1 语法制导的定义语法制导的定义语义规则的计算方法语义规则的计算方法 分析树方法：刚才介绍的方法，动态确定计分析树方法：刚才介绍的方法，动态确定计算次序，效率低算次序，效率低概念上的一般方法概念上的一般方法 基于规则的方法：基于规则的方法：（编译器实现者）（编译器实现者）静态确静态确定定（编译器设计者提供的）（编译器设计者提供的）语义规则的计算语义规则的计算次序次序 适用于手工构造的方法适用于手工构造的方法 忽略规则的方法：忽略规

19、则的方法：（编译器实现者）（编译器实现者）事先确事先确定属性的计算策略（如边分析边计算）定属性的计算策略（如边分析边计算）, ,（编（编译器设计者提供的）译器设计者提供的）语义规则必须符合所选语义规则必须符合所选分析方法的限制分析方法的限制 适用于自动生成的方法适用于自动生成的方法4.2 S属性定义的自下而上计算属性定义的自下而上计算4.2.1 语法树语法树 语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字是作为算符和关键字是作为内部结点内部结点 语法制导翻译可以基于分析树，也可以基于语法树语法制导翻译可以基于分析树，也可以基于语法树 语法树的例子：语法树的例子： if B th

20、en S1 else S2 8 + 5 2if-then-elseBS1S2+*2584.2 S属性定义的自下而上计算属性定义的自下而上计算4.2.2 构造语法树的语法制导定义构造语法树的语法制导定义产产 生生 式式语语 义义 规规 则则 E E1 + T E.nptr = mkNode( +, E1.nptr, T.nptr) E T E.nptr = T.nptr T T1 F T.nptr = mkNode( , T1.nptr, F.nptr) T F T.nptr = F.nptr F (E) F.nptr = E.nptr F id F.nptr = mkLeaf (id, id.

21、entry) F num F.nptr = mkLeaf (num, num.val) 4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnu

22、mididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.

23、nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+

24、F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptrid

25、T.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2 S属性定义的自下而上计算属性定义的自下而上计算4.2.3 S属性的自下而上计算属性的自下而上计算LR分析器的栈分析器的栈增加增加一个

26、域来保存综合属性值一个域来保存综合属性值若产生式若产生式A XYZ的语义规则是的语义规则是A.a = f (X.x, Y.y, Z.z)，那么归约后：那么归约后：. . . . . .AA.a. . . . . .top. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 语语 义义 规规 则则 L

27、E n print (E.val) E E1 + T E.val =E1 .val +T.val E T E.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.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n

28、 print (E.val) E E1 + T E.val =E1 .val +T.val E T E.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.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n pr

29、int (val top 1 ) E E1 + T E.val =E1 .val +T.val E T E.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.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n

30、print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T E.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.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码

31、段段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T 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.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L

32、E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段

33、段 L E n print (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) F.val = E.val F digit F.val = digit.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n pr

34、int (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit F.val = digit.lexval4.2 S属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码. . . . . .ZZ. zYY. yXX.x. . . . . .栈栈 state valtop产产 生生 式式 代代 码码 段段 L E n print

35、 (val top 1 ) E E1 + T val top 2 =val top 2+val top E T T T1 F val top 2 = val top 2 val top T F F (E) val top 2 =val top 1 F digit 4.3 L属性定义的自上而下计算属性定义的自上而下计算边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？ 属性的计算次序一定受分析方法所限定的分析树结属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制点建立次序的限制 分析树的结点是自左向右生成分析树的结点是自左向右生成 如果属性信息是自左向右流动，那么就

36、有可能在分如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算析的同时完成属性计算4.3 L属性定义的自上而下计算属性定义的自上而下计算4.3.1 L属性定义属性定义 如果每个产生式如果每个产生式A X1 X2 Xn 的每条语义的每条语义规则计算的属性是规则计算的属性是A的综合属性；或者是的综合属性；或者是Xj 的继承属性，的继承属性，1 j n, , 但它仅依赖：但它仅依赖： 该产生式中该产生式中Xj左边符号左边符号X1, X2, , Xj-1的属性；的属性； A的继承属性的继承属性 S属性定义属于属性定义属于L属性定义属性定义4.3 L属性定义的自上而下计算属性定义的自上而下计

37、算变量类型声明的语法制导定义是一个变量类型声明的语法制导定义是一个L属性定义属性定义 产产 生生 式式 语语 义义 规规 则则 D TL L.in = T.type T int T. type = integer T real T. type = real L L1, id L1.in = L.in; addType(id.entry, L.in) L id addType(id.entry, L.in) 4.3 L属性定义的自上而下计算属性定义的自上而下计算4.3.2 翻译方案翻译方案 例例 把有加和减的中缀表达式翻译成后缀表达式把有加和减的中缀表达式翻译成后缀表达式如果输入是如果输入是8+

38、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( )4.3 L属性定义的自上而下计算属性定义的自上而下计算 例例 数学排版语言数学排版语言EQ

39、N E sub 1 .val S B B B1 B2 B B1 sub B2 B text E1.val4.3 L属性定义的自上而下计算属性定义的自上而下计算 例例 数学排版语言数学排版语言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 =B.ps; B2.ps = shrink(B.ps); B.ht = disp (B1.ht, B2.ht ) B t

40、ext B.ht = text.h B.ps E1.val4.3 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) B2B.ht = disp (B1.ht, B2.ht ) B text B.ht = text.h B.ps 4.3 L属性定义的自上而下计算属性定义的自上而下计算 例例 数学排版语言数学排版语言E

41、QN S B.ps = 10 B继承属性的计算继承属性的计算BS.ht = B.ht 位于位于B的左边的左边 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 4.3 L属性定义的自上而下计算属性定义的自上而下计算 例例 数学排版语言数学排版语言EQN S B.ps = 10 BS.ht = B.ht B综合属性的计算综合属性的计算 B

42、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 4.3 L属性定义的自上而下计算属性定义的自上而下计算 例例 左递归的消除引起继承属性左递归的消除引起继承属性产产 生生 式式语语 义义 规规 则则 E E1 + T E.nptr = mkNode( +, E1.nptr, T.nptr) E T E.nptr =

43、T.nptr T T1 F T.nptr = mkNode( , T1.nptr, F.nptr) T F T.nptr = F.nptr F (E) F.nptr = E.nptr F id F.nptr = mkLeaf (id, id.entry) F num F.nptr = mkLeaf (num, num.val) 4.3 L属性定义的自上而下计算属性定义的自上而下计算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.n

44、ptr = W.sW FW1.i = mkNode ( , W.i, F.nptr)W1W.s = W1.sW W.s = W.i F 产生式部分没有给出产生式部分没有给出4.3 L属性定义的自上而下计算属性定义的自上而下计算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.sW FW1.i = mkNode ( , W.i, F.nptr)W1W.s = W1.sW W.s = W.i

45、F 产生式部分没有给出产生式部分没有给出4.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性

46、定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnu

47、mididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向

48、符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum 5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T 部分部分4.3 L属性定义的自上而下计算属性定义的自上而下计算4.3.3 预测翻译器的设计预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现把预测分析器的构造方法推广到翻译方案的实现产生式产生式R +TR | 的分析过程的分析过程void R( ) if (loo

49、kahead = + ) match ( + ); T( ); R( );else / 什么也不做什么也不做 /4.3 L属性定义的自上而下计算属性定义的自上而下计算syntaxTreeNode R (syntaxTreeNode i) syntaxTreeNode nptr, i1, s1, s;char addoplexeme;if (lookahead = + ) / 产生式产生式 R +T R /addoplexeme = lexval;match(+ ); nptr = T();i1 = mkNode(addoplexeme, i , nptr);s1 = R (i1); s = s

50、1;else s = i; / 产生式产生式 R /return s;R : i, sT : nptr+ : addoplexeme4.3 L属性定义的自上而下计算属性定义的自上而下计算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, i

51、d | 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,idLidintegerT4.4 L属性的自下而上计算属性

52、的自下而上计算在自下而上分析的框架中实现在自下而上分析的框架中实现L属性定义的方法属性定义的方法 它能实现任何基于它能实现任何基于LL(1)文法的文法的L属性定义属性定义 也能实现许多（但不是所有的）基于也能实现许多（但不是所有的）基于LR(1) 的的L属性定义属性定义4.4 L属性的自下而上计算属性的自下而上计算4.4.1 删除翻译方案中嵌入的动作删除翻译方案中嵌入的动作E T RR + T print (+)R1 | T print ( )R1 | T num print (num.val)在文法中加入产生在文法中加入产生 的的标记非终结符标记非终结符，让每个嵌入动，让每个嵌入动作由不同标

53、记非终结符作由不同标记非终结符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 = re

54、alL L1.in = L.in L1, id addtype (id.entry, L.in )L id addtype (id.entry, L.in )4.4 L属性的自下而上计算属性的自下而上计算4.4.2 分析栈上的继承属性分析栈上的继承属性1、属性位置能预测、属性位置能预测例例 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 )DT

55、LL,rL,qpint type ininin4.4 L属性的自下而上计算属性的自下而上计算4.4.2 分析栈上的继承属性分析栈上的继承属性1、属性位置能预测、属性位置能预测例例 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继承属性的计算可继承属性的计算可以略去，以略去，引用继承属引用继承

56、属性的地方改成引用其性的地方改成引用其他符号的综合属性他符号的综合属性4.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属性的自下而上计算属性的自下而上计算2、属性的位置不能预测、属性的位置不能预测S aACC.i = A.sS bABCC.i = A.sC cC.s = g(

57、C.i) 增加标记非终结符，使得位置可以预测增加标记非终结符，使得位置可以预测S aACC.i = A.sS bABMCM.i = A.s; C.i = M.sC cC.s = g(C.i)M M.s = M.i4.4 L属性的自下而上计算属性的自下而上计算2、属性的位置不能预测、属性的位置不能预测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.sM M

58、.s = M.i 计算的可预测计算的可预测4.4 L属性的自下而上计算属性的自下而上计算4.4.3 模拟继承属性的计算模拟继承属性的计算继承属性是某个综合属性的一个函数继承属性是某个综合属性的一个函数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

59、= 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 4.4 L属性的自下而上计算属性的自下而上计算产产 生生 式式 语语 义义 规规 则则 S LB B.ps = L.s; S.ht = B.ht L L.s = 10 将将B.ps存入栈中，便于引用存入栈中，便于引用B B1 MB2 B1.ps = B.

60、ps; M.i = B.ps;B2.ps = M.s;B.ht = max(B1.ht, B2.ht ) M M.s = M.iB 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 B.ps = L.s; S.ht = B.ht L L.s = 10 将将B.ps存入栈中，便于引用存入栈中，便于引用B B1