3

私は Bison の解析が初めてで、それがどのように機能するのか理解できません。私は次の文法を持っています。ここでは、問題を強調するために最小限を維持しています。

%left '~'
%left '+' 
%token T_VARIABLE
%% 
start: expr;
expr: composite_expr | variable_expr;
variable_expr: T_VARIABLE;
composite_expr:   
     expr '+' expr      
   | '~' variable_expr   { do_something_1(); }
   | '~' composite_expr  { do_something_2(); }
;

%%

ご覧の'~'とおり、後続の式の種類に応じて、さまざまな関数を演算子に適用したいと考えています。ただし、これにより 2 つの reduce/reduce 競合が発生します。

もちろん、composite_expr ルールを次のように書き直すと...

composite_expr:   
     expr '+' expr      
   | '~' expr           { /* ??? */ }
;

...その後、競合はありませんが、 isまたは かどうかわからなくなったため、 do_something_1()orを呼び出すことができません。do_something_2()exprvariable_exprcomposite_expr

これを行うことができる他の方法はありますか？そもそも競合を削減/削減する理由を誰かが説明できますか?

これは簡略化されたバージョンであり、実際にはルールcomposite_exprが非常に長いことに注意してください。したがって、それを複製することは問題外です。

4

1 に答える 1

4

基本的な問題は、あいまいな文法があり、あいまいさを解決するために優先順位規則を使用しようとしているが、あいまいさが削減/削減の競合として現れ、優先規則が役に立たないため失敗することです。bison のオプションを使用して、それが構築するステート マシンのリストを取得することで、何が起こっているのかをよりよく理解できるため-v、競合がどこでどのように発生するかを正確に確認できます。

この場合、次のように表示されます。

state 8

    3 expr: variable_expr .
    6 composite_expr: '~' variable_expr .

    $end      reduce using rule 6 (composite_expr)
    '+'       reduce using rule 3 (expr)
    '+'       [reduce using rule 6 (composite_expr)]
    $default  reduce using rule 3 (expr)

これは、 の先読みで削減するルールがわからないことを示しています+。優先ルールから明らかにルール 6 が必要ですが (~は よりも優先順位が高いため+)、bison の優先順位の曖昧さ回避ルールはちょっとしたハックであり、これに対処できません。ルール 3 を減らすと結果が生じることを理解できません。+を消費するルールを削減する前に をシフトし~ます。

それで、これについて何ができますか？競合の存在を受け入れて、正しいことが起こるようにルールを整えることができます。この場合、expr: composite_expr | variable_exprルールを最後 (少なくともcomposite_exprルールの後) に移動する必要があります。これは見苦しく、理解しにくく、維持するのがさらに困難です。

別の方法として、単一のルール (単一の非終端記号があり、右側に他に何もないルール - これらは、reduce/reduce の問題を引き起こす傾向があるルールです) を取り除くために要素を分解することができます。

composite_expr:   
     composite_expr '+' composite_expr
   | composite_expr '+' variable_expr
   | variable_expr '+' composite_expr
   | variable_expr '+' variable_expr
   | '~' variable_expr   { do_something_1(); }
   | '~' composite_expr  { do_something_2(); }
;

あなたが説明したような多くのcomposite_exprルールがある場合、これは実用的ではありません。

最良の代替案は、これを文法でまったく行わず、代わりにセマンティック ルールに基づいて選択することです。何かのようなもの：

expr:   
     expr '+' expr      { $$.isComposite = true; }
   | '~' expr           { if ($2.isComposite)
                              do_something_2();
                          else
                              do_something_1();
                          $$.isComposite = true; }
   | T_VARIABLE         { $$.isComposite = false; }
;

%typeそして、 forを、それを使用していた他のものと一緒exprに追加のbool isCompositeフィールドを持つ構造体になるようにセットアップします。

于 2011-07-18T23:25:14.633 に答える