Dangling else

The dangling else is a well-known problem in computer programming in which a seemingly well-defined grammar can become ambiguous. In many programming languages you can write conditionally executed code in two forms:

if form:

if a then s

if-else form:

if a then s1 else s2

This gives rise to an infinite number of grammar ambiguities whenever a statement ending in the if form appears at the s1 point in the if-else form.^[1] Substituting any of this series of statements for s1 result in an ambiguity.

if a then s
if a then s else if b then s2
if a then s else if b then s2 else if c then s3
... 

For example, substituting the first in the series for s1 in the if-else form yields code like this:

if a then if b then s1 else s2

which can be understood in two ways. Either as

if a then
{
  if b then
  {
    s1
  }
  else
  {
    s2
  }
}

or as

if a then
{
  if b then
  {
    s1
  }
}
else
{
  s2
}

This is a problem that often comes up in compiler construction. The convention when dealing with the dangling else is to attach the else to the nearby if statement.^[2] Programming languages like Pascal^[3] and C^[4] demand following this convention, so there is no ambiguity in the semantics of the language even though there is one in its grammar. Some corrective actions make the grammar unambiguous by making it non-Context Free. Depending on the compiler construction approach, one may take different corrective actions:

• If the compiler is the product of a programmer, instead of a parser generator, the compiler can be manually written to simply associate the else statement with the nearby if statement (or alternately just consider the if statement complete and associate the else with the leading if statement).
• 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.^[2]
• If the compiler is the product of a Pruning and Deep Pruning LR generator, one can issue directives than prune away the ambiguities completely.^[1]
• It can be solved by telling the parser the right way to solve the ambiguity^{[citation needed]}.
• It can be solved at the grammar level by using a modified parsing expression grammar or equivalent^{[citation needed]}.

Programmers using C and languages with similar syntax sometimes standardize a practice of using braces to clearly define the intent of the statement.^{[citation needed]}

Without resorting to such conventions, certain dangling-else constructs in C can be disambiguated by using logical and ternary operators, since in C semantics, statements are expressions and because logical operators short-circuit. For instance, given non-void statements s1 and s2,

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

can be rewritten as either

a && b ? s1 : s2;

or

a ? b && s1 : s2;

depending on the intended meaning.

Context Free Solutions

The problem can also be solved by removing the possibility for ambiguity in a Context Free Grammar, which is the only way to eliminate the potential for coincident human-error assumptions,^[5] e.g.

• by designing the language to have an "end if". Examples of such languages are ALGOL 68, Ada, Eiffel, PL/SQL, REALbasic, and Modula-2.
• by designing a grammar, that does not allow the statement following then to be an if-statement itself (it may however be a pair of statement brackets containing nothing but an if-statement). This approach has for example been taken in ALGOL 60^[6] and Python^[7]
• by designing a grammar, that does not allow any statement following then if there is a following else. This approach has for example been taken in Copute^[8]

References

1. ^ ^{a b} http://www.mightyheave.com/blog/?p=17#more-17
2. ^ ^{a b} 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.
5. ^ Ambiguity of dangling else: non-Context Free Grammers are semantically opaque
6. ^ 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
7. ^ The Python Language Reference, 9. Full Grammar specification
8. ^ Ambiguity of dangling else: require braces when else follows if