语法结构中Reduce/Reduce与Shift/Reduce冲突的含义及无表识别方法咨询

一、两种冲突的定义 #

1. Shift/Reduce（移进/归约）冲突 #

当LR分析器处于某个状态时，当前输入符号既可以执行移进操作（把符号压入分析栈，推进输入指针），又可以执行归约操作（用某个产生式替换栈顶的符号序列），这种二义性就是Shift/Reduce冲突。

2. Reduce/Reduce（归约/归约）冲突 #

当LR分析器处于某个状态时，当前输入符号可以用两个或多个不同的产生式对栈顶序列进行归约，这种情况就是Reduce/Reduce冲突，比Shift/Reduce冲突更严重，通常意味着语法本身存在歧义或设计缺陷。

二、不用构造LR表，直接从语法识别冲突的方法 #

不需要每次都构造LR表，通过观察语法规则的结构，就能快速识别常见冲突场景：

识别Shift/Reduce冲突的经验法则 #

• 悬空else问题：最经典的冲突场景，示例语法：

  stmt → if expr then stmt
       | if expr then stmt else stmt
       | other_stmt
  

  当分析到if expr then stmt的前缀后，遇到else前的状态时，分析器不知道是移进else与后续stmt结合，还是直接把前面的if结构归约为stmt——这就是典型的Shift/Reduce冲突。
• 表达式运算符优先级/结合性未明确：示例语法：

  expr → expr + expr
       | expr * expr
       | num
  

  输入num + num * num时，分析器在看到*时，不知道是先归约左边的num + num，还是移进*优先处理乘法——本质是语法没明确*优先级高于+，导致冲突。
• 可选后缀的重叠歧义：示例语法：

  decl → type ID
       | type ID [ num ]
  

  当输入type ID [时，分析器不知道是先把type ID归约为decl，还是移进[去匹配数组声明——触发Shift/Reduce冲突。

识别Reduce/Reduce冲突的经验法则 #

• 不同非终结符的产生式右部完全重叠：示例语法：

  stmt → ID = expr
  expr → ID = expr
  

  当输入ID = expr时，分析器无法判断该归约为stmt还是expr——直接触发Reduce/Reduce冲突。
• 同一上下文存在多个可匹配的产生式前缀：示例语法：

  func → ID ( params )
  var_decl → ID ( )
  params → param | params , param
  

  当输入ID (时，分析器不知道是归约为函数声明的前缀，还是变量声明的前缀——导致Reduce/Reduce冲突。

三、语法规则与冲突的核心关联 #

冲突本质是语法的二义性或上下文歧义导致的：

• Shift/Reduce冲突大多源于语法未明确优先级、结合性，或是嵌套结构的歧义（如悬空else）。
• Reduce/Reduce冲突则是因为两个不同语法规则在相同输入前缀下均可匹配，且后续输入无法区分归约方向。

内容的提问来源于stack exchange，提问作者Pavel Averin