工学语法制导的翻译.pptx
《工学语法制导的翻译.pptx》由会员分享,可在线阅读,更多相关《工学语法制导的翻译.pptx(156页珍藏版)》请在咨信网上搜索。
1、主讲人:范主讲人:范 敏敏陈意云陈意云 张张 昱昱高等教育出版社高等教育出版社编编 译译 原原 理理 -4-42024/4/7 周日第4章 语法制导的翻译2引入复习q词法分析的任务和正规式的作用q语法分析的任务和文法的作用思考q语言结构的属性如何计算?何时计算?属性值如何存放?2024/4/7 周日第4章 语法制导的翻译3第第1章章编译器概述编译器概述第第2章章词法分析词法分析第第3章章语法分析语法分析第第4章章语法制导的翻译语法制导的翻译第第5章章类型检查类型检查第第6章章运行时存储空间的组织和管理运行时存储空间的组织和管理第第7章章中间代码生成中间代码生成第第8章章代码生成代码生成第第9章
2、章*代码优化代码优化第第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语法制导的翻译,包括它的两种具体形式:语法制导
3、的定义和翻译方案介绍语法制导的翻译的实现方法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:
4、=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
5、计算相应产生式中文法符号的属性值计算相应产生式中文法符号的属性值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
6、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 综合属性综合属性如何计算综如何计算综合属性值?合属性值?2
7、024/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注意注释注意注释分析树与分析树与分析树之分析树之间的区别间的区别202
8、4/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
9、=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.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完
10、成自下而上、从左到右地完成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章 语法制
11、导的翻译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=
12、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.分析树各结点属性的计算可以分析树各结点属性的
13、计算可以自下而上、从左到右地完成自下而上、从左到右地完成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.v
14、al=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.分析树各结点属性的计算可以分析树各结点属性的计算可以自下而上、从左到右地完成自下而上、从左到
15、右地完成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.lexva
16、l=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 addty
17、pe(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的类型记为整型:的类型记为整型:a
18、ddtype(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所有属性可所有属性可用结点表示
19、用结点表示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拓扑排序拓扑排序:属性结点出现顺序的一种排序,使得有:属性结点出现顺序的一种排序,使
20、得有向边只从该次序中先出现的结点指向后出现的结点向边只从该次序中先出现的结点指向后出现的结点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属性计算过程属性计算过程 (
21、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)导致的导致的虚拟属性虚拟属性
22、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属性计算过程属性计算过
23、程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语义规则的计算方法语义规则的计算方法分析树方法:前面介绍方法(编译速分析树方法:前面介绍方法(编译速度慢)度
24、慢)基于规则的方法:基于事先静态确定基于规则的方法:基于事先静态确定语义规则的计算次序(手工构造编译语义规则的计算次序(手工构造编译器,时空改善)器,时空改善)2024/4/7 周日第4章 语法制导的翻译41语义规则的计算方法语义规则的计算方法分析树方法:前面介绍方法(编译速分析树方法:前面介绍方法(编译速度慢)度慢)基于规则的方法:基于事先静态确定基于规则的方法:基于事先静态确定语义规则的计算次序(手工构造编译语义规则的计算次序(手工构造编译器,时空改善)器,时空改善)忽略规则的方法:忽略规则的方法:事先确定属性的计事先确定属性的计算策略(如边分析边计算),那么语算策略(如边分析边计算),那
25、么语义规则的设计必须符合所选分析方法义规则的设计必须符合所选分析方法的限制(时空改善)的限制(时空改善)2024/4/7 周日第4章 语法制导的翻译42本节小结介绍了语法制导定义、继承属性、综合属性、属性依赖图、拓扑顺序等概念详细介绍了利用分析树计算属性的方法简单对比了属性计算的三种方法2024/4/7 周日第4章 语法制导的翻译43作业P140:12024/4/7 周日第4章 语法制导的翻译44思考语言结构属性计算的基础是什么?依赖图和拓扑顺序有什么作用?它们对计算S属性定义中的综合属性是否有用?计算语言结构属性的步骤是什么?本节在语法制导定义的基础上通过分析树研究了属性计算次序的问题,那么
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 工学 语法 制导 翻译
1、咨信平台为文档C2C交易模式,即用户上传的文档直接被用户下载,收益归上传人(含作者)所有;本站仅是提供信息存储空间和展示预览,仅对用户上传内容的表现方式做保护处理,对上载内容不做任何修改或编辑。所展示的作品文档包括内容和图片全部来源于网络用户和作者上传投稿,我们不确定上传用户享有完全著作权,根据《信息网络传播权保护条例》,如果侵犯了您的版权、权益或隐私,请联系我们,核实后会尽快下架及时删除,并可随时和客服了解处理情况,尊重保护知识产权我们共同努力。
2、文档的总页数、文档格式和文档大小以系统显示为准(内容中显示的页数不一定正确),网站客服只以系统显示的页数、文件格式、文档大小作为仲裁依据,平台无法对文档的真实性、完整性、权威性、准确性、专业性及其观点立场做任何保证或承诺,下载前须认真查看,确认无误后再购买,务必慎重购买;若有违法违纪将进行移交司法处理,若涉侵权平台将进行基本处罚并下架。
3、本站所有内容均由用户上传,付费前请自行鉴别,如您付费,意味着您已接受本站规则且自行承担风险,本站不进行额外附加服务,虚拟产品一经售出概不退款(未进行购买下载可退充值款),文档一经付费(服务费)、不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
4、如你看到网页展示的文档有www.zixin.com.cn水印,是因预览和防盗链等技术需要对页面进行转换压缩成图而已,我们并不对上传的文档进行任何编辑或修改,文档下载后都不会有水印标识(原文档上传前个别存留的除外),下载后原文更清晰;试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓;PPT和DOC文档可被视为“模板”,允许上传人保留章节、目录结构的情况下删减部份的内容;PDF文档不管是原文档转换或图片扫描而得,本站不作要求视为允许,下载前自行私信或留言给上传者【胜****】。
5、本文档所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用;网站提供的党政主题相关内容(国旗、国徽、党徽--等)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。
6、文档遇到问题,请及时私信或留言给本站上传会员【胜****】,需本站解决可联系【 微信客服】、【 QQ客服】,若有其他问题请点击或扫码反馈【 服务填表】;文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“【 版权申诉】”(推荐),意见反馈和侵权处理邮箱:1219186828@qq.com;也可以拔打客服电话:4008-655-100;投诉/维权电话:4009-655-100。