3

我是 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()ordo_something_2()因为我不能再判断expris variable_expror composite_expr。

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

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

4

1 回答 1

4

基本问题是您有一个模棱两可的语法，并且您（尝试）使用优先规则来解决歧义，但它失败了，因为歧义表现为减少/减少冲突，而优先规则在这种情况下是无用的。通过使用 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; }
;

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

于 2011-07-18T23:25:14.633 回答