如何修复支持type[]与type的LR(2)文法Bison归约冲突？

问题背景 #

你的文法需要同时解析普通类型（type）和数组类型（type[]），但出现了移进/归约冲突。从错误信息来看，冲突出现在解析到fqtypename或live_types后遇到[时：解析器无法判断是应该先将当前标识符归约为type，还是继续移进[以匹配数组类型规则。这确实是典型的LR(2)文法问题——解析器需要前瞻两个token（[和其后的]或其他表达式）才能做出正确判断，但LR(1)解析器只能前瞻一个token。

冲突根源 #

以最小复现示例为例：
当解析到blah IS blah [ ... ]时，存在两种合法解析路径：

1. 将blah[]视为type，解析为blah IS (blah[])
2. 将blah IS blah视为表达式，解析为(blah IS blah)[...]

LR(1)解析器看到[时无法区分这两种情况，因此产生冲突。

修复方案 #

方案1：启用GLR解析器（最简单直接） #

Bison的GLR解析器支持处理LR(2)甚至非LR文法，它会并行尝试所有可能的解析路径，直到获取足够token消除歧义。只需在文法开头添加一行配置：

%define parse.glr true

无需修改现有文法结构，即可自动解决冲突。缺点是会轻微增加解析时间，对大多数场景无影响。

方案2：重构文法，用递归定义数组类型 #

将数组类型改为递归后缀形式，让LR(1)解析器能明确判断移进动作：

// 替换原type规则
type
    : base_type
    | type LSQUARE RSQUARE  // 递归支持多维数组
    ;

base_type
    : fqtypename
    | live_types
    ;

// 保留原fqtypename和live_types规则不变
fqtypename
    : identifier
    | fqtypename DOT identifier
    ;

live_types
    : KW_INT | KW_DOUBLE | KW_BOOL | KW_STRING
    ;

这种结构下，解析器看到base_type后的[时，会先归约base_type为type，再移进[匹配数组后缀规则，消除冲突。

方案3：设置规则优先级（适用于语义明确的场景） #

如果你的语言规定type[]的优先级高于表达式数组访问（即不允许(expr IS type)[expr]这种写法），可以通过设置优先级让解析器优先匹配数组类型：

// 先定义优先级：LSQUARE（数组操作）优先级高于IS
%nonassoc LSQUARE
%left IS

// 给数组访问规则指定优先级
expression
    : expression LSQUARE expression RSQUARE %prec LSQUARE
    | expression KW_IS type
    | expression KW_AS type
    | identifier
    ;

// 保留原type规则不变
type
    : fqtypename LSQUARE RSQUARE
    | live_types LSQUARE RSQUARE
    | fqtypename
    | live_types
    ;

这样解析器遇到[时会优先移进，匹配数组类型规则，而非先归约type再处理表达式数组访问。

方案4：拆分表达式规则（避免重复代码） #

如果不想引入GLR或修改类型定义，可以直接将type的两种情况拆入表达式规则，消除中间非终结符带来的歧义：

expression
    : expression LSQUARE expression RSQUARE
    | expression KW_IS fqtypename
    | expression KW_IS fqtypename LSQUARE RSQUARE
    | expression KW_AS fqtypename
    | expression KW_AS fqtypename LSQUARE RSQUARE
    | expression KW_IS live_types
    | expression KW_IS live_types LSQUARE RSQUARE
    | expression KW_AS live_types
    | expression KW_AS live_types LSQUARE RSQUARE
    | identifier
    ;

缺点是会产生代码重复，若后续类型规则扩展，维护成本较高。

验证 #

以最小复现示例测试方案1：添加%define parse.glr true后，Bison编译时将不再报告冲突，且能正确解析两种场景。

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