次: , 前: Look-Ahead, 上: Algorithm


5.2 シフト還元衝突

次の2個の規則で定められる、“if-then”と“if-then-else”文を持つ 言語の構文解析について考えます。

     if_stmt:
               IF expr THEN stmt
             | IF expr THEN stmt ELSE stmt
             ;

ここで、IFTHENELSEは、 キーワードトークンを表す終端記号であると仮定します。

ELSEトークンが読まれて先読みトークンになったときに、 入力が正しいと仮定して、スタックの内容はちょうど 最初の規則で還元される右辺になっています。 しかし、いずれ起こるはずの第2の規則の還元のために、 ELSEトークンをシフトすることも有効です。

この、シフトと還元の両方が有効な場合を、 シフト還元衝突(shift/reduce conflict)と呼びます。 Bisonは、演算子優先規則宣言で特に指定されていないかぎり、 シフトを選ぶことで衝突を解決するように設計されています。 この理由を理解するために、別の選択肢と比較してみましょう。

構文解析器はELSEのシフトを選ぶので、その結果、 else節はもっとも内側のif文に対応し、次の2つの入力は等価になります。

     if x then if y then win (); else lose;
     
     if x then do; if y then win (); else lose; end;

しかし、字句解析器がシフトでなく還元を選ぶと、その結果、 else節がもっとも外側のif文に対応し、次の2つの入力は等価になります。

     if x then if y then win (); else lose;
     
     if x then do; if y then win (); end; else lose;

文法があいまいに書かれているために、衝突が起きます。 つまり、入れ子になったif文について、どちらの構文解析結果も正当なのです。 確立された習慣では、else節をもっとも内側のif文に対応させて、 あいまいさを解決しています。 これが、Bisonが還元よりもシフトを選ぶ理由です (理想的には、あいまいでない文法を書くべきですが、この場合には困難です)。 この問題は、Algol 60の仕様の中に現れたのが最初で、 「ぶらさがりelse(dangling else)」問題と呼ばれています。

予測可能で正当なシフト還元衝突について、Bisonが警告を表示しないように、 %expect n宣言を使えます。 すると、ちょうどn個のシフト還元衝突があるかぎり、 警告は表示されません。 See Suppressing Conflict Warnings

上記のif_stmtの定義は、衝突をわざと発生させるために書きましたが、 追加の規則がなければ実際には衝突が起きません。 次に、実際に衝突を含む完全なBison入力ファイルの例を示します。

     %token IF THEN ELSE variable
     %%
     stmt:     expr
             | if_stmt
             ;
     
     if_stmt:
               IF expr THEN stmt
             | IF expr THEN stmt ELSE stmt
             ;
     
     expr:     variable
             ;