3

次の bison 文法ファイルを作成しました。

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

%token NUMBER

%%

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

bisonに関する shift/reduce 競合を報告するようになりまし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、この 2 つの数値の積です。

4

2 に答える 2

3

ここでの問題は、トークンNUMBERに優先順位がないことです。そのため、(そのルールに優先順位があるかどうかに関係なく) ルールをシフトNUMBERまたは削減できる状態がある場合、どちらを実行するかを決定できません。

これで、優先順位 for NUMBER(make it the same as *) を追加することでこの文法を修正できますが、式以外の任意のトークンで始まる規則を追加すると、元に戻ってしまいNUMBERますexpr: '(' expr ')'。で shift/reduce 競合を取得し'('ます。

などの単項前置演算子を追加すると、さらに大きな問題になりますexpr: '-' expr。この場合、'-' がすでに優先されているため競合は発生しませんが、 のような入力はNUMBER - NUMBERとして解析されNUMBER ( - NUMBER )ます。この問題を優先ルールで処理する良い方法はありません。

この混乱の根底にある原因は、bison の優先順位規則が、「優先順位」という言葉の使用に基づいて素朴に期待するように、2 つの規則を比較することによって優先順位を解決しないことです。代わりに、削減されるルールの「優先順位」とシフトされるトークンの「優先順位」を比較し、それに基づいてシフトまたは削減の決定を下すことによって機能します。これが発生する解析の時点では、2 番目のルールはまだ認識されていません。代わりに、バイソンはトークンに基づいてそれが何であるかを推測しているだけです。

于 2012-02-12T03:03:54.370 に答える
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 つのシフト/リデュースの競合があります。これらは、それほど深刻ではないタイプの紛争です。%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

これら 2 つの状態には相違点と類似点がありますが、状態 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 を他の演算子の前にリストして、MISSING の優先順位を非常に低くすることもありません。

次のような式をどのように解析する必要があるかを考えると、問題が少しわかります。

NUMBER OP NUMBER NUMBER NUMBER OP NUMBER NUMBER OP NUMBER

OPは各登場で同じところ。脳が痛い！さんもそうですbison！

于 2012-02-11T20:05:18.580 に答える