野牛減少/減少

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領域的結構與其他任何你用它一起。