Skip to content
Tutorials Center
My learning

Topics

Lesson 61 of 61 ยท Practice and Review

Compiler Design Cheat Sheet

A one-page compiler design cheat sheet: phases, grammar classes, parser comparison, FIRST/FOLLOW rules, optimizations and handy formulas with examples.

This page is a quick reference for the whole track. It does not teach anything new. It collects the facts you look up again and again: what each phase does, which grammar class needs which machine, how the parsers compare, which optimizations exist, and the counting formulas that show up in exams and design discussions. Each row links to the lesson that explains it properly.

Use it as a map. If a line feels unfamiliar, follow the link, then come back. For practice, the exercises and interview questions use the same vocabulary.

The pipeline at a glance

flowchart LR
    S["Source text"] --> L["Lexer"]
    L -->|"tokens"| P["Parser"]
    P -->|"AST"| M["Semantic analysis"]
    M -->|"typed AST"| I["IR generation"]
    I -->|"three-address code"| O["Optimizer"]
    O -->|"better IR"| G["Code generator"]
    G --> T["Target code"]

Front end (lexer to semantic analysis), middle end (IR and optimizer), back end (code generator). The symbol table and error reporter serve every stage.

Phase Input Output Typical tool or technique Lesson
Lexical analysis characters tokens regex, DFA Writing a lexer
Syntax analysis tokens parse tree or AST recursive descent, LL(1), LR, Pratt Recursive descent
Semantic analysis AST annotated AST, symbol table scope chains, type rules, unification Type checking
IR generation annotated AST three-address code, bytecode tree walk with temporaries and labels Three-address code
Optimization IR smaller or faster IR CFG, data-flow analysis, SSA Local optimizations
Code generation IR assembly or machine code instruction selection, register allocation Code generation

Lexical analysis rules

  • A token is a (type, lexeme, position) triple. A lexeme is the matched text. A pattern is the rule, usually a regular expression.
  • Longest match wins: <= is one token, not < then =.
  • Priority breaks ties between equal-length matches: list keywords before identifiers.
  • Whitespace and comments are matched and thrown away.
  • Regex to scanner: regex, then NFA (Thompson), then DFA (subset construction), then minimized DFA. See from regex to DFA.
  • On a bad character, report the position, skip it (panic mode) and keep scanning. See lexical errors.

Grammar classes (Chomsky hierarchy)

Type Name Production shape Recognized by Compiler use
3 Regular A -> a or A -> aB (right-linear) finite automaton tokens
2 Context-free A -> ฮฑ (one nonterminal on the left) pushdown automaton syntax
1 Context-sensitive ฮฑAฮฒ -> ฮฑฮณฮฒ, ฮณ not empty linear-bounded automaton rarely used directly
0 Unrestricted ฮฑ -> ฮฒ Turing machine none

Every regular language is context-free, every context-free language is context-sensitive, and so on. Checks such as "variable declared before use" or "types match" are not context-free, which is why semantic analysis is a separate phase using a symbol table.

Grammar vocabulary

  • Derivation: leftmost replaces the leftmost nonterminal each step, rightmost the rightmost one.
  • Ambiguous grammar: some string has two parse trees (or two leftmost derivations). Fix it by layering rules for precedence. See ambiguity.
  • Left recursion A -> A ฮฑ | ฮฒ becomes A -> ฮฒ A2 and A2 -> ฮฑ A2 | ฮต. See grammar transformations.
  • Left factoring A -> ฮฑ ฮฒ1 | ฮฑ ฮฒ2 becomes A -> ฮฑ A2 and A2 -> ฮฒ1 | ฮฒ2.

FIRST, FOLLOW and the LL(1) test

Set Rule
nullable(X) X has an ฮต production, or a production whose symbols are all nullable
FIRST(X) terminals that can start a string derived from X; walk the right-hand side and continue past nullable symbols
FOLLOW(S) contains $ for the start symbol S
FOLLOW(B) for A -> ฮฑ B ฮฒ add FIRST(ฮฒ) without ฮต; if ฮฒ can vanish, add FOLLOW(A)
FOLLOW(B) for A -> ฮฑ B add FOLLOW(A)

A grammar is LL(1) when, for every nonterminal A with alternatives ฮฑ | ฮฒ: FIRST(ฮฑ) and FIRST(ฮฒ) are disjoint, at most one alternative is nullable, and if ฮฒ is nullable then FIRST(ฮฑ) and FOLLOW(A) are disjoint. See FIRST and FOLLOW and LL(1) parsing.

Parser comparison

Parser Direction Derivation traced Lookahead Handles left recursion Power Typical use
Recursive descent top-down leftmost any, by hand no (rewrite or loop) hand-tuned most production compilers
LL(1) table top-down leftmost 1 token no smallest class teaching, simple formats
Pratt / precedence climbing top-down leftmost 1 token yes, for operators expressions only operator-heavy languages
LR(0) bottom-up rightmost in reverse 0 yes weakest LR teaching
SLR(1) bottom-up rightmost in reverse 1, uses FOLLOW yes stronger than LR(0) teaching, small tools
LALR(1) bottom-up rightmost in reverse 1, merged states yes between SLR and LR(1) Yacc and Bison
Canonical LR(1) bottom-up rightmost in reverse 1, full context yes strongest rarely, tables are large

Power order for grammars: LR(0) โŠ‚ SLR(1) โŠ‚ LALR(1) โŠ‚ LR(1), and LL(1) โŠ‚ LR(1). LR(1) parses every deterministic context-free language. See bottom-up parsing and LR parsing.

Conflicts

  • Shift/reduce: the table has both a shift and a reduce in one cell. Often caused by an ambiguous grammar such as the dangling else.
  • Reduce/reduce: two different reductions are possible. Usually a real grammar bug.
  • LALR(1) merging can create reduce/reduce conflicts that canonical LR(1) does not have, but never new shift/reduce conflicts.

Semantic analysis

  • Synthesized attribute: computed from children (bottom-up). Inherited attribute: computed from parent or siblings.
  • S-attributed: synthesized only. L-attributed: inherited attributes depend only on the parent and left siblings. See syntax-directed translation.
  • Static scoping: a name is resolved by where it is written. Dynamic scoping: by the call chain at runtime.
  • Unification makes two types equal by binding type variables, with an occurs check to reject infinite types. See type inference.

Intermediate code and optimization

Optimization Scope Example
Constant folding local 2 * 3 becomes 6
Algebraic simplification local x + 0 becomes x
Strength reduction local or loop x * 2 becomes x + x or x << 1
Common subexpression elimination local or global reuse a + b computed earlier
Copy propagation local or global after t = x, use x instead of t
Dead code elimination local or global drop an assignment whose result is never read
Peephole optimization local replace short instruction windows with cheaper ones
Loop-invariant code motion loop hoist n * 4 out of the loop
Induction variable elimination loop replace i * 4 with a pointer that adds 4
Loop unrolling loop repeat the body to cut branches
Inlining global replace a call by the function body
Tail-call elimination global turn return f(x) into a jump

Details are in local optimizations and loop and global optimizations.

Data-flow analyses

Analysis Direction Meet operator Question answered
Reaching definitions forward union which assignments may reach this point?
Available expressions forward intersection which expressions are already computed on every path?
Live variables backward union may this value still be read later?
Very busy expressions backward intersection which expressions are computed on every path from here?

Equations: OUT[B] = gen[B] โˆช (IN[B] โˆ’ kill[B]) for forward problems. Live variables use IN[B] = use[B] โˆช (OUT[B] โˆ’ def[B]). Solve with a worklist until nothing changes. See data-flow analysis.

CFG and SSA

  • Leaders: the first instruction, every jump target, and every instruction right after a jump. A basic block runs from a leader up to the next leader.
  • Node d dominates n if every path from the entry to n passes through d.
  • SSA: every variable is assigned once. A phi function at a join picks the value by incoming edge. Phi nodes go at the dominance frontier of each definition. See SSA.

Code generation and runtime

  • Activation record: return address, saved registers, parameters, locals, temporaries, access or control links.
  • Register allocation by graph coloring: build an interference graph, color it with k colors, spill a node when no color is free. Linear scan sorts live intervals and is faster but less precise.
  • Garbage collection: reference counting (cannot free cycles), mark-and-sweep (pauses, fragmentation), copying (halves usable memory, compacts). See garbage collection.
  • Execution models: interpreter (slowest start-up cost, simplest), bytecode VM, JIT (compiles hot code at runtime), AOT (all code before running). See JIT and interpreters.

Formulas worth memorizing

Fact Formula
Thompson NFA for a regex with n symbols and operators at most 2n states
NFA with n states to DFA at most 2^n states
LR(0) items for production A -> X1 ... Xk k + 1 items (k = 0 gives one item, A -> .)
Total LR(0) items of a grammar sum of (k + 1) over all productions
Parse trees of n binary operators with no precedence Catalan number C(n) = (2n)! / ((n+1)! n!)
Tokens in a lexer match the longest prefix that any pattern accepts
Basic blocks in straight-line code with j jumps at most 2j + 1
Cost of LL(1) and LR parsing linear, O(n) in the number of tokens
Cost of the general CYK algorithm O(n^3)
Registers needed chromatic number of the interference graph

Try it: classify grammar productions

The classifier below follows the table in the Chomsky section. Capital letters are nonterminals, everything else is a terminal, and a grammar belongs to the loosest class any of its productions needs. Right-linear regular grammars only.

Python Which Chomsky type is this grammar?

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Try it: the counting formulas

These are the formulas from the table, as small functions you can call with your own numbers. The Catalan number is also the answer to "how many ways can you parenthesize n + 1 operands", which is why an ambiguous grammar explodes quickly.

Python Formula calculator

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Quick decisions

  • Writing a small language by hand? Use a hand-written lexer and a recursive descent parser, with Pratt parsing for expressions.
  • Need a grammar-driven tool? Use a parser generator (ANTLR for LL(*), Bison for LALR). See parser generators.
  • Need good error messages? Hand-written parsers give you the most control. See error recovery.
  • Targeting a fast runtime without writing assembly? Emit bytecode and write a VM, or emit an existing IR such as LLVM IR.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which parser family traces a rightmost derivation in reverse?

    Bottom-up LR parsers shift tokens and reduce handles, which reconstructs a rightmost derivation backwards. Recursive descent, LL(1) and Pratt parsers are top-down and follow a leftmost derivation.
  2. 2. In which direction does live-variable analysis flow, and which meet operator does it use?

    A value is live if some later path may read it, so information flows backward from uses, and paths are combined with union (a single path is enough).
  3. 3. How many LR(0) items does the production A -> B c d have?

    A body of k symbols has k + 1 items, one for each position of the dot. Here k is 3, so there are 4 items.
  4. 4. Which statement about grammar power is correct?

    The classes nest as LR(0) within SLR(1) within LALR(1) within LR(1). The reverse directions fail, and an LL(1) grammar is LR(1) but not necessarily LR(0).

Summary

  • The pipeline is lexer, parser, semantic analysis, IR, optimizer, code generator, with a symbol table and error reporting shared by all.
  • Tokens are regular, syntax is context-free, and meaning (types, scopes) needs a separate semantic pass.
  • Top-down parsers need non-left-recursive, left-factored grammars; LR parsers handle more grammars but are usually generated.
  • Grammar power: LR(0) < SLR(1) < LALR(1) < LR(1), and LL(1) sits inside LR(1).
  • Data-flow problems differ by direction and meet operator; solve them with a worklist to a fixed point.
  • Keep the counting formulas handy: 2n Thompson states, 2^n DFA states, k + 1 LR(0) items per production, Catalan numbers for ambiguity.

That is the end of the track. Test yourself once more with the interview questions.