Week 04 · Sipser 2.1 · Part II
A machine reads a string and answers. A grammar does the opposite: it produces strings, and the record of how it produced one is a parse tree. Ambiguity is a property of the grammar, never of the language — and you can see the two trees below.
The four steps in order. Doing them out of order is the classic way to get a grammar that is nearly in CNF and not quite.
One variable per line: S -> a S b | eps. A symbol is a
variable exactly when it appears on some left-hand side. Use spaces in a right-hand
side if your symbols are longer than one character.
Load the ambiguous E grammar and derive a+a*a. Two parse trees appear, and they disagree about what the expression means — one multiplies first, the other adds first. Now load …fixed with precedence and derive the same string: one tree, and it is the right one.
That is the whole point. Both grammars generate exactly the same language; only one of them is ambiguous. A language is called inherently ambiguous when no unambiguous grammar for it exists, which is a much rarer and much stronger claim.
The search here is bounded, so on a long string with a wildly branching grammar it may stop before finding every derivation. It will say so when it does.