Loading article…
ぶら下がりelseは、構文解析器生成器のプログラミングにおける問題で、 if-then(-else)文のオプションのelse句が、入れ子になった条件文を曖昧にする可能性がある。形式的には、この言語の参照文脈自由文法は曖昧であり、正しい構文木が複数存在することを意味する。
多くのプログラミング言語では、条件付き実行コードはif-then形式とif-then-else形式の2つの形式で記述できます。（else句は省略可能です。）
aならばs 、 bならばs1、そうでなければs2
s入れ子になった文がある場合、特に上記の if-then 構造内の文が if-then-else 形式に置き換えられた場合、解釈が曖昧になる可能性があります。
aならば、 bならば、 s1、そうでなければs2
この例では、はが真で がs1真の場合にのみ実行されます。では、 はどうでしょうか？ある人は、が偽のときはいつでも が実行されると確信するかもしれません（最初のifにelseを付加することで）。一方、別の人は、が真で が偽の場合にのみ が実行されると確信するかもしれません（2 番目のifにelseを付加することで）。言い換えれば、前の文は、次の明確な文のいずれかと同等であると解釈される可能性があります。abs2s2as2ab
aの場合{ bの場合s1 }それ以外の場合s2 aの場合{ bの場合s1 }それ以外の場合s2 }ぶら下がりelseの問題はALGOL 60 [ 1 ]に遡り、その後の言語ではさまざまな方法で解決されてきました。LRパーサーでは、ぶら下がりelseはシフトリデュース競合の典型的な例です。
具体的な例を以下に示します。
C言語における文法は、部分的に以下のようになっている。
声明 = ... 選択ステートメント 選択ステートメント = ... | IF（式）ステートメント | IF（式）文 ELSE文
したがって、追加の規則なしに、声明は
( a )の場合、( b )の場合、 s ;それ以外の場合はs2 ;曖昧に解釈される可能性があり、以下のどちらかである可能性がある。
if ( a ) { if ( b ) s ; else s2 ; }または：
if ( a ) { if ( b ) s ; } else s2 ;C 標準では、elseブロックは最も近い に関連付けられていることが明確にされていますif。[ 2 ]したがって、最初のツリーが選択されます。
この問題は、コンパイラの構築、特にスキャナレス構文解析でよく発生します。ぶら下がっているelseを処理する際の慣習は、elseを近くのif文に付加することです[ 3 ] 。これにより、特に曖昧さのない文脈自由文法が可能になります。Pascal [ 4 ] 、 C [ 2 ]、Java [ 5 ]などのプログラミング言語はこの慣習に従っているため、言語のセマンティクスに曖昧さはありませんが、パーサジェネレータを使用すると曖昧な文法begin...endになる可能性があります。このような場合、 Pascal [ 6 ]や{...}Cのように、明示的なブロックによって別のグループ化が行われます。
コンパイラの構築方法によっては、曖昧さを回避するために異なる修正措置を講じる必要がある。
構文内でelseとifの間のリンクを明示的にすることで、この問題も解決できます。これは通常、人的ミスを防ぐのに役立ちます。[ 7 ]
考えられる解決策は以下のとおりです。
if e do s1 択の場合に を、if e1 then e2 else e3一般的な場合にを使用します。 [ 10 ]上記の例は、曖昧さを解消するために次のように書き換えることができます 。
ステートメント: open_statement | クローズドステートメント ; open_statement: IF '(' 式 ')' ステートメント | IF '(' 式 ')' クローズドステートメント ELSE オープンステートメント ; closed_statement: non_if_statement | IF '(' 式 ')' クローズドステートメント ELSE クローズドステートメント ; non_if_statement: ... ; statement文に関連するその他の文法規則も、直接的または間接的に aまたはselection-statement非終端記号で終わる可能性がある場合は、同様に複製する必要があるかもしれません。
しかし、ここではif文とwhile文の両方を含む文法を示します。
ステートメント: open_statement | クローズドステートメント ; open_statement: IF '(' 式 ')' ステートメント | IF '(' 式 ')' クローズドステートメント ELSE オープンステートメント | WHILE '(' 式 ')' open_statement ; closed_statement: simple_statement | IF '(' 式 ')' クローズドステートメント ELSE クローズドステートメント | WHILE '(' 式 ')' closed_statement ; シンプルなステートメント: ... ; 最後に、曖昧なIF文を禁止する文法を示します。
ステートメント: open_statement | クローズドステートメント ; open_statement: IF '(' 式 ')' ステートメント | IF '(' 式 ')' クローズドステートメント ELSE オープンステートメント | WHILE '(' 式 ')' open_statement ; closed_statement: simple_statement | IF '(' 式 ')' クローズドステートメント ELSE クローズドステートメント | WHILE '(' 式 ')' closed_statement ; シンプルなステートメント: ... ; この文法では、文はif (a) if (b) c else d一方向にしか解析できません。なぜなら、もう一方の解釈（if (a) {if (b) c} else d）は次のように生成されるからです。
声明 オープンステートメント IF '(' 式 ')' クローズドステートメント ELSE オープンステートメント 'if' '(' 'a' ')' closed_statement 'else' 'd' そして、構文解析はclosed_statement「if (b) c」に一致させようとして失敗します。 を使用した試みもclosed_statement同様に失敗します。もう一方の構文解析if (a) {if (b) c else d}) は成功します。
声明 オープンステートメント IF '(' 式 ')' ステートメント IF '(' 式 ')' 閉じられたステートメント IF '(' a ')' (IF '(' 式 ')' closed_statement ELSE closed_statement) IF '(' a ')' (IF '(' b ')' c ELSE 'd')