academic-compilers-language-processors

# Compiler Engineering and Language Processors (Dragon Book) This skill establishes the complete architecture of pipelines that translate high-level source code into intermediate representations and optimized machine code, covering the lexical/syntactic front end, semantic analysis, the SSA middle end, and the back end for code generation and register allocation. --- ## 🔄 1. Complete Compilation Pipeline ```mermaid flowchart LR A["Source Code"] --> B["Lexical Analysis (Scanner / Flex)"] B -->|Tokens| C["Syntax Analysis (Parser / Bison)"] C -->|AST| D["Semantic Analysis (Type Checker)"] D -->|Decorated AST| E["Intermediate Code Generation"] E -->|LLVM IR / SSA| F["Code Optimizer (LLVM Opt Passes)"] F -->|Optimized IR| G["Register Allocation & Code Generation"] G --> H["Object Code / Native Assembly (x86_64 / ARM / RISC-V)"] ``` --- ## 🔡 2. Lexical Analysis: From Regular Expressions to Finite Automata ### 2.1 Thompson Construction (Regex $\to$ NFA-$\varepsilon$) Converts regular operators ($a|b$, $ab$, $a^*$) into non-deterministic finite automata with $\varepsilon$-transitions linear in the size of the expression. ### 2.2 Subset Construction Algorithm (NFA $\to$ DFA) - **$\varepsilon$-closure ($\varepsilon\text{-closure}(S)$)**: The set of states reachable from $S$ by empty $\varepsilon$-transitions only. - **Transition $\delta_{DFA}(T, a) = \varepsilon\text{-closure}(\text{move}(T, a))$**: Maps DFA states to disjoint sets of NFA states. - **DFA Minimization (Hopcroft's Algorithm)**: Partitions states into distinguishable equivalences with complexity $\mathcal{O}(k |S| \log |S|)$. --- ## 🌲 3. Syntax Analysis: Formal Grammars and Top-Down / Bottom-Up Parsers ### 3.1 FIRST and FOLLOW Sets Given a grammar $G = (V, \Sigma, R, S)$: - $\text{FIRST}(\alpha)$: The set of terminals that begin strings derived from $\alpha$. - $\text{FOLLOW}(A)$: The set of terminals that can appear immediately to the right of the variable $A$ in some sentential form derived from the root $S$. ### 3.2 LL(1) vs LR(1) / LALR(1) Parsing Table | Parser Family | Direction and Derivation | Common Conflicts | Expressive Power | | :--- | :--- | :--- | :--- | | **LL(1) (Top-Down)** | Left-to-right, Leftmost Derivation | FIRST/FIRST and FIRST/FOLLOW conflicts (requires left factoring and elimination of left recursion). | Lowest (does not handle direct left recursion). | | **LR(0) / SLR(1)** | Left-to-right, Reverse Rightmost Derivation (*Shift-Reduce*) | Shift-Reduce and Reduce-Reduce conflicts when FOLLOW does not discriminate the state. | Intermediate. | | **LR(1)** | Shift-Reduce with canonical 1-symbol lookahead | State explosion in the canonical table. | Maximum for deterministic context-free grammars. | | **LALR(1) (Bison/Yacc)** | Merges LR(1) states with the same *core* | May introduce Reduce-Reduce conflicts, but preserves SLR(1) compactness. | Industry standard for production compilers. | --- ## 🏷️ 4. Semantic Analysis and Type Checking - **Symbol Tables in a Stack of Lexical Scopes**: Support for shadowing, closures, and identifier resolution by block lifetime (`Scope::enter()`, `Scope::exit()`). - **Type System and Hindley-Milner Inference (Algorithm W)**: Type unification via substitutions of type variables with cycle detection (*occurs check*). --- ## ⚡ 5. Middle-End: Static Single Assignment (SSA Form) and Cytron In SSA form, each variable is assigned exactly once, and $\phi$ functions (*phi-nodes*) are inserted at dominance frontiers: ### 5.1 Dominance Tree and Dominance Frontier ($DF$) - A node $d$ dominates $n$ ($d \, \text{dom} \, n$) if every path from the entry node to $n$ passes through $d$. - The dominance frontier $DF(X)$ contains nodes $Y$ where $X$ dominates a predecessor of $Y$, but $X$ does not strictly dominate $Y$. - **Cytron Algorithm**: $\phi$-nodes for the variable $v$ are inserted at the transitive closure of the dominance frontiers of the blocks containing assignments to $v$: $$DF^+(Def(v))$$ ```llvm ; LLVM IR representation in canonical SSA define i32 @fatorial(i32 %n) { entry: %cmp = icmp sle i32 %n, 1 br i1 %cmp, label %base, label %recurse base: br label %exit recurse: %n.sub = sub nsw i32 %n, 1 %call = call i32 @fatorial(i32 %n.sub) %res.rec = mul nsw i32 %n, %call br label %exit exit: %retval = phi i32 [ 1, %base ], [ %res.rec, %recurse ] ret i32 %retval } ``` --- ## 🚀 6. Code Optimizations and Back-End ### 6.1 Catalog of SSA Optimizations (LLVM Passes) 1. **Mem2Reg**: Promotes stack allocations (`alloca`) to pure SSA registers via dominance analysis. 2. **GVN (Global Value Numbering) & CSE**: Identifies and eliminates equivalent redundant computations through value numbers. 3. **LICM (Loop Invariant Code Motion)**: Moves loop-independent instructions to the pre-header. 4. **DCE (Dead Code Elimination)**: A backward sweep that eliminates instructions whose results are not read by any live instruction. 5. **Function Inlining**: Replaces direct calls with the expanded function body when the heuristic cost outweighs the call overhead. ### 6.2 Graph-Coloring Register Allocation (Chaitin-Briggs) - **Interference Graph**: Vertices are temporary variables; edges connect temporaries that are simultaneously live (overlapping *live ranges*). - **Coloring Algorithm with $K$ Registers**: 1. **Simplify**: Remove nodes with degree $< K$ and push them onto a stack. 2. **Spill**: If all nodes have degree $\ge K$, choose a spill candidate based on memory cost / loop nesting. 3. **Select**: Pop the nodes and assign physical registers of a compatible color with no collisions with neighbors. --- ## 🧮 7. Thinking Low-Level: HLL Constructs to Machine Code (Hyde) - **Thesis:** write high-level code by mentally simulating the assembly it will produce, and verify by reading compiler output — never trust marketing claims about optimizer quality. After any "optimization" edit, regenerate compiler output and diff it; measure the machine code. - **Compiler pipeline:** lexical scan → parse (AST) → intermediate code → optimization → code generation; interpreters, compilers and JITs move translation cost to different times and open different optimization windows. Optimization is NP-complete, so production optimizers are heuristic and budgeted; JITs must optimize in milliseconds, which is why ahead-of-time languages typically peak higher. - **Basic blocks + data-flow analysis** let the compiler prove value ranges, constant states, liveness and deadness — ambiguity in the source bounds what the analysis can conclude. - **Optimization catalog:** constant folding/propagation, dead-code elimination, common-subexpression elimination, strength reduction (shift/AND for multiply/divide/modulo), induction-variable elimination, loop-invariant code motion. Know the optimization flags: most compilers optimize nothing by default; flags trade speed, space and target CPU. - **Binding time is the real constant question:** language-definition, compile, link, load or run time; manifest constants cost nothing at runtime. - **Object files and layout:** sections, relocation records, symbol tables; section alignment causes internal fragmentation — a space vs load-efficiency trade-off. Tooling: assembly output, dumpbin/objdump, javap/ILDasm for bytecode, and before/after assembly diffing as the micro-benchmark method. - **Representation cost model:** declare wider locals before narrower ones to get alignment without padding waste; power-of-two element sizes make scaled-index array access nearly free; string format choice (zero-terminated vs length-prefixed vs descriptor) drives the cost of every string operation; virtual dispatch adds a vtable pointer per object and an indirect call per method. - **Semantics that are not optimizations:** short-circuit versus complete boolean evaluation changes correctness (null-guard idioms break under complete evaluation) and skips side effects; switch statement structure (dense case ranges) determines whether the compiler can emit a jump table; undefined evaluation order is a correctness trap.