2

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

  • 如果语法有歧义（例如 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]+”形式的分号分隔的行。

4

2 回答 2

2

使用 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;

消除了移位/减少冲突。

于 2009-06-06T04:48:40.833 回答
0

感谢您精简语法并将其发布。将后继规则更改为 -

successor:      /* empty */ | LETTER successor;

...为我工作。ITYM语言看起来毫不含糊。

于 2009-06-06T04:03:40.640 回答