Topic 2 · Class activity 3 · Week 3 · Wednesday

Parse Tree, Syntax Tree, and Attributes

Draw both trees, count what you threw away, then annotate with attributes and check the arrows only point upward.

Format individual, then compareTime 40 min

The point

You are about to design a data structure that five later phases must live with. Design it on paper first, and be deliberate about what you throw away.

Do this

  1. Draw the parse tree AND the syntax tree for
    int a;
int b;
a = 1 + 2;
b = a + a;
print(b);
  2. Count the nodes in each and write both numbers down.
  3. For every node in the parse tree that is NOT in the syntax tree, say in one phrase what it was for and why no later phase needs it. Group them: punctuation, single-child chains, and anything else.
  4. Attributes. Annotate your syntax tree with a val attribute wherever it can be computed, and draw an arrow for each attribute dependency. Are any of your arrows pointing downward? If not, your definition is S-attributed — say what that buys you.
  5. Design decision. Our NODE_STMT_LIST holds two children — a statement and 'the rest'. The alternative is one node holding an array of statements. Sketch both for the five-statement program above.
  6. Argue it. Which is easier to build in a bison action? Which is easier to walk in generateTAC? They are not the same answer, and noticing that is the point of the exercise.
A nudge on step 6

A left-recursive rule reduces one statement at a time, so the action naturally builds a linked structure — an array version has to grow and copy. But walking a list-of-lists means every visitor needs a special case for 'this child is itself a list', and forgetting it is exactly the bug that makes a compiler silently skip statements. Look at how the given code handles it in checkStmtList.

Deliverable

Both trees, both node counts, your grouped list from step 3, the annotated tree from step 4, and a paragraph on step 6. This is Lab Question 6 nearly verbatim.