Compiler Design

What a Compiler Does

A compiler translates a program written in a source language into an equivalent program in a target language — usually machine code, bytecode, or another high-level language. It does this while preserving meaning and, ideally, improving efficiency. The work is split into a front end (understand the source), a middle end (optimise a language-neutral representation), and a back end (emit target code).

The Phases

Lexical Analysis (Scanning)

The lexer reads the character stream and groups characters into tokens — the smallest meaningful units. Each token has a type (keyword, identifier, number, operator) and often a lexeme value. Whitespace and comments are usually discarded.

Token patterns are described with regular expressions, compiled to a finite automaton, and matched using the maximal munch rule: always take the longest lexeme that matches (so >= is one token, not > then =).

// Source
let x = 42 + y;

// Token stream produced by the lexer
[KEYWORD  "let"]
[IDENT    "x"]
[ASSIGN   "="]
[NUMBER   "42"]
[PLUS     "+"]
[IDENT    "y"]
[SEMI     ";"]

// Token regex definitions
IDENT   ::= [a-zA-Z_][a-zA-Z0-9_]*
NUMBER  ::= [0-9]+ (\.[0-9]+)?
KEYWORD ::= "let" | "if" | "while" | "return"

Regular expressions are converted to an NFA via Thompson's construction, then to a DFA via subset construction, then minimised. Tools like lex/flex automate this — you supply patterns and actions, they generate the scanner.

Syntax Analysis (Parsing)

The parser checks that the token stream conforms to the language's context-free grammar and builds a tree. A grammar is a set of production rules; a nonterminal on the left expands to a sequence of terminals and nonterminals on the right.

// Grammar for arithmetic expressions (encodes precedence + associativity)
expr   -> expr "+" term  |  expr "-" term  |  term
term   -> term "*" factor |  term "/" factor |  factor
factor -> "(" expr ")"   |  NUMBER  |  IDENT

// This grammar is LEFT-RECURSIVE (expr -> expr ...), fine for LR parsers
// but must be rewritten for LL / recursive-descent parsers:
expr   -> term expr'
expr'  -> "+" term expr'  |  "-" term expr'  |  ε
term   -> factor term'
term'  -> "*" factor term' |  "/" factor term' |  ε

Top-Down: LL Parsing

An LL(1) parser reads input Left-to-right, builds a Leftmost derivation, using 1 token of lookahead. It expands nonterminals from the top down, choosing productions using FIRST and FOLLOW sets. Recursive-descent parsers are hand-written LL parsers — one function per nonterminal.

// Recursive-descent parser for the expression grammar above
function parseExpr() {
  let node = parseTerm();
  while (peek() === "+" || peek() === "-") {
    const op = next();
    node = { type: "binop", op, left: node, right: parseTerm() };
  }
  return node;
}
function parseTerm() {
  let node = parseFactor();
  while (peek() === "*" || peek() === "/") {
    const op = next();
    node = { type: "binop", op, left: node, right: parseFactor() };
  }
  return node;
}
function parseFactor() {
  if (peek() === "(") { expect("("); const e = parseExpr(); expect(")"); return e; }
  return { type: "num", value: next() };
}

Bottom-Up: LR Parsing

An LR parser reads Left-to-right and builds a Rightmost derivation in reverse. It uses a stack and a table of shift (push next token) and reduce (replace a right-hand side on the stack with its nonterminal) actions. LR parsers handle a strictly larger class of grammars than LL — including left-recursive ones — which is why generators like yacc/bison use them.

Abstract Syntax Trees

A parse tree records every grammar rule applied, including punctuation. An AST is a condensed version that keeps only semantically meaningful structure — operators become internal nodes, operands become children. Parentheses vanish because the tree shape already encodes grouping.

// Source:  a + b * c
// AST (note * binds tighter, so it sits deeper):
//        (+)
//       /   \
//     a     (*)
//          /   \
//        b      c

{ type: "binop", op: "+",
  left:  { type: "var", name: "a" },
  right: { type: "binop", op: "*",
           left:  { type: "var", name: "b" },
           right: { type: "var", name: "c" } } }

Semantic Analysis & Symbol Tables

Syntax says a program is well-formed; semantics says it is meaningful. This phase walks the AST to check scope and types: every name must be declared before use, operators must get compatible operand types, function calls must match arity and signatures.

The symbol table maps each identifier to its attributes (type, scope level, memory offset). Nested scopes are handled with a stack of tables or a chain of scopes; entering a block pushes a new scope, leaving it pops.

// Type checking a binary expression node
function typeOf(node, scope) {
  switch (node.type) {
    case "num":  return "int";
    case "var": {
      const sym = scope.lookup(node.name);
      if (!sym) throw new SemanticError(`undeclared: ${node.name}`);
      return sym.type;
    }
    case "binop": {
      const lt = typeOf(node.left, scope);
      const rt = typeOf(node.right, scope);
      if (lt !== rt) throw new SemanticError(`type mismatch: ${lt} ${node.op} ${rt}`);
      return lt;
    }
  }
}

Intermediate Representation

The IR is a machine-independent form that is easier to optimise than an AST and easier to lower to machine code. The most common linear IR is three-address code (TAC): every instruction has at most one operator and up to three operands.

// Source:  x = a + b * c
// Three-address code (temporaries t1, t2 introduced):
t1 = b * c
t2 = a + t1
x  = t2

// Modern optimisers use SSA (Static Single Assignment): every variable
// is assigned exactly once. phi-nodes merge values from control-flow paths.
x1 = a + 1
if x1 > 10 goto L2
x2 = x1 * 2
L2:
x3 = phi(x1, x2)   // picks whichever definition reached this block

The IR is organised into basic blocks (maximal straight-line runs with one entry and one exit) connected into a control-flow graph (CFG). Most analyses and optimisations operate over the CFG.

Optimization

Optimisations rewrite the IR to run faster or use less space, while preserving observable behaviour. They range from local (within a basic block) to global (whole function, driven by data-flow analysis) to interprocedural.

// Before                      // After LICM + constant folding
for (i = 0; i < n; i++) {      t = a + b;        // hoisted, loop-invariant
  x = a + b;                    for (i = 0; i < n; i++) {
  arr[i] = x * 2;                 arr[i] = t << 1;  // strength reduction
}                              }

Code Generation

The back end lowers IR to target instructions. Three intertwined problems dominate: instruction selection (pick machine ops that implement each IR op), register allocation (map unlimited temporaries to a finite register set, spilling to memory when needed — typically via graph coloring of an interference graph), and instruction scheduling (order instructions to hide latency and keep the pipeline busy).

// TAC:  t1 = b * c ;  t2 = a + t1 ;  x = t2
// Naive x86-64 code generation (assuming a,b,c,x in memory):
mov  rax, [b]
imul rax, [c]      ; rax = b * c
add  rax, [a]      ; rax = a + (b*c)
mov  [x], rax

Practice Exercises

1. Write a lexer that tokenises arithmetic expressions with numbers, + - * /, and parentheses, applying maximal munch.
2. Extend the recursive-descent parser to produce an AST and add unary minus with correct precedence.
3. Given the left-recursive grammar for expressions, eliminate the left recursion and compute FIRST and FOLLOW sets.
4. Write an AST walker that generates three-address code with fresh temporaries for a nested expression.
5. Implement constant folding and dead code elimination as passes over a small three-address IR.
6. Convert a straight-line block with a branch into SSA form, inserting a phi-node where two definitions merge.