MENU

【编译原理】SLR算法

June 2, 2020 • Read: 34 • 编程之路,编译原理

回顾:LR(0)分析算法的缺点分析

对每一个形如X -> α ● 的项目

  • 直接把 α 归约成 X, 紧跟一个 “goto”
  • 尽管不会漏掉错误,但会延迟错误发现时机
  • LR(0)分析表中可能包含冲突

问题1:错误定位

FOLLOW(S) = { $}, 如果输入的是● x x y x到状态3的时候是x x y ● x下一个输入是x,而非$,此时应该就该抛出异常,而实际上他会一直归约到状态4后再报错。这就是错误定位

问题2:冲突

而事实上FOLLOW(E) = {$} ,+号并不是FOLLOW集里的,所以并不应该执行第2个(归约)操作,而应该是第1个(移进)操作。

SLR

  1. 和LR(0)分析算法基本步骤相同
  2. 仅区别于对 归约 的处理

    • 对于状态i上的项目X -> α ●,仅对y ∈ FOLLOW(X)添加ACTION[i, y]

如:问题1中错误定位图中的分析表,把四个划红线的归约删掉即为修改后的分析表。当到状态3时,下一个输入是结束$,进行归约,否则报错。

问题2 中冲突的图,也就不会在执行第2个的归约操作。

  1. 和LR(0)分析算法基本步骤相同
  2. 仅区别于对 归约 的处理

    • 对于状态i上的项目X -> α ●,仅对y ∈ FOLLOW(X)添加ACTION[i, y]

如:问题1中错误定位图中的分析表,把四个划红线的归约删掉即为修改后的分析表。当到状态3时,下一个输入是结束$,进行归约,否则报错。

问题2 中冲突的图,也就不会在执行第2个的归约操作。

SLR分析表的冲突

根据SLR算法,FOLLOW(R) = { =, ....},可以直接移进也可以执行归约,存在冲突

解决

解决冲突: → LR(1)算法

- - - 结束 - - -
  • 文章标题:【编译原理】SLR算法
  • 文章链接:https://blog.canye365.cn/archives/337.html
  • 版权所有:本文版权归 残夜 所有,转载请注明出处!除特殊注明外 (如有侵权,请 点此联系我 )
  • Last Modified: April 11, 2021