为何给定文法LR(0)存在Reduce/Reduce冲突?自制SLR表无同单元格双归约
核心差异:LR(0)冲突判定与SLR冲突消解的逻辑边界
基础规则澄清
- LR(0)分析的归约判定完全不考虑输入符号:只要项目集中出现归约项目,无论当前展望的输入终结符是什么,都要执行对应归约操作。LR(0)文法的判定不需要完整构造分析表,只要扫描项目集中的项目类型,发现同一项目集存在两个及以上归约项目、或者归约项目和移进项目共存,就可以直接判定存在冲突。
- SLR分析的归约判定是对LR(0)的针对性修正:仅当输入终结符属于归约项目左部非终结符的Follow集时,才执行对应归约操作,以此分流原本会在LR(0)表中重叠的操作。
该状态存在LR(0)层面Reduce/Reduce冲突的根本原因
你构造的这个项目集中,包含两个独立的归约项目,这是冲突的核心来源:
- 对于空产生式
M -> ε,对应的LR(0)项目M -> ·本质是归约项目——因为产生式右部是空串,没有需要匹配的符号,点的位置即代表已经读完了M的全部右部内容,满足归约条件。 - 同理,空产生式
N -> ε对应的项目N -> ·也是独立的归约项目。
按照LR(0)分析表的构造规则,只要项目集中有归约项目,就需要把所有终结符对应的ACTION单元格全部填入对应归约操作。这个状态同时存在两个归约项目,会导致所有终结符的ACTION单元格都同时出现两个归约操作,完全符合LR(0)层面Reduce/Reduce冲突的判定标准,因此教材直接判定该状态存在LR(0)层面的冲突。
为什么SLR分析表中未观察到冲突
SLR的设计目标就是消解LR(0)的固有冲突,它不会把归约操作填到所有终结符列,而是仅在归约项目左部非终结符的Follow集对应的列填写归约操作:
- 你计算的
Follow(M) = {x},因此仅在x对应的ACTION单元格填入「用规则M->ε归约」的操作; - 你计算的
Follow(N) = {y},因此仅在y对应的ACTION单元格填入「用规则N->ε归约」的操作。
由于两个Follow集没有交集,两个归约操作不会落入同一个单元格,因此SLR分析表中不存在表面冲突。但这种无冲突是SLR规则修正后的结果,并不改变该项目集在LR(0)层面存在Reduce/Reduce冲突的本质。
内容的提问来源于stack exchange,提问作者vesii
相关产品推荐
相关产品推荐

