是否存在上下文无关文法使得LR(0)与SLR(1)的SR冲突始终相等
推导错误点拆解
你的推导核心问题是对「SR冲突相等」的双向性判断缺失,以及对SLR(1)表达能力的理解偏差,具体分三点说明:
- 首先,你推导的前半部分结论是成立的:若某文法在LR(0)中不存在SR冲突,那么它在SLR(1)中确实不会存在SR冲突。原因是SLR(1)和LR(0)使用完全一致的LR(0)项目集规范族,LR(0)无SR冲突意味着所有项目集都不会同时出现移进项目和归约项目,自然SLR(1)也不会产生新的SR冲突。
- 你的错误出在「二者的SR冲突相等」的推论:
相等要求双向成立,但你只证明了「LR(0)无冲突→SLR(1)无冲突」这一个方向,反过来「SLR(1)无冲突→LR(0)无冲突」并不成立。存在大量文法在LR(0)的项目集中存在SR冲突,但可以通过SLR(1)的FOLLOW集判断规则消解冲突,也就是SLR(1)下无冲突,但LR(0)下有冲突,二者的SR冲突集合是包含关系而非相等关系。 - 你对「SLR(1)表达能力强于LR(0)」的理解也存在偏差:这个性质的本质是SLR(1)能识别的文法集合严格包含LR(0)能识别的文法集合,核心原因就是SLR(1)可以消解部分LR(0)的SR冲突,这恰恰说明二者的SR冲突不可能相等,LR(0)的冲突数量一定大于等于SLR(1)的冲突数量。
内容的提问来源于stack exchange,提问作者Ayush Kumar
相关产品推荐
相关产品推荐

