なぜこの単純な文法には、シフト/リダクションの競合がありますか？

Question

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

THISワークス：

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

これは2 SHIFT /還元衝突HAS：

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

WHYを？

Answer 1

これは実際にはあいまいであるためです。最初の文法もそうですが、あなたは%leftを追加してあいまいさを解決しました。

この%leftは、連合性と優先度がルール間で継承されないため、2番目の文法では機能しません。私。 binaryop​​とMINUSを生成しても、非終端記号はそのようなものを継承しません。連合性とpredecenceは規則にローカライズされ、終端記号を中心に回転します。

我々は%left binaryopを行うことはできませんが、我々はわずか文法リファクタリングすることができます

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

それは暗黙のうちに、左結合されているので、今何の競合を持っていません。私。右側がでINTしか生成されないため、より長い表現と長い表現の生成は、binaryopの左側でのみ発生する可能性があります。

Answer 2

これは、Bisonのマニュアルでは「Mysterious Conflicts」と呼ばれています。私のための4つのS/Rの競合を与える

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

：あなたがそれを複製することができます。

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の/バイソンでの優先順位のルールは何をすべきかに関して、いくつかの混乱を示しているように見えます。

優先ルールは、文法におけるシフト/リダクションの競合を半自動的に解決する方法です。彼らは優先順位を指定するときに何をしているのかを知る必要があるという点で半自動でしかありません。

Bascallyでは、シフトされるトークンと縮小されるルールとの間にシフト/リダクションの競合がある場合、yaccはシフトされるトークンの優先順位と削減されるルールを比較します。どちらにも優先順位が割り当てられています。トークンまたはルールに優先順位が割り当てられていない場合、競合はユーザーに報告されます。

%left/%right/%nonassocトークンとルールの優先順位が同じ場合に画像が表示されます。その場合、%leftは縮約を意味し、%rightはシフトを意味し、%nonassocはどちらも実行しないことを意味します。この場合、パーサーが実行されると実行時に構文エラーが発生します。

優先レベル自体は、%left/%right/%nonassocのトークンと%precのルールで割り当てられます。唯一の奇妙な点は、%precのないルールとRHSの少なくとも1つの端末がRHSの最後の端末の優先順位を取得することです。これにより、優先順位をつけたくないルールに優先順位を割り当てることがあります。ルールを誤って解決すると、競合が隠されることがあります。問題のルールに余分なレベルの間接参照を追加することで、これらの問題を回避できます。RHSの問題のある端末を、その端末だけに展開する新しい非終端記号に変更します。