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:[1]

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,[2] 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,[3] allowing for unambiguous context-free grammars, in particular. Programming languages like Pascal[4] and C[5] 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[6] and {...} in C.

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

  • If the compiler is the product of 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.[3]
  • If the compiler is the product of a Pruning and Deep Pruning LR generator, one can issue directives that prune away the ambiguities completely.[1]
  • If the compiler is the product of a programmer instead of a parser generator, 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". This is necessary in a language which does not allow mutable variables.[11]

Examples[edit]

Concrete examples follow.

C[edit]

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 as:

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

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

See also[edit]

References[edit]

  1. ^ a b http://www.mightyheave.com/blog/?p=17#more-17
  2. ^ 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
  3. ^ a b 5.2 Shift/Reduce Conflicts from GNU Operating System web site
  4. ^ ISO 7185:1990 (Pascal) 6.8.3.4: An if-statement without an else-part shall not be immediately followed by the token else.
  5. ^ 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
  6. ^ Pascal, Nell Dale and Chip Weems, "Dangling Else", p. 160–161
  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
  11. ^ Ambiguity of dangling else: immutability requires every if to be paired with else