intermediateGrammar

Here is a grammar for arithmetic expressions with `+` and `*` and no precedence. What is wrong with it, and how do you fix it?

Whether the candidate can recognise ambiguity as a property of the grammar rather than a bug in the parser, and whether they know the two distinct ways to remove it and what each costs.

What a strong answer covers

  • The grammar is ambiguous: E -> E + E | E * E | num admits two distinct parse trees for 1 + 2 * 3, and nothing in the grammar chooses between them. An ambiguous grammar does not mean the input is ambiguous — it means the specification has not said what the input means.
  • There are two standard fixes and they are not equivalent. The structural fix stratifies the grammar into levels — expression, term, factor — so that only one derivation exists: E -> E + T | T, T -> T * F | F, F -> num | ( E ). Left recursion in each rule gives left associativity; right recursion would give right associativity. The grammar now encodes precedence, and any parser for it produces the right tree.
  • The other fix is to keep the ambiguous grammar and resolve it outside it: precedence and associativity declarations in a parser generator, or a Pratt parser that carries a binding power per operator. The grammar is shorter and adding an operator is a one-line change, but the meaning of the language is no longer in the grammar — it is in a table beside it, and a reader of the grammar alone cannot tell you what a + b * c means.
  • The dangling else is the same problem with different stakes, because there the two readings are both plausible programs and neither errors. Most languages resolve it by fiat — bind to the nearest if — and a few remove it by requiring braces or a terminator.
✓ Green flags
  • Produces the two parse trees rather than describing the ambiguity abstractly.
  • Knows the stratification pattern by shape, and knows which recursion direction gives which associativity.
  • Names the alternative — precedence declarations or Pratt binding powers — and states the trade honestly.
  • Brings up the dangling else unprompted, and knows it is resolved by a rule outside the grammar in most languages.
  • Notes that ambiguity is undecidable in general for context-free grammars, so a generator can only report the conflicts it finds.
✗ Red flags
  • "Just add parentheses to the input." That changes the program, not the grammar; the grammar is still ambiguous for every input without them.
  • "The parser will pick the right one automatically." A recursive-descent parser picks one by the order of its recursive calls; that is a decision hidden in code, and it is the thing you were supposed to specify.
  • "Ambiguity means the grammar is not context-free." Unrelated: plenty of ambiguous grammars are context-free, and some context-free languages have no unambiguous grammar at all.
  • "A shift/reduce conflict is a parser generator bug." It is the generator reporting your ambiguity; the default resolution is what hides it.

Follow-up

Now add unary minus and exponentiation, where exponentiation is right-associative and binds tighter than unary minus in some languages and looser in others. Show the grammar.

Implementation challenge

What to ask them to write or trace on a whiteboard.

Write the stratified grammar for + - * / ( ) num with the usual precedence, then write the Pratt binding-power table that produces the same trees. Say which you would ship and why.

The lessons behind it

Ambiguous Grammars →Operator Precedence →Associativity →Context-Free Grammars →Formal Grammars →Left Recursion →
← All questions