欢迎来到三一办公! | 帮助中心 三一办公31ppt.com(应用文档模板下载平台)
三一办公
全部分类
  • 办公文档>
  • PPT模板>
  • 建筑/施工/环境>
  • 毕业设计>
  • 工程图纸>
  • 教育教学>
  • 素材源码>
  • 生活休闲>
  • 临时分类>
  • ImageVerifierCode 换一换
    首页 三一办公 > 资源分类 > PPT文档下载  

    语法分析-复习习题.ppt

    • 资源ID:6609158       资源大小:277KB        全文页数:29页
    • 资源格式: PPT        下载积分:15金币
    快捷下载 游客一键下载
    会员登录下载
    三方登录下载: 微信开放平台登录 QQ登录  
    下载资源需要15金币
    邮箱/手机:
    温馨提示:
    用户名和密码都是您填写的邮箱或者手机号,方便查询和重复下载(系统自动生成)
    支付方式: 支付宝    微信支付   
    验证码:   换一换

    加入VIP免费专享
     
    账号:
    密码:
    验证码:   换一换
      忘记密码?
        
    友情提示
    2、PDF文件下载后,可能会被浏览器默认打开,此种情况可以点击浏览器菜单,保存网页到桌面,就可以正常下载了。
    3、本站不支持迅雷下载,请使用电脑自带的IE浏览器,或者360浏览器、谷歌浏览器下载即可。
    4、本站资源下载后的文档和图纸-无水印,预览文档经过压缩,下载后原文更清晰。
    5、试题试卷类文档,如果标题没有明确说明有答案则都视为没有答案,请知晓。

    语法分析-复习习题.ppt

    1,上下文无关文法,自上而下,自下而上,LL(1)文法,2个函数,递归下降预测分析,非递归的预测分析,最左推导,最右推导,!,LR文法,移进-归约分析,归约,移进-归约冲突,规约-归约冲突,句柄,活前缀,右句型的前缀,该前缀不超过最右句柄的右端,1。句柄与某个产生式的右部符号串相同2。句柄是句型的一个子串3。把句柄归约成非终结符代表了最右推导逆过程的一步,简单的LR方法(SLR)规范的LR方法向前看的LR方法(LALR),温故知新,2,语法分析部分回顾,自上而下分析的知识点 LL(1)文法的判定 FIRST、FOLLOW集的计算(重点)LL(1)文法判定方法 LL(1)分析的实现方法 递归函数实现 非递归的预测分析实现先求FIRST、FOLLOW集画预测分析表,3,语法分析部分回顾,应用LL(1)分析方法的步骤判定文法是否是LL(1)文法如果不是,则改写文法 消除左递归 提取左因子如果改写后的文法是LL(1)的,那么进行LL(1)分析构造LL(1)分析算法可以采用递归函数实现,也可以采用非递归的栈式分析方法实现,4,文法G:S-aSb|P P-bPc|bQc Q-Qa|a(1)它是chomsky哪一型文法?(2)它生成的语言是什么?(3)给出提取左因子、消除左递归之后的文法(4)求出每个非终结符的First集和Follow集(5)构建LL(1)预测分析表(6)文法G是否是LL(1)文法(7)利用非递归预测分析程序,验证abacb是否是文法G描述的语言的句子,5,文法G:S-aSb|P P-bPc|bQc Q-Qa|a(1)它是chomsky哪一型文法?答:它是2型文法,即上下文无关文法。(2)它生成的语言是什么?答:aibjakcjbi|i=0;j,k=1,6,文法G:S-aSb|P P-bPc|bQc Q-Qa|a(3)给出提取左因子、消除左递归之后的文法答:S-aSb|P P-bP P-Pc|Qc Q-aQ Q-aQ|,7,S-aSb|PP-bPP-Pc|QcQ-aQQ-aQ|,First(S)=a,bFirst(P)=bFirst(P)=a,bFirst(Q)=aFirst(Q)=a,Follow(S)=$,bFollow(P)=$,b,cFollow(P)=$,b,cFollow(Q)=cFollow(Q)=c,(4)求出每个非终结符的First集和Follow集,8,(5)构建LL(1)预测分析表,9,(6)文法G是否是LL(1)文法答:构建出的LL(1)分析表不含有多重定义的条目,因此文法G是LL(1)文法。,10,(7)利用非递归预测分析程序,验证abacb是否是文法G描述的语言的句子,11,接上表,12,语法分析部分回顾,例2 文法GE:E-T T-TE|F F-a|aF(1)判断这个文法是不是LL(1)的?(2)消除左递归、提取左因子之后的文法G是否是LL(1)的?,13,例1 解答:提取左因子,消除左递归后 文法变为GE:E-T T-F T T-ET|F-aF F-F|,GS:E-TT-TE|F F-a|aF,语法分析部分回顾,14,FIRST(E)=FIRST(T)=aFIRST(T)=,FIRST(F)=aFIRST(F)=a,FOLLOW(E)=,$FOLLOW(T)=,$FOLLOW(T)=,$FOLLOW(F)=FOLLOW(F)=,GE:E-T T-F T T-ET|F-aF F-F|,不是LL(1)文法!,通过提取左因子和消除左递归的方法,并不一定能够把文法改写为一个LL(1)文法,语法分析部分回顾,15,左递归的消除 GS:S-Qc|c Q-Sa|a这是一类间接左递归 S-Sac|ac|c Q-Sa|a,语法分析部分回顾,16,左递归的消除 GS:S-Qc|c Q-Sa|a这是一类间接左递归 S-acS|cS S-acS|Q-Sa|a,语法分析部分回顾,S-Sac|ac|c Q-Sa|a,17,语法分析部分回顾,LR分析部分的知识点 活前缀 识别活前缀的DFA 分析表 分析算法,18,语法分析内容总结,自下而上分析部分知识点 SLR的DFA的构造及分析表的构成初始项目集合的产生(拓广文法)能够识别同一符号的项目都转移到同一集合中求闭包过程中每一个“.”后面的非终结符都要重新考虑是否已经在状态中列出对产生式A-归约,“ri”写在FOLLOW(A)集合中元素对应的位置。,19,语法分析内容总结,自下而上分析部分知识点 LR,LALR的构造方法(在SLR的基础上加上搜索符)搜索符的求法,根据造成目前项目出现的那个父项目来求。求闭包的过程中可能出现要添加的项目已经存在,但是搜索符不同的情况,相当于其父项目已经改变,此时需要再求一遍搜索符。,20,语法分析内容总结,自下而上分析部分知识点 SLR,LR,LALR的区别及判别方法通过构造DFA,看其中的状态是否有冲突(“移进归约”或“归约归约”)若有冲突则不属于该文法类型。通过构造分析表,看其中某项是否有冲突。,21,文法类的层次图,22,语法分析部分回顾,例2 文法GS:S-AaS|bAe|BeS|bBa A-d B-d 判断这个文法是SLR(1)的,还是LR(1)的,抑或是LALR(1)的,23,例2 解答:I2=goto(I0,d),I0:SS SAaSS bAe SBeSS bBa A d B d,I2:AdBd,d,S-AaS|bAe|BeS|bBaA-dB-d,e属于FOLLOW(A),同时也属于FOLLOW(B),I2里存在归约-归约冲突,语法分析部分回顾,24,LR(1)分析练习题目,基于LR(1)项目来构造识别G活前缀的DFA,并基于DFA构建分析表.,S V=ES E V*EV id E V,25,LR(1)分析练习解答过程,答:Step 1.对原文法进行拓广(添加产生式S-S),S V=ES E V*EV id E V,S SS V=ES E V*EV id E V,26,id,S SS V=ES EV*EV idE V,V id,S V=EE V,S S,I0,I1,I2,I5,S E,I3,V*EE VV idV*E,I4,S,V,*,id,E,S V=EE VV*EV id,I6,=,E,S V=E,E V,V,V,I8,id,I3,*,*,V*E,E,I7,I9,识别产生式文法活前缀的DFA,27,Step 2:构建识别(拓广)文法活前缀的DFA,I0:S-S,$S-V=E,$S-E,$V-*E,=/$V-id,=/$E-V,$,I1:S-S,$,S,I2:S-V=E,$E-V,$,V,E,I3:S-E,$,*,I4:V-*E,=/$E-V,=/$V-*E,=/$V-id,=/$,id,I5:V-id,=/$,=,I6:S-V=E,$E-V,$V-*E,$V-id,$,E,I8:S-*E,=/$,V,I9:E-V,=/$,*,id,指向I5,E,I10:S-V=E,$,*,I12:V-*E,$E-V,$V-*E,$V-id,$,I7:E-V,$,V,指向I7,id,I11:V-id,$,E,I13:S-*E,$,V,指向I7,*,id,指向I11,LR(1)分析练习解答过程,28,构建分析表首先,为表达式编号然后,计算action表和goto表,0 S S1 S V=E2 S E 3 V*E4 V id 5 E V,LR(1)分析练习解答过程,29,构建分析表Action(0,*)=s4,action(0,id)=s5Goto(0,S)=1,goto(0,V)=2,goto(0,E)=3Action(1,$)=accAction(2,=)=s6Goto(2,V)=7Action(3,$)=r2Action(4,*)=s4,action(4,id)=s5Goto(4,E)=8,goto(4,V)=9,LR(1)分析练习解答过程,

    注意事项

    本文(语法分析-复习习题.ppt)为本站会员(牧羊曲112)主动上传,三一办公仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知三一办公(点击联系客服),我们立即给予删除!

    温馨提示:如果因为网速或其他原因下载失败请重新下载,重复下载不扣分。




    备案号:宁ICP备20000045号-2

    经营许可证:宁B2-20210002

    宁公网安备 64010402000987号

    三一办公
    收起
    展开