给定文法 #

S → 0S0 
S → 1S1
S → 10

拓广文法：S' → S

状态集推导（规范LR(0)项目集） #

I0:
  S'→ .S
  S → .0S0 
  S → .1S1
  S → .10

I1（I0输入S）:
  S'→ S.（接受状态）

I2（I0输入0）:
  S → 0.S0
  S → .0S0
  S → .1S1
  S → .10

I3（I0输入1）:
  S → 1.S1
  S → .0S0
  S → .1S1
  S → .10
  S → 1.0  

冲突分析 #

在状态I3遇到输入0时，存在移进-归约冲突：

• 移进动作：由项目S→.0S0触发，移进0后进入状态I2；
• 归约动作：由项目S→1.0触发，因为0属于FOLLOW(S)（计算得FOLLOW(S)={0,1,#}），符合SLR归约条件。

SLR分析表（含冲突） #

注：sX表示移进并转入状态X；rX表示用第X个产生式归约（r1对应S→0S0，r2对应S→1S1，r3对应S→10）；acc表示接受。

冲突解决方法 #

SLR无法区分该冲突，因为它仅依赖FOLLOW集判断归约，无法识别后续输入符号的差异。最优解决方案是改用LR(1)分析：

在LR(1)项目集中，每个项目附带向前看符号，I3的项目会被细化为：

I3(LR(1)):
  S → 1.S1, #
  S → 1.0, #
  S → .0S0, 1
  S → .1S1, 1
  S → .10, 1

此时：

• 仅当输入0且下一个符号为#时，触发S→10的归约；
• 仅当输入0且下一个符号为1时，触发移进动作进入I2。

通过向前看符号精准区分两种动作的适用场景，彻底消除冲突。

若坚持使用SLR，可调整产生式优先级（优先移进或优先归约），但这可能导致部分合法字符串无法被正确分析，因此不推荐。

内容的提问来源于stack exchange，提问作者Vansh Guleria