Dangling else

<h2 id="avoiding-ambiguity-while-keeping-the-syntax">Avoiding ambiguity while keeping the syntax</h2>
This problem often comes up in <a href="/facts/Compiler_design/WNfCDFJe">compiler construction</a>, especially <a href="/facts/Scannerless_parsing/xH5lmd0Y">scannerless parsing</a>. The convention when dealing with the dangling else is to attach the else to the nearby if statement,<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> allowing for unambiguous context-free grammars, in particular. Programming languages like Pascal,<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> C,<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a> and Java<a class="footnote-ref" id="fnref:5" href="#fn:5">5</a> follow this convention, so there is no ambiguity in the semantics of the language, though the use of a parser generator may lead to ambiguous grammars. In these cases alternative grouping is accomplished by explicit blocks, such as begin...end in Pascal<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a> and {...} in C.
Depending on the compiler construction approach, one may take different corrective actions to avoid ambiguity:

<ul><li>If the parser is produced by an SLR, LR(1), or LALR <a href="/facts/LR_parser/bpMod8K0">LR parser</a> generator, the programmer will often rely on the generated parser feature of preferring shift over reduce whenever there is a conflict.<a class="footnote-ref" id="fnref:7" href="#fn:7">7</a> Alternatively, the grammar can be rewritten to remove the conflict, at the expense of an increase in grammar size (see below).</li>
<li>If the parser is hand-written, the programmer may use a non-ambiguous context-free grammar. Alternatively, one may rely on a non-context-free grammar or a <a href="/facts/Parsing_expression_grammar/8XdfJ7D0">parsing expression grammar</a>.</li></ul>
<h2 id="avoiding-ambiguity-by-changing-the-syntax">Avoiding ambiguity by changing the syntax</h2>
The problem can also be solved by making explicit the link between an else and its if, within the syntax. This usually helps avoid human errors.<a class="footnote-ref" id="fnref:8" href="#fn:8">8</a>
Possible solutions are:

<ul><li>Having an "end if" symbol delimiting the end of the if construct. Examples of such languages are <a href="/facts/ALGOL_68/NTnc9fy7">ALGOL 68</a>, <a href="/facts/Ada_(programming_language)/Y2yHel4l">Ada</a>, <a href="/facts/Eiffel_(programming_language)/gEzPjzmn">Eiffel</a>, <a href="/facts/PL%2fSQL/LLghPhdc">PL/SQL</a>, <a href="/facts/Visual_Basic/7QMXM6fP">Visual Basic</a>, <a href="/facts/Modula-2/DFyUTdAq">Modula-2</a>, and <a href="/facts/AppleScript/cc3rc4wD">AppleScript</a>.</li>
<li>Disallowing the statement following a "then" to be an "if" itself (it may however be a pair of statement brackets containing only an if-then-clause). Some implementations of <a href="/facts/ALGOL_60/QnpxUYQm">ALGOL 60</a> follow this approach.<a class="footnote-ref" id="fnref:9" href="#fn:9">9</a></li>
<li>Requiring braces (parentheses) when an "else" follows an "if".<a class="footnote-ref" id="fnref:10" href="#fn:10">10</a></li>
<li>Requiring every "if" to be paired with an "else". To avoid a similar problem concerning semantics rather than syntax, <a href="/facts/Racket_(programming_language)/5n7LW08b">Racket</a> deviates from <a href="/facts/Scheme_(programming_language)/0aGdf3SC">Scheme</a> by considering an if without a fallback clause to be an error, effectively distinguishing conditional expressions (i.e if) from conditional statements (i.e when and unless, which do not have fallback clauses).</li>
<li>Using different keywords for the one-alternative and two-alternative "if" statements. <a href="/facts/S-algol/S6LGGXA7">S-algol</a> uses if e do s for the one-alternative case and if e1 then e2 else e3 for the general case.<a class="footnote-ref" id="fnref:11" href="#fn:11">11</a></li>
<li>Requiring braces unconditionally, like <a href="/facts/Swift_(programming_language)/A7qHQC32">Swift</a> and <a href="/facts/Rust_(programming_language)/8JNMV19F">Rust</a>. This is effectively true in <a href="/facts/Python_(programming_language)/YbuGqofa">Python</a> as its indentation rules delimit every block, not just those in "if" statements.</li></ul>
<h2 id="examples">Examples</h2>
Concrete examples follow.

<h3>C</h3>
In <a href="/facts/C_(programming_language)/Ky2No763">C</a>, the grammar reads, in part:

 statement = ...
 | selection-statement

selection-statement = ...
 | IF ( expression ) statement
 | IF ( expression ) statement ELSE statement
Thus, without further rules, the statement

if (a) if (b) s; else s2;

could ambiguously be parsed as if it were either:

if (a)
{
 if (b)
 s;
 else
 s2;
}

or:

if (a)
{
 if (b)
 s;
}
else
 s2;

The C standard clarifies that an else block is associated with the nearest if.<a class="footnote-ref" id="fnref:12" href="#fn:12">12</a> Therefore, the first tree is chosen.

<h2 id="avoiding-the-conflict-in-lr-parsers">Avoiding the conflict in LR parsers</h2>
The above example could be rewritten in the following way to remove the ambiguity :

statement: open_statement
 | closed_statement
  ;

open_statement: IF '(' expression ')' statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              ;

closed_statement: non_if_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                ;

non_if_statement: ...
                ;

Any other statement-related grammar rules may also have to be duplicated in this way if they may directly or indirectly end with a statement or selection-statement non-terminal.
However, we give grammar that includes both of if and while statements.

statement: open_statement
 | closed_statement
  ;

open_statement: IF '(' expression ')' statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              | WHILE '(' expression ')' open_statement
              ;

closed_statement: simple_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                | WHILE '(' expression ')' closed_statement
                ;

simple_statement: ...
                ;

Finally, we give the grammar that forbids ambiguous IF statements.

statement: open_statement
 | closed_statement
  ;

open_statement: IF '(' expression ')' statement
              | IF '(' expression ')' closed_statement ELSE open_statement
              | WHILE '(' expression ')' open_statement
              ;

closed_statement: simple_statement
                | IF '(' expression ')' closed_statement ELSE closed_statement
                | WHILE '(' expression ')' closed_statement
                ;

simple_statement: ...
                ;

With this grammar the statement if (a) if (b) c else d can only be parsed one way, because the other interpretation (if (a) {if (b) c} else d) is produced as

statement
open_statement
IF '(' expression ')' closed_statement ELSE open_statement
'if' '(' 'a' ')' closed_statement 'else' 'd'

and then the parsing fails trying to match closed_statement to "if (b) c". An attempt with closed_statement fails in the same way. The other parse, if (a) {if (b) c else d}) succeeds:

statement
open_statement
IF '(' expression ')' statement
IF '(' expression ')' closed_statement
IF '(' a ')' (IF '(' expression ')' closed_statement ELSE closed_statement)
IF '(' a ')' (IF '(' b ')' c ELSE 'd')

<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/Lexer_hack/BlqdnN15">Lexer hack</a></li>
<li><a href="/facts/Most_vexing_parse/dx9ELRxG">Most vexing parse</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Abrahams, P. W. (1966). "A final solution to the Dangling else of ALGOL 60 and related languages". Communications of the ACM. 9 (9): 679–682. doi:10.1145/365813.365821. S2CID 6777841. <a href="https://doi.org/10.1145%2F365813.365821" target="_blank">https://doi.org/10.1145%2F365813.365821</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">"5.2 Shift/Reduce Conflicts". Bison 3.8.1. GNU. Retrieved 2021-08-07. <a href="https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html#Shift_002fReduce" target="_blank">https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html#Shift_002fReduce</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">ISO 7185:1990 (Pascal) 6.8.3.4: An if-statement without an else-part shall not be immediately followed by the token else. <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">ISO 9899:1999 (C): 6.8.4.1(3): "An else is associated with the lexically nearest preceding if that is allowed by the syntax.", available at WG14 N1256, p. 134 <a href="https://www.open-std.org/jtc1/sc22/wg14/www/standards" target="_blank">https://www.open-std.org/jtc1/sc22/wg14/www/standards</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">"The Java Language Specification, Java SE 9 Edition, 14.5. Statements". <a href="https://docs.oracle.com/javase/specs/jls/se9/html/jls-14.html" target="_blank">https://docs.oracle.com/javase/specs/jls/se9/html/jls-14.html</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">Dale, Nell B.; Weems, Chip (November 1996). "Dangling Else". Introduction to Pascal and Structured Design. Jones & Bartlett Learning. pp. 160–161. ISBN 9780763703974. <a href="9780763703974" target="_blank">9780763703974</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
<li id="fn:7">"5.2 Shift/Reduce Conflicts". Bison 3.8.1. GNU. Retrieved 2021-08-07. <a href="https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html#Shift_002fReduce" target="_blank">https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html#Shift_002fReduce</a> <a href="#fnref:7" class="footnote-back-ref">↩</a></li>
<li id="fn:8">Ambiguity of dangling else: non-context-free grammars are semantically opaque <a href="https://code.google.com/archive/p/copute/issues/21#c2" target="_blank">https://code.google.com/archive/p/copute/issues/21#c2</a> <a href="#fnref:8" class="footnote-back-ref">↩</a></li>
<li id="fn:9">4.5.1 Conditional Statements — Syntax in P. Nauer (ed.), Revised Report on the Algorithmic Language ALGOL 60, CACM 6,1, 1963 pp. 1-17 <a href="#fnref:9" class="footnote-back-ref">↩</a></li>
<li id="fn:10">Ambiguity of dangling else: require braces when else follows if <a href="https://code.google.com/archive/p/copute/issues/21#c1" target="_blank">https://code.google.com/archive/p/copute/issues/21#c1</a> <a href="#fnref:10" class="footnote-back-ref">↩</a></li>
<li id="fn:11">Davie, Antony J. T.; Ronald Morrison (1981), Brian Meek (ed.), Recursive Descent Compiling, Ellis Horwood series in computers and their applications, Chichester, West Sussex: Ellis Horwood, p. 20, ISBN 0-470-27270-8 <a href="0-470-27270-8" target="_blank">0-470-27270-8</a> <a href="#fnref:11" class="footnote-back-ref">↩</a></li>
<li id="fn:12">ISO 9899:1999 (C): 6.8.4.1(3): "An else is associated with the lexically nearest preceding if that is allowed by the syntax.", available at WG14 N1256, p. 134 <a href="https://www.open-std.org/jtc1/sc22/wg14/www/standards" target="_blank">https://www.open-std.org/jtc1/sc22/wg14/www/standards</a> <a href="#fnref:12" class="footnote-back-ref">↩</a></li>
</ol>

Dangling else open-in-new

Dangling else