爲什麼這個簡單的語法有一個轉換/減少衝突？

Question

%token <token> PLUS MINUS INT 
%left PLUS MINUS 

工作的：

exp : exp PLUS exp; 
exp : exp MINUS exp; 
exp : INT; 

這具有2 SHIFT /減少衝突：

exp : exp binaryop exp; 
exp : INT; 
binaryop: PLUS | MINUS ; 

爲什麼？

Answer 1

這是因爲第二個其實是模棱兩可的。第一個語法也是如此，但您通過添加%left來解決模糊問題。

這個%left在第二個語法中不起作用，因爲關聯性和優先級不是從規則到規則繼承的。即即使產生了​​和MINUS，那麼binaryop非終結符也不會繼承任何此類事物。關聯性和預定性本地化爲一個規則，圍繞着終端符號。

我們不能做%left binaryop，但我們可以稍微重構語法：

exp : exp binaryop term 
exp : term; 
term : INT; 
binaryop: PLUS | MINUS ; 

那現在有沒有衝突，因爲它是隱含左結合。即產生更長和更長的表達式只能發生在binaryop的左側，因爲右側是僅產生INT的term。

Answer 2

我認爲這屬於Bison手冊所稱的「Mysterious Conflicts」。你可以複製：

exp: exp plus exp; 
exp: exp minus exp; 
exp: INT; 
plus: PLUS; 
minus: MINUS; 

這給我四個S/R衝突。

Answer 3

描述Linux上Bison（版本2.3）產生的衝突語法的輸出文件如下。頂部的關鍵信息是'國家7有衝突'。

State 7 conflicts: 2 shift/reduce 

Grammar 

    0 $accept: exp $end 

    1 exp: exp binaryop exp 
    2 | INT 

    3 binaryop: PLUS 
    4   | MINUS 

Terminals, with rules where they appear 

$end (0) 0 
error (256) 
PLUS (258) 3 
MINUS (259) 4 
INT (260) 2 

Nonterminals, with rules where they appear 

$accept (6) 
    on left: 0 
exp (7) 
    on left: 1 2, on right: 0 1 
binaryop (8) 
    on left: 3 4, on right: 1 

state 0 

    0 $accept: . exp $end 

    INT shift, and go to state 1 

    exp go to state 2 

state 1 

    2 exp: INT . 

    $default reduce using rule 2 (exp) 

state 2 

    0 $accept: exp . $end 
    1 exp: exp . binaryop exp 

    $end shift, and go to state 3 
    PLUS shift, and go to state 4 
    MINUS shift, and go to state 5 

    binaryop go to state 6 

state 3 

    0 $accept: exp $end . 

    $default accept 

state 4 

    3 binaryop: PLUS . 

    $default reduce using rule 3 (binaryop) 

state 5 

    4 binaryop: MINUS . 

    $default reduce using rule 4 (binaryop) 

state 6 

    1 exp: exp binaryop . exp 

    INT shift, and go to state 1 

    exp go to state 7 

這裏是關於「國家7」的信息：

state 7 

    1 exp: exp . binaryop exp 
    1 | exp binaryop exp . 

    PLUS shift, and go to state 4 
    MINUS shift, and go to state 5 

    PLUS  [reduce using rule 1 (exp)] 
    MINUS  [reduce using rule 1 (exp)] 
    $default reduce using rule 1 (exp) 

    binaryop go to state 6 

麻煩的是通過在該行的.標記描述標記1。由於某種原因，%left不像您預期​​的那樣「生效」，所以Bison在讀取exp PLUS exp時發現衝突，並在其後發現​​或MINUS。在這種情況下，Bison（和Yacc）會進行轉變而不是減少。在這種情況下，我認爲這等於給予規則正確的優先權。

將%left更改爲%right並省略它不會更改結果（根據衝突警告）。我也在Solaris上嘗試過Yacc，它產生了基本相同的衝突。

那麼，爲什麼第一個語法工作？這裏的輸出：

Grammar 

    0 $accept: exp $end 

    1 exp: exp PLUS exp 
    2 | exp MINUS exp 
    3 | INT 

Terminals, with rules where they appear 

$end (0) 0 
error (256) 
PLUS (258) 1 
MINUS (259) 2 
INT (260) 3 

Nonterminals, with rules where they appear 

$accept (6) 
    on left: 0 
exp (7) 
    on left: 1 2 3, on right: 0 1 2 

state 0 

    0 $accept: . exp $end 

    INT shift, and go to state 1 

    exp go to state 2 

state 1 

    3 exp: INT . 

    $default reduce using rule 3 (exp) 

state 2 

    0 $accept: exp . $end 
    1 exp: exp . PLUS exp 
    2 | exp . MINUS exp 

    $end shift, and go to state 3 
    PLUS shift, and go to state 4 
    MINUS shift, and go to state 5 

state 3 

    0 $accept: exp $end . 

    $default accept 

state 4 

    1 exp: exp PLUS . exp 

    INT shift, and go to state 1 

    exp go to state 6 

state 5 

    2 exp: exp MINUS . exp 

    INT shift, and go to state 1 

    exp go to state 7 

state 6 

    1 exp: exp . PLUS exp 
    1 | exp PLUS exp . 
    2 | exp . MINUS exp 

    $default reduce using rule 1 (exp) 

state 7 

    1 exp: exp . PLUS exp 
    2 | exp . MINUS exp 
    2 | exp MINUS exp . 

    $default reduce using rule 2 (exp) 

區別似乎是在狀態6和7，它能夠根據接下來的內容來區分做什麼。

解決這個問題的方法之一是：

%token <token> PLUS MINUS INT 
%left PLUS MINUS 

%% 

exp : exp binaryop term; 
exp : term; 
term : INT; 
binaryop: PLUS | MINUS; 

Answer 4

你需要指定exp binop exp規則優先級，如果你想優先規則來解決歧義：

exp : exp binaryop exp %prec PLUS; 

與該改變，所有的衝突都得到解決。

編輯

的評論似乎表明一些混亂，什麼YACC /野牛優先規則做。

優先規則是一種半自動解決語法中的移位/減少衝突的方法。它們只是半自動的，因爲在指定優先級時，您必須知道自己在做什麼。基本上，每當在要移動的標記和要減少的規則之間存在移位/減少衝突時，yacc比較要移位的標記的優先級和要減少的規則，以及 - 只要兩者都有優先權 - 以較高優先權爲準。如果令牌或規則沒有分配優先級，則將衝突報告給用戶。

%left/%right/%nonassoc當令牌和規則具有相同的優先級時進入圖片。在這種情況下，%left表示執行縮減，%right表示執行移位，而%nonassoc表示兩者都不執行，如果解析器運行到此情況，則會在運行時導致語法錯誤。

優先級本身被分配給標記%left/%right/%nonassoc以及規則%prec。唯一的奇怪之處在於，沒有%prec的規則和RHS上的至少一個終端獲得了RHS上最後一個終端的優先級。這有時最終可能會將優先級分配給您不希望優先考慮的規則，而這些優先規則有時會因錯誤地解決而導致隱藏衝突。您可以通過在相關規則中添加額外級別的間接來避免這些問題 - 將RHS上的有問題的終端更改爲擴展到該終端的新的非終端。