The full journey: one program traced through every phase

1 · Word Desk — lexical analysis

8 tokens. The lexemes total, price and qty become ⟨id, 1⟩, ⟨id, 2⟩, ⟨id, 3⟩ with entries in the symbol table; 50 becomes ⟨num, 50⟩.

2 · Sentence Desk — syntax analysis (SLR(1))

Grammar (Lesson 3.4):

S → id = E
E → E + T | T
T → T * F | F
F → ( E ) | id | num

The SLR(1) automaton has 16 states and no conflicts. The parse of id = id * id + num takes 17 steps:

Shift-reduce trace (computed). Each reduce pops a handle and pushes the left side.

Parse tree: 16 nodes. * sits below +, so price * qty is grouped first.

3 · Meaning Desk — semantic analysis

Syntax tree with types: qty is int, so the type checker inserts inttofloat(qty); 50 is converted to 50.0 at compile time. Every node is float.

4 · Drafting Room — three-address code

t1 = inttofloat(qty)
t2 = price * t1
t3 = t2 + 50.0
total = t3

Quadruples.

Triples refer to earlier results by position.

5 · The line inside a loop: basic blocks and the flow graph

Now the line runs n times inside a function (types left out for brevity):

total = 0;
i = 0;
while (i < n) {
  total = total + price * qty + 50;
i = i + 1;
} print(total);

Jumping code (Lesson 4.2.3) gives 11 instructions; the leader rules (Lesson 4.4) cut them into 5 blocks:

5 basic blocks and 5 edges (computed). B2 → B4 → B2 is the loop.

6 · Optimization Room

• Liveness (Lesson 6.4, computed above): n, price and qty are live on entry (they are inputs); total is live on exit from the loop because it is printed.
• Loop-invariant code motion (Lesson 6.6): t1 = price * qty uses only values that never change in the loop, so it moves to a preheader. Operations inside the loop drop from 4 to 3 per iteration:

total = 0
i = 0
t1 = price * qty
L1: if i < n goto L2
goto L3
L2: t2 = total + t1
total = t2 + 50
i = i + 1
goto L1
L3: param total
call print, 1

• Constant propagation (Lesson 6.3) finds nothing to fold: total and i are NAC at the loop header, because the back edge brings new values.
• Inside B4, local optimization (Lesson 6.1) finds no common subexpression: every operation is different.

7 · Records Room — the activation record at run time

Calling bill(10, 2, 3) (Lesson 5.2) creates one activation record on the stack. The interpreter’s snapshot just before return:

Output: 210 = 3 × (10 × 2 + 50) (computed by running the program).

8 · Printing Room — target code (as in Lesson 0.1.3)

LD   R2, qty
ITOF R2, R2
LDF  R1, price
MULF R1, R1, R2
ADDF R1, R1, #50.0
STF  total, R1

🔗

One line, every phase: 8 tokens → a 16-node parse tree → a 7-node typed syntax tree with one conversion → 4 three-address instructions → (inside a loop) 5 basic blocks, liveness sets, a hoisted multiplication → one activation record → six machine instructions.

Practice set

Q1NAT1 markLexical

How many tokens does the journey line total = price * qty + 50; have?

Numerical answer: ________

Q2NAT2 marksParsing

How many reduce actions does the SLR(1) parse of id = id * id + num (grammar above) perform?

Numerical answer: ________

Q3MCQ1 markSemantic

Which conversion does the type checker insert for the journey line?

• (A) floattoint(price)
• (B) inttofloat(qty)
• (C) inttofloat(total)
• (D) none

Q4NAT1 markBlocks

How many basic blocks does the loop version have?

Numerical answer: ________

Q5MCQ2 marksOptimization

Which instruction of the loop body can be moved to a preheader?

• (A) t2 = total + t1
• (B) t1 = price * qty
• (C) total = t2 + 50
• (D) i = i + 1