野牛减少/减少

我是 Bison 解析的新手，我无法理解它是如何工作的。我有以下语法，我保留了最低限度以突出问题。

%left '~'
%left '+'
%token T_VARIABLE
%%
start: expr;
expr: composite_expr | variable_expr;
variable_expr: T_VARIABLE;
composite_expr:
     expr '+' expr
   | '~' variable_expr   { do_something_1(); }
   | '~' composite_expr  { do_something_2(); }
;

%%

如您所见，我想根据后面的表达式类型对 '~' 运算符应用不同的函数。但是，这会产生 2 个减少/减少冲突。

当然，如果我像这样重写composite_expr规则......

composite_expr:
     expr '+' expr
   | '~' expr           { /* ??? */ }
;

...然后没有冲突，但现在我不能调用 do_something_1() 或 do_something_2() ，因为我无法再判断 expr 是 variable_expr 还是 composite_expr 。

有没有其他方法可以做到这一点？谁能解释为什么首先减少/减少冲突？

请记住，这是一个精简版，实际上，规则 composite_expr 很长。所以复制它是不可能的。

最佳答案

基本问题是你有一个歧义的语法，你(试图)使用优先规则来解决歧义，但它失败了，因为歧义表现为减少/减少冲突，在这种情况下优先规则是无用的。通过使用 bison 的 -v 选项获取它构建的状态机的列表，您可以更好地了解正在发生的事情，这样您就可以准确地看到冲突在哪里以及如何表现出来。

在这种情况下，您将看到如下内容:

state 8

    3 expr: variable_expr .
    6 composite_expr: '~' variable_expr .

    $end      reduce using rule 6 (composite_expr)
    '+'       reduce using rule 3 (expr)
    '+'       [reduce using rule 6 (composite_expr)]
    $default  reduce using rule 3 (expr)

这告诉你它不知道在 + 的前瞻中减少哪个规则。现在显然从您的优先规则来看，您需要规则 6(因为 ~ 的优先级高于 + )，但是 bison 中的优先消歧规则有点麻烦，无法解决这个问题——它无法理解减少规则 3将导致在减少消耗 + 的规则之前移动 ~ 。

那么你能做些什么呢？您可以接受冲突的存在并制定规则，以便正确的事情发生。在这种情况下，您需要将 expr: composite_expr | variable_expr 规则移到最后(至少到 composite_expr 规则之后)。这有点难看，难以理解，甚至更难维护。

或者，您可以取消因素以摆脱单个规则(具有单个非终端且右侧没有其他任何内容的规则 - 这些规则往往会触发减少/减少问题。)例如:

composite_expr:
     composite_expr '+' composite_expr
   | composite_expr '+' variable_expr
   | variable_expr '+' composite_expr
   | variable_expr '+' variable_expr
   | '~' variable_expr   { do_something_1(); }
   | '~' composite_expr  { do_something_2(); }
;

如果像您描述的那样有很多 composite_expr 规则，这不太可能实用。

最好的选择可能是根本不在语法中这样做，而是根据您的语义规则进行选择。就像是:

expr:
     expr '+' expr      { $$.isComposite = true; }
   | '~' expr           { if ($2.isComposite)
                              do_something_2();
                          else
                              do_something_1();
                          $$.isComposite = true; }
   | T_VARIABLE         { $$.isComposite = false; }
;

并且您将 %type 的 expr 设置为一个带有额外 bool isComposite 字段的结构以及您使用它的任何其他内容。

关于野牛减少/减少，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/6718917/