{{Short description|Problem in computer programming}} The '''dangling else''' is a problem in programming of parser generators in which an optional else clause in an if–then(–else) statement can make nested conditional statements ambiguous. Formally, the reference context-free grammar of the language is ambiguous, meaning there is more than one correct parse tree.
==Description== In many programming languages, one may write conditionally executed code in two forms: the if-then form, or the if-then-else form. (The else clause is optional.): '''if''' a '''then''' s '''if''' b '''then''' s1 '''else''' s2
Ambiguous interpretation becomes possible when there are nested statements; specifically when an if-then-else form replaces the statement <code>s</code> inside the above if-then construct:
'''if''' a '''then''' '''if''' b '''then''' s1 '''else''' s2 In this example, <code>s1</code> gets executed if and only if <code>a</code> is true ''and'' <code>b</code> is true. But what about <code>s2</code>? One person might be sure that <code>s2</code> gets executed whenever <code>a</code> is false (by attaching the ''else'' to the first ''if''), while another person might be sure that <code>s2</code> gets executed only when <code>a</code> is true ''and'' <code>b</code> is false (by attaching the ''else'' to the second ''if''). In other words, someone could interpret the previous statement as being equivalent to either of the following unambiguous statements: '''if''' a '''then''' { '''if''' b '''then''' s1 } '''else''' s2 '''if''' a '''then''' { '''if''' b '''then''' s1 '''else''' s2 }
The dangling-else problem dates back to ALGOL 60,<ref>{{cite journal |last1=Abrahams |first1=P. W. |title=A final solution to the Dangling else of ALGOL 60 and related languages |journal=Communications of the ACM |volume=9 |issue=9 |pages=679–682 |year=1966 |doi=10.1145/365813.365821 |doi-access=free |s2cid=6777841}}</ref> and subsequent languages have resolved it in various ways. In LR parsers, the dangling else is the archetypal example of a shift-reduce conflict.
==Examples== Concrete examples follow.
===C=== In C, the grammar reads, in part: <pre> statement = ... | selection-statement
selection-statement = ... | IF ( expression ) statement | IF ( expression ) statement ELSE statement</pre>
Thus, without further rules, the statement <syntaxhighlight lang="C"> if (a) if (b) s; else s2; </syntaxhighlight> could ambiguously be parsed as if it were either: <syntaxhighlight lang="C"> if (a) { if (b) s; else s2; } </syntaxhighlight> or: <syntaxhighlight lang="C"> if (a) { if (b) s; } else s2; </syntaxhighlight> The C standard clarifies that an <code>else</code> block is associated with the nearest <code>if</code>.<ref name="c-standard"/> Therefore, the first tree is chosen.
==Approaches to avoid the issue== ===Avoiding ambiguity while keeping the syntax===
This problem 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,<ref name="Bison Manual">{{cite book |title=Bison 3.8.1 |section=5.2 Shift/Reduce Conflicts |publisher=GNU |section-url=https://www.gnu.org/software/bison/manual/html_node/Shift_002fReduce.html#Shift_002fReduce |url=https://www.gnu.org/software/bison/manual/html_node/ |access-date=2021-08-07}}</ref> allowing for unambiguous context-free grammars, in particular. Programming languages like Pascal,<ref>ISO 7185:1990 (Pascal) 6.8.3.4: ''An if-statement without an else-part shall not be immediately followed by the token else.''</ref> C,<ref name="c-standard">[https://www.open-std.org/jtc1/sc22/wg14/www/standards 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 [https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf WG14 N1256], p. 134</ref> and Java<ref>{{cite web |title=The Java Language Specification, Java SE 9 Edition, 14.5. Statements |ref=jls-14.5 |url=https://docs.oracle.com/javase/specs/jls/se9/html/jls-14.html}}</ref> 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 <code>begin...end</code> in Pascal<ref>{{cite book |last1=Dale |first1=Nell B. |last2=Weems |first2=Chip |title=Introduction to Pascal and Structured Design | section=Dangling Else |pages=160–161 |date=November 1996 |publisher=Jones & Bartlett Learning |isbn=9780763703974 |url=https://books.google.com/books?id=5x2k4vWwn1wC&pg=PA160}}</ref> and <code>{...}</code> in C.
Depending on the compiler construction approach, one may take different corrective actions to avoid ambiguity:
*If the parser is produced by an 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.<ref name="Bison Manual"/> 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 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=== 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.<ref>[https://code.google.com/archive/p/copute/issues/21#c2 Ambiguity of dangling else: non-context-free grammars are semantically opaque]</ref>
Possible solutions are: * Having an "end if" symbol delimiting the end of the if construct. Examples of such languages are ALGOL 68, Ada, Eiffel, PL/SQL, Visual Basic, Modula-2, and AppleScript. * Disallowing the statement following a "then" to be an "if" itself (it may however be a pair of statement brackets containing only an if-then-clause). Some implementations of ALGOL 60 follow this approach.<ref>''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</ref> * Requiring braces (parentheses) when an "else" follows an "if".<ref>[https://code.google.com/archive/p/copute/issues/21#c1 Ambiguity of dangling else: require braces when else follows if]</ref> * Requiring every "if" to be paired with an "else". Haskell works this way as a result of its purely functional semantics. * Using different keywords for the one-alternative and two-alternative "if" statements. S-algol uses <code>if e do s</code> for the one-alternative case and <code>if e1 then e2 else e3</code> for the general case.<ref>{{citation |last=Davie |first=Antony J. T. |author2=Ronald Morrison |editor=Brian Meek |title=Recursive Descent Compiling |series=Ellis Horwood series in computers and their applications |year=1981 |publisher=Ellis Horwood |location=Chichester, West Sussex |isbn=0-470-27270-8 |page=20}}</ref> * Requiring braces unconditionally, like Swift and Rust. This is effectively true in Python as its indentation rules delimit every block, not just those in "if" statements.
===Avoiding the conflict in LR parsers=== The above example could be rewritten in the following way to remove the ambiguity : <pre> statement: open_statement | closed_statement ;
open_statement: IF '(' expression ')' statement | IF '(' expression ')' closed_statement ELSE open_statement ;
closed_statement: non_if_statement | IF '(' expression ')' closed_statement ELSE closed_statement ;
non_if_statement: ... ; </pre>
Any other statement-related grammar rules may also have to be duplicated in this way if they may directly or indirectly end with a <code>statement</code> or <code>selection-statement</code> non-terminal.
However, we give grammar that includes both of if and while statements.
<pre> statement: open_statement | closed_statement ;
open_statement: IF '(' expression ')' statement | IF '(' expression ')' closed_statement ELSE open_statement | WHILE '(' expression ')' open_statement ;
closed_statement: simple_statement | IF '(' expression ')' closed_statement ELSE closed_statement | WHILE '(' expression ')' closed_statement ;
simple_statement: ... ; </pre>
Finally, we give the grammar that forbids ambiguous IF statements.
<pre> statement: open_statement | closed_statement ;
open_statement: IF '(' expression ')' statement | IF '(' expression ')' closed_statement ELSE open_statement | WHILE '(' expression ')' open_statement ;
closed_statement: simple_statement | IF '(' expression ')' closed_statement ELSE closed_statement | WHILE '(' expression ')' closed_statement ;
simple_statement: ... ; </pre>
With this grammar the statement <code>if (a) if (b) c else d</code> can only be parsed one way, because the other interpretation (<code>if (a) {if (b) c} else d</code>) is produced as <pre> statement open_statement IF '(' expression ')' closed_statement ELSE open_statement 'if' '(' 'a' ')' closed_statement 'else' 'd' </pre> and then the parsing fails trying to match <code>closed_statement</code> to "if (b) c". An attempt with <code>closed_statement</code> fails in the same way. The other parse, <code>if (a) {if (b) c else d}</code>) succeeds: <pre> statement open_statement IF '(' expression ')' statement IF '(' expression ')' closed_statement IF '(' a ')' (IF '(' expression ')' closed_statement ELSE closed_statement) IF '(' a ')' (IF '(' b ')' c ELSE 'd') </pre>
==See also== *Lexer hack *Most vexing parse
==References== {{Reflist}}
Category:Ambiguity Category:Computer programming Category:Conditional constructs Category:Parsing