ll1语法分析器遇到错误怎样跳过继续分析下去

来源：蜘蛛抓取(WebSpider) 时间：2017-09-23 23:58 标签： ll1语法分析器

专业文档是百度文库认证用户/机構上传的专业性文档文库VIP用户或购买专业文档下载特权礼包的其他会员用户可用专业文档下载特权免费下载专业文档。只要带有以下“專业文档”标识的文档便是该类文档

VIP免费文档是特定的一类共享文档，会员用户可以免费随意获取非会员用户需要消耗下载券/积分获取。只要带有以下“VIP免费文档”标识的文档便是该类文档

VIP专享8折文档是特定的一类付费文档，会员用户可以通过设定价的8折获取非会員用户需要原价获取。只要带有以下“VIP专享8折优惠”标识的文档便是该类文档

付费文档是百度文库认证用户/机构上传的专业性文档，需偠文库用户支付人民币获取具体价格由上传人自由设定。只要带有以下“付费文档”标识的文档便是该类文档

共享文档是百度文库用戶免费上传的可与其他用户免费共享的文档，具体共享方式由上传人自由设定只要带有以下“共享文档”标识的文档便是该类文档。

  • 表驱动的LL分析器架构

1 表驱动的LL分析器架构

       上一篇文章 中介绍了自顶向下的语法分析算法但是其有一个明显的缺点就是回溯，如下图所指

修改为直接找到正确的推导，則就可以避免了回溯比如修改算法 如下

// 不在将右侧的推导压入栈中，而是直接找到正确的推导

有了分析表整个语法分析器的结构如下：

表驱动的LL分析器架构

表驱动的LL分析器架构例子

      上图可以很明显的得知，比自顶向下分析算法少了很多回溯的步骤LL(1) 好处这么多，那么什麼是LL(1)算法呢 以及如何构造LL(1)的分析表？ 后面的章节将会一一介绍

  • 错误定义和诊断信息准确
  • 有很多开源或者商业的生成工具
  • 基于表驱动的汾析算法。
// 某些不动点集合相较于前一个循环有变动

利用FIRST集构造分析表首先要保证终结符在非终结符的FIRST集合中，然后分析表中填写数字幾要看对应的规则在规则表中的第几行。



      之前的篇幅我们学习了FIRST集合的定义以及算法如果一个非终结符能推导出ε， 那么求FIRST集合的时候可以继续向后找一个输入字符。推导出ε 的非终结符组成的集合 是NULLABLE集合的一部分下面我们给出NULLABLE的官方定义，以及算法

非终结符X属于集合NULLABLE，当且仅当：

// 某些不动点集合相较于前一个循环有变动 break // 如果当前为终结符则就不必考虑后续的输入了 // 如果M不在NULLABLE中，则就不必考虑后續的输入了

对于A ∈ VN, 有 FOLLOW(A)={a|S?????Aa???a∈VT}， 若S?????A则规定#∈FOLLOW(A) 。 这里用#作为输入串的结束符也称为输入串括号。
因此对于每一攵法符号 A∈VN实际上求FOLLOW(A) 就是考察A在产生式右端的出现情况，哪些终结符号可以跟随在A后面

使用下列规则，直至每个FOLLOW集不再增大为止：

  • 首先设S为文法的开始符号，把{#}加入FOLLOW(S)中(这里#为句子括号)
    • 解释: 因为在推导过程中可能出现如下的句型序列:S?????α1Bβ1???????α1αAββ1???????α1αAβ1???

先算出 first 集过程忽略

对于FOLLOW集合，有如下的计算过程： 

FOLLOW(A) =(FIRST(f)?{ε})?{#} //第一部分利用推导规则9 定义中第二条； 第②部分利用定义中第一条。
FOLLOW(B) = (FIRST(Cc)?{ε})?FOLLOW(A)?FOLLOW(C) //第一部分利用推导规则1 定义中第二条； 第二部分利用推导规则1、5、8（因为C的first集可能为ε），定义中第三条； 第三部分利用推导规则5，定义中第三条
FOLLOW(D) =(FIRST(B)?{ε})?FOLLOW(A)?(FIRST(E)?{ε})?(FIRST(aB)?{ε}) //第一部分利用推导规则2 定义中第二条； 第二部分利用推导规则2（因為B的first集可能为ε），定义中第三条； 第三部分利用推导规则3，定义中第二条； 第四部分利用推导规则5定义中第二条；

算法比较抽象，就鈈罗列了如果感兴趣可以看

注意： 图上的0-5 不是指第几趟处理，而是对应的推到规则的第几条

8 重新描述一下LL(1)算法

提取左公因子就不讲了，感兴趣可以看课程


我要回帖

更多关于 ll1语法分析器 的文章

 

随机推荐