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

これは機能します：

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

これには 2 つの SHIFT/REDUCE 競合があります。

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

なぜ？

4

4 に答える 4

5

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

%left結合性と優先順位は規則から規則へと継承されないため、これは 2 番目の文法では機能しません。つまり、非終端記号はandbinaryopを生成しても、そのようなものを継承しません。結合性と優先順位は規則にローカライズされ、終端記号を中心に展開されます。PLUSMINUS

はできませんが%left binaryop、文法を少しリファクタリングできます。

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

暗黙的に左結合であるため、競合はなくなりました。binaryopつまり、右側はtermINT のみを生成する であるため、ますます長い式の生成は の左側でのみ発生します。

于 2012-03-15T20:14:12.750 に答える
4

exp binop exp優先順位ルールであいまいさを解決する場合は、ルールの優先順位を指定する必要があります。

exp : exp binaryop exp %prec PLUS;

その変更により、すべての競合が解決されます。

編集

コメントは、yacc/bison の優先順位規則が何をするかについての混乱を示しているようです。

優先順位規則は、文法内のシフト/削減の競合を半自動的に解決する方法です。優先順位を指定するときに何をしているのかを知る必要があるという点で、それらは半自動です。

基本的に、シフトされるトークンと削減されるルールとの間にシフト/削減の競合がある場合は常に、yacc は、シフトされるトークンと削減されるルールの優先順位を比較し、両方に優先順位が割り当てられている限り、 -- 優先順位の高い方を実行します。トークンまたはルールに優先順位が割り当てられていない場合、競合がユーザーに報告されます。

%left//トークン%rightと%nonassocルールの優先順位が同じ場合に問題になります。その場合%left、reduce を行うことを%right意味し、shift を行うことを%nonassoc意味し、どちらも行わないことを意味します。パーサーがこのケースに遭遇すると、実行時に構文エラーが発生します。

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

于 2012-03-16T00:13:01.393 に答える
0

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を行って、PLUSまたはそれ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では、次に何をするかに基づいて何をすべきかを区別できることです。

問題を修正する1つの方法は次のとおりです。

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

%%

exp  : exp binaryop term;
exp  : term;
term : INT;
binaryop: PLUS | MINUS;
于 2012-03-15T21:05:48.370 に答える
0

これは、バイソンのマニュアルで「不思議な対立」と呼ばれているものに該当すると思います。あなたはそれを複製することができます：

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

これにより、4つのS/Rの競合が発生します。

于 2012-03-15T19:17:31.763 に答える