ぶら下がっているelse

ぶら下がりelseは、パーサー ジェネレーターのプログラミングにおける問題で、 if-then(-else)ステートメント内のオプションの else 節によって、ネストされた条件があいまいになります。正式には、言語の参照文脈自由文法はあいまいであり、正しい構文解析ツリーが複数存在することを意味します。

多くのプログラミング言語では、条件付きで実行されるコードを、if-then 形式と if-then-else 形式の 2 つの形式で記述できます。else 句はオプションです。

もしaならばs、
もしbならばs1 、そうでなければs2

これにより、ネストされたステートメントがある場合、特に if-then 形式がs1if-then-else 形式のように現れる場合は、解釈の曖昧さが生じます。

もしaならば bならばs、そうでなければs2

この例では、が真で が真のs場合に が明確に実行されますが、 が偽の場合(つまり、else が最初の if に付加される) またはが真で が偽の場合 (つまり、else が 2 番目の if に付加される) に が実行される、と解釈することもできます。つまり、前のステートメントは、次のいずれかの式として見ることができます。 abs2aab

もしaならば(もしbならばs)そうでなければs2
もしaならば(もしbならばsそうでなければs2)

ぶら下がりelse問題はALGOL 60 ^[1]に遡り、その後の言語では様々な方法で解決されてきました。LRパーサでは、ぶら下がりelseはシフト還元競合の典型的な例です。

これはコンパイラの構築、特にスキャナレス構文解析でよく起こる問題です。ぶら下がっているelseを扱うときの慣例は、elseを近くのif文に付加することです。^[2]これにより、特に明確な文脈自由文法が可能になります。Pascal、^[3]、 C ^[4]、Java ^{[5]などのプログラミング言語はこの慣例に従っているため、}言語の意味に曖昧さはありませんが、パーサジェネレータを使用すると文法がbegin...end曖昧になる可能性があります。このような場合、 Pascal ^[6]や{...}Cの ように明示的なブロックによって代替のグループ化が行われます。

コンパイラの構築アプローチに応じて、曖昧さを避けるためにさまざまな修正アクションを実行する場合があります。

• パーサーがSLR、LR(1)、またはLALR LRパーサージェネレータによって生成された場合、プログラマは、競合がある場合には常にシフトをリデュースよりも優先するという生成されたパーサー機能に依存することがよくあります。^[2]あるいは、文法を書き直して競合を除去することもできますが、文法のサイズが増加します（以下を参照）。
• パーサーが手書きの場合、プログラマーは曖昧さのない文脈自由文法を使用できます。あるいは、非文脈自由文法または解析式文法に頼ることもできます。

この問題は、構文内でelseとそのifの間のリンクを明示的にすることでも解決できます。これにより、通常、人為的なエラーを回避できます。^[7]

考えられる解決策は次のとおりです。

• if 構造の終了を区切る「end if」記号を持ちます。このような言語の例としては、ALGOL 68、Ada、Eiffel、PL/SQL、Visual Basic、Modula-2、AppleScriptなどがあります。
• 「then」に続く文が「if」そのものになることを禁止する（ただし、if-then節のみを含む一対の文括弧は許可される）。このアプローチはALGOL 60で採用されている。^[8]
• 「else」が「if」に続く場合は中括弧（括弧）が必要である。^[9]
• すべての「if」を「else」とペアにする必要があります。構文ではなく意味に関する同様の問題を回避するために、Racket はSchemeとは異なりif、フォールバック句のない をエラーと見なして、条件式(つまりif) と条件文(つまり、フォールバック句のないwhenおよび) を効果的に区別します。unless
• 1つの選択肢と2つの選択肢の「if」文に異なるキーワードを使用する。S -algolはif e do s、1つの選択肢の場合とif e1 then e2 else e3一般的な場合に使用します。 ^[10]
• Swiftのように、無条件に中括弧を必要とします。Python では、インデント ルールによって「if」ステートメント内のブロックだけでなく、すべてのブロックが区切られるため、これは事実上当てはまります。

具体的な例は以下の通りです。

Cでは、文法の一部は次のようになります。

ステートメント = ...
    | 選択ステートメント

 選択ステートメント = ...
    | IF (式) ステートメント
    | IF (式) 文 ELSE 文

したがって、さらなる規則がなければ、

もし( a )ならば( b ) s ;そうでなければs2 ;      

次のように曖昧に解析される可能性があります:

もしaなら{もしbならs ;そうでなければs2 ; } 

   
    
  
    

または：

もしaなら{もしbならs ; }そうでなければs2 ; 

   
    


  

C標準では、elseブロックは最も近いものと関連付けられていることが明確にされていますif。^[4]したがって、最初のツリーが選択されます。

上記の例は、曖昧さをなくすために次のように書き直すことができます。

ステートメント: open_statement
         | クローズドステートメント
         ;

open_statement: IF '(' 式 ')' ステートメント
              | IF '(' 式 ')' 閉じたステートメント ELSE 開いたステートメント
              ;

closed_statement: 非if文
                | IF '(' 式 ')' クローズドステートメント ELSE クローズドステートメント
                ;

非 if ステートメント: ...
                ;

その他のステートメント関連の文法規則も、直接的または間接的にstatementまたはselection-statement非終端記号で終わる可能性がある場合は、この方法で複製する必要がある場合もあります。

ただし、if 文と while 文の両方を含む文法を提供します。

ステートメント: open_statement
         | クローズドステートメント
         ;

open_statement: IF '(' 式 ')' ステートメント
              | IF '(' 式 ')' 閉じたステートメント ELSE 開いたステートメント
              | WHILE '(' 式 ')' オープンステートメント
              ;

クローズドステートメント: シンプルステートメント
                | IF '(' 式 ')' クローズドステートメント ELSE クローズドステートメント
                | WHILE '(' 式 ')' クローズドステートメント
                ;

単純なステートメント: ...
                ;

最後に、あいまいな IF 文を禁止する文法を示します。

ステートメント: open_statement
         | クローズドステートメント
         ;

open_statement: IF '(' 式 ')' ステートメント
              | IF '(' 式 ')' 閉じたステートメント ELSE 開いたステートメント
              | WHILE '(' 式 ')' オープンステートメント
              ;

クローズドステートメント: シンプルステートメント
                | IF '(' 式 ')' クローズドステートメント ELSE クローズドステートメント
                | WHILE '(' 式 ')' クローズドステートメント
                ;

単純なステートメント: ...
                ;

この文法では、他の解釈（ ）は次のように生成される ため、文はif (a) if (b) c else d一方向にしか解析できません。if (a) {if (b) c} else d

声明
オープンステートメント
IF '(' 式 ')' 閉じたステートメント ELSE 開いたステートメント
'if' '(' 'a' ')' 終了ステートメント 'else' 'd'

そして、closed_statement"if (b) c" に一致しようとして解析が失敗します。 を使用した試行もclosed_statement同様に失敗します。 他の解析、if (a) {if (b) c else d}) は成功します。

声明
オープンステートメント
IF '(' 式 ')' ステートメント
IF '(' 式 ')' クローズドステートメント
IF '(' a ')' (IF '(' 式 ')' 終了ステートメント ELSE 終了ステートメント)
'(' a ')' の場合 ('(' b ')' c の場合、'd' の場合)

• 字句解析ハック
• 最も厄介な解析