BISON模算术计算器实现单目减运算消除归约冲突方案咨询

问题根源 #

你遇到的归约/归约冲突本质是文法存在歧义：当解析输入- NUMBER时，存在两条合法的归约路径：

1. - NUMBER → num → exp（你期望的路径，直接输出模运算后的常量）
2. NUMBER → num → exp → - exp → exp（非期望路径，会输出原数字加~）
   两条路径优先级相同，所以解析器会报冲突告警，虽然你实际运行时因为默认归约顺序拿到了正确结果，但歧义仍然存在。

解决方案 #

方案1：调整优先级消除冲突 #

给负号+数字的规则设置比一元负号更高的优先级，让解析器遇到- NUMBER时优先匹配num规则，直接计算模值，不需要走一元表达式的归约路径：

/* 优先级声明：CONST_NEG优先级高于NEG */
%left '+'
%nonassoc NEG
%nonassoc CONST_NEG

exp: 
    num { std::cout << $1 << " "; $$ = $1; }
    | exp '+' exp { $$ = add($1, $3); std::cout << "+ "; }
    | '-' exp %prec NEG { $$ = negate($2); std::cout << "~ "; }
;

num:
    '-' NUMBER %prec CONST_NEG { $$ = negate(mod_p($2)); }
    | NUMBER { $$ = mod_p($1); }
;

其中mod_p函数负责将输入的数字转换为模p后的值，比如p=7时输入8返回1。

方案2：分层文法彻底消除歧义 #

如果不想依赖优先级规则，可以直接拆分文法结构，明确区分「负号加常量」和「负号加表达式」两种场景，从根源上消除歧义：

exp:
    /* 单独正常量 */
    NUMBER { $$ = mod_p($1); std::cout << $$ << " "; }
    /* 单独负常量，直接输出模后值 */
    | '-' NUMBER { $$ = negate(mod_p($2)); std::cout << $$ << " "; }
    /* 负号作用于复合表达式，输出~ */
    | '-' compound_exp %prec NEG { $$ = negate($2); std::cout << "~ "; }
    /* 复合表达式直接传递 */
    | compound_exp { $$ = $1; }
;

/* 复合表达式：包含运算或者括号的表达式，不能是单个常量 */
compound_exp:
    exp '+' exp { $$ = add($1, $3); std::cout << "+ "; }
    | '(' exp ')' { $$ = $2; }
;

这种写法完全没有歧义，不需要额外的优先级规则就能满足所有需求：

• 输入-5（p=7）直接输出2
• 输入-(8+5)输出1 5 + ~

两种方案都可以完全消除归约/归约告警，同时满足你的模运算计算器需求。

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