Dangling else

The dangling else is a problem in computer programming in which an optional else clause in an if–then(–else) statement results in nested conditionals being ambiguous. Formally, the reference context-free grammar of the language is ambiguous, meaning there is more than one correct parse tree.

In many programming languages one may write conditionally executed code in two forms: the if-then form, and the if-then-else form – the else clause is optional:

if a then s
if b then s1 else s2

This gives rise to an ambiguity in interpretation when there are nested statements, specifically whenever an if-then form appears as s1 in an if-then-else form:

if a then if b then s else s2

In this example, s is unambiguously executed when a is true and b is true, but one may interpret s2 as being executed when a is false (thus attaching the else to the first if) or when a is true and b is false (thus attaching the else to the second if). In other words, one may see the previous statement as either of the following expressions:

if a then (if b then s) else s2
      or
if a then (if b then s else s2)

The dangling else problem dates to ALGOL 60,^[1] and has been resolved in various ways in subsequent languages. In LR parsers, the dangling else is the archetypal example of a shift-reduce conflict.

Avoiding ambiguity while keeping the syntax

This is a problem that often comes up in compiler construction, especially scannerless parsing. The convention when dealing with the dangling else is to attach the else to the nearby if statement,^[2] allowing for unambiguous context-free grammars, in particular. Programming languages like Pascal^[3] and C^[4] 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^[5] and {...} in C.

Depending on the compiler construction approach, one may take different corrective actions to avoid ambiguity:

• If the parser is produced by an SLR, LR(1) or LALR LR parser generator, the programmer will often rely on the generated parser feature of preferring shift over reduce whenever there is a conflict.^[2] Alternatively, the grammar can be rewritten to remove the conflict, at the expense of an increase in grammar size (see below).
• If the parser is produced by a Pruning and Deep Pruning LR generator, one can issue directives that prune away the ambiguities completely.^[6]
• 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 parsing expression grammar.

Avoiding ambiguity by changing the syntax

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.^[7]

Possible solutions are:

• Having an "end if" statement. Examples of such languages are ALGOL 68, Ada, Eiffel, PL/SQL, Visual Basic, and Modula-2.
• 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). This approach is followed by ALGOL 60.^[8]
• Requiring braces (parenthesizing) when an "else" follows an "if".^[9] This is effectively true in Python as its indentation rules delimit every block, not just those in "if" statements.
• Requiring every "if" to be paired with an "else".
• Using different keywords for the one-alternative and two-alternative "if" statements. S-algol uses if e do s for the one-alternative case and if e1 then e2 else e3 for the general case.^[10]

Examples

Concrete examples follow.

C

In C, 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;

In practice in C the first tree is chosen, by associating the else with the nearest if.

Avoiding the conflict in LR parsers

The above example could be rewritten in the following way to remove the ambiguity:

 statement = ...
    | selection-statement

 statement-with-else = ...
    | selection-statement-with-else

 selection-statement = ...
    | IF ( expression ) statement
    | IF ( expression ) statement-with-else ELSE statement

 selection-statement-with-else = ...
    | IF ( expression ) statement-with-else ELSE statement-with-else

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.

See also

• The lexer hack

References

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. doi:10.1145/365813.365821.
2. 5.2 Shift/Reduce Conflicts from GNU Operating System web site
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.
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
5. Pascal, Nell Dale and Chip Weems, "Dangling Else", p. 160–161
6. http://www.mightyheave.com/blog/?p=17#more-17
7. Ambiguity of dangling else: non-context-free grammars are semantically opaque
8. 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
9. Ambiguity of dangling else: require braces when else follows if
10. 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