野牛减少/减少

Question

我是 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个reduce/reduce冲突。

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

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

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

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

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

Answer 1

基本问题是您的语法不明确，并且您（尝试）使用优先级规则来解决歧义性，但它失败了，因为歧义性表现为归约/归约冲突，并且优先级规则在这种情况下毫无用处。您可以通过使用 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 将导致在减少将消耗 ~ 的规则之前移动 +。

那么你能对此做些什么呢？您可以接受冲突的存在并制定规则，以便正确的事情发生。在这种情况下，您需要移动表达式：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; }
;

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