如何在GNU Bison中解决移进/归约冲突？

问题描述 #

我定义了如下GNU Bison语法规则：

%precedence KW2
%left "or"
%left "and"
%left "==" "!=" ">=" ">" "<=" "<"
%left "-" "+"
%left "/" "*"

%start statement1

%%

param
    : id
    | id ":" expr        // 冲突来源
    | id "=" expr
    ;

param_list
    : param_list "," param
    | param
    ;

defparam
    : param_list "," "/"
    | param_list "," "/" ","
    ;

param_arg_list
    : defparam param_list
    | param_list
    ;

statement1
    : KEYWORD1 "(" param_arg_list ")" ":" expr {}

expression1
    : KEYWORD2 param_arg_list ":" expr %prec KW2 {} // 引发移进/归约冲突

expr
    : id

    | expr "+" expr
    | expr "-" expr
    | expr "*" expr
    | expr "/" expr

    | expr "==" expr
    | expr "!=" expr
    | expr "<" expr
    | expr "<=" expr
    | expr ">" expr
    | expr ">=" expr
    | expr "and" expr
    | expr "or" expr
    | expression1

id
    : TK_NAME {}

对应的.output文件内容：

State 33

   12 param: id .  [":", ",", ")"]
   13      | id . ":" expr
   14      | id . "=" expr

    ":"  shift, and go to state 55
    "="  shift, and go to state 56

    ":"       [reduce using rule 12 (param)]
    $default  reduce using rule 12 (param)

核心问题：expression1不需要param规则中的id ":" expr格式，删除该规则能解决冲突，但statement1必须保留这个格式。我想复用param_arg_list简化语法，避免重复定义规则，请问除了删除该规则外，还有其他解决冲突的方法吗？

可行的解决方法 #

1. 拆分param规则，区分两种参数集合 #

既然statement1和expression1需要的参数格式不同，可以把param拆成两个规则，再基于它们分别构建参数列表，最后统一到param_arg_list里：

// 给statement1用的参数，支持id ":" expr
param_stmt
    : id
    | id ":" expr
    | id "=" expr
    ;

// 给expression1用的参数，不支持id ":" expr
param_expr
    : id
    | id "=" expr
    ;

// 分别构建列表
param_list_stmt
    : param_list_stmt "," param_stmt
    | param_stmt
    ;

param_list_expr
    : param_list_expr "," param_expr
    | param_expr
    ;

// 复用defparam逻辑
defparam_stmt
    : param_list_stmt "," "/"
    | param_list_stmt "," "/" ","
    ;

defparam_expr
    : param_list_expr "," "/"
    | param_list_expr "," "/" ","
    ;

// 统一param_arg_list，根据上下文匹配不同分支
param_arg_list
    : defparam_stmt param_list_stmt
    | param_list_stmt
    | defparam_expr param_list_expr
    | param_list_expr
    ;

这种方式从语法层面区分了两种场景的参数格式，既保留了复用性，又从根源上消除冲突。

2. 显式指定冲突解决策略 #

Bison的冲突是因为遇到:时，不知道该归约param: id还是移进:去匹配id ":" expr。可以用以下方式处理：

• 设置优先级：给":"设置比param归约更高的优先级，让Bison优先移进:。注意要确认这个调整不会破坏statement1的语法逻辑。
• 声明预期冲突：使用%expect 1告诉Bison预期有1个移进/归约冲突，让它按照默认的移进优先策略处理（Bison默认移进优先级高于归约）。这种方法是接受冲突并指定处理逻辑，需要确保默认策略符合你的语义需求。

3. 语义分析辅助判断 #

在归约param: id时，通过语义动作判断当前上下文是statement1还是expression1，决定是否允许后续的:：

param
    : id {
        // 查看解析栈的上下文，判断当前处于statement1还是expression1的参数场景
        if (当前是expression1的参数上下文) {
            // 直接归约为param，不等待后续的":"
        } else {
            // 保留栈状态，等待可能的":"移进
            // 可结合yylookahead预判下一个token做判断
        }
    }
    | id ":" expr
    | id "=" expr
    ;

这种方式灵活性高，但需要熟悉Bison的栈访问和语义分析接口，实现稍复杂。

4. 重构参数列表引用逻辑 #

让statement1和expression1分别引用不同的参数列表入口，而非共用param_arg_list：

// 原param_arg_list改名为param_arg_list_stmt，保留id ":" expr支持
param_arg_list_stmt
    : defparam param_list
    | param_list
    ;

// 新建param_arg_list_expr，基于去掉id ":" expr的param规则
param_expr
    : id
    | id "=" expr
    ;

param_list_expr
    : param_list_expr "," param_expr
    | param_expr
    ;

defparam_expr
    : param_list_expr "," "/"
    | param_list_expr "," "/" ","
    ;

param_arg_list_expr
    : defparam_expr param_list_expr
    | param_list_expr
    ;

// 各自引用对应的列表
statement1
    : KEYWORD1 "(" param_arg_list_stmt ")" ":" expr {}

expression1
    : KEYWORD2 param_arg_list_expr ":" expr %prec KW2 {}

这种方式聚焦于入口区分，避免大量重复规则，同时解决冲突。

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