第四章第四章语法制导的翻译语法制导的翻译本章内容本章内容介绍一种形式化的语义描述方法：介绍一种形式化的语义描述方法：语法制导语法制导的翻译的翻译，包括它的两种具体形式：，包括它的两种具体形式：语法制导语法制导的定义和翻译方案的定义和翻译方案介绍语法制导翻译的实现方法介绍语法制导翻译的实现方法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=F.val F(E) F.val=E.val F digit F.val=digit.lexval4.1语法制导的定义语法制导的定义4.1.1语法制导定义的形式语法制导定义的形式基础文法基础文法每个文法符号有一组属性每个文法符号有一组属性每个文法产生式每个文法产生式A 有一组形式为有一组形式为b= f(c1,c2,ck)的语义规则的语义规则，其中其中f是函数，是函数，b和和c1,c2,ck是该产生式文法符号的属性是该产生式文法符号的属性综合属性：综合属性：如果如果b是是A的属性，的属性，c1,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(E) F.val=E.val F digit F.val=digit.lexval4.1语法制导的定义语法制导的定义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语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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语法制导的定义语法制导的定义分析树各结点属性的计算可以自下而上地完成分析树各结点属性的计算可以自下而上地完成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语法制导的定义语法制导的定义注释分析树注释分析树: :结点的属性值都标注出来的分析树结点的属性值都标注出来的分析树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继承属性继承属性intid,id,id产产 生生 式式 语语义义规规则则 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语法制导的定义语法制导的定义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 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义4.1.5属性计算次序属性计算次序拓扑排序拓扑排序：结点的一种排序，使得边只会从该次序中：结点的一种排序，使得边只会从该次序中先出现的结点到后出现的结点先出现的结点到后出现的结点例：例：1，2，3，4，5，6，7，8，9，10DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义属性计算次序属性计算次序 构造输入的分析树构造输入的分析树DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义属性计算次序属性计算次序 构造输入的分析树，构造属性依赖图构造输入的分析树，构造属性依赖图DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义属性计算次序属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行构造输入的分析树，构造属性依赖图，对结点进行拓扑排序拓扑排序DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义属性计算次序属性计算次序 构造输入的分析树，构造属性依赖图，对结点进行构造输入的分析树，构造属性依赖图，对结点进行拓扑排序，按拓扑排序的次序计算属性拓扑排序，按拓扑排序的次序计算属性DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type4.1语法制导的定义语法制导的定义语义规则的计算方法语义规则的计算方法分析树方法：前面介绍的方法分析树方法：前面介绍的方法4.1语法制导的定义语法制导的定义语义规则的计算方法语义规则的计算方法分析树方法：前面介绍的方法分析树方法：前面介绍的方法基于规则的方法：静态确定基于规则的方法：静态确定语义规则的计算语义规则的计算次序次序4.1语法制导的定义语法制导的定义语义规则的计算方法语义规则的计算方法分析树方法：前面介绍的方法分析树方法：前面介绍的方法基于规则的方法：静态确定基于规则的方法：静态确定语义规则的计算语义规则的计算次序次序忽略规则的方法：忽略规则的方法：事先确定属性的计算策略事先确定属性的计算策略（如边分析边计算），那么语义规则的设计（如边分析边计算），那么语义规则的设计必须符合所选分析方法的限制必须符合所选分析方法的限制4.2S属性定义的自下而上计算属性定义的自下而上计算4.2.1 语法树语法树语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字是作为算符和关键字是作为内部结点内部结点语法制导翻译可以基于分析树，也可以基于语法树语法制导翻译可以基于分析树，也可以基于语法树语法树的例子：语法树的例子：if-then-elseBS1S2+*2584.2S属性定义的自下而上计算属性定义的自下而上计算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.entry) F num F.nptr=mkLeaf (num,num.val) 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.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属性定义的自下而上计算属性定义的自下而上计算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属性定义的自下而上计算属性定义的自下而上计算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属性定义的自下而上计算属性定义的自下而上计算a+5 b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+ F.nptrF.nptridnumididnum5 + +指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口4.2S属性定义的自下而上计算属性定义的自下而上计算4.2.3S属性的自下而上计算属性的自下而上计算将将LR分析器分析器增加增加一个域来保存综合属性值一个域来保存综合属性值.ZZ.zYY.yXX.x.栈栈state valtop4.2S属性定义的自下而上计算属性定义的自下而上计算4.2.3S属性的自下而上计算属性的自下而上计算将将LR分析器分析器增加增加一个域来保存综合属性值一个域来保存综合属性值.ZZ.zYY.yXX.x.栈栈state valtop若产生式若产生式AXYZ的语义规则是的语义规则是A.a=f (X.x,Y.y,Z.z)4.2S属性定义的自下而上计算属性定义的自下而上计算4.2.3S属性的自下而上计算属性的自下而上计算将将LR分析器分析器增加增加一个域来保存综合属性值一个域来保存综合属性值.ZZ.zYY.yXX.x.栈栈state valtop若产生式若产生式AXYZ的语义规则是的语义规则是A.a=f (X.x,Y.y,Z.z)，那么归约后：那么归约后：.AA.a.top4.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属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码.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.栈栈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 (valtop 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 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 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属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码.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属性定义的自下而上计算属性定义的自下而上计算台式计算器的语法制导定义改成栈操作代码台式计算器的语法制导定义改成栈操作代码.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属性定义的自上而下计算属性定义的自上而下计算边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制点建立次序的限制4.3L属性定义的自上而下计算属性定义的自上而下计算边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制点建立次序的限制分析树的结点是自左向右生成分析树的结点是自左向右生成4.3L属性定义的自上而下计算属性定义的自上而下计算边分析边翻译的方式能否用于继承属性边分析边翻译的方式能否用于继承属性？属性的计算次序一定受分析方法所限定的分析树结属性的计算次序一定受分析方法所限定的分析树结点建立次序的限制点建立次序的限制分析树的结点是自左向右生成分析树的结点是自左向右生成如果属性信息是自左向右流动，那么就有可能在分如果属性信息是自左向右流动，那么就有可能在分析的同时完成属性计算析的同时完成属性计算4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.1L属性定义属性定义如如果果每每个个产产生生式式A X1X2Xn 的的每每条条语语义义规规则则计计算算的的属属性性是是A的的综综合合属属性性；或或者者是是Xj 的的继承属性，继承属性，1 j n, , 但它仅依赖：但它仅依赖：该产生式中该产生式中Xj左边符号左边符号X1,X2,Xj-1的属性；的属性；A的继承属性的继承属性4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.1L属性定义属性定义如如果果每每个个产产生生式式A X1X2Xn 的的每每条条语语义义规规则则计计算算的的属属性性是是A的的综综合合属属性性；或或者者是是Xj 的的继承属性，继承属性，1 j n, , 但它仅依赖：但它仅依赖：该产生式中该产生式中Xj左边符号左边符号X1,X2,Xj-1的属性；的属性；A的继承属性的继承属性S属性定义属于属性定义属于L属性定义属性定义4.3L属性定义的自上而下计算属性定义的自上而下计算变量类型声明的语法制导定义是一个变量类型声明的语法制导定义是一个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，则输出是，则输出是85+2 4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.2翻译方案翻译方案例例把有加和减的中缀表达式翻译成后缀表达式把有加和减的中缀表达式翻译成后缀表达式如果输入是如果输入是8+5 2，则输出是，则输出是85+2 E T RT +T + T + R addopT print (addop.lexeme)R1| T numprint (num.val)4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.2翻译方案翻译方案例例把有加和减的中缀表达式翻译成后缀表达式把有加和减的中缀表达式翻译成后缀表达式如果输入是如果输入是8+5 2，则输出是，则输出是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 textE1.val4.3L属性定义的自上而下计算属性定义的自上而下计算例例数学排版语言数学排版语言EQNEsub1.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属性定义的自上而下计算属性定义的自上而下计算例例数学排版语言数学排版语言EQNS 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.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.nptr=mkLeaf (num,num.val) 4.3L属性定义的自上而下计算属性定义的自上而下计算E TR.i =T.nptrRE.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.i4.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.i4.3L属性定义的自上而下计算属性定义的自上而下计算TF.nptrF.nptridi W F.nptridnumididnum5 指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中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;charaddoplexeme;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 : TT integer|charL L,id|id4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.4用综合属性代替继承属性用综合属性代替继承属性Pascal的声明，如的声明，如m,n:integerD L : TT integer|charL L,id|id改成从右向左归约改成从右向左归约D idLL ,idL |:TT integer|char4.3L属性定义的自上而下计算属性定义的自上而下计算4.3.4用综合属性代替继承属性用综合属性代替继承属性Pascal的声明，如的声明，如m,n:integerD L : TT integer|charL L,id|id改成从右向左归约改成从右向左归约D idLL ,idL |:TT integer|charD:L,idLidintegerT4.3L属性定义的自上而下计算属性定义的自上而下计算DidL addtype(id.entry,L.type)L,id L1L.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属性的自下而上计算属性的自下而上计算4.4.1 删除翻译方案中嵌入的动作删除翻译方案中嵌入的动作E T RR +T print (+)R1| T print ( )R1| T numprint (num.val) 4.4L属性的自下而上计算属性的自下而上计算4.4.1 删除翻译方案中嵌入的动作删除翻译方案中嵌入的动作E T RR +T print (+)R1| T print ( )R1| T numprint (num.val)在文法中加入产生在文法中加入产生 的的标记非终结符标记非终结符，让每个嵌入动，让每个嵌入动作由不同标记非终结符作由不同标记非终结符M代表，并把该动作放在产代表，并把该动作放在产生式生式M 的右端的右端4.4L属性的自下而上计算属性的自下而上计算4.4.1 删除翻译方案中嵌入的动作删除翻译方案中嵌入的动作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分析栈上的继承属性分析栈上的继承属性例例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分析栈上的继承属性分析栈上的继承属性属性位置能预测属性位置能预测例例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 ininin4.4L属性的自下而上计算属性的自下而上计算DTLL,rL,qpint type ininin产产 生生 式式 代代 码码 段段 D TLTintvaltop=integerTrealvaltop=realLL1,idaddType(valtop,valtop 3)LidaddType(valtop,valtop 1)4.4L属性的自下而上计算属性的自下而上计算属性的位置不能预测属性的位置不能预测SaACC.i=A.sSbABCC.i=A.sC cC.s=g(C.i)4.4L属性的自下而上计算属性的自下而上计算属性的位置不能预测属性的位置不能预测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 M.s=M.i4.4L属性的自下而上计算属性的自下而上计算4.4.3 模拟继承属性的计算模拟继承属性的计算继承属性是某个综合属性的一个函数继承属性是某个综合属性的一个函数SaACC.i=f (A.s)C cC.s=g(C.i)4.4L属性的自下而上计算属性的自下而上计算4.4.3 模拟继承属性的计算模拟继承属性的计算继承属性是某个综合属性的一个函数继承属性是某个综合属性的一个函数SaACC.i=f (A.s)C cC.s=g(C.i)增加标记非终结符，把增加标记非终结符，把f(A.s)的计算移到对标记的计算移到对标记非终结符归约时进行非终结符归约时进行SaANCN.i=A.s;C.i=N.sN N.s=f (N.i)C cC.s=g(C.i)4.4L属性的自下而上计算属性的自下而上计算例例数学排版语言数学排版语言EQNS 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.ps=shrink(B.ps)B2B.ht=disp(B1.ht,B2.ht )B text B.ht=text.h B.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 语语 义义 规规 则则 S LB B.ps=L.s;S.ht=B.htL L.s =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.iB B1 sub NB2B1.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.ps4.4L属性的自下而上计算属性的自下而上计算举例说明举例说明SM sB L s BBtext BsubN sBtext text4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段S LB B.ps=L.s;S.ht=B.htL L.s =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.iB B1 sub NB2B1.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.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段S LB valtop 1=valtopL L.s =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.iB B1 sub NB2B1.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.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段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.iB B1 sub NB2B1.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.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段S LB valtop 1=valtopL valtop+1 =10B B1 MB2 valtop 2= max(valtop 2,valtop)M M.s =M.iB B1 sub NB2B1.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.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段S LB valtop 1=valtopL valtop+1 =10B B1 MB2 valtop 2= max(valtop 2,valtop)M valtop+1 =valtop 1B B1 sub NB2B1.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.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段S LB valtop 1=valtopL valtop+1 =10B B1 MB2 valtop 2= max(valtop 2,valtop)M valtop+1 =valtop 1B B1 sub NB2valtop 3=disp(valtop 3,valtop )N N.s =shrink(N.i)B text B.ht=text.h B.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段S LB valtop 1=valtopL valtop+1 =10B B1 MB2 valtop 2= max(valtop 2,valtop)M valtop+1 =valtop 1B B1 sub NB2valtop 3=disp(valtop 3,valtop )N valtop+1 =shrink(valtop 2)B text B.ht=text.h B.ps4.4L属性的自下而上计算属性的自下而上计算产产生生式式 代代 码码 段段S LB valtop 1=valtopL valtop+1 =10B B1 MB2 valtop 2= max(valtop 2,valtop)M valtop+1 =valtop 1B B1 sub NB2valtop 3=disp(valtop 3,valtop )N valtop+1 =shrink(valtop 2)B text valtop=valtop valtop 1本本章章要要点点语语义义规规则则的的两两种种描描述述方方法法：语语法法制制导导的的定定义义和和翻译方案翻译方案设设计计简简单单问问题题的的语语法法制制导导定定义义和和翻翻译译方方案案，这这是本章的重点和难点是本章的重点和难点S属性的自下而上计算（边分析边计算）属性的自下而上计算（边分析边计算）L属性的自上而下计算（边分析边计算）属性的自上而下计算（边分析边计算）L属性的自下而上计算（边分析边计算）属性的自下而上计算（边分析边计算）不再介绍先分析后计算的方法不再介绍先分析后计算的方法不能边分析边计算的情况是存在的，见不能边分析边计算的情况是存在的，见5.6节节例例 题题 1下面是产生字母表下面是产生字母表 =0,1,2上数字串的一个上数字串的一个文法：文法：SDSD|2D0|1写一个语法制导定义，判断它接受的句子是否为回文写一个语法制导定义，判断它接受的句子是否为回文数数S Sprint(S.val)SD1S1D2S.val=(D1.val=D2.val)andS1.valS2S.val=trueD0D.val=0D1D.val=1例例 题题 2为下面文法写一个语法制导的定义，用为下面文法写一个语法制导的定义，用S的综合属性的综合属性val给给出下面文法中出下面文法中S产生的二进制数的值。例如，输入产生的二进制数的值。例如，输入101.101时，时，S.val=5.625。不得修改文法，但属性使用不得修改文法，但属性使用没有限制没有限制SL.R|LLLB|BRBR|BB0|1S.LLBLBBRRBRBB例例 题题 2SL.RS.val=L.val+R.valSLS.val=L.valLL1BL.val=L1.val 2+B.valLBL.val=B.valRBR1R.val=R1.val/2+B.val/2RBR.val=B.val /2B0B.val=0B1B.val=1例例 题题 3给出把中缀表达式翻译成没有冗余括号的中缀表给出把中缀表达式翻译成没有冗余括号的中缀表达式的语法制导定义。例如达式的语法制导定义。例如, ,因为因为 和和 是左结合是左结合, ,(a (b+c) (d)可以重写成可以重写成a (b+c) d先先把把表表达达式式的的括括号号都都去去掉掉，然然后后在在必必要要的的地地方方再加括号再加括号去掉表达式中的冗余括号，保留必要的括号去掉表达式中的冗余括号，保留必要的括号例例 题题 3第一种方法第一种方法S Eprint(E.code)EE1+TifT.op=plusthenE.code =E1.code|“+”|“(”|T.code|“)”elseE.code=E1.code|“+”|T.code;E.op =plusETE.code=T.code;E.op =T.op例例 题题 3TT1 Fif(F.op=plus)or(F.op =times)thenifT1.op=plusthenT.code=“(”|T1.code|“)”|“ ”|“(”|F.code|“)”elseT.code=T1.code|“ ”|“(”|F.code|“)”elseifT1.op=plusthenT.code=“(”|T1.code|“)”|“ ”|F.codeelseT.code=T1.code|“ ”|F.code;T.op =times例例 题题 3T FT.code = F. code; T. op = F. opF idF. code = id. lexeme; F. op = idF ( E )F. code = E. code; F. op = E. op例例 题题 3第二种方法第二种方法给给E，T和和F两个继承属性两个继承属性left_op和和right_op分别表示左右两侧算符的优先级分别表示左右两侧算符的优先级给给它它们们一一个个综综合合属属性性self_op表表示示自自身身主主算算符符的的优先级优先级再再给给一一个个综综合合属属性性code表表示示没没有有冗冗余余括括号号的的代代码码分分别别用用1和和2表表示示加加和和乘乘的的优优先先级级，用用3表表示示id和和(E)的的优优先先级级，用用0表表示示左左侧侧或或右右侧侧没没有有运运算算对对象的情况象的情况例例 题题 3S EE. left_op =0; E. right_op =0; print (E. code )E E1 + TE1. left_op = E. left_op; E1. right_op =1;T. left_op =1; T. right_op = E. right_op;E.code=E1.code| “+” | T. code; E. self_op =1;E TT. left_op = E. left_op; T. right_op = E. right_op;E. code = T. code; E. self_op = T. self_op例例 题题 3T T1 F . . .T F . . .F idF. code = id. lexeme; F. self_op = 3例例 题题 3F ( E )E. left_op =0; E. right_op =0;F. self_op = if(F. left_op = F. right_op) then E. self_op else 3F. code = if(F. left_op = F. right_op) then E. code else “(”| E. code |“)”习习 题题第一次第一次4.1，4.3，4.5第二次第二次 4.7，4.9,4.10第三次第三次4.13，4.14