Intermediate code: expressions, control flow and backpatching
Goal and conventions
Translate expressions and Boolean control flow into explicit intermediate instructions. Three-address code (TAC) usually has at most one elementary operator per instruction, such as t=a+b, x=t, if x<y goto L, or goto L. Labels identify instructions, not source lines. Temporaries name intermediate values. The examples use pure integer arithmetic unless a side effect is explicitly named; division-by-zero behavior matters in the Boolean example.
1. Expressions and representations
For x=(a+b)(c-d), emit t1=a+b; t2=c-d; t3=t1t2; x=t3. The final multiply may instead write directly to x when the representation permits, giving x=t1*t2. Therefore instruction-count questions must state whether a separate final copy is required.
A quadruple stores (op,arg1,arg2,result). The first two instructions are (+,a,b,t1) and (-,c,d,t2). A triple stores (op,arg1,arg2) and refers to a previous instruction's position instead of a named result. With zero-based positions: 0:(+,a,b), 1:(-,c,d), 2:(*,(0),(1)). An indirect-triple representation adds a separate ordering list so movement need not force all references to be renumbered. Parenthesized (0) is a result reference, not the integer literal zero.
2. Array-address calculation
For a one-dimensional array A with base address B for A[L], element width w, address(A[i])=B+(i−L)w. If B=1000, L=1, w=4 and i=6, offset=(6−1)4=20, so address=1020. Do not multiply the base address by width.
For a row-major two-dimensional array with lower bounds Lr,Lc and N columns, address(A[i,j])=B+((i−Lr)N+(j−Lc))w. Example: a 3×5 array, lower bounds 0,0, B=2000 and w=8. A[2,3] has element offset 2*5+3=13 and byte address 2104. Column-major layout would require a different stride; a declared layout is essential. Bounds checks, if required by the language, are separate operations from this address formula.
3. Short-circuit Boolean translation
For if (a!=0 && b/a>2) x=1; else x=0;, a correct short-circuit TAC sequence is:
1: if a!=0 goto 3 2: goto 7 3: t=b/a 4: if t>2 goto 6 5: goto 7 6: x=1; goto 8 7: x=0 8: next statement
Instruction 6 here is displayed as assignment plus branch for readability; expand it into two TAC instructions when counting instructions. If a=0, execution takes 1→2→7→8 and never evaluates b/a. If a=2,b=8, it takes 1→3→4→6→8, sets x=1, and the false assignment is skipped. Eagerly evaluating both operands before && would violate this short-circuit behavior and could divide by zero.
For B1 || B2, a true B1 bypasses B2, while a false B1 enters B2. For B1 && B2, a true B1 enters B2, while a false B1 bypasses B2. Logical negation can exchange true and false branch lists without evaluating an arithmetic negation.
4. Backpatching unresolved jumps
Backpatching records the instruction indices of jumps whose targets are not known yet. makelist(i) creates a singleton list, merge joins lists, and backpatch(list,L) fills each listed jump target with L. The list holds jump locations, not the values tested in conditions.
A relational test at indices i and i+1 can emit “if a<b goto _” and “goto _”, giving truelist={i}, falselist={i+1}. For B=B1&&B2, record the start m of B2, patch B1.truelist to m, set B.truelist=B2.truelist, and B.falselist=merge(B1.falselist,B2.falselist). For OR, patch B1.falselist to B2's start, merge truelists, and retain B2.falselist. A marker nonterminal or explicit saved next-instruction index can capture m.
Pitfalls and self-check
TAC is a representation, not a unique output for a source expression. The required evaluation order must preserve side effects, exceptions and language semantics. Short-circuit and bitwise operators differ. A target label is an instruction address in the abstract IR, not a jump-list element value. Signed overflow, floating-point arithmetic, aliasing and bounds checks constrain later optimization; do not discard these merely because code is intermediate.
Original practice: six single-correct MCQs
These original teaching questions are not previous-year questions. Choose exactly one answer.
P01. Using named temporaries and a required final copy, x=(a+b)*(c-d) needs how many shown TAC instructions?
A. 2 B. 3 C. 4 D. 5
Answer: C
A: There are three arithmetic operations plus a copy.
B: Three would omit the required final copy.
C: Two subexpressions, one multiply, and one copy give four.
D: No fifth operation is required.
P02. A[1] starts at 1000 with 4-byte elements. Address of A[6]?
A. 1006 B. 1020 C. 1024 D. 4006
Answer: B
A: The index difference must be scaled.
B: 1000+(6−1)×4=1020.
C: This incorrectly assumes lower bound zero.
D: The base address must not be multiplied by width.
P03. Row-major A[3][5], zero lower bounds, base 2000, width 8: address of A[2][3]?
A. 2040 B. 2072 C. 2104 D. 2120
Answer: C
A: This uses only i+j instead of the row stride.
B: This does not use the five-column row stride correctly.
C: Offset is (2×5+3)×8=104 bytes.
D: Fifteen elements is the total size, not this element offset.
P04. For a!=0 && b/a>2 when a=0, correct short-circuit evaluation:
A. Evaluates b/a first B. Skips b/a and returns false C. Skips b/a and returns true D. Always signals division by zero
Answer: B
A: The first operand must be tested before the second.
B: False left operand determines conjunction immediately.
C: False AND anything is false.
D: The dangerous expression is not evaluated.
P05. For B1&&B2, which list is patched to B2’s beginning?
A. B1.truelist B. B1.falselist C. B2.truelist D. Both B2 lists
Answer: A
A: A true first operand requires evaluating the second.
B: A false first operand bypasses B2.
C: This list belongs to the result of B2.
D: These targets represent outcomes after B2.
P06. In a triple operand written (0), 0 denotes:
A. Always literal zero B. The source variable named zero C. The result produced at triple position 0 D. A mandatory null pointer
Answer: C
A: Parentheses mark an instruction-result reference here.
B: No such variable was introduced.
C: Triples reference prior results by positions.
D: This notation is unrelated to null pointer values.
Sources and scope
Aligned to the official 2026 course. This lesson covers a bounded topic slice; no claim of 2027 completeness. All examples and exercises are original.
Sign in to keep your progress. Sign in