Dangling else
The dangling else is a problem in computer programming in which a seemingly well-defined statement can become ambiguous. In many programming languages one may write conditionally executed code in two forms: the if-then form, and the if-then-else form:
if a then s if a then s1 else s2
This gives rise to an ambiguity in interpretation 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)
[edit] Avoiding ambiguity while keeping the syntax
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] 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.
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.[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]
- 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.
Programmers[who?] using C and languages with similar syntax sometimes standardize a practice of using braces to clearly define the intent of the statement. Similarly, some[who?] programmers use logical and ternary operators to avoid ambiguity.
[edit] 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.[5] Possible solutions are:
- Having an "end if" statement. Examples of such languages are ALGOL 68, Ada, Eiffel, PL/SQL, REALbasic, and Modula-2.
- 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-close). This approach is followed by ALGOL 60[6] and Python.[7]
- Requiring braces (parenthesizing) when an "else" follows an "if".[8]
- Requiring every "if" to be paired with an "else". This is necessary in a language which does not allow mutable variables.[9]
[edit] References
- ^ a b http://www.mightyheave.com/blog/?p=17#more-17
- ^ a b 5.2 Shift/Reduce Conflicts from GNU Operating System web site
- ^ ISO 7185:1990 (Pascal) 6.8.3.4: An if-statement without an else-part shall not be immediately followed by the token else.
- ^ 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.
- ^ Ambiguity of dangling else: non-context-free grammers are semantically opaque
- ^ 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
- ^ The Python Language Reference, 9. Full Grammar specification
- ^ Ambiguity of dangling else: require braces when else follows if
- ^ Ambiguity of dangling else: immutability requires every if to be paired with else
