In a rule language with optional else branches, why does "if A then if B then X else Y" parse two ways?

## The string and its two readings Start from the productions a straightforward conditional gives you: ``` stmt -> 'if' cond 'then' stmt | 'if' cond 'then' stmt 'else' stmt | simple ``` Now derive `if A then if B then X else Y`. The inner conditional is a `stmt`, and there is one `else` for two `if`s, so two trees exist: 1. **Inner attachment.** The outer statement uses the else-less production; its body is the whole `if B then X else Y`. 2. **Outer attachment.** The outer statement uses the else production; its then-branch is the else-less `if B then X`, and `Y` is the outer else-branch. Both use only the productions above, so both are legal. This is the **dangling-else** ambiguity, and it is the example every interviewer reaches for because it is ambiguity with an observable, unarguable behavioural difference. ## What each reading does at runtime | Attachment | Tree | When `X` runs | When `Y` runs | |---|---|---|---| | Inner `if` | `if A then (if B then X else Y)` | `A` and `B` | `A` and not `B` | | Outer `if` | `if A then (if B then X) else Y` | `A` and `B` | not `A` | The two readings agree on `X` and disagree completely on `Y`. There is no input on which the difference is cosmetic, and nothing else in the program text distinguishes them — which is why the same source can behave differently under two conforming parsers. ## How implementations settle it: the convention Almost universally the rule is: **an `else` binds to the nearest preceding `if` that does not already have one.** Two things are worth saying about this convention: - It is a **tie-break applied outside the grammar**, not something the grammar states. The grammar still generates the string two ways; the implementation simply declines to build one of the trees. - Generated bottom-up parsers arrive at it by default because, on seeing `else`, they prefer to keep extending the statement in progress rather than finish it — which is exactly the inner attachment. The preference is a default resolution, not a proof that the grammar is fine. A convention is enough to make one implementation deterministic. It is not enough to make two implementations agree, because the next reader of the grammar — a formatter, a validator, a second evaluator — sees only the ambiguous rules. ## The grammar-level fix The repair that keeps the language exactly as it is splits statements by whether every `if` inside them is already matched with an `else`: ``` stmt -> matched | unmatched matched -> 'if' cond 'then' matched 'else' matched | simple unmatched -> 'if' cond 'then' stmt | 'if' cond 'then' matched 'else' unmatched ``` Trace the witness through it. For the outer attachment you would need a production whose then-branch is the *unmatched* `if B then X` and which also carries an `else` — and no such production exists: both else-carrying rules demand a `matched` statement before the `else`. Only the inner attachment derives, so the string has exactly one tree, and that tree is the one the convention would have chosen. The set of accepted programs is unchanged; only the number of trees per program falls to one. ## The surface-syntax fix The other repair changes what users write: end every conditional with a closing keyword, or bracket the branches, so a branch's extent is delimited by terminals rather than inferred. Compared with the matched/unmatched split: - It makes the ambiguity **impossible to express** rather than merely underivable, and it survives later grammar edits that add new statement forms. - It improves diagnostics, because a missing delimiter is reported near where it belongs instead of silently re-attaching a branch. - It costs users keystrokes and, crucially, **changes the accepted language** — so it is a choice for a new syntax, not a repair you can retrofit to text already written and stored. ## Interview register The strong answer does three things in order: states the two derivations, states the behavioural difference for `Y`, then separates the convention (an implementation tie-break) from the fix (a grammar or syntax change). The weak answer stops at "the else goes with the nearest if" — which is true, and which is a description of what implementations do rather than an explanation of why there was a choice at all.