Next: Precedence, Previous: Look-Ahead, Up: Algorithm
次の2個の規則で定められる、“if-then”と“if-then-else”文を持つ 言語の構文解析について考えます。
if_stmt: IF expr THEN stmt | IF expr THEN stmt ELSE stmt ;
ここで、IF
、THEN
、ELSE
は、
キーワードトークンを表す終端記号であると仮定します。
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 ;