Grammars, Derivations and Ambiguity
Build the same parse tree top-down, and see why one string having many derivations is harmless but two trees is not.
Skip to the animationA derivation repeatedly replaces a non-terminal with the right-hand side of a production until only terminals remain; the parse tree records which productions were used, and a grammar is ambiguous when one string has two different trees.
Grammars, formally
- Terminal
- A symbol that appears in the final string — the tokens. They are never expanded.
- Non-terminal
- A placeholder standing for a set of strings. Each has one or more productions saying what it may become.
- Production
- A rule
A → α: whereverAappears it may be replaced byα. Context-free means the left side is always a single non-terminal — the replacement never depends on the surroundings. - Start symbol
- Where every derivation begins. The language is exactly the set of terminal strings derivable from it.
- Sentential form
- Any intermediate string of terminals and non-terminals along the way.
Leftmost, rightmost, and why it does not matter
A leftmost derivation always expands the leftmost non-terminal; a rightmost one always expands the rightmost. Both are conventions for bookkeeping, and both produce the same tree — they differ only in the order the tree's nodes are discovered.
This is why one string always has many derivations, and why that is completely harmless. What matters is whether it has more than one tree.
Top-down parsers such as LL trace a leftmost derivation forwards. Bottom-up parsers such as LR trace a rightmost derivation backwards — which is exactly what the shift-reduce topic is doing to this same string.
Ambiguity
A grammar is ambiguous if some string has two distinct parse trees. That is a genuine problem, because the tree is the meaning — two trees mean two answers.
| Grammar | On id + id * id | Verdict |
|---|---|---|
| E → E + T | T, T → T * F | F, F → id | one tree; * forced below + | unambiguous |
| E → E + E | E * E | id | two trees, meaning 5 and 7 for 1+2*3 | ambiguous |
The layered grammar removes the ambiguity structurally: * can only appear inside a T, and T sits below + in every tree, so precedence has nowhere else to go. Left recursion in E → E + T similarly forces left associativity.
Some languages are inherently ambiguous — no unambiguous grammar exists for them at all. And there is no algorithm that decides whether a given grammar is ambiguous; that question is undecidable. In practice parser generators report the conflicts and the grammar gets rewritten.
Advantages and disadvantages
Advantages
- Grammars describe nested structure that no regular expression can express.
- The parse tree is the meaning, in a form later compiler phases can walk directly.
- Layering the non-terminals encodes precedence and associativity with no extra machinery.
Disadvantages
- Ambiguity is easy to introduce and undecidable to detect in general.
- The unambiguous version of a grammar is longer and less readable than the ambiguous one.
- Left recursion is natural here but breaks top-down parsers, so it must be removed for LL.
Watch it work
Check yourself
question 1 / 4
One question at a time. Pick an answer to see why it is right or wrong, then move on — there is no score to keep and nothing is saved.