Compiler Design Semester Guide: Trace One Program from Tokens to Target Code

Lexical analysis, parsing, type checking, intermediate code and target code are often revised as separate definitions, so the artefact passed from one phase to the next remains unclear. This guide carries total = base + 3 * 60; through every major phase while connecting theory answers, grammar exercises and a small compiler lab. With base = 20 at run time, the final stored value must be total = 200.

This journey sits within the wider CS Fundamentals learning path.

1. Put the semester topics in data-flow order

Use this dependency chain as your map: source characters -> tokens -> parse tree and AST -> symbol table and typed AST -> three-address code -> optimized IR -> target instructions. The front end recognises and validates source, the middle end transforms an intermediate form, and the back end chooses target operations and storage. Textbooks may group or name phases differently, so check your university's current syllabus and treat this as a learning map, not a universal syllabus.

Our complete fragment is int base; int total; base = input(); total = base + 3 * 60;. In this toy language, input() returns an integer, identifiers need declarations, + and * take integer operands, * binds more tightly than +, and ; ends a statement. Learners who also need adjacent semester subjects can use Zero to Hero as the wider route.

2. Lex the assignment into eight exact tokens

The scanner uses ID = [A-Za-z_][A-Za-z0-9_]*, NUM = [0-9]+, literal one-character tokens for =, +, * and ;, and a rule that ignores spaces and tabs. Scanning only total = base + 3 * 60; from left to right produces exactly:

<ID,total>, <ASSIGN,=>, <ID,base>, <PLUS,+>, <NUM,3>, <MUL,*>, <NUM,60>, <SEMI,;>

The lexer groups characters and preserves useful attributes, such as an identifier-table reference or integer value. It does not decide whether the expression follows the grammar or whether base was declared. Spaces vanish because the skip rule says so.

In total = base + 3 @ 60;, @ matches no token rule, so the scanner reports a lexical error there. In total = base + 3 * 60, every visible character can be tokenised, but SEMI is missing, so the parser reports the error. The lexical-analysis guide explains the DFA construction behind this recognition.

3. Parse precedence into one concrete tree and one smaller AST

Use this expression grammar:

S -> id = E ;
E -> E + T | T
T -> T * F | F
F -> id | num

Its leftmost derivation over token classes is:

S => id = E ;
  => id = E + T ;
  => id = T + T ;
  => id = F + T ;
  => id = id + T ;
  => id = id + T * F ;
  => id = id + F * F ;
  => id = id + num * F ;
  => id = id + num * num ;

Substituting lexemes recovers total = base + 3 * 60;. The concrete tree groups the right operand through T -> T * F, giving base + (3 * 60), not (base + 3) * 60. Removing punctuation and single-child grammar nodes yields the exact AST Assign(Id(total), Add(Id(base), Multiply(Int(3), Int(60)))).

The displayed grammar is left-recursive. It is suitable for explaining precedence or for bottom-up parsing, but predictive recursive descent must remove that recursion, for example: E -> T E', E' -> + T E' | epsilon, T -> F T', T' -> * F T' | epsilon, F -> id | num.

4. Run name and type checks on the same AST

The toy compiler's symbol table contains (base, variable, int, offset 0), (total, variable, int, offset 4) and (input, function, () -> int, no data offset). These offsets are local assumptions for this example, not a rule for every compiler or machine. Name resolution first connects both identifier uses to their declarations.

Type annotation then works bottom-up: Int(3):int; Int(60):int; Multiply(int,int):int; Id(base):int; Add(int,int):int; and Id(total):int <- int. The assignment is valid.

Parsing success is not semantic success. total = base + rate * 60; matches the same grammar and creates the same AST shape, but lookup fails because rate has no declaration. If rate were declared bool, multiplication would instead fail the toy language's integer-operand check. No C-style implicit conversion is part of these stated rules.

5. Lower the typed AST, then optimize only what is known

Three-address code makes dependency order explicit:

t1 = 3 * 60
t2 = base + t1
total = t2

The matching quadruples are (*, 3, 60, t1), (+, base, t1, t2) and (=, t2, -, total). Temporaries describe intermediate results without committing them to physical registers.

Now apply only justified transformations. Constant folding changes t1 = 3 * 60 to t1 = 180. Constant and copy propagation make the next line t2 = base + 180. Removing the redundant final temporary produces total = base + 180.

The compiler cannot replace the entire expression with 200: base comes from input(), while its demonstration value 20 becomes known only during the later execution trace. The correctness check is direct:

original:  20 + 3 * 60 = 20 + 180 = 200
optimized: 20 + 180 = 200

Both forms agree. For more representations and conversion practice, use Intermediate Code Generation: TAC, Quadruples, Triples.

6. Select target instructions and trace the run-time value

Consider an abstract load-store target, not a named real instruction set. LOAD R1, base reads base from memory, ADDI R1, R1, #180 adds an immediate integer, and STORE total, R1 writes the register to total. Optimized IR total = base + 180 therefore becomes:

LOAD R1, base
ADDI R1, R1, #180
STORE total, R1

Before execution, memory has base = 20 and total is unassigned. After LOAD, R1 = 20. After ADDI, R1 = 200. After STORE, memory has total = 200. The selector uses an immediate form because 180 is known at compile time, while base still requires a run-time load.

A small lab acceptance test should demand eight tokens, an Assign AST root, three unoptimized TAC statements, one optimized IR statement and these three target instructions. Interpreting them with base = 20 must store 200.

7. Fix the phase-confusion traps that cost marks and lab time

Use the numerical checksum to catch a wrong tree, IR or target trace. Correct grouping gives 20 + (3 * 60) = 20 + 180 = 200. Wrong grouping gives (20 + 3) * 60 = 23 * 60 = 1380. The gap exposes a faulty phase result more reliably than memorising phase definitions alone.

8. How theory papers and lab vivas test the chain, then the short version

These are exam-style prompts, not quoted previous-year questions.

• Prompt A: For total = base + 3 * 60;, give the tokens and AST. The answer is the eight-token stream above and Assign(Id(total), Add(Id(base), Multiply(Int(3), Int(60)))).

• Prompt B: Give TAC, optimized IR and output for base = 20. The answer is the three TAC statements, total = base + 180, and 200.

• Prompt C: Replace base with undeclared rate. Parsing succeeds, then semantic name resolution fails.

• Prompt D: Remove ;. The parser rejects the statement after the expression because SEMI is expected.

For a lab viva, explain each hand-off in one sentence and run five tests: valid source, extra whitespace yielding the same eight tokens, illegal @, missing ;, and undeclared rate. KnowledgeGate has 700+ published Compiler Design questions for optional practice, but that count says nothing about official topic weightage.

The short version

Check your university's official current syllabus, theory-paper instructions and compiler-lab brief. For recall, keep the chain characters -> tokens -> tree -> typed tree -> TAC -> optimized IR -> instructions -> run-time result. Replay that chain as a compact phase refresher, then take the focused Compiler Design route when you want a structured next step.