回顾: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
- 和LR(0)分析算法基本步骤相同
仅区别于对 归约 的处理
- 对于状态i上的项目X -> α ●,仅对y ∈ FOLLOW(X)添加ACTION[i, y]
如:问题1中错误定位图中的分析表,把四个划红线的归约删掉即为修改后的分析表。当到状态3时,下一个输入是结束$,进行归约,否则报错。
而问题2 中冲突的图,也就不会在执行第2个的归约操作。
- 和LR(0)分析算法基本步骤相同
仅区别于对 归约 的处理
- 对于状态i上的项目X -> α ●,仅对y ∈ FOLLOW(X)添加ACTION[i, y]
如:问题1中错误定位图中的分析表,把四个划红线的归约删掉即为修改后的分析表。当到状态3时,下一个输入是结束$,进行归约,否则报错。
而问题2 中冲突的图,也就不会在执行第2个的归约操作。
SLR分析表的冲突
根据SLR算法,FOLLOW(R) = { =, ....},可以直接移进也可以执行归约,存在冲突。
解决
解决冲突: → LR(1)算法
- - - 结束 - - -