Ambiguity & Precedence

## What ambiguity means precisely A **context-free grammar** is a set of productions that rewrite a nonterminal into a sequence of terminals and nonterminals. A **parse tree** records one way of applying those productions to produce a given string: the root is the start symbol, each internal node is a nonterminal, and each node's children are the right-hand side of the production used there. A grammar is **ambiguous** when *at least one* string in its language has **two distinct parse trees**. The quantifier matters in both directions: - It is **existential**, so a single witness string settles it. You demonstrate ambiguity by exhibiting one string and two trees, never by surveying the grammar's shape. - It says nothing about the *other* strings. Almost every string a grammar generates may have exactly one tree while a rare shape has two, and the grammar is still ambiguous. An equivalent formulation: two distinct **leftmost** derivations. That qualifier is load-bearing — see the next section. ## The witness: one rule, two trees Take the flat expression grammar `E -> E - E | number` and the string `9 - 5 - 2`. - **Left grouping.** The top `-` is the second minus; its left child derives `9 - 5`, its right child is `2`. The tree denotes `(9 - 5) - 2` = **2**. - **Right grouping.** The top `-` is the first minus; its left child is `9`, its right child derives `5 - 2`. The tree denotes `9 - (5 - 2)` = **6**. Both trees are built entirely from the two productions given, so both are legal. The grammar generates the string twice over, and it offers no rule that would prefer one shape. ## Derivations, orders and trees Candidates often reach for the wrong witness here, so keep the three notions apart: | Observation | Proves ambiguity? | Why | |---|---|---| | One tree has both a leftmost and a rightmost derivation | No | True of every grammar; it is the same tree walked in two orders | | Two derivations differ only in which nonterminal was expanded first | No | Different expansion order, same resulting tree | | Two distinct **leftmost** derivations exist for one string | **Yes** | Leftmost derivations are in one-to-one correspondence with parse trees | | Two distinct parse trees exist for one string | **Yes** | This is the definition | ## Why it bites a running system The grammar is where the meaning of stored text is specified, so an ambiguous one leaves the meaning under-specified everywhere that text is read: - Two independently written evaluators — one in a request path, one in a batch job — can each be faithful to the grammar and still compute different results for one saved rule. - Swapping the parser, or regenerating it with a different tool, can silently change what existing data means without any change to the data or to the rules as written. - The tree drives more than evaluation: error messages, highlighting, optimisation and code generation all read it, so the divergence surfaces in places nobody connected to a grammar question. - A rule that has behaved correctly for a year can flip the first time it is re-parsed, because nothing ever forced a choice. Note the honest limit: two different trees do **not** always give two different results. If the operator is associative and exact, both groupings evaluate the same and the ambiguity stays invisible until an operator that is not associative — subtraction, division, comparison chains — appears in a rule. ## A grammar property, not a language property Ambiguity is attached to the *rules*, not to the set of strings they generate. The same language usually has other grammars, and the standard repair is to write one of them: 1. **Stratify** the rules into one layer per precedence level, so a tighter operator can only be reached by descending; that removes the mixed-operator ambiguity. 2. **Recurse on one side** at each layer — left recursion forces left grouping, right recursion forces right grouping — which removes the same-operator chain ambiguity that `9 - 5 - 2` exhibits. 3. **Change the surface syntax** so grouping is explicit, for example by requiring brackets around nested operations; this changes what users may write but makes the ambiguity impossible rather than merely unreachable. The first two keep the language exactly as it was and only reduce the number of trees per string, which is what you want when rules are already stored. ## What an interviewer is listening for The definition alone is the floor. What separates answers is whether you reach for a witness immediately — one string, two trees, two values — and whether you locate the defect in the grammar rather than blaming a parser for "getting it wrong". A parser that produced either tree did nothing wrong; the grammar never told it which one to build.