Java CUP实现类C++语言语法时出现移归冲突求助

我们团队正在重构类C++语言的语法解析器，目前因函数定义相关非终结符陷入Shift-Reduce冲突。相关语法规则如下：

program ::= program variable_declaration SEMICOLON
          | program function_declaration SEMICOLON
          | program function_definition
          | program type_definition SEMICOLON;

function_definition ::= type IDENTIFIER OPENBRACKET argument_list CLOSEBRACKET block;

block ::= OPENCURLYBRACKET instruction_sequence CLOSECURLYBRACKET;

instruction_sequence ::= instruction_sequence instruction | /*EPS*/;

instruction ::= non_balanced_instruction | balanced_instruction;

balanced_instruction ::= IF OPENBRACKET expression CLOSEBRACKET balanced_instruction ELSE balanced_instruction
                       | not_if_instruction;

non_balanced_instruction ::= IF OPENBRACKET expression CLOSEBRACKET instruction
                           | IF OPENBRACKET expression CLOSEBRACKET balanced_instruction ELSE non_balanced_instruction;

not_if_instruction ::= block| while| for| switch| semicolon_instruction;

注：大写为终结符，小写为非终结符；function_declaration表示函数原型，function_definition表示函数实现。

CUP输出的冲突信息：

Shift/Reduce conflict found in state #197
between instruction ::= balanced_instruction()
and non_balanced_instruction ::= IF OPENBRACKET expression CLOSEBRACKET balanced_instruction () ELSE non_balanced_instruction
and balanced_instruction ::= IF OPENBRACKET expression CLOSEBRACKET balanced_instruction (*) ELSE balanced_instruction
under symbol ELSE

我们调试多日，发现移除function_definition非终结符后冲突消失，通过逐步重构语法定位到该非终结符，寻求解决办法。

问题分析 #

这个冲突本质是经典的悬空else歧义问题，引入function_definition后触发冲突的原因是：函数体内的block包含完整的instruction_sequence上下文，使得语法分析器进入了之前未触发的状态——当识别出一个balanced_instruction后遇到ELSE，分析器无法判断是将balanced_instruction归约为instruction，还是继续ShiftELSE匹配外层的IF分支。而无函数定义时，语法上下文未覆盖到该状态，冲突被暂时掩盖。

解决方案 #

方案1：简化语法规则，用优先级解决歧义 #

移除balanced_instruction和non_balanced_instruction的区分，合并为统一的instruction规则，通过设置ELSE的优先级来强制最近匹配：

instruction ::= IF OPENBRACKET expression CLOSEBRACKET instruction
              | IF OPENBRACKET expression CLOSEBRACKET instruction ELSE instruction
              | not_if_instruction;

在CUP配置中，为ELSE设置高于IF归约的优先级，或者让IF语句的归约优先级更低。这样遇到ELSE时，分析器会优先Shift（处理后续的else分支），而非Reduce前面的IF语句，符合C++的就近匹配规则。

方案2：保留现有规则，指定冲突解决策略 #

如果必须保留balanced_instruction和non_balanced_instruction的结构，可在CUP中针对冲突状态（#197）设置优先Shift：

• 在CUP的spec文件中，为balanced_instruction ::= ... ELSE balanced_instruction和non_balanced_instruction ::= ... ELSE non_balanced_instruction这两条规则设置更高的优先级，确保遇到ELSE时优先执行Shift操作，而非归约instruction ::= balanced_instruction。

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