Bison跨规则解决移进/归约冲突：如何标记优先级？

当规则展开内容存在重叠时，比如定义expression IS type规则（其中type递归展开为type DOT identifier），同时expression规则中也包含expression DOT identifier，Bison会报告冲突。我们需要让expression IS后的所有DOT都归约为type——例如a is b.c.d要解析为(a is b.c.d)，而非(a is b).c.d。

冲突的最简语法 #

%require "3.0"
%defines

%define api.pure full
%define parse.trace

%token DOT '.'
%token IS "is"

%left DOT
%left IS

%%

example
    : expression
    ;
    
expression
    : expression DOT identifier
    | expression IS type
    | identifier
    ;
    
type
    : fqtypename
    ;

fqtypename
    : identifier
    | fqtypename DOT identifier
    ;

identifier: 
    "blah"
    ;

%%

错误信息 #

State 10

5 type: fqtypename •
7 fqtypename: fqtypename • DOT identifier

DOT  shift, and go to state 12

DOT       [reduce using rule 5 (type)]
$default  reduce using rule 5 (type)

解决方案 #

方法1：拆分表达式规则，明确优先级

通过单独拆分IS相关的表达式规则，让Bison先完整解析type部分（包括所有嵌套的DOT），再归约为expression，避免和普通成员访问规则冲突：

%require "3.0"
%defines

%define api.pure full
%define parse.trace

%token DOT '.'
%token IS "is"

// 调整优先级：IS优先级低于DOT，确保type内部的DOT先处理
%left IS
%left DOT

%%

example
    : expression
    ;
    
expression
    : expression DOT identifier       // 普通成员访问表达式
    | is_expression                   // 单独定义IS表达式
    | identifier
    ;

// 明确IS表达式的结构，确保type先完成递归解析
is_expression
    : identifier IS type
    | expression DOT identifier IS type
    ;
    
type
    : fqtypename
    ;

fqtypename
    : identifier
    | fqtypename DOT identifier       // type内部的DOT递归，优先于expression的DOT
    ;

identifier: 
    "blah"
    ;

%%

方法2：使用%prec绑定更高优先级

给fqtypename的递归规则绑定更高优先级的标记，让Bison在遇到DOT时优先选择移进构建完整的type，而非归约type后处理expression DOT：

%require "3.0"
%defines

%define api.pure full
%define parse.trace

%token DOT '.'
%token IS "is"

// 定义优先级层级：DOT_HIGH > DOT > IS
%left IS
%left DOT
%left DOT_HIGH

%%

example
    : expression
    ;
    
expression
    : expression DOT identifier
    | expression IS type
    | identifier
    ;
    
type
    : fqtypename
    ;

fqtypename
    : identifier
    | fqtypename DOT identifier %prec DOT_HIGH  // 绑定更高优先级
    ;

identifier: 
    "blah"
    ;

%%

两种方法的核心都是让Bison明确：IS关键字后的DOT属于type的递归解析，优先级高于普通的expression DOT成员访问，从而避免归约冲突。

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