Yacc/Bison泛型函数表达式移进/归约冲突解决求助

问题场景 #

要实现一套包含标识符、比较操作、泛型函数调用的表达式语法，合法示例包括：

• 简单标识符：myVar
• 简单比较：myVar < yourVar
• 泛型函数调用：myFunction < int > ()
  要求禁止链式比较（比如a < b > c这种形式），但当前编写的Bison文法出现了移进/归约冲突，最小复现文法如下：

%token ID OP_GT OP_LT OPEN_PARANT CLOSE_PARANT

%nonassoc COMPARISON
%nonassoc GENERIC

%start expr

%%

expr:
    basic_expr
    | comp_expr
    ;

basic_expr:
    ID
    | function_call_expr
    ;

function_call_expr:
    ID OPEN_PARANT CLOSE_PARANT
    | ID OP_LT ID OP_GT OPEN_PARANT CLOSE_PARANT %prec GENERIC
    ;

comp_expr:
    basic_expr OP_LT basic_expr     %prec COMPARISON
    | basic_expr OP_GT basic_expr   %prec COMPARISON
    ;
%%

Bison verbose输出的冲突状态报告：

state 1

    3 basic_expr: ID .
    5 function_call_expr: ID . OPEN_PARANT CLOSE_PARANT
    6                   | ID . OP_LT ID OP_GT OPEN_PARANT CLOSE_PARANT

    OP_LT        shift, and go to state 6
    OPEN_PARANT  shift, and go to state 7

    OP_LT     [reduce using rule 3 (basic_expr)]
    $default  reduce using rule 3 (basic_expr)

冲突原因 #

冲突点在于：当解析器读到ID后面跟着OP_LT时，不知道该优先做什么——是把ID归约成basic_expr（后续可能组成比较表达式basic_expr OP_LT basic_expr），还是移进OP_LT去匹配泛型函数调用的规则。

之前设置的优先级没起作用，是因为Bison的优先级规则只针对产生式之间的归约冲突，而这里是移进动作和归约动作的冲突，直接给产生式加%prec标记无法解决这种场景。

解决方法 #

方法一：重构文法，明确匹配顺序 #

核心是让解析器先尝试匹配泛型函数的前缀，再回退到普通标识符，这样就能自然优先处理泛型调用的情况。修改后的文法如下：

%token ID OP_GT OP_LT OPEN_PARANT CLOSE_PARANT

%nonassoc COMPARISON

%start expr

%%

expr:
    basic_expr
    | comp_expr
    ;

// 优先匹配泛型相关的结构，再匹配普通ID
basic_expr:
    generic_part
    | ID
    ;

// 整合泛型前缀和函数调用规则
generic_part:
    ID OP_LT ID OP_GT                              // 泛型前缀
    | generic_part OPEN_PARANT CLOSE_PARANT        // 完整泛型函数调用
    | ID OPEN_PARANT CLOSE_PARANT                  // 普通函数调用
    ;

comp_expr:
    basic_expr OP_LT basic_expr     %prec COMPARISON
    | basic_expr OP_GT basic_expr   %prec COMPARISON
    ;
%%

这种结构下，解析器看到ID OP_LT会先移进尝试匹配泛型结构，只有当后续无法完成泛型函数调用时，才会回退把ID当成普通标识符，进而处理比较表达式。

方法二：调整优先级并使用%expect抑制冲突（快速临时方案） #

如果不想大改文法，可以通过调整终结符优先级，让解析器优先移进OP_LT，同时用%expect告诉Bison预期有一个冲突，避免警告。修改后的文法：

%token ID OP_GT OP_LT OPEN_PARANT CLOSE_PARANT

// 让OP_LT/OP_GT的优先级高于COMPARISON，优先移进处理泛型
%nonassoc COMPARISON
%nonassoc OP_LT OP_GT

// 告诉Bison预期有1个移进/归约冲突，抑制警告
%expect 1
%start expr

%%

expr:
    basic_expr
    | comp_expr
    ;

basic_expr:
    ID
    | function_call_expr
    ;

function_call_expr:
    ID OPEN_PARANT CLOSE_PARANT
    | ID OP_LT ID OP_GT OPEN_PARANT CLOSE_PARANT
    ;

comp_expr:
    basic_expr OP_LT basic_expr     %prec COMPARISON
    | basic_expr OP_GT basic_expr   %prec COMPARISON
    ;
%%

这种方法依赖Bison默认的移进优先策略，虽然能快速解决问题，但不如文法重构清晰可靠，适合临时调试或小项目使用。

内容的提问来源于stack exchange，提问作者eric.toader