Intermediate Code Generation Formula Sheet: TAC, Quadruples and Backpatching Revision Notes

You remember TAC, quadruples, triples and backpatching, but under pressure mix row formats, temporary counts and jump lists. This sheet gives one formula set, traced expression and exact backpatching trace. Since conventions vary, name yours before counting rows or temporaries.

Intermediate Code Generation Formula Sheet at a Glance

The pipeline is:

source program → syntax tree or DAG → intermediate code → machine-independent optimisation → target code

An intermediate representation (IR) bridges front end and back end; TAC is one linear IR. With four sources and three targets, direct translation needs 4 × 3 = 12 combinations; a shared IR needs 4 + 3 = 7 front-end and back-end components.

Need full teaching? Read the complete guide to intermediate code generation.

TAC Forms and Syntax-Directed Translation Rules

Here, n counts arguments; || means code concatenation, not Boolean OR:

• E → E1 op E2: E.place = newtemp() and E.code = E1.code || E2.code || gen(E.place = E1.place op E2.place)

• E → id: E.place = id and E.code = ε

• S → id = E: S.code = E.code || gen(id = E.place)

See syntax-directed translation worked examples for dependency order.

For y = -a + b * c, a = 4, b = 2, c = 6: t1 = uminus a = -4, t2 = b * c = 12, t3 = t1 + t2 = 8, y = t3. Convention: 4 rows, 3 temporaries; unary minus gets its own row.

Worked Example: Expression to TAC, DAG, Quadruples and Triples

Use x = (a + b) * (c - d) + (a + b) with a = 2, b = 3, c = 9, d = 5.

Naive tree TAC: 6 rows, 5 temporaries

1. t1 = a + b = 2 + 3 = 5

2. t2 = c - d = 9 - 5 = 4

3. t3 = t1 * t2 = 5 * 4 = 20

4. t4 = a + b = 2 + 3 = 5

5. t5 = t3 + t4 = 20 + 5 = 25

6. x = t5 = 25

DAG-reuse TAC: 5 rows, 4 temporaries

1. t1 = a + b = 5

2. t2 = c - d = 4

3. t3 = t1 * t2 = 20

4. t4 = t3 + t1 = 25

5. x = t4 = 25

Reuse is safe because a and b do not change.

The optimised representations are:

Triple (0) means row 0's result. Pointers start [0, 1, 2, 3, 4]. Rows 0 and 1 are independent, so [1, 0, 2, 3, 4] is valid with later references unchanged.

Array, Pointer and Procedure-Call Formulas

Definitions: base(A) is base address, L1/L2 lower bounds, w element width, and N1/N2 row and column counts.

For zero-based 4 × 5 array A, let base(A) = 1000, w = 4; find A[2][3]:

• Row major: ((2 × 5) + 3) × 4 = 13 × 4 = 52, so the address is 1000 + 52 = 1052.

• Column major: ((3 × 4) + 2) × 4 = 14 × 4 = 56, so the address is 1000 + 56 = 1056.

Row-major TAC: t1 = 2 * 5 = 10, t2 = t1 + 3 = 13, t3 = t2 * 4 = 52, t4 = 1000 + t3 = 1052, x = *t4. Index 13 is not byte offset 52.

Call mnemonic: param a; param b; t = call f, 2; return t. Do not invent unstated conventions.

Boolean Translation and Backpatching Rules

makelist(i) creates a one-jump list, merge(p1,p2) combines unresolved lists, and backpatch(p,i) fills target i into each jump in p.

• B1 && B2: patch B1.truelist to the first instruction of B2; true list is B2.truelist; false list is merge(B1.falselist, B2.falselist).

• B1 || B2: patch B1.falselist to the first instruction of B2; true list is merge(B1.truelist, B2.truelist); false list is B2.falselist.

• !B1: swap the true and false lists.

For a = 7, b = 4, c = 2, d = 5, trace if (a < b || c < d) x = 1; else x = 0:

100: if a < b goto _
101: goto _
102: if c < d goto _
103: goto _
104: x = 1
105: goto _
106: x = 0
107: next

Patch [101] → 102, true list [100,102] → 104, false list [103] → 106, and [105] → 107. Path: 100 false → 101 → 102 true → 104 → 105 → 107; hence x = 1.

How GATE CS Tests Intermediate Code Generation

The official GATE 2024 Computer Science and Information Technology syllabus lists syntax-directed translation, runtime environments and intermediate code generation under Compiler Design. It assigns no fixed marks or yearly weightage to the topic.

Practice asks for TAC counts, representation conversion, safe reuse, array offsets, backpatch lists and SDT dependency order. Place these within your wider GATE CS preparation.

In 60 seconds: circle operators and side effects, state the convention, emit one operator per row, mark temporaries, check redefinitions before DAG reuse, then convert.

Common Mistakes and the Two-Minute Final Check

Final check: a + b = 5, result 25, DAG reuse 5 rows and 4 temporaries, no operand redefinition. Trace, table and diagram must agree.

Short Version and the Next Revision Step

• At most one right-hand-side operator per TAC row.

• place names a result; code concatenates emitted rows.

• Quadruples name results.

• Triples reference row numbers.

• DAGs reuse only safe common subexpressions.

• Backpatching fills unresolved jump targets.

Concept gap? Continue with GATE Guidance by Sanchit Sir. Ready for timed practice? Use the GATE Test Series, then study code optimisation worked traces.

Cover the formulas, regenerate the main TAC and backpatch rows from memory, then check every count and target.