0

私は Bison で文法を定義する過程にあり、排除したい shift/reduce 競合に出くわしました。if/else競合は、ステートメントを一致させることを目的としたルールによって引き起こされます。

state 17

   13 Stmt: IfBlock . OptionalElseBlock

    ELSE  shift, and go to state 42

    ELSE      [reduce using rule 16 (OptionalElseBlock)]
    $default  reduce using rule 16 (OptionalElseBlock)

    OptionalElseBlock  go to state 43

OptionalElseBlockは次のように定義されました。

   16 OptionalElseBlock: /* empty */
   17                  | ELSE Stmt

状態 42 と 43 は、shift と reduce の情報が省略された次のようになります。

state 42
   17 OptionalElseBlock: ELSE . Stmt

state 43
   13 Stmt: IfBlock OptionalElseBlock .

OptionalElseBlock以前にオプションのトークンを使用したことがありますが、パーサーの先読みバッファーには 1 つの端末しか含まれていないため、競合が発生していると推測しています。この競合を解決する簡単な方法はありますか?

4

2 に答える 2

0

同じ質問に対する私の回答を見たいと思うかもしれません。これはよくある質問です。

if-then-else の競合を減らすシフトを削除するための文法の修正

%expect n0 以外には使用しないことをお勧めします。

于 2012-11-26T08:27:23.557 に答える
0

これは古典的な shift/reduce 競合です。問題は次のとおりです。

if (c1) if (c2) stmt1; else stmt2;

問題は がどちらifにelse属しているかです。オプションではない場合、問題はありません。または、ifステートメントを終了する必要がある場合 (人気のある 2 つの選択肢を選択するためにfiorendで言う)、C構文が勝ったように見えるため、シフト/リデュースの競合が発生します。

この問題を示さない文法を書くことは可能ですが、自明ではありません。優先順位ルールでゲームをプレイするか、シフト/削減の競合を単に「期待」することで、競合を隠すことができます。（私は後者を好みますが、優先ハックの方が優れていると言う人はたくさんいますが、同じことになります。）

書き換えられた文法は、ドラゴン ブックやおそらく他の構文解析テキストの演習であるため、学習目的で行う価値はあるかもしれませんが、文法の維持という点では非常に面倒であり、文法が非常に読みにくくなります。すべての懸念。

優先順位とシフト優先度を使用して構文解析を単純化する方法に関する古典的な論文は、1975 年に出版された Aho、Johnson、および Ullman による「あいまいな文法の決定論的構文解析」です。適切なライブラリにアクセスできない場合でも、Google はオンラインで読めるコピーを見つけてくれるでしょう。

于 2012-11-25T17:16:52.410 に答える