Why an intermediate representation; syntax trees vs DAGs; counting nodes in a DAG

0 · Recall Warm-up

Answer from memory first. Answers are in the Answer Vault at the end of this lesson.

• How many nodes does the syntax tree of a − 4 + c have? from Lesson 3.4
• What does the semantic analyzer do with price * qty when price is float and qty is int? from Lesson 3.4
• With m languages and n machines, why does a shared intermediate code help? from Lesson 0.1.3

1 · The Story

📖

One card per distinct calculation

Dev in the Drafting Room receives Anaya’s outlines and must write a plain draft that any back-end desk can follow. He notices outlines like “a plus a times (b minus c) plus (b minus c) times d”: the phrase “b minus c” appears twice and would be worked out twice.

Dev keeps one card per distinct calculation. When the same calculation on the same inputs appears again, he does not write a new card; he draws an arrow to the existing one. His outline is no longer a family tree, because one card can have two parents. But it never loops back on itself.

Why a draft at all, instead of jumping from the outline straight to the printed English? Because the same draft can be printed for several kinds of audience, and because a plain draft is the easiest thing to tidy up later.

2 · Predict First

🤔

How many nodes does the shared structure for a + a * (b − c) + (b − c) * d have, if repeated parts are written once? Write your guess down. The answer is in the vault.

3 · Core Concept

Why an intermediate representation

An intermediate representation (IR) is the program form between the front end and the back end. Benefits:

• Retargeting: one front end per language, one back end per machine, sharing the IR (m + n instead of m × n).
• Optimization: machine-independent improvements are done once, on the IR.
• Each phase is simpler: it translates between two nearby levels.

IRs range from high level (syntax trees, DAGs) to low level (linear code with one operation per instruction, next lesson). Compilers often use several.

Syntax trees vs DAGs

A directed acyclic graph (DAG) for an expression is a syntax tree in which identical subexpressions are represented by one shared node. It has the same leaves (one per distinct variable or constant) and one interior node per distinct operator application.

A DAG shows the compiler where a value can be computed once and reused, and it is cheaper to store.

Building a DAG: value numbering

Process the expression bottom-up. Before creating a node (op, left, right), look it up in a table keyed by (op, left node, right node). If it exists, reuse it; otherwise create it. Leaves are looked up by name. This is the value-number method: each node gets a number, and a hash table maps the key to it (Primer 0.2.4).

DAG of a sequence of assignments

For straight-line assignments x = y op z, build nodes for the right side as above, then attach the label x to the node, removing x from any other node (x now names the new value). Initial values of variables are leaves written b₀, c₀, …. Two variables computing the same value from the same inputs end up as labels on one node.

Counting

Story → compiler term

4 · Visual

Syntax tree: 13 nodes.

DAG: 9 nodes, 10 edges; b − c and the leaf a are shared.

DAG of the block a = b + c; b = a − d; c = b + c; d = a − d: 6 nodes. b and d label the same node, because d = a − d computes the same value as b.

5 · Worked Examples

Example 1 Easy

Draw the DAG of a + a * (b - c) + (b - c) * d and count its nodes and edges.

Solution

Leaves a, b, c, d (a used twice, one node). Operators: b − c (shared), a * (b − c), a + a * (b − c), (b − c) * d, and the final +. Total 9 nodes and 10 edges. Dev wrote “b minus c” on one card and pointed to it twice.

Example 2 Medium

Build the DAG for the block: a = b + c; b = a − d; c = b + c; d = a − d.

Solution

a labels node +(b₀, c₀). b labels −(a, d₀). c labels +(b, c₀), a new node because b now names a different value than b₀. d = a − d₀ finds the existing node −(a, d₀), so d becomes a second label on b’s node. Total 6 nodes. The draft can compute that value once and copy it.

Example 3 GATE

What are the numbers of nodes and edges in the DAG of (a * b + c) * (a * b + c) - a * b?

Solution

Leaves a, b, c (3). Operators: a * b (shared three times), a * b + c (shared twice), the product of the two equal sums, and the final −. Nodes = 3 + 4 = 7; edges = 2 × 4 = 8. The syntax tree would have 15 nodes.

6 · Shortcuts

⚡

DAG nodes = distinct leaves + distinct subexpressions; write each subexpression once, bottom-up, and count. Valid when: expressions with binary operators.

⚡

DAG edges = 2 × binary operator nodes (+1 per unary operator node). Valid when: questions asking for edges.

7 · GATE Traps

⚠️

• A repeated variable is one leaf in the DAG, but many leaves in the syntax tree.
• Two subexpressions are shared only if the operator and both operand nodes are identical: a * b and b * a are different nodes unless the compiler uses commutativity.
• In a sequence of assignments, reassigning a variable makes later uses refer to a new node.
• A DAG is acyclic: it can share nodes but never form a loop.

8 · Memory Hook

🧠

Tree: write it every time. DAG: write it once, point to it again.

9 · Connect the Dots

The DAG is still a picture. The back end wants a list of simple instructions it can read in order. The next lesson writes the draft as instructions with at most one operator and three names each.

10 · Self-Test

GATE format. Try every question before opening the vault.

Q1NAT1 markDAG nodes

How many nodes does the DAG of (x + y) * (x + y) + (x + y) have?

Numerical answer: ________

Q2NAT2 marksDAG edges

How many edges does the DAG of (x + y) * (x + y) + (x + y) have?

Numerical answer: ________

Q3NAT2 marksBlock DAG

How many nodes does the DAG of the block p = a + b; q = a + b; r = p * q; s = q * p have (no commutativity)?

Numerical answer: ________

Q4MCQ1 markIR

The main reason for an intermediate representation is:

• (A) to make the lexer faster
• (B) to separate language-dependent and machine-dependent parts and enable optimization
• (C) to remove the need for a parser
• (D) to produce machine code directly

Q5MSQ1 markDAG facts

Which are true about the DAG of an expression?

• (A) It has one leaf per distinct variable or constant.
• (B) It may have a node with two parents.
• (C) It may contain a cycle.
• (D) It never has more nodes than the syntax tree.

11 · Rule Card

• IR: between front end and back end; retargeting (m + n) and machine-independent optimization.
• DAG = syntax tree with identical subexpressions shared.
• Value numbering: reuse node (op, left, right) if it already exists.
• Block DAG: labels move to the newest node of each variable; initial values are leaves x₀.
• Nodes = distinct leaves + distinct operator applications; edges = 2 per binary node.

12 · Concept Ledger

intermediate representation (IR)retargetingDAG (for expressions)node sharingvalue numberingDAG of a blockinitial value leaf x₀

13 · Answer Vault