野牛轉變/減少衝突:: = AA規則

Question

我已經寫了下面的野牛語法文件：

%left '+' '-' 
%left '*' '/' 

%token NUMBER 

%% 

expr 
: NUMBER 
| expr '+' expr 
| expr '-' expr 
| expr '*' expr 
| expr '/' expr 
| expr  expr %prec '*' /* implicit multiplication */ 
; 

現在bison報告轉移/減少有關expr : expr expr衝突。我已經提取的問題如下最小集：

%left OP 

%% 

expr 
: 'a' 
| expr expr %prec OP 
; 

我不知道爲什麼是bison仍然會抱怨移進/歸約衝突。我發現了一些舊的郵件存檔：Re: bison/yacc: shift/reduce conflict using %prec for composition，但我也不理解作者的解釋。

有人可以澄清爲什麼這個語法是模棱兩可的，以及如何解決衝突？

編輯：通過NUMBER NUMBER我的意思是NUMBER * NUMBER，即這兩個數字的產品。

Answer 1

這裏的問題是，令牌NUMBER不具有優先級。所以當有一種狀態可以改變NUMBER或減少規則（不管該規則是否有優先權），它不能決定要做什麼。

現在，你可以通過添加一個優先用於NUMBER（使它一樣*）修復這個語法，但它會回來，如果你添加的表達與任何標記以外NUMBER啓動任何規則 - 爲例如，如果您添加expr: '(' expr ')'，您將在'('上獲得轉換/減少衝突。

一個更大的問題是，如果你加一元前綴運算符，如expr: '-' expr。在這種情況下，您不會遇到衝突，因爲' - '已經具有優先權，但像NUMBER - NUMBER這樣的輸入將被解析爲NUMBER (- NUMBER)，這可能根本就不是您想要的。有優先規則處理這個問題沒有好方法。

這種混亂的根本原因是野牛的優先級規則不通過比較兩個規則，你可能會天真地指望基於使用單詞「優先」解決的優先級。相反，他們通過比較要降低的規則的「優先級」和要移動的令牌的「優先級」來進行工作，並基於該優先級來決定是否轉移或減少。在解析發生這種情況時，第二條規則尚未得到承認;相反，野牛隻是猜測它可能基於令牌。

Answer 2

答案的一部分是從bison -v難以看清輸出文件。對於你的第一個語法，我得到了這些摘錄：

State 8 conflicts: 1 shift/reduce 
State 9 conflicts: 1 shift/reduce 
State 10 conflicts: 1 shift/reduce 
State 11 conflicts: 1 shift/reduce 
State 12 conflicts: 1 shift/reduce 

Grammar 

    0 $accept: expr $end 

    1 expr: NUMBER 
    2  | expr '+' expr 
    3  | expr '-' expr 
    4  | expr '*' expr 
    5  | expr '/' expr 
    6  | expr expr 

所以在語法中有5個shift/reduce衝突。這些是較不嚴重的衝突類型;如果您確信語法正在做的是正確的，那麼您可以聲明，如果您希望他們在文法中使用%expect 5。

state 0 

    0 $accept: . expr $end 

    NUMBER shift, and go to state 1 

    expr go to state 2 

state 1 

    1 expr: NUMBER . 

    $default reduce using rule 1 (expr) 

state 2 

    0 $accept: expr . $end 
    2 expr: expr . '+' expr 
    3  | expr . '-' expr 
    4  | expr . '*' expr 
    5  | expr . '/' expr 
    6  | expr . expr 

    $end shift, and go to state 3 
    '+'  shift, and go to state 4 
    '-'  shift, and go to state 5 
    '*'  shift, and go to state 6 
    '/'  shift, and go to state 7 
    NUMBER shift, and go to state 1 

    expr go to state 8 

state 3 

    0 $accept: expr $end . 

    $default accept 

state 4 

    2 expr: expr '+' . expr 

    NUMBER shift, and go to state 1 

    expr go to state 9 

狀態5,6,7模擬狀態4但是對於其他操作員。州8是第一個有轉變/減少衝突的州。記住規則中的.（點）表示解析器達到此狀態時的位置。

state 8 

    2 expr: expr . '+' expr 
    3  | expr . '-' expr 
    4  | expr . '*' expr 
    5  | expr . '/' expr 
    6  | expr . expr 
    6  | expr expr . 

    NUMBER shift, and go to state 1 

    NUMBER [reduce using rule 6 (expr)] 
    $default reduce using rule 6 (expr) 

    expr go to state 8 

state 9 

    2 expr: expr . '+' expr 
    2  | expr '+' expr . 
    3  | expr . '-' expr 
    4  | expr . '*' expr 
    5  | expr . '/' expr 
    6  | expr . expr 

    '*'  shift, and go to state 6 
    '/'  shift, and go to state 7 
    NUMBER shift, and go to state 1 

    NUMBER [reduce using rule 2 (expr)] 
    $default reduce using rule 2 (expr) 

    expr go to state 8 

有這兩種狀態之間的差異和相似性，但狀態10，11，12匹配狀態9除了不同點模糊性。

麻煩的是，當語法看到：

NUMBER OP NUMBER NUMBER 

它不能告訴是否能夠解析爲：

（NUMBER OP NUMBER）NUMBER EXPR EXPR

或爲：

NUMBER OP (NUMBER NUMBER) 
expr OP  expr 

考慮到這是一個轉換/減少關聯在每種情況下，它都選擇轉移。如果這就是你想要的，然後添加%expect 5並繼續生活。如果這不是你想要的，那麼你需要重新思考你的語法。一對相鄰的數字表示什麼，你確定你不需要一些操作符（可能是逗號或冒號）來區分它們嗎？

---

我試圖通過提高丟失的運算符的優先級：

%left MISSING 

其他優先級聲明後，再使用：

expr expr %prec MISSING 

這並沒有改變任何東西。將MISSING的優先級列入其他運營商的優先級也不會太低。

，如果你考慮如何像這樣的表達應該解釋你得到的問題的端倪：

NUMBER OP NUMBER NUMBER NUMBER OP NUMBER NUMBER OP NUMBER 

凡OP是每個外觀相同。我的大腦受傷了！那麼bison的！