Compilers and Formal Languages
From regular expressions to code generation — understanding the soul of programming languages.
Prerequisites
Requires systems fundamentals (Vol 3), familiarity with C and basic data structures.
Completion marker: Understand the Chomsky hierarchy, DFA/NFA, CFG, Turing machines; able to implement lexical/parser generators; understand the code generation pipeline.
Part 1: Formal Language Theory
Chapter 1 — Formal Languages and Automata Overview Complete
The four levels of the Chomsky hierarchy, grammar definitions, language as sets of strings.
Chapter 2 — DFA/NFA and Regular Languages Complete
State diagrams, subset construction, Thompson's construction.
Chapter 3 — Context-Free Grammars and Pushdown Automata Complete
Derivation trees, ambiguity elimination, PDA stack matching, LL/LR.
Chapter 4 — Turing Machines and Computability Complete
The seven elements of a TM, the halting problem, reduction, P/NP intuition.
Part 2: Compiler Implementation
Chapter 5 — Lexical Analysis Complete
Hand-written C state machines, longest match, flex rules, lexer-parser collaboration.
Chapter 6 — Parsing and AST Complete
Recursive descent in C, CST vs AST, LL vs LR.
Chapter 7 — Semantic Analysis and Intermediate Representation Complete
Symbol tables, type checking, three-address code, SSA.
Chapter 8 — Code Generation and Optimization Complete
Constant folding/CSE, graph-coloring register allocation, loop optimization, JIT.
This volume has 8 chapters, all complete