Compilers Cheatsheet

── The pipeline ─────────────────────────
text -> LEXER -> tokens
     -> PARSER -> AST (tree = precedence & structure)
     -> SEMANTIC -> names resolved, types checked
     -> IR -> OPTIMIZER -> better IR
     -> CODEGEN -> assembly / bytecode / other language

front end understands source; back end emits target
LLVM: shared back end (Rust, Swift, Clang all use it)

── Vocabulary decoder ───────────────────
token         a "word": NUMBER(42), IDENT(x), PLUS
AST           tree of the program's structure
symbol table  stack of scopes: name -> declaration
type checking do these types allow this operation?
  static = at compile time | dynamic = at runtime
IR            simplified middle language (e.g. SSA form)
transpiler    compiler targeting a high-level language
JIT           compile at runtime, guided by profiling
linker        stitches .o files, resolves symbols
ABI           binary-level calling conventions

── Error messages, decoded ──────────────
"unexpected character"    lexer choked
"unexpected token"        parser: legal word, wrong place
"undefined variable"      name resolution failed
"type mismatch"           type checker said no
"undefined reference"     LINKER: no definition anywhere
"duplicate symbol"        linker found two

── Optimizations (what -O2 does) ────────
constant folding      3*60 -> 180 at compile time
constant propagation  x=5; y=x+1 -> y=6
dead code elimination unreachable/unused -> gone
inlining              call -> pasted body (enables more)
CSE                   compute repeated expr once
loop hoisting         invariant work out of loops
strength reduction    i*2 -> i<<1
unrolling             fewer branches, more straight line
vectorization         SIMD: 8 adds per instruction
as-if rule: anything goes if behavior looks unchanged
UB warning (C/C++): compiler assumes UB never happens
  -> may delete your overflow checks

── JIT tiers (V8, JVM) ──────────────────
interpret -> profile -> compile hot code specialized
to observed types -> guards -> deoptimize if wrong
lesson: consistent types = code stays fast

── Experiments to run ───────────────────
godbolt.org                    # any language -> assembly
gcc -E file.c                  # preprocessor only
gcc -S -O2 file.c              # emit assembly
gcc -c file.c && nm file.o     # symbols: T defined, U needed
objdump -d ./binary            # disassemble
python3 -c "import dis; dis.dis(lambda x: x*2)"  # bytecode
node --print-bytecode app.js   # V8's bytecode

── Build one yourself ───────────────────
lexer: loop chars, group into tokens        (~40 lines)
parser: recursive descent, fn per rule      (~60 lines)
eval: walk the tree                         (~10 lines)
then read: Crafting Interpreters (free online)