如何解决Bison代码中if/else分支语法的归约/归约冲突？

嗨，作为刚上手Bison的新手，碰到这类语法冲突确实容易懵，我来帮你一步步拆解问题根源和解决办法～

先看第一个归约/归约冲突的原因 #

你最初的语法规则是这样的：

ifinstr: KW_IF expr_decl KW_THEN statements elseifinstr elseinstr KW_END ;
elseifinstr : %empty {$$ = "";} | elseifinstr KW_ELSE KW_IF expr_decl KW_THEN statement ;
elseinstr : %empty {$$ = "";} | KW_ELSE statement ;

这里的问题在于：elseifinstr和elseinstr都定义了空产生式（%empty）。当解析器处理到没有elseif和else的if语句时（比如if ... then ... end），它需要同时归约elseifinstr的空和elseinstr的空，但Bison不知道该先归约哪一个，这就直接触发了归约/归约冲突。

再看你修改后出现的移进/归约冲突 #

你把elseinstr合并到elseifinstr里，规则变成：

ifinstr: KW_IF expr_decl KW_THEN statements elseifinstr KW_END ;
elseifinstr : %empty {$$ = "";} | elseifinstr KW_ELSE KW_IF expr_decl KW_THEN statement | KW_ELSE statement ;

这次的冲突是经典的**悬空else（dangling else）**问题：当出现嵌套if时（比如if A then if B then ... else ... end），解析器遇到KW_ELSE时，不知道应该移进它（把else绑定到内层的if B），还是归约外层的ifinstr（把else绑定到外层的if A），这种歧义就导致了移进/归约冲突。

正确的语法设计方案 #

要解决这两个问题，我们需要让语法明确else的绑定优先级，同时避免多个空产生式的冲突。推荐两种方式：

方式1：用递归结构明确else绑定关系 #

把elseif和else设计成if语句的后缀递归结构，让else只能和最近的if关联：

# 基础if语句：不带else/elseif，或者带else
ifinstr: KW_IF expr_decl KW_THEN statements KW_END
       | KW_IF expr_decl KW_THEN statements KW_ELSE statements KW_END
       # 带elseif的情况，递归嵌套
       | KW_IF expr_decl KW_THEN statements elseif_chain KW_END
       ;

# elseif链：可以连续嵌套elseif，最后也可以跟一个else
elseif_chain: KW_ELSE KW_IF expr_decl KW_THEN statements
            | KW_ELSE KW_IF expr_decl KW_THEN statements KW_ELSE statements
            | KW_ELSE KW_IF expr_decl KW_THEN statements elseif_chain
            ;

这种结构完全避免了空产生式的冲突，同时通过递归明确了else的绑定逻辑——每个else/elseif都属于紧挨着它的前一个if。

方式2：利用Bison优先级解决悬空else #

如果想保留更简洁的规则，可以给KW_ELSE设置更高的移进优先级，让解析器优先移进KW_ELSE，绑定到最近的if：

# 先定义优先级：KW_ELSE的优先级高于归约动作
%nonassoc KW_THEN
%nonassoc KW_ELSE

# 语法规则
ifinstr: KW_IF expr_decl KW_THEN statements KW_END
       | KW_IF expr_decl KW_THEN statements KW_ELSE statements KW_END
       | KW_IF expr_decl KW_THEN statements elseifinstr KW_END
       ;

elseifinstr: KW_ELSE KW_IF expr_decl KW_THEN statements
           | KW_ELSE KW_IF expr_decl KW_THEN statements elseifinstr
           | KW_ELSE statements
           ;

这里%nonassoc声明了KW_THEN和KW_ELSE的优先级，KW_ELSE优先级更高，当遇到KW_ELSE时，解析器会选择移进而不是归约，从而解决悬空else的歧义。

新手调试小技巧 #

你可以用bison -v your_parser.y命令生成一个.output文件，里面会详细列出每个状态下的冲突情况、产生式和符号栈，通过这个文件能更直观地看到Bison到底在纠结什么，对理解冲突根源非常有帮助～

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