Compiler Design: From Source to Machine Code

On a trading day, the co-location servers that sit inside the National Stock Exchange's Mumbai data centre receive a price tick and must decide, before the next tick arrives, whether to fire an order. The decision logic itself is a few hundred lines of C++: compare a bid-ask spread against a threshold, check available margin, place an order. A programmer reading that file sees ordinary arithmetic and a few conditionals. The engineers who tune such systems for microsecond latency do not read it that way. They ask a narrower, harder question: what will the compiler turn this arithmetic into, and can that translation be made faster without changing what the program computes? Whether a helper function gets folded into its caller, which variable is left sitting in a CPU register instead of round-tripping to memory, whether a division becomes an actual divide instruction or a cheaper multiply-and-shift sequence: none of this is visible anywhere in the source file. It is decided entirely inside the compiler, in a pipeline of well-defined stages between the semicolon a programmer types and the bytes the processor executes. This chapter opens that pipeline up.

Translator, Interpreter, Assembler: Naming the Job Correctly

A compiler is one member of a family of translator programs, and the vocabulary matters. An assembler converts assembly language, a symbolic, near one-to-one stand-in for machine instructions, into binary opcodes; it performs almost no analysis. An interpreter reads a high-level program and executes it directly, statement by statement, effectively re-examining the same loop body every single time control passes through it. A compiler reads the entire program once (or, more precisely, in a small, fixed number of passes over it), builds a complete internal model of that program, and emits a separate target-language program, typically assembly or machine code, that can then be run independently and repeatedly with no further translation cost. That distinction, translate-once-run-many versus translate-and-run-together, is exactly why compiled C++ is the default choice for a latency-critical trading engine and an interpreted script is not: every microsecond spent re-parsing a line is a microsecond not spent trading. Real systems blur this line productively: the Java compiler javac emits JVM bytecode, an intermediate form that the JVM then interprets and, for its hottest loops, further compiles at run time with a Just-In-Time compiler. But the pipeline this chapter dissects, the classic ahead-of-time compiler, is the one every other translator design borrows its phases from.

Six Phases, One Shared Table

A compiler is not a single transformation from characters to bytes. It is a sequence of analysis phases followed by a sequence of synthesis phases, each consuming the output of the phase before it, and each capable of rejecting the program with its own specific class of error.

Lexical analysis, done by the scanner, reads the raw character stream and groups characters into tokens: keywords, identifiers, numeric and string literals, operators, punctuation. It is implemented as a finite automaton scanning strictly left to right, and it is the only phase that sees whitespace and comments, both of which it discards. A character sequence that matches no valid token pattern is a lexical error, caught here before anything about grammar or meaning is even considered.

Syntax analysis, done by the parser, consumes the token stream and checks it against the language's context-free grammar, building a parse tree and then collapsing it into a leaner abstract syntax tree (AST) that keeps only the structure later phases need: operator precedence is baked directly into the tree's shape, and punctuation such as parentheses and semicolons is discarded once its grouping job is done. A token sequence that is individually valid but arranged illegally, an assignment missing its right-hand side, an unmatched bracket, is a syntax error, caught here.

Semantic analysis walks the AST and checks meaning rather than shape: is every identifier declared before use, does an expression's type match what its context requires, is a function called with the right number and type of arguments. This phase is the primary reader and writer of the symbol table, a data structure, in practice a hash table per lexical scope, that maps each identifier to its declared type, its scope, and its eventual storage location. A program can be grammatically perfect and still be semantically wrong (assigning a string literal to a variable declared int is the standard example), and only this phase catches that.

Intermediate code generation lowers the type-checked AST into a representation that is independent of any target machine, most commonly three-address code (TAC): a sequence of simple instructions, each with at most one operator and three operands, of the form t1 = a op b. TAC exists because it is far easier to optimise and retarget than either the tree-shaped AST or the eventual machine code; it is close enough to real instructions that translating it to any given architecture is mechanical, but abstract enough that no architecture-specific decision has been locked in yet.

Code optimization rewrites the TAC into an equivalent but cheaper TAC. Standard transformations include constant folding (replacing 3 * 4 with 12 at compile time, since both operands are already known), common subexpression elimination (computing a repeated expression once and reusing the stored result), dead code elimination (deleting computations whose results are never read), and strength reduction (replacing an expensive operation with a cheaper one that produces an identical result, such as a left shift standing in for a multiply by a power of two). This phase is never allowed to change what the program computes, only how expensively it computes it.

Code generation is where TAC becomes real target instructions. It bundles three sub-problems: instruction selection (choosing which machine opcodes implement each TAC operation), register allocation (deciding which of the small, fixed set of CPU registers holds each live value, and which values must be spilled to memory when there are more live values than registers), and instruction scheduling. A final linking step, strictly outside the compiler proper but part of the same toolchain, stitches the resulting object file together with library code and resolves addresses across files into one runnable executable.

The diagram below lays out this six-phase pipeline together with the one structure, the symbol table, that four of the six phases read from or write into as the program moves through them.

The four dashed lines are the part of the diagram most students skip past and the part that matters most: the symbol table is not one more box in the sequence, it is shared state that the lexer populates, the parser and semantic analyzer consult and enrich, and the code generator reads from when it needs to decide a variable's memory offset or register. Every phase in the chain above it is, in effect, also writing a program for the phase below it to read.

Worked Example: Tracing total = base + tax * base / 100; Through Every Phase

Take a single statement, the kind of line that appears in a billing routine anywhere from an IRCTC fare calculator to a GST invoice module, and walk it through all six phases by hand.

1. Lexical analysis. The scanner reduces the character stream to this token sequence, discarding all whitespace between tokens:

IDENTIFIER(total)  OP(=)  IDENTIFIER(base)  OP(+)
IDENTIFIER(tax)  OP(*)  IDENTIFIER(base)  OP(/)  NUMBER(100)  PUNCT(;)

2. Syntax analysis. The parser applies the grammar's precedence rules: * and / bind tighter than +, and among themselves * and / are left-associative. The token stream above is therefore not grouped left to right as written; it is grouped as base + ((tax * base) / 100). The resulting AST has an addition node at its root, with base as its left child and a division node as its right child, and that division node in turn has a multiplication node (tax, base) as its left child and the literal 100 as its right child.

3. Semantic analysis. The analyzer looks up base, tax, and total in the symbol table, confirms all three were declared as compatible numeric types, and confirms the literal 100 is int-compatible for the division. No mismatch is found, so the AST is annotated with type information and passed on unchanged in structure.

4. Intermediate code generation. Walking the annotated AST bottom-up, the compiler allocates one temporary per internal node:

t1 = tax * base
t2 = t1 / 100
t3 = base + t2
total = t3

5. Code optimization. The optimizer checks each standard transformation in turn. Constant folding does not apply: tax and base are run-time variables, not compile-time constants, so t1 cannot be precomputed. Common subexpression elimination does not apply either: although base appears twice, it appears as two different subexpressions (once multiplied by tax, once added to t2), not as one repeated computation, so there is nothing to reuse. Strength reduction does not apply to the division: the shift trick that replaces x / 2 with a single right-shift instruction only works when the divisor is a power of two, and 100 is not one (a production compiler such as GCC or LLVM would still eliminate the actual divide instruction here, replacing it with a fixed multiply-by-a-magic-constant-and-shift sequence computed once at compile time for the specific divisor 100, but deriving that constant is a separate algorithm and not a transformation a student is expected to hand-derive). The optimizer therefore leaves this particular TAC unchanged, which is itself a useful lesson: optimization passes are allowed to do nothing when no legal, meaning-preserving improvement exists.

6. Code generation. Targeting a generic x86-style instruction set with general-purpose registers eax, ebx, ecx, edx:

MOV  eax, [tax]      ; eax = tax
IMUL eax, [base]     ; eax = tax * base        (t1)
CDQ                  ; sign-extend eax into edx:eax, required before IDIV
MOV  ecx, 100
IDIV ecx             ; eax = t1 / 100 (quotient)  (t2)
MOV  ebx, [base]     ; ebx = base
ADD  ebx, eax        ; ebx = base + t2          (t3)
MOV  [total], ebx    ; total = t3

Two register-allocation decisions are visible here even in eight lines. First, temporary t1 never gets its own register: liveness analysis shows t1 is dead the instant t2 is computed from it, so the allocator lets eax simply be overwritten by the IDIV result instead of copying it to a fresh temporary, saving an instruction. Second, IDIV is not a two-operand instruction the way ADD is; the x86 architecture hard-wires it to divide the 64-bit value held across edx:eax by its one explicit operand, which is precisely why the seemingly unrelated CDQ instruction has to appear immediately before it: without sign-extending eax into edx first, the division would read garbage out of edx and produce the wrong quotient. That instruction exists purely because of a target-architecture constraint that was invisible at every phase before code generation. Trace the arithmetic with concrete numbers to confirm correctness end to end: if base = 2400 and tax = 18, then t1 = 18 * 2400 = 43200, t2 = 43200 / 100 = 432, and total = 2400 + 432 = 2832, which is exactly base-plus-18-percent-GST computed by hand.

Correcting a Misconception: Compilation Is Not Line-by-Line Translation

A student who has only ever seen an interpreter run a script line by line, printing output after each statement, tends to picture a compiler doing the same thing, just producing assembly instead of results: read one source line, emit its machine-code equivalent, move to the next line. That mental model is wrong in a way that matters. A compiler does not translate the token stream directly; it translates the tree that the parser builds from the token stream, and several of the most important compiler decisions are only possible because the compiler can see the whole expression, or the whole function, or the whole program, at once. Precedence is the clearest small-scale proof: a + b * c is not correctly evaluated by processing tokens left to right, because doing so would compute (a + b) * c. With a = 2, b = 3, c = 4, the correct grammar-driven grouping gives 2 + (3 * 4) = 14, while the naive left-to-right reading gives (2 + 3) * 4 = 20, a different number entirely. The parser can only produce the correct grouping because it builds a tree from the whole expression and applies the grammar's precedence rules to that structure, not because it walks the token stream once left to right. The same whole-expression view is what makes optimization possible at all: common subexpression elimination has to recognise that two textually separate pieces of an expression compute the same value, which is a comparison across the tree, not a property of any single line.

Why the Front End Is Reusable and the Back End Is Not

Splitting the pipeline at the point where TAC is generated is not an arbitrary implementation choice; it is what makes real compiler engineering tractable. Everything before intermediate code generation, the lexer, the parser, the semantic analyzer, depends only on the source language, never on the target CPU. Everything from code generation onward depends only on the target architecture, never on the source language. This is why GCC and LLVM can compile the same C++ source to x86-64, ARM, or RISC-V by swapping out only the back end: one front end, several interchangeable code generators, all communicating through the same intermediate representation. It is also why the register-allocation and instruction-selection work in a low-latency trading engine's build is a back-end concern entirely: the source code an engineer writes never changes, but compiling with aggressive optimization flags changes which functions get inlined (eliminating call overhead of a few nanoseconds, and, more importantly, giving the register allocator a bigger, unbroken block of code to work with so a hot variable can stay in a register across what used to be a function boundary instead of being spilled to memory on every call). None of that is a change to what the program computes. It is entirely a change to how the code generator, at the very last phase of the pipeline this chapter has just walked through, chooses to realise the same TAC in silicon.

Active Recall

1. Given y = (a - b) * (a - b) + c;, write the naive three-address code generated directly from the AST, then write the version a common-subexpression-elimination pass would produce.
2. Why can a lexer never detect that x = y + ; is invalid, while a parser detects it immediately? Name the phase and the exact structural rule that is violated.
3. A statement int x; x = "hello"; passes the parser without complaint. Which phase rejects it, using which data structure, and on what grounds?
4. At one point in a compiled function, three variables a, b, and c are simultaneously live, but the target machine has only two general-purpose registers available. What must the register allocator do, and what extra instructions does that decision add to the generated code?
5. A classmate claims: "Compiled code is always faster than interpreted code, so a compiler is strictly better than an interpreter." Using the javac / JVM example from this chapter, explain what that claim overlooks.

Worked answers.

1. Naive TAC, generated bottom-up from an AST that has no knowledge that its two (a - b) subtrees are identical: t1 = a - b, t2 = a - b, t3 = t1 * t2, t4 = t3 + c, y = t4, five instructions including one subtraction that duplicates work. After common subexpression elimination recognises that t1 and t2 compute the identical expression: t1 = a - b, t2 = t1 * t1, t3 = t2 + c, y = t3, four instructions, one subtraction instead of two. Check both against concrete numbers, a = 5, b = 2, c = 1: both versions compute (5-2)*(5-2)+1 = 3*3+1 = 10, confirming the optimization preserved meaning while removing one redundant subtraction.
2. The lexer only ever asks "does this character sequence form a valid token," working on isolated characters with no notion of grammar; every individual token in x = y + ; is perfectly valid (identifier, operator, identifier, operator, punctuation), so the lexer accepts the whole stream with no complaint. The parser is the phase that checks token sequences against the grammar rule for an expression, which requires an operand on both sides of a binary operator like +; finding a semicolon where an operand is grammatically required is a syntax error, caught only once the parser tries to build a parse tree for that expression.
3. Semantic analysis rejects it, using the symbol table. The parser accepts x = "hello"; because it matches the grammar for an assignment statement (identifier, =, expression, semicolon) regardless of types. The semantic analyzer then looks up x in the symbol table, finds its declared type is int, computes the type of the right-hand side as a string literal, and flags the mismatch: an int cannot be assigned a string.
4. The allocator must choose two of the three variables to keep resident in the two available registers and spill the third: store its value to a reserved slot on the stack at the point it becomes displaced, and insert a load instruction to bring it back into a register just before its next use. Concretely, if a and b occupy the two registers and c is spilled, the generated code gains one extra STORE c, [stack_slot] earlier and one extra LOAD reg, [stack_slot] right before c is next read, both of which are pure overhead that would not exist if a third register had been available.
5. The claim conflates "compiled" with "fast" as if the two were the same property, when what actually determines speed is whether translation work is repeated at run time, not which category label the tool wears. The JVM interprets bytecode for code that runs rarely, avoiding the cost of compiling paths that barely execute, and reserves its Just-In-Time compiler for the specific loops that run often enough to justify the compilation cost, often producing machine code, at run time, that is competitive with ahead-of-time compiled C++ for that hot loop. A tool being called a compiler guarantees nothing about the speed of any specific program; the phases this chapter covered, and in particular how aggressively the optimizer and code generator are allowed to work, are what determine that.

Think About It

Think about this: How would you explain compiler design: from source to machine code to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind compiler design: from source to machine code, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.