Compiler Design Cheatsheet

REFERENCE v1.0

Compiler Design Quick Reference

Everything you need day‑to‑day – phases, parsing, and code generation.

What is a Compiler?

A compiler translates source code written in a high‑level programming language into target code (machine code / assembly) while reporting errors and optimising the output.

Phases of a Compiler

1. Lexical Analysis (Scanner)

Reads source code character by character
Produces tokens (keywords, identifiers, literals, operators)
Removes whitespace and comments
Uses regular expressions
Output: token stream

2. Syntax Analysis (Parser)

Checks syntax using grammar
Builds Abstract Syntax Tree (AST) or Parse Tree
Reports syntax errors
Uses context‑free grammars (CFG)
Output: parse tree / AST

3. Semantic Analysis

Checks semantic correctness
Type checking
Symbol table management
Scope resolution
Output: annotated AST

4. Intermediate Code Generation

Converts AST to intermediate representation (IR)
Three‑address code (TAC), quadruples, triples
Abstract syntax tree to IR
Machine‑independent
Output: intermediate code

5. Code Optimisation

Improves performance and efficiency
Peephole optimisation
Loop optimisation
Dead code elimination
Output: optimised intermediate code

6. Code Generation

Translates IR to target machine code
Register allocation and instruction selection
Generates assembly or object code
Output: target code

Symbol Table

Stores information about identifiers
Name, type, scope, memory location
Used by all phases
Implemented as hash table, BST, or linked list

Lexical Analysis

Tokens, Patterns, Lexemes

Token: category (KEYWORD, IDENTIFIER, NUMBER)
Pattern: regular expression defining token
Lexeme: actual character sequence

Regular Expressions

c – character c
| – alternation (A | B)
· – concatenation (A · B)
* – Kleene star (zero or more)
+ – one or more
? – zero or one
[...] – character class
^ – complement

Examples

[a‑z] – any lowercase letter
[0‑9]+ – one or more digits
[a‑zA‑Z][a‑zA‑Z0‑9]* – identifier
0|1|2|...|9 – digit
(\+|\-)?[0‑9]*\.?[0‑9]+ – floating point

Finite Automata

NFA – Nondeterministic Finite Automaton (multiple transitions)
DFA – Deterministic Finite Automaton (single transition)
DFA is faster to simulate, NFA is easier to construct
Thompson's construction – RE → NFA
Subset construction – NFA → DFA
DFA minimisation – merge equivalent states
Lex / Flex – tools for lexical analysis

Syntax Analysis (Parsing)

Context‑Free Grammar (CFG)

// Grammar components
G = (N, T, P, S)
N – non‑terminals
T – terminals
P – production rules
S – start symbol

// Example: Expression grammar
E → E + T | T
T → T * F | F
F → (E) | id

Types of Parsers

Top‑Down Parsers

Start from start symbol
Derive using productions
LL(k) – Left‑to‑right, Leftmost derivation, k lookahead
Recursive Descent
Predictive (LL(1))
No left recursion, left factoring needed

Bottom‑Up Parsers

Start from input string
Reduce to start symbol
LR(k) – Left‑to‑right, Rightmost derivation, k lookahead
SLR, CLR, LALR
More powerful than LL
LR(0), SLR(1), LALR(1), LR(1)

Eliminating Left Recursion

A → A α | β
// Convert to
A → β A'
A' → α A' | ε

Left Factoring

A → α β1 | α β2
// Convert to
A → α A'
A' → β1 | β2

LL(1) Parsing (Table‑Driven)

Uses FIRST and FOLLOW sets
Predictive parsing table
FIRST(A) – terminals that can start strings derived from A
FOLLOW(A) – terminals that can follow A
LL(1) grammar – no conflicts in parsing table

LR Parsing

LR(0) – simplest, limited
SLR(1) – Simple LR, uses FOLLOW sets
CLR(1) – Canonical LR, most powerful
LALR(1) – Lookahead LR, practical
YACC / Bison – tools for parser generation

Semantic Analysis

Type Checking

Static – compile time (C, Java)
Dynamic – run time (Python, JS)
Strong – strict type rules
Weak – implicit conversions
Type compatibility – equality, coercion
Type conversion – widening, narrowing

Scope

Global – accessible everywhere
Local – function / block scope
Static – lexical scope (compile time)
Dynamic – runtime scope (rare)
Nested scopes – inner hides outer

Intermediate Code Generation

Three‑Address Code (TAC)

// Statements
x = y op z          // Binary operation
x = op y            // Unary operation
x = y               // Assignment
goto L              // Jump
if x relop y goto L // Conditional jump
param x             // Function argument
call p, n           // Function call
return x            // Return

// Example: a = b + c * d
t1 = c * d
t2 = b + t1
a = t2

Representations

Quadruples – (op, arg1, arg2, result)
Triples – (op, arg1, arg2) – implicit result
Indirect Triples – list of pointers to triples
Static Single Assignment (SSA) – each variable assigned once

Code Optimisation

Machine‑Independent

Constant folding – compile‑time evaluation
Constant propagation – replace with constants
Dead code elimination – remove unused code
Common subexpression elimination – reuse computed value
Loop optimisation – hoisting, unrolling
Strength reduction – x*2 → x+x
Inlining – replace function call with body
Tail recursion optimisation – convert to loop

Machine‑Dependent

Register allocation – minimise memory access
Instruction selection – choose fastest instruction
Peephole optimisation – local instruction improvement
Pipeline optimisation – reduce stalls
Cache optimisation – improve cache locality

Register Allocation

Graph Colouring – greedy, heuristic
Chaitin's algorithm – build interference graph
Live variable analysis – determine active variables
Spilling – store to memory when registers full
Linear scan – fast, used in JIT compilers

Syntax Directed Translation

SDD (Syntax Directed Definition) – grammar with semantic rules
SDT (Syntax Directed Translation) – grammar with embedded actions
Inherited attributes – passed from parent to child
Synthesised attributes – computed from children
L‑attributed – left‑to‑right traversal
S‑attributed – synthesised only (post‑order)

Error Handling

Lexical Errors

Invalid characters
Unterminated strings
Panic mode – skip to next token

Syntactic Errors

Unexpected tokens
Missing tokens
Panic mode – synchronise token
Phrase‑level recovery – insert/delete tokens
Error productions – include common errors
Global correction – minimum changes

Semantic Errors

Type mismatches
Undeclared identifiers
Scope violations
Report with line numbers

Error Recovery

Skip to synchronisation token
Insert missing tokens
Continue parsing
Restart from a safe point

Compiler Tools

Lexical Analysis

Lex / Flex – generate tokeniser
RE2C – generate DFA
JFlex – Java version

Parsing

YACC / Bison – LALR(1) parser
ANTLR – ALL(*) parser (LL)
JavaCC – Java compiler compiler
LLVM – compiler framework (IR, optimisation)

Common Terms

Token – lexical unit (keyword, identifier)
Lexeme – actual sequence of characters
Production – grammar rule
Derivation – sequence of productions
Parse Tree – derivation tree
Ambiguity – multiple parse trees
Sentinel – end marker ($)

Handle – right‑hand side of production
Item – grammar rule with dot position
Kernel Item – initial item
Closure – set of items reachable via ε
GOTO – transition function for LR
LALR – Lookahead LR
DAG – Directed Acyclic Graph (for expressions)

📌 Quick Reference

Compiler phases: Lexical → Syntax → Semantic → Intermediate → Optimisation → Code Gen
Parsing: LL (Top‑down) vs LR (Bottom‑up)
Grammar types: LL(1), SLR(1), LALR(1), LR(1)
Symbol Table: scope, type, location
IR: Three‑Address Code (TAC), Quadruples, SSA
Optimisation: Constant folding, dead code elimination, loop unrolling, register allocation

← Back to All Cheatsheets