工学语法制导的翻译.pptx

主讲人：范主讲人：范 敏敏陈意云陈意云 张张 昱昱高等教育出版社高等教育出版社编编 译译 原原 理理 -4-42024/4/7 周日第4章 语法制导的翻译2引入复习q词法分析的任务和正规式的作用q语法分析的任务和文法的作用思考q语言结构的属性如何计算？何时计算？属性值如何存放？2024/4/7 周日第4章 语法制导的翻译3第第1章章编译器概述编译器概述第第2章章词法分析词法分析第第3章章语法分析语法分析第第4章章语法制导的翻译语法制导的翻译第第5章章类型检查类型检查第第6章章运行时存储空间的组织和管理运行时存储空间的组织和管理第第7章章中间代码生成中间代码生成第第8章章代码生成代码生成第第9章章*代码优化代码优化第第10章章*编译系统和运行系统编译系统和运行系统第第11章章*面向对象语言的编译面向对象语言的编译第第12章章*函数式语言的编译函数式语言的编译目目 录录2024/4/7 周日第4章 语法制导的翻译44.1语法制导的定义语法制导的定义4.2S属性定义的自下而上计算属性定义的自下而上计算4.3L属性定义的自上而下计算属性定义的自上而下计算4.4L属性的自下而上计算属性的自下而上计算4.5递归计算递归计算第第4 4章章 语法制导的翻译语法制导的翻译2024/4/7 周日第4章 语法制导的翻译5本章内容介绍一种形式化的语义描述方法q语法制导的翻译，包括它的两种具体形式：语法制导的定义和翻译方案介绍语法制导的翻译的实现方法2024/4/7 周日第4章 语法制导的翻译6本章学习目标掌握综合属性、继承属性、语法树、翻译方案等概念掌握语法制导的定义方法掌握S属性和L属性的计算方法2024/4/7 周日第4章 语法制导的翻译74.1 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.lexval注意基础注意基础文法与拓文法与拓广文法的广文法的区别区别2024/4/7 周日第4章 语法制导的翻译8基础文法基础文法q基础文法是语法制导定义中的文法。其中，每基础文法是语法制导定义中的文法。其中，每个文法符号都有一组可以用于个文法符号都有一组可以用于计算计算的属性的属性每个产生式每个产生式A 有一组形式为有一组形式为b:=f(c1,c2,ck)的语义规则。其中的语义规则。其中f是函数，是函数，b,c1,c2,ck是文法符号的属性是文法符号的属性语义规则语义规则q一组计算表达式一组计算表达式q计算相应产生式中文法符号的属性值计算相应产生式中文法符号的属性值4.1.1 4.1.1 语法制导定义的形式语法制导定义的形式2024/4/7 周日第4章 语法制导的翻译9文法符号属性分类文法符号属性分类q继承属性继承属性：如果：如果b是产生是产生式右部某个文法符号式右部某个文法符号X的的属性，属性，c1,c2,ck是产是产生式左部文法符号生式左部文法符号A的属的属性性或产生式右部文法符号或产生式右部文法符号属性属性q综合属性综合属性：如果如果b是是A的的属性，属性，c1,c2,ck是产是产生式右部文法符号属性或生式右部文法符号属性或A的继承属性的继承属性bbb:=f(c1,c2,ck)A X B属属于于子子结结点点B属属于于父父结结点点2024/4/7 周日第4章 语法制导的翻译10S属性定义属性定义：仅使用仅使用综合综合属性的语法制导定义属性的语法制导定义产产生生式式 语语义义规规则则 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.2 4.1.2 综合属性综合属性如何计算综如何计算综合属性值？合属性值？2024/4/7 周日第4章 语法制导的翻译11q8+5*2n的计算：的计算：1.根据基础文法画出推导出根据基础文法画出推导出句子的分析树句子的分析树digitLEnTETFdigitT+*FFdigit2024/4/7 周日第4章 语法制导的翻译12q8+5*2n的计算：的计算：2.标出分析树中每个结点的属性标出分析树中每个结点的属性（如果有）（如果有）digit.lexvalLE.valn 换行符换行符T.valE.valT.valF.valdigit.lexvalT.val+*F.valF.valdigit.lexval注意注释注意注释分析树与分析树与分析树之分析树之间的区别间的区别2024/4/7 周日第4章 语法制导的翻译13q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexvalLE.valnT.valE.valT.valF.valdigit.lexval=8T.val+*F.valF.valdigit.lexval2024/4/7 周日第4章 语法制导的翻译14q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexvalLE.valnT.valE.valT.valF.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2024/4/7 周日第4章 语法制导的翻译15q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexvalLE.valnT.valE.valT.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2024/4/7 周日第4章 语法制导的翻译16q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval2024/4/7 周日第4章 语法制导的翻译17q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.valF.valdigit.lexval=52024/4/7 周日第4章 语法制导的翻译18q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val+*F.val=5F.valdigit.lexval=52024/4/7 周日第4章 语法制导的翻译19q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexvalLE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.valdigit.lexval=52024/4/7 周日第4章 语法制导的翻译20q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexval=2LE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.valdigit.lexval=52024/4/7 周日第4章 语法制导的翻译21q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexval=2LE.valnT.valE.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52024/4/7 周日第4章 语法制导的翻译22q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexval=2LE.valnT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52024/4/7 周日第4章 语法制导的翻译23q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52024/4/7 周日第4章 语法制导的翻译24q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=52024/4/7 周日第4章 语法制导的翻译25q8+5*2n的计算：的计算：3.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到右地完成digit.lexval=2LE.val=18nT.val=10E.val=8T.val=8F.val=8digit.lexval=8T.val=5+*F.val=5F.val=2digit.lexval=5打印打印E属性值属性值Print(E.val)2024/4/7 周日第4章 语法制导的翻译26利用分析树对S属性定义中综合属性的计算方法小结q画出句子（词法记号流符号串）的分析树q标出每个结点的属性（如果有）q根据语义规则自下而上、从左到右完成各个结点属性的计算2024/4/7 周日第4章 语法制导的翻译27intid,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.3 4.1.3 继承属性继承属性如何计算继如何计算继承属性值？承属性值？2024/4/7 周日第4章 语法制导的翻译28intid1,id2,id3的注释分析树的注释分析树q分析树分析树Dint T,id3 L L Lid2id1,2024/4/7 周日第4章 语法制导的翻译29intid1,id2,id3的注释分析树的注释分析树q在注释分析树每个在注释分析树每个L结点，除传递继承属性结点，除传递继承属性in给子给子结点结点L1外，外，addtype过程在符号表中将过程在符号表中将L右子结点右子结点上标识符上标识符id的类型记为整型：的类型记为整型：addtype(id.entry,L.in)DintT.type=integer,id3L.in=integerL.in=integerL.in=integerid2id1,包含结点属性包含结点属性T.typeid.entryL.in，虚拟属性虚拟属性L1.in:=L.in2024/4/7 周日第4章 语法制导的翻译30intid1,id2,id3的分析树的依赖图的分析树的依赖图描述结点属性间依赖关系的有向图称为依赖图描述结点属性间依赖关系的有向图称为依赖图D TL L.in:=T.type 4.1.4 4.1.4 属性依赖图属性依赖图DintTLin 54type所有属性可所有属性可用结点表示用结点表示2024/4/7 周日第4章 语法制导的翻译31intid1,id2,id3的分析树的依赖图的分析树的依赖图LL1,id L1.in:=L.in;addtype(id.entry,L.in)DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54typeaddtype(id.entry,L.in)导致的导致的虚拟属性虚拟属性注意：注意：L有两个属性有两个属性(继继承属性承属性in和虚拟属性和虚拟属性)2024/4/7 周日第4章 语法制导的翻译32拓扑排序拓扑排序：属性结点出现顺序的一种排序，使得有：属性结点出现顺序的一种排序，使得有向边只从该次序中先出现的结点指向后出现的结点向边只从该次序中先出现的结点指向后出现的结点q例：例：1，2，3，4，5，6，7，8，9，104.1.5 4.1.5 属性计算次序属性计算次序DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type只有结点属只有结点属性传递的方性传递的方向性不够向性不够2024/4/7 周日第4章 语法制导的翻译33属性计算过程属性计算过程 （1 1）构造输入串的分析树）构造输入串的分析树DintT,id3LLLid2id1,2024/4/7 周日第4章 语法制导的翻译34属性计算过程属性计算过程 （1 1）构造输入串的分析树；（）构造输入串的分析树；（2 2）构造属性依赖图）构造属性依赖图DintT,id3LLLid2id1,entryentryentryininin type2024/4/7 周日第4章 语法制导的翻译35属性计算过程属性计算过程 （1 1）构造输入串的分析树；（）构造输入串的分析树；（2 2）构造属性依赖图；）构造属性依赖图；（3 3）对属性结点进行拓扑排序）对属性结点进行拓扑排序DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54typeaddtype(id.entry,L.in)导致的导致的虚拟属性虚拟属性2024/4/7 周日第4章 语法制导的翻译36属性计算过程属性计算过程 （1 1）构造输入串的分析树；（）构造输入串的分析树；（2 2）构造属性依赖图；）构造属性依赖图；（3 3）对属性结点进行拓扑排序；（）对属性结点进行拓扑排序；（4 4）按拓扑排序）按拓扑排序的次序计算属性的次序计算属性DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type2024/4/7 周日第4章 语法制导的翻译37DintT,id3LLLid2id1,1entry102 entry3entryin 98in 76in 54type属性计算过程属性计算过程a4:=integer;a5:=a4;addtype(id3.entry,a5);a7:=a5;addtype(id2.entry,a7);a9:=a7;addtype(id1.entry,a9);2024/4/7 周日第4章 语法制导的翻译38语义规则的计算方法语义规则的计算方法2024/4/7 周日第4章 语法制导的翻译39语义规则的计算方法语义规则的计算方法分析树方法：前面介绍方法（编译速分析树方法：前面介绍方法（编译速度慢）度慢）2024/4/7 周日第4章 语法制导的翻译40语义规则的计算方法语义规则的计算方法分析树方法：前面介绍方法（编译速分析树方法：前面介绍方法（编译速度慢）度慢）基于规则的方法：基于事先静态确定基于规则的方法：基于事先静态确定语义规则的计算次序（手工构造编译语义规则的计算次序（手工构造编译器，时空改善）器，时空改善）2024/4/7 周日第4章 语法制导的翻译41语义规则的计算方法语义规则的计算方法分析树方法：前面介绍方法（编译速分析树方法：前面介绍方法（编译速度慢）度慢）基于规则的方法：基于事先静态确定基于规则的方法：基于事先静态确定语义规则的计算次序（手工构造编译语义规则的计算次序（手工构造编译器，时空改善）器，时空改善）忽略规则的方法：忽略规则的方法：事先确定属性的计事先确定属性的计算策略（如边分析边计算），那么语算策略（如边分析边计算），那么语义规则的设计必须符合所选分析方法义规则的设计必须符合所选分析方法的限制（时空改善）的限制（时空改善）2024/4/7 周日第4章 语法制导的翻译42本节小结介绍了语法制导定义、继承属性、综合属性、属性依赖图、拓扑顺序等概念详细介绍了利用分析树计算属性的方法简单对比了属性计算的三种方法2024/4/7 周日第4章 语法制导的翻译43作业P140：12024/4/7 周日第4章 语法制导的翻译44思考语言结构属性计算的基础是什么？依赖图和拓扑顺序有什么作用？它们对计算S属性定义中的综合属性是否有用？计算语言结构属性的步骤是什么？本节在语法制导定义的基础上通过分析树研究了属性计算次序的问题，那么如何在此基础上编程实现呢？2024/4/7 周日第4章 语法制导的翻译454.2 4.2 S S属性定义的自下而上计算属性定义的自下而上计算 语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字作为算符和关键字作为内部结点内部结点q语法树的例子：语法树的例子：if-then-elseBS1S24.2.1 4.2.1 语法树语法树算符运算对象if B then S1 else S2复习复习S属性定义？属性定义？2024/4/7 周日第4章 语法制导的翻译464.2 4.2 S S属性定义的自下而上计算属性定义的自下而上计算 语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字作为算符和关键字作为内部结点内部结点q语法树的例子：语法树的例子：if-then-elseBS1S24.2.1 4.2.1 语法树语法树算符运算对象if B then S1 else S28+5*2算符优算符优先级别先级别？2024/4/7 周日第4章 语法制导的翻译474.2 4.2 S S属性定义的自下而上计算属性定义的自下而上计算 语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字作为算符和关键字作为内部结点内部结点q语法树的例子：语法树的例子：if-then-elseBS1S2+*84.2.1 4.2.1 语法树语法树算符运算对象if B then S1 else S28+5*22024/4/7 周日第4章 语法制导的翻译484.2 4.2 S S属性定义的自下而上计算属性定义的自下而上计算 语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字作为算符和关键字作为内部结点内部结点q语法树的例子：语法树的例子：if-then-elseBS1S2+*2584.2.1 4.2.1 语法树语法树算符运算对象if B then S1 else S28+5*22024/4/7 周日第4章 语法制导的翻译494.2 4.2 S S属性定义的自下而上计算属性定义的自下而上计算 语法树是分析树的浓缩表示语法树是分析树的浓缩表示：算符和关键字是作为算符和关键字是作为内部结点内部结点语法制导翻译可以基于分析树，也可以基于语法树语法制导翻译可以基于分析树，也可以基于语法树if-then-elseBS1S2+*2584.2.1 4.2.1 语法树语法树算符运算对象if B then S1 else S28+5*22024/4/7 周日第4章 语法制导的翻译504.2.2 4.2.2 构造语法树的语法制导定义构造语法树的语法制导定义语法树的存储语法树的存储q语法树的结点可以用有若干域的记录来实现语法树的结点可以用有若干域的记录来实现q对于对于算符结点算符结点：一个域存放算符，该域作为该结点的标记，：一个域存放算符，该域作为该结点的标记，其余两个域含指向运算对象的指针其余两个域含指向运算对象的指针三地址三地址q对于对于基本运算对象结点基本运算对象结点：一个域存放运算对象类别，另一：一个域存放运算对象类别，另一个域存放其值个域存放其值二地址二地址q用于语法制导翻译时，一个结点可能还有其它域来保存加用于语法制导翻译时，一个结点可能还有其它域来保存加在该结点的其它属性值（即域中保存属性值存储位置的指在该结点的其它属性值（即域中保存属性值存储位置的指针）针）结点的结点的类型类型2024/4/7 周日第4章 语法制导的翻译51产产 生生 式式语语义义规规则则 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)用于构造算术表达式语法树的语法制导定义用于构造算术表达式语法树的语法制导定义mkleaf(id,entry)：建立标识符建立标识符id的结点，结点的的结点，结点的entry域用于存放该标识符条目的域用于存放该标识符条目的指针指针2024/4/7 周日第4章 语法制导的翻译52产产 生生 式式语语义义规规则则 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)用于构造算术表达式语法树的语法制导定义用于构造算术表达式语法树的语法制导定义mkleaf(num,val)：建立数建立数num的结点，结点的的结点，结点的val域用于域用于存放该存放该数值数值2024/4/7 周日第4章 语法制导的翻译53产产 生生 式式语语义义规规则则 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)用于构造算术表达式语法树的语法制导定义用于构造算术表达式语法树的语法制导定义mknode(op,left,right)：建立建立算符算符op的结点，指针域的结点，指针域left和和right分别存放该算符左、右运算对象的指针分别存放该算符左、右运算对象的指针2024/4/7 周日第4章 语法制导的翻译54a+5*b的语法树的构造的语法树的构造P112结点属性结点属性E.nptrT.nptrF.nptrE.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口变量变量aleft right数值数值5变量变量b2024/4/7 周日第4章 语法制导的翻译55a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译56a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译57a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译58a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译59a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译60a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译61a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译62a+5*b的语法树的构造的语法树的构造E.nptrT.nptrE.nptrT.nptrF.nptridT.nptr+*F.nptrF.nptridnumididnum5*+指向符号表中指向符号表中a的入口的入口指向符号表中指向符号表中b的入口的入口aleft right5b自下而上、从左自下而上、从左到右构造语法树到右构造语法树2024/4/7 周日第4章 语法制导的翻译63a+5*b的语法树的构造的语法树的构造+id *num id2024/4/7 周日第4章 语法制导的翻译64S属性可以由属性可以由自下而上分析器自下而上分析器在语法分析输入时完成在语法分析输入时完成计算，即计算，即“边分析边计算边分析边计算”q自下而上分析器用栈保存已经分析的子树的信息自下而上分析器用栈保存已经分析的子树的信息，S属性属性定义的翻译器可以借助定义的翻译器可以借助LR分析器的生成器来实现分析器的生成器来实现qLR分析器分析器可以把文法符号的综合属性放在它的栈内可以把文法符号的综合属性放在它的栈内，每，每当当归约归约时，根据出现在时，根据出现在栈顶栈顶的产生式右部符号串中符号的的产生式右部符号串中符号的属性来计算左部符号的综合属性属性来计算左部符号的综合属性4.2.3 4.2.3 S S属性的自下而上计算属性的自下而上计算复习复习LR分析器分析器的工作原理：的工作原理：栈内可以不存栈内可以不存储文法符号储文法符号综合属性综合属性来自来自于子节点或自于子节点或自身的继承属性身的继承属性2024/4/7 周日第4章 语法制导的翻译65将将LR分析器分析器增加增加一个域来保存综合属性值一个域来保存综合属性值ZZ.zYY.yXX.x.栈栈state valtop2024/4/7 周日第4章 语法制导的翻译66将将LR分析器分析器增加增加一个域来保存综合属性值一个域来保存综合属性值ZZ.zYY.yXX.x.栈栈state valtop若产生式若产生式AXYZ的的语义规则语义规则是是A.a:=f(X.x,Y.y,Z.z)右部符号从左右部符号从左至右压入栈内至右压入栈内2024/4/7 周日第4章 语法制导的翻译67将将LR分析器分析器增加增加一个域来保存综合属性值一个域来保存综合属性值ZZ.zYY.yXX.x.若产生式若产生式AXYZ的的语义规则语义规则是是A.a:=f(X.x,Y.y,Z.z)，那么归约后：那么归约后：.AA.a.栈栈state valtoptoptop=top-2Top2024/4/7 周日第4章 语法制导的翻译68例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码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.lexvalTop2024/4/7 周日第4章 语法制导的翻译69例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码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.lexvalTop2024/4/7 周日第4章 语法制导的翻译70例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码nEE.val.产产生生式式 代代 码码 段段 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.lexval栈栈state valtop:=左边为归约后左左边为归约后左部文法符号的属性部文法符号的属性值，下标为值的存值，下标为值的存储位置储位置Top2024/4/7 周日第4章 语法制导的翻译71例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码TT.val+EE.val.产产生生式式 代代 码码 段段 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.lexval栈栈state valtop:=左边为归约后左左边为归约后左部文法符号的属性部文法符号的属性值，下标为值的存值，下标为值的存储位置储位置Top2024/4/7 周日第4章 语法制导的翻译72例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码TT.val.产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2:=valtop 2+valtop E T valtop不变不变 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.lexval栈栈state valtop:=左边为归约后左左边为归约后左部文法符号的属性部文法符号的属性值，下标为值的存值，下标为值的存储位置储位置2024/4/7 周日第4章 语法制导的翻译73例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码FF.val*TT.val.产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2:=valtop 2+valtop E T valtop不变不变 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.lexval栈栈state valtop:=左边为归约后左左边为归约后左部文法符号的属性部文法符号的属性值，下标为值的存值，下标为值的存储位置储位置Top2024/4/7 周日第4章 语法制导的翻译74例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码FF.val.产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2:=valtop 2+valtop E T valtop不变不变 T T1*F valtop 2:=valtop 2 valtop T F valtop不变不变 F(E)F.val:=E.val F digit F.val:=digit.lexval栈栈state valtop:=左边为归约后左左边为归约后左部文法符号的属性部文法符号的属性值，下标为值的存值，下标为值的存储位置储位置2024/4/7 周日第4章 语法制导的翻译75例：台式计算器的语法制导定义改成栈操作代码例：台式计算器的语法制导定义改成栈操作代码)EE.val(.产产生生式式 代代 码码 段段 L E n print(valtop 1)E E1+T valtop 2:=valtop 2+valtop E T valtop不变不变 T T1*F valtop 2:=valtop 2 valtop T F valtop不变不变 F(E)val top 2:=val top 1 F digit F.val:=digit.lexval栈栈state valtop:=左边为归约后左左边为归约后左部文法符号的属性部文法符号的属性值