第五章语法制导的翻译5.1-5.3

《第五章语法制导的翻译5.1-5.3》由会员分享，可在线阅读，更多相关《第五章语法制导的翻译5.1-5.3（51页珍藏版）》请在金锄头文库上搜索。

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

2、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.lexval5.1 语法制导的定义语法制导的定义5.1.1 语法制导定义的形式语法制导定义的形式v基础文法基础文法v每个文法符号有一组属性每个文法符号有一组属性v每个文法产生式每个文法产生式A 有有一组形式为一组形式为b=f(c1, c2, , ck )的语义规则的语义规则，其中其中b和和c1, c2, , ck 是该产生式文法符号的属性，是该产生式文法符号的属性，f 是函数是函数v综合属性：

3、综合属性：如果如果b是是A的属性，的属性，c1 , c2 , , ck 是产生是产生式右部文法符号的属性或式右部文法符号的属性或A的其它属性的其它属性v继承属性继承属性：如果：如果b是右部某文法符号是右部某文法符号X的属性的属性5.1 语法制导的定义语法制导的定义5.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.

4、val T F T.val = F.val F (E) F.val = E.val F digit F.val = digit.lexval5.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 = 55.1 语法制导的定义语法制导的定义分析树各

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

6、8T.val = 5+ F.val = 5F.val = 2digit.lexval = 55.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval

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

8、1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.val = 8T.val = 8F.va

9、l = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 55.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可

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

11、 2digit.lexval = 55.1 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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 语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval = 2LE.val = 18nT.val = 10E.

12、val = 8T.val = 8F.val = 8digit.lexval = 8T.val = 5+ F.val = 5F.val = 2digit.lexval = 55.1 语法制导的定义语法制导的定义5.1.3 继承属性继承属性int id, id, id产产 生生 式式 语语 义义 规规 则则 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) 5.1 语法

13、制导的定义语法制导的定义v例例 int id1, id2, id3的标注了部分属性的分析树的标注了部分属性的分析树不可能像像综合属性那样自下而上标注属性不可能像像综合属性那样自下而上标注属性DintT.type = integer,id3L.in = integerL.in = integerL.in = integerid2id1,5.1 语法制导的定义语法制导的定义5.1.4 属性依赖图属性依赖图例例 int id1, id2, id3的分析树（虚线）的依赖图的分析树（虚线）的依赖图（实线）（实线） D TL L.in = T.typeD intT,id3LLLid2id1,1 entry

14、102 entry3 entryin 98in 76in 54 type5.1 语法制导的定义语法制导的定义5.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 type5.1 语法制导的定义语法制导的定义5.1.4 属性依赖图属性依赖图例例 int id1, id2, id3的分析树（虚线）的依赖图

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

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

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

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

19、性的计算策略（如边分析边计算）定属性的计算策略（如边分析边计算）, ,（编（编译器设计者提供的）译器设计者提供的）语义规则必须符合所选语义规则必须符合所选分析方法的限制分析方法的限制 适用于自动生成的方法适用于自动生成的方法5.2 S属性定义的自下而上计算属性定义的自下而上计算5.2.1 语法树语法树语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字是作为算符和关键字是作为内部结点内部结点语法制导翻译可以基于分析树，也可以基于语法树语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：语法树的例子： if B then S1 else S2 8 + 5 2if-then-els

20、eBS1S2+*2585.2 S属性定义的自下而上计算属性定义的自下而上计算5.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.entry) F num F.nptr = mkLeaf (nu

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

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

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

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

25、 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口5.2 S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum 5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口5.2 S属性定义的自下而上计算属性定义的自下而上计算5.2.3 S属性的自下而上计算属性的自下而上计算LR分析器的栈分析器的栈增加增加一个域来保存综合属性值一个域来保存综合属性值若产生式若产生式A XY

26、Z的语义规则是的语义规则是A.a = f (X.x, Y.y, Z.z)，那么归约后：那么归约后：. . . . .AA.a. . . . .top. . . . .ZZ. zYY. yXX.x. . . . .栈栈 state valtop5.2 S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码 . . . . .ZZ. zYY. yXX.x. . . . .栈栈 state valtop产产 生生 式式 语语 义义 规规 则则 L E n print (E.val) E E1 + T E.val =E1 .val +

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

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

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

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

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

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

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

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