Dangling else

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 a 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
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[edit]

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 a 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[edit]

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:

  • Disallowing the statement following a "then" to be an "if" itself (it may however be a pair of statement brackets containing nothing but an if-then-clause). This approach is followed by ALGOL 60[8] and Python.[9]
  • Requiring braces (parenthesizing) when an "else" follows an "if".[10]
  • Requiring every "if" to be paired with an "else".


Concrete examples follow.


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)

or as:

 if (a) {
   if (b)

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

Avoiding the conflict in LR parsers[edit]

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[edit]


  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.  edit
  2. ^ a b 5.2 Shift/Reduce Conflicts from GNU Operating System web site
  3. ^ ISO 7185:1990 (Pascal) An if-statement without an else-part shall not be immediately followed by the token else.
  4. ^ ISO 9899:1999 (C): "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. ^ The Python Language Reference, 9. Full Grammar specification
  10. ^ Ambiguity of dangling else: require braces when else follows if