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)
Contents |
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.
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 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.[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]
See also [edit]
References [edit]
- ^ 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 grammars 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
