《【教学课件】第四章语法制导的翻译.ppt》由会员分享，可在线阅读，更多相关《【教学课件】第四章语法制导的翻译.ppt（110页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
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.val=T1.val F.val T F T.val=
2、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,c2,ck是是产生式右部文法符号的属性或产生式右部文法符号的属性或A的其它属性的其它属性继承属性继承属性：
3、如果：如果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(E)F.val=E.val F digit F.val=digit.lexval4.1语法制导的定义语法制导的定义注释分析树注释分析树:结点的属性值都标注出来的分析树
4、结点的属性值都标注出来的分析树8+5*2n的注释分析树的注释分析树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.val=2digit.lexval=54.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=54.1语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+F.val=5F.val
6、=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.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8
7、T.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.lexval=2LE.val=18nT.val=10E.val=8T.val=8F
8、.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语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.lexval=2LE.val=18nT.v
9、al=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语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成digit.l
10、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=54.1语法制导的定义语法制导的定义继承属性继承属性intid,id,id产产 生生 式式
11、 语语义义规规则则 D TL L.in=T.type T int T.type=integer T real T.type=real LL1,id L1.in=L.in;addType(id.entry,L.in)L id addType(id.entry,L.in)4.1语法制导的定义语法制导的定义例例 intid1,id2,id3的标注了部分属性的分析树的标注了部分属性的分析树不可能像像综合属性那样自下而上标注属性不可能像像综合属性那样自下而上标注属性DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,4.1语法
12、制导的定义语法制导的定义4.1.4属性依赖图属性依赖图例例 intid1,id2,id3的分析树（虚线）的依赖图的分析树（虚线）的依赖图（实线）（实线）D TLL.in=T.typeDintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.4属性依赖图属性依赖图例例 intid1,id2,id3的分析树（虚线）的依赖图的分析树（虚线）的依赖图（实线）（实线）LL1,id L1.in=L.in;addType(id.entry,L.in)DintT,id3LLLid2id1,1entry102
13、entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.4属性依赖图属性依赖图例例 intid1,id2,id3的分析树（虚线）的依赖图的分析树（虚线）的依赖图（实线）（实线）LidaddType(id.entry,L.in)DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.5属性计算次序属性计算次序1、拓扑排序、拓扑排序：结点的一种排序，使得边只会从该次序：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点中先出现的结点到后出
14、现的结点例例 1，2，3，4，5，6，7，8，9，10DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.5属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树构造输入的分析树DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.5属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树，构造属性依赖构造输入的分析树，构造属性依赖图图DintT
15、,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.5属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树，构造属性依赖构造输入的分析树，构造属性依赖图，对结点进行拓扑排序图，对结点进行拓扑排序DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.5属性计算次序属性计算次序2、属性计算次序：、属性计算次序：构造输入的分析树，构造属性依赖构造输入的分析树，构造属性依赖图，对
16、结点进行拓扑排序，按拓扑排序的次序计算图，对结点进行拓扑排序，按拓扑排序的次序计算属性属性DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义语义规则的计算方法语义规则的计算方法分析树方法：刚才介绍的方法，动态确定计分析树方法：刚才介绍的方法，动态确定计算次序，效率低算次序，效率低概念上的一般方法概念上的一般方法基于规则的方法：基于规则的方法：（编译器实现者）（编译器实现者）静态确静态确定定（编译器设计者提供的）（编译器设计者提供的）语义规则的计算语义规则的计算次序次序 适用于手工构造的方法适用
17、于手工构造的方法忽略规则的方法：忽略规则的方法：（编译器实现者）（编译器实现者）事先确事先确定属性的计算策略（如边分析边计算）定属性的计算策略（如边分析边计算）,（编（编译器设计者提供的）译器设计者提供的）语义规则必须符合所选语义规则必须符合所选分析方法的限制分析方法的限制 适用于自动生成的方法适用于自动生成的方法4.2S属性定义的自下而上计算属性定义的自下而上计算 语法树语法树语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字是作为算符和关键字是作为内部结点内部结点语法制导翻译可以基于分析树，也可以基于语法树语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：语法树的例子：
18、ifBthenS1 elseS28+5 2if-then-elseBS1S2+*2584.2S属性定义的自下而上计算属性定义的自下而上计算 构造语法树的语法制导定义构造语法树的语法制导定义产产 生生 式式语语义义规规则则 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(num,num.v
19、al)4.2S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4
20、.2S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属
21、性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的
22、自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的自下而上
23、计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+F.nptrF.nptridnumididnum5+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的自下而上计算属性定义的自下而上计算4.2.3S属性的自下而上计算属性的自下而上计算LR分析器的栈分析器的栈增加增加一个域来保存综合属性值一个域来保存综合属性值若产生式若产生式AXYZ的语义规则是的语义规则是A.a=f(X.x,Y.y,Z.z)，那么归约后：那么归约后：.AA.a.top.ZZ.zYY.yXX.x
24、.栈栈state valtop4.2S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 语语 义义 规规 则则 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(E)F.val=E.val F digit F.val=digit.lexval4.2S属性定义的自下而上计算属性定义的自下而上计算简单计算
25、器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 代代 码码 段段 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(E)F.val=E.val F digit F.val=digit.lexval4.2S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.
26、栈栈state valtop产产生生式式 代代 码码 段段 L E n print(valtop 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.2S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 代代 码码 段段 L E n print(val
27、top 1)E E1+T valtop 2=valtop 2+valtop 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.2S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2=valtop 2+valtop E
28、 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.2S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2=valtop 2+valtop E T T T1 F valtop 2=valtop 2 valtop T F T.val=F.val
29、F(E)F.val=E.val F digit F.val=digit.lexval4.2S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2=valtop 2+valtop E T T T1 F valtop 2=valtop 2 valtop T F F(E)F.val=E.val F digit F.val=digit.lexval4.2S属性定义的自下而上计算
30、属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2=valtop 2+valtop E T T T1 F valtop 2=valtop 2 valtop T F F(E)val top 2=val top 1 F digit F.val=digit.lexval4.2S属性定义的自下而上计算属性定义的自下而上计算简单计算器的语法制导定义改成栈操作代码简单计算器的语法制导定义改成栈操作代码
31、.ZZ.zYY.yXX.x.栈栈state valtop产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2=valtop 2+valtop E T T T1 F valtop 2=valtop 2 valtop T F F(E)val top 2=val top 1 F digit 4.3L属性定义的自上而下计算属性定义的自上而下计算边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制点建立次序的限制分析树的结点是自左向
32、右生成分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算析的同时完成属性计算4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.1L属性定义属性定义如如果果每每个个产产生生式式AX1Xj-1XjXn的的每每条条语语义义规规则则计计算算的的属属性性是是A的的综综合合属属性性；或或者者是是Xj 的继承属性，但它仅依赖：的继承属性，但它仅依赖：该产生式中该产生式中Xj左边符号左边符号X1,X2,Xj-1的属性；的属性；A的继承属性的继承属性S属性定义属于属性定义属于L属性定义属性定义4.3L属性定义的自上而下
33、计算属性定义的自上而下计算变量类型声明的语法制导定义是一个变量类型声明的语法制导定义是一个L属性定义属性定义产产 生生 式式 语语义义规规则则 D TL L.in=T.type T int T.type=integer T real T.type=real LL1,id L1.in=L.in;addType(id.entry,L.in)L id addType(id.entry,L.in)4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.2翻译方案翻译方案例例 把有加和减的中缀表达式翻译成后缀表达式把有加和减的中缀表达式翻译成后缀表达式如果输入是如果输入是8+5 2，则输出是，则输出
34、是85+2 E T RR addopT print(addop.lexeme)R1|T numprint(num.val)E T R numprint(8)Rnumprint(8)addopTprint(+)R numprint(8)addopnumprint(5)print(+)R print(8)print(5)print(+)addopTprint()Rprint(8)print(5)print(+)print(2)print()4.3L属性定义的自上而下计算属性定义的自上而下计算例例 数学排版语言数学排版语言EQNEsub1.valS B B B1 B2B B1 sub B2B tex
35、tE1.val4.3L属性定义的自上而下计算属性定义的自上而下计算例例 数学排版语言数学排版语言EQN（语法制导定义）（语法制导定义）Esub1.val产产生生式式语语义义规规则则S B B.ps=10;S.ht=B.htB B1 B2B1.ps=B.ps;B2.ps=B.ps;B.ht=max(B1.ht,B2.ht)B B1 sub B2B1.ps=B.ps;B2.ps=shrink(B.ps);B.ht=disp(B1.ht,B2.ht)B text B.ht=text.h B.psE1.val4.3L属性定义的自上而下计算属性定义的自上而下计算例例 数学排版语言数学排版语言EQN（翻译
36、方案）（翻译方案）S B.ps=10B继承属性的计算继承属性的计算BS.ht=B.ht位于位于B的左边的左边4.3L属性定义的自上而下计算属性定义的自上而下计算例例 数学排版语言数学排版语言EQN（翻译方案）（翻译方案）S B.ps=10B综合属性的计算综合属性的计算BS.ht=B.ht放在右部末端放在右部末端4.3L属性定义的自上而下计算属性定义的自上而下计算例例 数学排版语言数学排版语言EQN（翻译方案）（翻译方案）S B.ps=10BS.ht=B.htB B1.ps=B.ps B1B2.ps=B.ps B2B.ht=max(B1.ht,B2.ht)B B1.ps=B.psB1sub B2
37、.ps=shrink(B.ps)B2B.ht=disp(B1.ht,B2.ht)B text B.ht=text.h B.ps4.3L属性定义的自上而下计算属性定义的自上而下计算例例 左递归的消除引起继承属性左递归的消除引起继承属性产产 生生 式式语语义义规规则则 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
38、.nptr=mkLeaf(num,num.val)4.3L属性定义的自上而下计算属性定义的自上而下计算E TR.i=T.nptrT+T+T+RE.nptr=R.sR+TR1.i=mkNode(+,R.i,T.nptr)R1R.s=R1.sR R.s=R.iT FW.i=F.nptrWT.nptr=W.sW FW1.i=mkNode(,W.i,F.nptr)W1W.s=W1.sW W.s=W.iF 产生式部分不再给出产生式部分不再给出4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的
39、入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分部分4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分部分4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分
40、部分4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分部分4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分部分4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi
41、 W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分部分4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分部分4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向
42、符号表中指向符号表中b的入口的入口i W si W 略去了略去了E TR T部分部分4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.3预测翻译器的设计预测翻译器的设计把预测分析器的构造方法推广到翻译方案的实现把预测分析器的构造方法推广到翻译方案的实现产生式产生式R+TR|的分析过程的分析过程voidR()if(lookahead=+)match(+);T();R();else/什么也不做什么也不做/4.3L属性定义的自上而下计算属性定义的自上而下计算syntaxTreeNode R(syntaxTreeNode i)syntaxTreeNode nptr,i1,s1,s;chara
43、ddoplexeme;if(lookahead=+)/产生式产生式R+T R/addoplexeme=lexval;match(+);nptr=T();i1=mkNode(addoplexeme,i,nptr);s1=R(i1);s=s1;elses=i;/产生式产生式 R /returns;R:i,sT:nptr+:addoplexeme4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.4用综合属性代替继承属性用综合属性代替继承属性Pascal的声明，如的声明，如m,n:integerD L:T（非（非L属性定义）属性定义）T integer|charL L,id|id信息从右向左
44、流，归约从左向右，两者不一致信息从右向左流，归约从左向右，两者不一致4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.4用综合属性代替继承属性用综合属性代替继承属性Pascal的声明，如的声明，如m,n:integerD L:T（非（非L属性定义）属性定义）T integer|charL L,id|id等所需信息获得后再归约等所需信息获得后再归约改成从右向左归约改成从右向左归约D idLL,idL|:TT integer|charD:L,idLidintegerT4.3L属性定义的自上而下计算属性定义的自上而下计算DidL addtype(id.entry,L.type)L,id L
45、1L.type=L1.Type;addtype(id.entry,L1.type)L:TL.type=T.typeTintegerT.type=integerTreal T.type=realD:L,idLidintegerT4.4L属性的自下而上计算属性的自下而上计算在自下而上分析的框架中实现在自下而上分析的框架中实现L属性定义的方法属性定义的方法它能实现任何基于它能实现任何基于LL(1)文法的文法的L属性定义属性定义也能实现许多（但不是所有的）基于也能实现许多（但不是所有的）基于LR(1)的的L属性定义属性定义4.4L属性的自下而上计算属性的自下而上计算 删除翻译方案中嵌入的动作删除翻译方
46、案中嵌入的动作E T RR+T print(+)R1|T print()R1|T numprint(num.val)在文法中加入产生在文法中加入产生 的的标记非终结符标记非终结符，让每个嵌入动，让每个嵌入动作由不同标记非终结符作由不同标记非终结符M代表，并把该动作放在产代表，并把该动作放在产生式生式M 的右端的右端E T RR+T M R1|T N R1|T numprint(num.val)M print(+)N print()这些动作的一个重要这些动作的一个重要特点：特点：没有引用原来产生式没有引用原来产生式文法符号的属性文法符号的属性4.4L属性的自下而上计算属性的自下而上计算4.4.2
47、分析栈上的继承属性分析栈上的继承属性例例intp,q,rD TL.in=T.type LTintT.type=integerTrealT.type=realLL1.in=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)4.4L属性的自下而上计算属性的自下而上计算4.4.2分析栈上的继承属性分析栈上的继承属性1、属性位置能预测、属性位置能预测例例intp,q,rD TL.in=T.type LTintT.type=integerTrealT.type=realLL1.in=L.inL1,idaddtype(id.entry,L.in
48、)Lidaddtype(id.entry,L.in)DTLL,rL,qpint type ininin4.4L属性的自下而上计算属性的自下而上计算4.4.2分析栈上的继承属性分析栈上的继承属性1、属性位置能预测、属性位置能预测例例intp,q,rD TL.in=T.type LTintT.type=integerTrealT.type=realLL1.in=L.inL1,idaddtype(id.entry,L.in)Lidaddtype(id.entry,L.in)DTLL,rL,qpint type ininin继承属性的计算可继承属性的计算可以略去，以略去，引用继承属引用继承属性的地方改
49、成引用其性的地方改成引用其他符号的综合属性他符号的综合属性4.4L属性的自下而上计算属性的自下而上计算DTLL,rL,qpint type ininin产产 生生 式式 代代 码码 段段 D TLTintvaltop=integerTrealvaltop=realLL1,idaddType(valtop,valtop 3)LidaddType(valtop,valtop 1)4.4L属性的自下而上计算属性的自下而上计算2、属性的位置不能预测、属性的位置不能预测SaACC.i=A.sSbABCC.i=A.sC cC.s=g(C.i)增加标记非终结符，使得位置可以预测增加标记非终结符，使得位置可以
50、预测SaACC.i=A.sSbABMCM.i=A.s;C.i=M.sC cC.s=g(C.i)M M.s=M.i4.4L属性的自下而上计算属性的自下而上计算2、属性的位置不能预测、属性的位置不能预测SaACC.i=A.sSbABCC.i=A.sC cC.s=g(C.i)增加标记非终结符，使得位置可以预测增加标记非终结符，使得位置可以预测SaACC.i=A.sSbABMCM.i=A.s;C.i=M.sC cC.s=g(C.i)还得考虑还得考虑M.sM M.s=M.i 计算的可预测计算的可预测4.4L属性的自下而上计算属性的自下而上计算 模拟继承属性的计算模拟继承属性的计算继承属性是某个综合属性的