语法分析专题培训市公开课金奖市赛课一等奖课件.pptx
《语法分析专题培训市公开课金奖市赛课一等奖课件.pptx》由会员分享,可在线阅读,更多相关《语法分析专题培训市公开课金奖市赛课一等奖课件.pptx(294页珍藏版)》请在咨信网上搜索。
1、第三章第三章语法分析语法分析本章内容本章内容上下文无关文法上下文无关文法自上而下自上而下分析和自下而上分析分析和自下而上分析围绕分析器自动生成展开围绕分析器自动生成展开词词法法分析器分析器记记号号取下一个取下一个记号记号源程序源程序分析分析树树前端前端其余部分其余部分分析器分析器中间中间表示表示符号表符号表第1页第1页3.1上下文无关文法上下文无关文法3.1.1上下文无关文法定义上下文无关文法定义正规式能定义一些简朴语言正规式能定义一些简朴语言,能表示给定结构固能表示给定结构固定次数重复或者没有指定次数重复定次数重复或者没有指定次数重复例:例:a(ba)5,a(ba)*正规式不能用于描述配对或
2、嵌套结构正规式不能用于描述配对或嵌套结构例例1:配对括号串集合配对括号串集合例例2:wcw|w是是a和和b串串 第2页第2页3.1上下文无关文法上下文无关文法上下文无关文法上下文无关文法是四元组(是四元组(VT,VN,S,P)VT:终止符终止符集合集合VN:非非终止符终止符集合集合S:开始符号,非终止符中一个开始符号,非终止符中一个P :产生式产生式集合,集合,产生式形式产生式形式:A 例例 (id,+,(,),expr,op,expr,P)exprexpropexpr expr(expr)expr expr expridop+op 第3页第3页3.1上下文无关文法上下文无关文法简化表示简化表
3、示exprexpropexpr|(expr)|expr|idop+|简化表示简化表示E E A E|(E)|E|idA+|第4页第4页3.1上下文无关文法上下文无关文法3.1.2 推导推导 把产生式当作重写规则,把符号串中非终止符用把产生式当作重写规则,把符号串中非终止符用其产生式右部串来代替其产生式右部串来代替例例 E E+E|E E|(E)|E|id E E (E)(E+E)(id+E)(id+id)概念概念上下文无关语言上下文无关语言、等价等价文法、文法、句型句型记号记号S*、S+w 第5页第5页3.1上下文无关文法上下文无关文法例例E E+E|E E|(E)|E|id 最左最左推导推导
4、E lm E lm(E)lm(E+E)lm(id+E)lm (id+id)最右最右推导(规范推导)推导(规范推导)E rm E rm(E)rm(E+E)rm(E+id)rm (id+id)第6页第6页3.1上下文无关文法上下文无关文法3.1.3分析树分析树例例E E+E|E E|(E)|E|idEE()EEE+idid第7页第7页3.1上下文无关文法上下文无关文法3.1.4 二义性E E E E E+E id E E E+E id E+E id E+E id id+E id id+E id id+id id id+id两个不同最左推导第8页第8页3.1上下文无关文法上下文无关文法3.1.4 二
5、义性E E E E E+E id E E E+E id E+E id E+E id id+E id id+E id id+id id id+id两棵不同语法树EEE*+EEidididEEidE*+EEidid第9页第9页3.2 语言和文法语言和文法 文法长处文法长处文法给出了准确,易于理解语法阐明文法给出了准确,易于理解语法阐明自动产生高效分析器自动产生高效分析器能够给语言定义出层次结构能够给语言定义出层次结构以文法为基础语言实现以文法为基础语言实现便于语言修改便于语言修改文法问题文法问题文法只能描述编程语言大部分语法,不能描述语文法只能描述编程语言大部分语法,不能描述语言中上下文相关语法特
6、性言中上下文相关语法特性第10页第10页3.2 语言和文法语言和文法 3.2.1 正规式和上下文无关文法比较正规式和上下文无关文法比较正规式正规式(a|b)*ab文法文法A0aA0|b A0|aA1A1bA2A2 12开始开始a0abb第11页第11页3.2 语言和文法语言和文法 3.2.2分离词法分析器理由分离词法分析器理由为何要用正规式定义词法为何要用正规式定义词法词法规则非常简朴,不必用上下文无关文法词法规则非常简朴,不必用上下文无关文法对于词法记号,正规式描述简练且易于理解对于词法记号,正规式描述简练且易于理解从正规式结构出词法分析器效率高从正规式结构出词法分析器效率高第12页第12页
7、3.2 语言和文法语言和文法 从软件工程角度看,词法分析和语法分析分从软件工程角度看,词法分析和语法分析分离有下列好处离有下列好处简化设计简化设计编译器效率会改进编译器效率会改进编译器可移植性加强编译器可移植性加强便于编译器前端模块划分便于编译器前端模块划分 第13页第13页3.2 语言和文法语言和文法 能否把词法分析并入到语法分析中,直接从能否把词法分析并入到语法分析中,直接从字符流进行语法分析字符流进行语法分析若把词法分析和语法分析合在一起,则必须将语若把词法分析和语法分析合在一起,则必须将语言注解和空白规则反应在文法中,文法将大大复言注解和空白规则反应在文法中,文法将大大复杂杂注解和空白
8、由自己来处理分析器,比注解和空格注解和空白由自己来处理分析器,比注解和空格已由词法分析器删除分析器要复杂得多已由词法分析器删除分析器要复杂得多第14页第14页3.2 语言和文法语言和文法 3.2.3 验证文法产生语言验证文法产生语言G:S(S)S|L(G)=配正确括号串集合配正确括号串集合第15页第15页3.2 语言和文法语言和文法 3.2.3 验证文法产生语言验证文法产生语言G:S(S)S|L(G)=配正确括号串集合配正确括号串集合按推导步数进行归纳按推导步数进行归纳:推出是:推出是配对括号串配对括号串归纳基归纳基础:础:S 归纳假设:归纳假设:少于少于n步推导都产生配正确括号串步推导都产生
9、配正确括号串归纳环节:归纳环节:n步最左推导步最左推导下列:下列:S(S)S*(x)S*(x)y第16页第16页3.2 语言和文法语言和文法 3.2.3 验证文法产生语言验证文法产生语言G:S(S)S|L(G)=配正确括号串集合配正确括号串集合按串长进行归纳按串长进行归纳:配对括号串可由配对括号串可由S推出推出归纳基归纳基础:础:S 归纳假设:归纳假设:长度小于长度小于2n都能够从都能够从S推导出来推导出来归纳环节:归纳环节:考虑长度为考虑长度为2n(n 1)w=(x)yS(S)S*(x)S*(x)y第17页第17页3.2 语言和文法语言和文法 3.2.4适当表示式文法适当表示式文法用一个层次
10、观点看待表示式用一个层次观点看待表示式id id(id+id)+id id+id第18页第18页3.2 语言和文法语言和文法 3.2.4适当表示式文法适当表示式文法用一个层次观点看待表示式用一个层次观点看待表示式id id(id+id)+id id+idid id(id+id)文法文法exprexpr+term|termterm term factor|factorfactorid|(expr)第19页第19页3.2 语言和文法语言和文法 exprexpr+term|termtermterm factor|factorfactorid|(expr)expridtermfactorididter
11、m*termfactorfactor*exprexpr+idfactortermididterm*termfactorfactorid+id id分析树分析树 id id id分析树分析树 第20页第20页3.2 语言和文法语言和文法 3.2.5消除二义性消除二义性stmtifexprthenstmt|ifexprthenstmtelsestmt|other句型句型:ifexprthenifexprthenstmtelsestmt两个最左推导:两个最左推导:stmt ifexprthenstmt ifexprthenifexprthenstmtelsestmtstmt ifexprthenst
12、mtelsestmt ifexprthenifexprthenstmtelsestmt第21页第21页3.2 语言和文法语言和文法 无二义文法无二义文法stmtmatched_stmt|unmatched_stmtmatched_stmtifexprthenmatched_stmtelsematched_stmt|otherunmatched_stmtif exprthenstmt|ifexprthenmatched_stmtelseunmatched_stmt第22页第22页3.2 语言和文法语言和文法 3.2.6消除左递归消除左递归文法文法左递归左递归A+A 直接左递归直接左递归AA|串特
13、点串特点.消除直接左递归消除直接左递归A A A A|第23页第23页3.2 语言和文法语言和文法 例例算术表示文法算术表示文法EE+T|T(T+T.+T)TT F|F(F F.F)F(E)|id消除左递归后文法消除左递归后文法 ETE E+TE|TFT T F T|F(E)|id第24页第24页3.2 语言和文法语言和文法 非直接左递归非直接左递归SAa|bASd|先变换成直接左递归先变换成直接左递归S Aa|bAAad|bd|再消除左递归再消除左递归S Aa|bA bd A|A A adA|第25页第25页3.2 语言和文法语言和文法 3.2.7 提左因子提左因子有左因子文法有左因子文法A
14、1|2提左因子提左因子A A A 1|2 第26页第26页3.2 语言和文法语言和文法 例例 悬空悬空else文法文法 stmtifexprthenstmtelsestmt|ifexprthenstmt|other提左因子提左因子stmtifexprthenstmtoptional_else_part|otheroptional_else_part elsestmt|第27页第27页3.2 语言和文法语言和文法 3.2.8 非上下文无关语言结构非上下文无关语言结构L1=wcw|w属于属于(a|b)*标识符申明应先于其引用抽象标识符申明应先于其引用抽象L2=anbmcndm|n 0,m 0形参个
15、数和实参个数应当相同抽象形参个数和实参个数应当相同抽象L3=anbncn|n 0早先排版描述一个现象抽象早先排版描述一个现象抽象begin:5个字母键,个字母键,5个回退键,个回退键,5个下划线键个下划线键第28页第28页3.2 语言和文法语言和文法 L1=wcwR|w(a|b)*S aSa|bSb|c L2=anbmcmdn|n 1,m 1SaSd|aAdA bAc|bcL2=anbncmdm|n 1,m 1S ABA aAb|abB cBd|cd第29页第29页3.2 语言和文法语言和文法 L3=anbn|n 1S aSb|abL3 是不能用正规式描述语言一个范例是不能用正规式描述语言一个
16、范例 若存在接受若存在接受L3 DFAD,状态数为状态数为k个个设设D读完读完,a,aa,ak 分别到达状态分别到达状态s0,s1,sk至少有两个状态相同,比如是至少有两个状态相同,比如是si和和sj,则则ajbi属于属于L3 sifs0标识为标识为ai路径路径标识为标识为bi路径路径标识为标识为aj i路径路径第30页第30页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:型文法:,,(VN VT)*,|1第31页第31页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:
17、型文法:,,(VN VT)*,|1短语文法短语文法第32页第32页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:型文法:,,(VN VT)*,|11型文法:型文法:|,但但S 能够例外能够例外短语文法短语文法第33页第33页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:型文法:,,(VN VT)*,|11型文法:型文法:|,但但S 能够例外能够例外短语文法、上下文相关文法短语文法、上下文相关文法第34页第34页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式
18、语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:型文法:,,(VN VT)*,|11型文法:型文法:|,但但S 能够例外能够例外2型文法:型文法:A,A VN,(VN VT)*短语文法、上下文相关文法短语文法、上下文相关文法第35页第35页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:型文法:,,(VN VT)*,|11型文法:型文法:|,但但S 能够例外能够例外2型文法:型文法:A,A VN,(VN VT)*短语文法、上下文相关文法、上下文无关文短语文法、上下文相关文法、上下文无关文法法第36页第36页3.2 语言和文法语言
19、和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:型文法:,,(VN VT)*,|11型文法:型文法:|,但但S 能够例外能够例外2型文法:型文法:A,A VN,(VN VT)*3型文法:型文法:A aB或或A a,A,B VN,a VT短语文法、上下文相关文法、上下文无关文短语文法、上下文相关文法、上下文无关文法法第37页第37页3.2 语言和文法语言和文法 3.2.9 形式语言鸟瞰形式语言鸟瞰文法文法G=(VT,VN,S,P)0型文法:型文法:,,(VN VT)*,|11型文法:型文法:|,但但S 能够例外能够例外2型文法:型文法:A,A VN,(VN
20、 VT)*3型文法:型文法:A aB或或A a,A,B VN,a VT短语文法、上下文相关文法、上下文无关文短语文法、上下文相关文法、上下文无关文法、正规文法法、正规文法第38页第38页3.2 语言和文法语言和文法 例例 L3anbncn|n 1上下文相关文法上下文相关文法S aSBC S aBCCBBCaB abbB bbbC bccC ccanbncn推导过程下列:推导过程下列:S*an-1S(BC)n 1用用S aSBC n-1次次S+an(BC)n用用S aBC 1次次S+anBnCn用用CBBC互换相邻互换相邻CBS+anbBn 1Cn用用aBab1次次S+anbnCn用用bB bb
21、 n-1次次S+anbncCn-1用用bC bc 1次次S+anbncn用用cCcc n-1次次第39页第39页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SaCbSaCbcdSaCbc不能处理不能处理左递归左递归第40页第40页3.3 自上而下分析自上而下分析不能处理左递归例子不能处理左递归例子算术表示文法算术表示文法EE+T|TTT F|FF(E)|idEE+TE+TE+T 第41页第41页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析
22、普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术第42页第42页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术、回溯造成回溯造成语义工作推倒重来语义工作推倒重来第43页第43页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例
23、例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术、回溯造成回溯造成语义工作推倒重来语义工作推倒重来、难以汇报犯错确实切位难以汇报犯错确实切位置置第44页第44页3.3 自上而下分析自上而下分析 3.3.1自上而下分析普通办法自上而下分析普通办法例例 文法文法 S aCb C cd|c为输入串为输入串w=acb建立分析树建立分析树SSSaCbaaCCbbcdc不能处理不能处理左递归左递归、复杂回溯技术复杂回溯技术、回溯造成回溯造成语义工作推倒重来语义工作推倒重来、难以汇报犯错确
24、实切位难以汇报犯错确实切位置置、效率低效率低第45页第45页3.3 自上而下分析自上而下分析 3.3.2 LL(1)文法 对文法加什么样限制能够确保没有回溯?先定义两个和文法相关函数FIRST()=a|*a,a VT 尤其是,*时,要求 FIRST()对A任何两个不同选择i 和j,希望有FIRST(i)FIRST(j)=若FIRST(i)或 FIRST(j)含,还需增加条件第46页第46页3.3 自上而下分析自上而下分析 3.3.2LL(1)文法文法对文法加什么样限制能够确保没有对文法加什么样限制能够确保没有回溯回溯?先定义两个和文法相关函数先定义两个和文法相关函数FIRST()=a|*a,a
25、 VT尤其是,尤其是,*时,要求时,要求 FIRST()FOLLOW(A)=a|S*Aa,a VT假假 如如 A是是 某某 个个 句句 型型 最最 右右 符符 号号,那那 么么$属属 于于FOLLOW(A)第47页第47页3.3 自上而下分析自上而下分析 LL(1)文法文法任何两个产生式任何两个产生式A|都满足下列条件:都满足下列条件:FIRST()FIRST()=若若 *,那么,那么FIRST()FOLLOW(A)=比如比如,对于下面文法,面临对于下面文法,面临a时,第时,第2步推导不步推导不知用哪个产生式知用哪个产生式S ABAa b|a FIRST(ab)FOLLOW(A)Ba CC 第
- 配套讲稿:
如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。