Intro to Compilers Formula Sheet and Revision Notes: Six Phases in One Worked Trace

You may remember the six compiler phases yet confuse a token with a lexeme, a phase with a pass, or an assembler with a compiler. Revise them through one connected trace: characters become tokens, tokens become structure, structure gains meaning, meaning becomes IR, IR is safely improved, and IR becomes target instructions. Use the Compiler Design Blog when you need the wider subject sequence.

1. Language processing system: what each tool consumes and produces

This sheet uses one teaching model: a conventional C toolchain with .c, .i, .s and .o suffixes; a front/middle/back-end grouping; operation count as the optimisation cost model; architecture-neutral pseudo-instructions; and integer division by zero as a runtime fault.

A compiler translates high-level source, while an assembler translates assembly into object or machine code. An interpreter executes source or IR without requiring a separate permanent target executable. Classify each shown stage by what it consumes and produces rather than by a product name.

2. The six compiler phases and their outputs

Match evidence to the transformation and output.

The front end covers lexical, syntax and semantic analysis and produces IR. The middle end handles target-independent analysis and optimisation. The back end selects target instructions, storage and registers. The symbol table and error reporting are shared services beside the chain, not phase seven. For a longer journey, see Compiler Design: Six Phases Traced in One Example.

3. Lexical and syntax analysis: tokens before trees

A token has the form token = <token-name, optional attribute>. A lexeme is the exact source sequence matched. A pattern describes every valid lexeme in a token class. For the preprocessed assignment, the 12 token occurrences are:

id(total), =, num(12.5f), +, id(units), *, (, num(2), *, num(2), ), ;

Whitespace separates tokens here but is not a token. The two occurrences of 2 count separately. When rules overlap, choose the longest valid lexeme. Attach a symbol-table pointer or literal value as an attribute when needed. Finish token counting before applying grammar precedence. For regular expressions, DFA scanning, maximal munch and buffering, revise Lexical Analysis: Tokens, Patterns and DFA Scanning.

Syntax analysis gives =(total, +(12.5f, *(units, *(2, 2)))). Parentheses force the inner 2 * 2, and multiplication binds before addition. A parse tree keeps grammar scaffolding, while an AST removes punctuation and unit productions that do not carry essential structure.

4. Semantic analysis and symbol table rules

A symbol table maps an identifier and scope to attributes needed during translation.

It may also record declaration location, parameter information and visibility. Numeric literals are tree values, not identifier declarations here.

Language policies decide allowed conversions, while semantic analysis enforces them. Bottom-up typing gives 2 * 2 : int and units * (2 * 2) : int. Since 12.5f : float, convert the integer product before addition. The result is +(12.5f, inttofloat(*(units, *(2,2)))), with final type float, suitable for assignment to total.

5. Fully worked trace: compile the statement and confirm total = 24.5

Start with total = 12.5f + units * (2 * 2); and runtime input units = 3. Lexical analysis produces the same 12-token stream. Syntax analysis builds =(total, +(12.5f, *(units, *(2, 2)))). The symbol table supplies units : int and total : float, so semantic analysis inserts the integer-to-float conversion before addition. The checked expression remains a float suitable for assignment to total.

The unoptimised three-address code is:

t1 = 2 * 2
t2 = units * t1
t3 = inttofloat(t2)
t4 = 12.5f + t3
total = t4

Check every temporary in order: t1 = 2 * 2 = 4; t2 = 3 * 4 = 12; t3 = 12.0; t4 = 12.5f + 12.0 = 24.5; therefore total = 24.5.

Constant folding changes 2 * 2 to 4. Constant propagation places 4 in the multiplication, and copy removal assigns the addition directly:

t2 = units * 4
t3 = inttofloat(t2)
total = 12.5f + t3

With units = 3, this gives t2 = 12, t3 = 12.0 and total = 24.5 again, while constant folding reduces runtime arithmetic from three operations to two.

Architecture-neutral pseudo-target code is:

LOADI R1, units
MULI R1, R1, #4
ITOF F1, R1
ADDF F1, F1, #12.5f
STOREF total, F1

Track the machine state: R1 = 3 -> 12, then F1 = 12.0 -> 24.5, then memory total = 24.5. Semantic equivalence from source to target is the invariant.

6. Errors, recovery and passes

Classify errors by the violated rule.

Recovery reports a location and resumes without inventing correctness. Panic-mode syntax recovery may skip to ;, then check later statements.

A phase is a logical transformation. A pass is one traversal over source or IR. Thus phase count != pass count: phases may share a pass, and one analysis may need repeated passes to reach a fixed point.

7. How questions test the sheet and traps to audit

Questions may ask you to order processors; match phase I/O; count tokens; distinguish token, lexeme and pattern; draw an AST; infer types and conversions; classify errors; construct TAC; test constant folding; compare phases and passes; or identify a cross compiler. An x86-hosted compiler targeting ARM is cross-compiling because host and target differ, regardless of source language.

Audit five traps:

1. Preprocessor, linker and loader are not extra compiler phases.

2. Symbol table is shared state, not phase seven.

3. Classify errors by violated rules, not reporting points.

4. AST is not a token list.

5. Shorter IR must preserve behaviour.

KnowledgeGate’s published Intro to Compilers questions provide practice across these skills. Use Compiler Design for GATE: Syllabus, Weightage and Prep Order for wider sequencing.

8. The five-minute Intro to Compilers revision routine

Use this recall card:

1. Write preprocess -> compile -> assemble -> link -> load.

2. Write characters -> tokens -> AST -> typed AST -> IR -> optimised IR -> target.

3. Define token, lexeme and pattern.

4. Place the symbol table beside every phase.

5. Type expressions bottom-up.

6. Optimise only after proving equivalence.

7. Separate compile, link and runtime errors.

8. Remember phase != pass.

Recheck units = 3 -> total = 24.5 from source through target. The short version: know every stage's input, output and failure boundary, then trace one statement completely. Use Compiler Design for structured study, or return to the Compiler Design Blog at the start for topic-by-topic browsing.