咨询Bison代码出现1个offset/reduce冲突警告的原因

问题背景 #

目标命令格式为 save depth=1 exclude=[w1 w2]，编译Bison文件时出现警告：

parser.y: Warning: 1 offset/reduce conflict [-Wconflicts-sr]
parser.y: note: rerun with option '-Wcounterexamples' to generate conflict counterexamples

执行bison -Wcounterexamples parser.y得到冲突示例：

Example: • STRING
  Shift derivation
    strings
    ↳ 5: • STRING
  Reduce derivation
    strings
    ↳ 6: strings  STRING
         ↳ 4: ε •

Bison代码片段如下：

%union {
    char *str;
    int number;
}
%token SAVE DEPTH EXCLUDE
%token LB RB EQ COMMA NUMBER STRING NEWLINE
%%
input:
    | command NEWLINE input
    | command
    ;
strings:
    | STRING
    | strings STRING
    ;
command:
    SAVE DEPTH EQ NUMBER EXCLUDE EQ LB strings RB{ printf("Command parsed successfully.\n"); }
    | error { printf("Error: Invalid command.\n"); }
    ;
%%
int main()
{
    printf("Enter your commands:\n");
    while (1) {
        yyparse();
        if (feof(stdin)) {
            break;
        }
        yylex_destroy();
        yyrestart(stdin);
    }
    return 0;
}

需求是EXCLUDE的格式应为EXCLUDE=[w1]或EXCLUDE=[x1 m1 a3]，需明确冲突原因。

冲突原因 #

冲突源于strings规则的歧义：

strings:
    | STRING          // 匹配单个字符串
    | strings STRING  // 匹配字符串序列
    ;

第一条空分支允许strings匹配空串。当解析器遇到第一个STRING时，有两种合法操作：

1. 移进：直接将当前STRING作为strings的唯一元素（对应strings: STRING规则）。
2. 归约：先把空串归约为strings，再将当前STRING与空strings组合成新的strings（对应strings: strings STRING规则，其中第一个strings是空串）。

这两种操作的结果等价，但Bison无法自动判断优先级，因此抛出移进/归约冲突警告。

解决方法 #

根据需求，EXCLUDE的方括号内至少要有一个字符串，因此可以去掉strings的空分支，重新定义规则：

strings:
    STRING
    | strings STRING
    ;

修改后，strings必须包含至少一个STRING，既符合格式要求，又消除了歧义——解析器遇到第一个STRING时只能选择移进，后续STRING则会与已有的strings组合，不再出现冲突。

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