Derivations, Parse Trees, and Ambiguity

The point

Before touching bison, derive some sentences by hand. Ambiguity is easy to define and hard to recognize, and the only reliable way to recognize it is to have once found two trees for the same string yourself.

Do this

1. Derive. Using the starter grammar, write a leftmost derivation for

   int x;
   x = 1 + 2;

   Show every step: program ⇒ stmt_list ⇒ …. Then write the rightmost derivation of the same input and say which one a bottom-up parser would produce in reverse.
2. Draw the parse tree for that derivation. Confirm that both derivations give the same tree — that is the point of §4.2.3.
3. Now the interesting one. Take this fragment, with no precedence declarations:

   expr -> expr '+' expr | expr '*' expr | NUM

   Draw two different parse trees for 1 + 2 * 3. Evaluate both. You should get two different numbers, and that is what ambiguity costs.
4. Fix it two ways. (a) Rewrite the grammar into expr → term → factor layers. (b) Keep the ambiguous grammar and write the %left declarations. Write both out in full.
5. Check associativity. Under your layered grammar, draw the tree for 17 - 5 - 3 and evaluate it. Then make the recursion right-recursive instead and redraw. Which is correct, and what does that tell you about the direction of recursion?
6. Argue. Which fix would you ship, and why? Write the answer you actually believe, not the one you think is expected — Dragon §4.8 argues for the second and most textbooks teach the first.