[编译原理.第2版.第五章.ppt

  1. 1、本文档共70页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[编译原理.第2版.第五章

第5章 LL(1)文法及其分析程序 5.1 自上而下的语法分析 5.2 预测分析程序 递归下降子程序 表驱动的预测分析程序 5.3 LL(1)分析程序的生成 LL(1)文法 FIRST和FOLLOW集 定义和计算 5.4 非LL(1)文法的改造 5.1自上而下的语法分析 1语法分析概念 2自上而下的语法分析的一般过程 3自上而下的语法分析面临的问题 (上下文无关文法)句型的分析 句型分析就是识别一个符号串是否为某文法的句型的过程,或者说是某个推导的构造过程。 语法树-推导的几何表示 句型aabbaa的可能推导序列和语法树 语法分析 在语言的编译实现中,把句子分析的过程称为语法分析,即完成这个任务的程序称为语法分析程序或称为识别程序。分析算法又称识别算法。 从左到右的分析算法,即总是从左到右地识别输入符号串,首先识别符号串中的最左符号,进而依次识别右边的一个符号,直到分析结束。 分析算法分类 分析算法可分为: 自上而下分析法: 从文法的开始符号出发,寻找与输入符号串匹配的推导,或者说,为输入串寻找一个最左推导。 自下而上分析法: 从输入符号串开始,逐步进行归约,直至归约到文法的开始符号。 两种方法反映了语法树的两种构造过程。 自上而下方法是从文法符号开始,将它做为语法树的根,向下逐步建立语法树,使语法树的结果正好是输入符号串 自下而上方法则是从输入符号串开始,以它做为语法树的结果,自底向上的构造语法树 自上而下分析 对任何输入串,试图用一切可能的办法,从文法开始符号着手,自上而下地为输入串构造一棵语法树,或者说,为输入串寻找一个最左推导。本质上是一个试探过程,反复使用不同地产生式谋求匹配输入串的过程。 自上而下的语法分析的一般过程 例:文法G: S → cAd A → ab A → a 识别输入串w=cabd是否为该文法的句子 自上而下的语法分析的一般过程 (1)S → cAd (2) A → ab (3) A → a 识别输入串w=cad是否为 该文法的句子 1.S ? cAd 2.后选择(2)扩展A,得到推导S ? cAd ? cabd 这时 w的第二个符号可以与叶子结点a得以匹配,但第三个符号d却不能与下一叶子结点b匹配 怎么办?-查看A有无另一个选择,有!回溯,把A为根的子树剪掉,扫描过的输入串中的a吐出来,再试探用产生式(3)构造推导S ? cAd ? cad 识别输入串w=caa的过程: 1.S ? cAd 2.选择(2)扩展A,得到推导S ? cAd ? cabd 3.回溯回到推导S ? cAd 4.选择(3)扩展A,得到推导S ? cAd ? cad 5. A没有选择了!回溯到推导S ? cAd 6.再回溯S有无另一个选择?没有! 宣告分析失败。 (请思考 若有 (4) S → cB (5) B → aa 会怎样? ) 自上而下的语法分析面临的问题-实现考虑 回朔 文法的左递归性 S→Sa 自上而下分析对文法的要求 例文法G0[S]: (1) S→Sa (2) S→b 分析baa是不是文法的句子 按照自上而下的分析思想 选用产生式(1)来推导S?Sa 语法树末端结点最左符号为非终结符,所以选用(1)继续推导S?Sa?Saa 此时语法树末端结点最左符号仍为非终结符,所以选用(1)继续推导S?Sa?Saa ?Saaa 问题——试图用S匹配输入串时,出现:在没有读入任何输入符 号的情况下,又得重新要求S去进行新的匹配 原因——文法含有左递归, 自上而下的语法分析--左递归规则 G[S]: S→Sa ?????? ?????? ??S→b L={ban | n≥1} W=baaa S b S S a

文档评论(0)

wu12youli + 关注
实名认证
内容提供者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档