野牛减少/减少

Question

我是新来的野牛解析，我不明白它是如何工作的。我有以下语法，我一直保持最低限度以突出问题。

%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是非常长的。所以重复它是不可能的。

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（因为~比+更高优先级）来说，你的规则很重要，但是野牛中的优先消歧规则有点破解并且无法处理 - 它不了解减少规则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领域的结构与其他任何你用它一起。