How do you rewrite a flat expression grammar so that operator precedence and associativity follow from the rule shape?

## Precedence is a shape, not a setting The flat rule `E -> E '+' E | E '*' E | number` is ambiguous twice over: `1 + 2 * 3` has one tree with the multiplication on top and another with the addition on top, and `1 - 2 - 3` has one tree grouping left and another grouping right. Neither problem is solved by telling a parser what to prefer — that only hides it behind an implementation. The repair is to write a different grammar for the same language, one whose *structure* permits only the tree you want. ## The layered rule set The standard construction gives each precedence level its own nonterminal, ordered from loosest at the top to tightest at the bottom: ``` expr -> expr '+' term | expr '-' term | term term -> term '*' factor | term '/' factor | factor factor -> base '^' factor | base base -> number | '(' expr ')' ``` Two mechanisms are at work, and they are worth separating because interviews probe them separately. **Precedence comes from the descent.** An `expr` may contain a `+` directly, but to reach a `*` it must first go through `term`. So in `1 + 2 * 3`, the multiplication can only appear as one of the addition's operands, never the other way round: the tree is `1 + (2 * 3)` and there is no second one. Operators of the *same* precedence share a layer — `+` and `-` are alternatives of `expr`, not layers of their own. **Associativity comes from the recursive side.** At each layer, exactly one side of the operator recurses back to the same nonterminal and the other side drops to the layer below: | Rule shape | Grouping of `a op b op c` | Note | |---|---|---| | `A -> A op B`, else `B` | `(a op b) op c` | left-associative; the standard shape for `+ - * /` | | `A -> B op A`, else `B` | `a op (b op c)` | right-associative; used for exponent-style and assignment-style operators | | `A -> B op B`, else `B` | not derivable | non-associative; chaining is a syntax error | | `A -> A op A`, else `B` | both | ambiguous — this is the shape you are removing | So `term -> term '*' factor` forces `2 * 3 * 4` to group as `(2 * 3) * 4`, while `factor -> base '^' factor` forces `2 ^ 3 ^ 2` to group as `2 ^ (3 ^ 2)`. ## Where brackets fit The bottom layer contains `'(' expr ')'`, which jumps straight back to the top. That is deliberate: - It gives a user the only escape from the layering, so `(1 + 2) * 3` becomes writable. - It does not re-open the ambiguity, because the recursion is fenced by two literal terminals — every bracketed group has a determined extent, so no string gains a second tree. - It keeps the atom rule tiny, which is where you later add other primaries such as names or calls. ## Costs and limits The construction is not free, and a good answer names the price: - **One layer per precedence level.** A language with a dozen levels needs a dozen nonterminals, and deriving a bare number walks all twelve. The cost is paid in rule count and in descent depth, not in correctness. - **Editing the ladder is not local.** Inserting a new precedence level between two existing ones means re-pointing the layer above it and the layer below it, so the grammar has to be read as a whole. - **It removes ambiguity only where it is applied.** Layering the arithmetic operators does nothing for an unrelated ambiguity elsewhere in the grammar, such as an optional trailing clause that could attach to two different constructs. - **Unary operators need care.** A prefix operator usually gets its own layer just above the atoms so that it binds tighter than the binary operators but still allows a bracketed operand underneath. ## Why this is the answer interviewers want The question is really "do you understand that a grammar encodes meaning, not just syntax?". A candidate who says "set the precedence in the parser" has located the meaning in an implementation, where a second implementation cannot see it. A candidate who writes three rules and points at which side recurses has put the meaning where every reader of the grammar — including a future reimplementation — is forced to find it. That is also why the layered grammar is the right fix when rules written in the language are already stored: it changes the number of trees per string without changing which strings are legal, so nothing that was written before becomes unparseable.