如何解决明确语法中的移位归约冲突

Question

我正在尝试使用 LALR(1) 解析器生成器（Bison，但问题并非特定于该工具）来解析简单的语法，并且遇到了移位归约冲突。 我发现的有关修复这些问题的文档和其他来源往往会说明以下一项或多项内容：

• 如果语法不明确（例如 if-then-else 不明确），请更改语言以修复不明确之处。
• 如果是运算符优先级问题，请明确指定优先级。
• 接受默认分辨率并告诉生成器不要抱怨它。

然而，这些似乎都不适用于我的情况：据我所知，语法是明确的（当然，它只有一个前瞻字符是不明确的），它只有一个运算符，默认解析会导致解析错误在正确形成的输入上。 是否有任何技术可以重新设计语法的定义，以消除不属于上述范围的移位归约冲突？

具体而言，这里是有问题的语法：

%token LETTER

%%
%start input;
input:          /* empty */ | input input_elt;
input_elt:      rule | statement;
statement:      successor ';';
rule:           LETTER "->" successor ';';
successor:      /* empty */ | successor LETTER;
%%

目的是解析“[A-Za-z]+”或“[A-Za-z] -> [A-Za-z] 形式的分号分隔行+”。

Answer 1

使用 Solaris 版本的 yacc，我得到：

1: shift/reduce conflict (shift 5, red'n 7) on LETTER
state 1
    $accept :  input_$end
    input :  input_input_elt
    successor : _    (7)

    $end  accept
    LETTER  shift 5
    .  reduce 7

    input_elt  goto 2
    rule  goto 3
    statement  goto 4
    successor  goto 6

所以，问题是，正如经常出现的那样，空规则 - 具体来说，空后继者。 目前尚不完全清楚您是否希望允许分号作为有效输入 - 目前是这样。 如果将后继规则修改为：

successor: LETTER | successor LETTER;

则消除了移位/归约冲突。

Answer 2

感谢您削减语法并发布它。 将继任者规则更改为 -

successor:      /* empty */ | LETTER successor;

...对我有用。 ITYM 这种语言看起来很明确。