Compiler Design and Programming
Language Implementation
Comprehensive Table of Contents
1. Language Fundamentals and Design
2. Lexical Analysis and Tokenization
3. Syntax Analysis and Parsing
4. Semantic Analysis and Type Checking
5. Intermediate Code Generation
6. Code Optimization Techniques
7. Register Allocation and Memory Management
8. Runtime Systems and Virtual Machines
9. Just-In-Time (JIT) Compilation
10. Garbage Collection Algorithms
11. Debugging and Profiling Support
12. Modern Language Features and Implementation
Chapter 1: Language Fundamentals and Design
1.1 Language Design Decisions
Paradigms:
Imperative:
├─ Describe how to compute
├─ Statements: Assignments, loops
├─ Examples: C, Python, Java
├─ Direct execution model
Declarative:
├─ Describe what to compute
├─ Rules and constraints
├─ Examples: SQL, Prolog, Datalog
├─ Let system figure out how
Functional:
├─ Functions as first-class citizens
├─ Immutability, pure functions
├─ Examples: Haskell, Lisp, Scala
├─ Composition over mutation
Object-Oriented:
├─ Objects with state and methods
├─ Inheritance and polymorphism
├─ Examples: Java, C++, Python
├─ Encapsulation and modularity
Typing System:
Static Typing:
├─ Check types at compile-time
├─ Errors caught early
├─ Examples: Java, C++, Rust
├─ More verbose
Dynamic Typing:
├─ Check types at runtime
├─ Flexible, less verbose
├─ Examples: Python, JavaScript
├─ More runtime errors
Gradual Typing:
├─ Mix static and dynamic
├─ Optional type annotations
├─ Examples: Python (with mypy), TypeScript
├─ Best of both worlds
Type Safety:
Strongly Typed:
├─ Type errors prevented
├─ No automatic coercions
├─ Example: Java (mostly)
Weakly Typed:
├─ Implicit coercions allowed
├─ Example: JavaScript
├─ Error-prone but flexible
Memory Management:
Manual:
├─ Programmer controls allocation/deallocation
├─ Examples: C, C++
├─ Efficient but error-prone (memory leaks)
Garbage Collected:
├─ Automatic memory management
├─ Examples: Java, Python, Go
├─ Convenient but overhead
Reference Counted:
├─ Count references to object
├─ Deallocate when count = 0
├─ Examples: Python (partially), Swift
├─ Cycle detection needed
1.2 Language Specification
Abstract Syntax:
├─ Tree representation of program
├─ No syntax details (like whitespace)
├─ What matters semantically
├─ Used for analysis and compilation
Example:
Source: x = 1 + 2 AST: Assignment ├─ Variable: x └─ BinaryOp: + ├─ Literal: 1 └─
Literal: 2
Grammar:
├─ Formal rules of language
├─ Usually context-free grammar (CFG)
├─ Used for parsing
Example (simplified):
Expr → Expr + Term | Term Term → Term * Factor | Factor Factor → ( Expr ) | Number
Number → [0-9]+
Semantics:
├─ What programs mean
├─ Formal semantics: Logic, type rules
├─ Operational semantics: Step-by-step execution
├─ Denotational semantics: Mathematical meaning
Chapter 2: Lexical Analysis and Tokenization
2.1 Lexical Analysis (Lexing)
Purpose:
├─ Convert source code into tokens
├─ Ignore whitespace and comments
├─ Identify token types
Token Categories:
Keywords:
├─ Reserved words: if, while, for
├─ Language-defined meaning
├─ Cannot be used as identifiers
Identifiers:
├─ Variable, function, class names
├─ User-defined
├─ Must follow naming rules
Literals:
├─ Constants: 123, 3.14, "hello"
├─ Numbers, strings, booleans
Operators:
├─ Arithmetic: +, -, *, /
├─ Logical: &&, ||, !
├─ Assignment: =, +=, -=
Punctuation:
├─ Delimiters: {}, [], ()
├─ Separators: ;, :, .
Examples:
Source: if (x > 10) { y = x + 1; }
Tokens: [IF, LPAREN, IDENTIFIER(x), GT, NUMBER(10), RPAREN, LBRACE,
IDENTIFIER(y), ASSIGN, IDENTIFIER(x), PLUS, NUMBER(1), SEMICOLON,
RBRACE]
2.2 Regex and Finite Automata
Regular Expressions:
├─ Pattern matching language
├─ Describe token patterns
Examples:
├─ Number: [0-9]+(\.[0-9]+)?
├─ Identifier: [a-zA-Z_][a-zA-Z0-9_]*
├─ String: \"[^\"]*\"
Finite Automata:
├─ State machine recognizing strings
├─ DFA: Deterministic (one path per input)
├─ NFA: Non-deterministic (multiple paths)
Lexer Implementation:
Hand-written:
├─ Explicitly code state machine
├─ Fast, full control
├─ Error-prone, tedious
Regex-based:
├─ Describe token patterns
├─ Tool generates lexer (lex, flex)
├─ Easier to maintain
├─ Slightly less efficient
Challenges:
Maximal Munch:
├─ "if" vs "ifx"
├─ Read longest possible token
├─ Must buffer ahead
Reserved Words:
├─ "if" is keyword, not identifier
├─ Check if token is reserved
├─ Separate list of keywords
Comments:
├─ Ignored by parser
├─ Nested comments: Tricky
├─ Multi-line: Need state tracking
Chapter 3: Syntax Analysis and Parsing
3.1 Parsing Algorithms
Context-Free Grammar (CFG):
├─ Rules: A → B C | D
├─ Nonterminals: A, B
├─ Terminals: Tokens
├─ Start symbol
Parse Tree:
├─ Tree showing grammar structure
├─ Root: Start symbol
├─ Leaves: Tokens
├─ Internal nodes: Grammar rules
Abstract Syntax Tree (AST):
├─ Simplified parse tree
├─ Remove redundant nodes
├─ Keep meaningful structure
├─ Used for compilation
Parsing Strategies:
Top-Down (Recursive Descent):
├─ Start with start symbol
├─ Try to match tokens
├─ Backtrack if no match
├─ Intuitive to implement
├─ LL(1): Can look ahead 1 token
Bottom-Up (Shift-Reduce):
├─ Start with tokens
├─ Build larger trees
├─ Recognize grammar rules
├─ LR(k): More powerful
├─ Used by: LALR(1) parser generators
Predictive Parsing:
├─ No backtracking
├─ Choose rule using lookahead
├─ FIRST/FOLLOW sets
├─ Construct parsing table
Ambiguity:
├─ Grammar: Multiple parse trees
├─ Example: 1 + 2 * 3
├─ (1 + 2) * 3 vs 1 + (2 * 3)
├─ Solution: Precedence and associativity
Precedence:
├─ * higher than +
├─ Evaluated first
├─ 1 + 2 * 3 = 1 + (2 * 3)
Associativity:
├─ Left: 1 - 2 - 3 = (1 - 2) - 3
├─ Right: a = b = c = d (right)
3.2 Parser Generators
Tools:
Yacc/Bison:
├─ Input: Grammar + actions
├─ Output: C parser
├─ LALR(1) parser
├─ Industry standard
ANTLR:
├─ Input: Grammar
├─ Output: Lexer + Parser
├─ LL(*) parsing
├─ Multiple target languages
Grammar Specification:
Example (Arithmetic):
program → statement statement → assignment SEMICOLON assignment → IDENTIFIER
ASSIGN expression expression → term ((PLUS | MINUS) term) term → factor ((MUL |
DIV) factor)* factor → NUMBER | IDENTIFIER | LPAREN expression RPAREN
Actions:
├─ Semantic actions on rules
├─ Build AST nodes
├─ Evaluate expressions
├─ Type checking
Example (with actions):
expression → term ((PLUS term {push +}) | (MINUS term {push -}))*
Error Recovery:
├─ Syntax error: Expected X but got Y
├─ Panic recovery: Skip tokens until sync point
├─ Error productions: Extra grammar rules
├─ Error messages: Help user fix
Chapter 4: Semantic Analysis and Type Checking
4.1 Type Systems
Type Checking:
Static:
├─ Compile-time
├─ Example: Java, C++
├─ Errors caught early
├─ No runtime overhead
Dynamic:
├─ Runtime
├─ Example: Python, JavaScript
├─ More flexible
├─ Slower execution
Type Inference:
├─ Deduce type from context
├─ Example: x = 5 → x is int
├─ Hindley-Milner algorithm
├─ Used in: ML, Haskell, Scala
Subtyping:
├─ Cat is subtype of Animal
├─ Cat where Animal expected
├─ Liskov Substitution Principle
├─ Used in: OOP inheritance
Generic Types:
├─ Parameterized types
├─ List<T>, Dict<K, V>
├─ Code reuse
├─ Compile-time checking
Type Errors:
Assignment Type Mismatch:
├─ int x = "hello"; // ERROR
├─ Expected int, got string
Argument Type Mismatch:
├─ void foo(int x)
├─ foo("hello"); // ERROR
Return Type Mismatch:
├─ int foo() { return "hello"; } // ERROR
4.2 Symbol Tables and Scoping
Symbol Table:
├─ Maps identifiers to declarations
├─ Variables, functions, types, classes
├─ Attributes: Type, scope, address
Scoping Rules:
Global:
├─ Visible everywhere
├─ Namespace pollution risk
Local:
├─ Visible in function/block
├─ Shadowing: Inner scope hides outer
Lexical (Static) Scoping:
├─ Scope determined by code structure
├─ Look at nesting in source
├─ Most common
Dynamic Scoping:
├─ Scope determined at runtime
├─ Look at call stack
├─ Unusual, confusing
Scope Chain:
├─ Look up in current scope
├─ If not found, look in parent scope
├─ Recursive until global
├─ Stop if found
Implementation:
Hash Table:
├─ Fast lookup O(1)
├─ Easy to implement
├─ Collisions possible
Tree:
├─ Scope hierarchy
├─ Each scope: Entries + parent
Forward Declarations:
├─ Can use identifier before defined?
├─ Two-pass compiler: First pass collects declarations
├─ Used in: C requires, Python doesn't
Chapter 5: Intermediate Code Generation
5.1 Intermediate Representations (IRs)
Three-Address Code:
├─ Instruction ≤ 3 operands
├─ t = a op b
├─ Example: a = b + c * d
├─ Compiles to:
├─ t1 = c * d
├─ a = b + t1
Benefits:
├─ Machine independent
├─ Easier optimization
├─ Intermediate between source and assembly
SSA (Static Single Assignment):
├─ Each variable assigned once
├─ Makes dataflow explicit
├─ Example:
├─ x = 5
├─ if (cond) { x = 10 }
├─ y = x
├─ Becomes:
├─ x1 = 5
├─ if (cond) { x2 = 10 } else { x3 = x1 }
├─ x4 = φ(x2, x3) // merge point
├─ y = x4
Benefits:
├─ Dataflow analysis easier
├─ Optimization opportunities
├─ Used in: LLVM
Bytecode:
├─ Machine-independent instruction set
├─ Stack-based or register-based
├─ Example: Java bytecode, Python bytecode
├─ Interpreted or JIT compiled
Example (Stack-based):
Source: a = (b + c) * d
Bytecode:
LOAD b
LOAD c
ADD
LOAD d
MUL
STORE a
5.2 Code Generation Strategies
Template-based:
├─ Each AST node: Template code
├─ Plug in variables/expressions
├─ Simple but inefficient
Example:
BinaryOp(+, a, b):
LOAD a
LOAD b
ADD
Recursive Generation:
├─ Traverse AST recursively
├─ Generate code for children
├─ Combine results
├─ Natural fit with recursive descent
Function Calls:
Calling Convention:
├─ Who saves registers?
├─ How are arguments passed?
├─ Where is return value?
├─ ABI (Application Binary Interface)
cdecl (C convention):
├─ Arguments: Right to left on stack
├─ Return value: eax (x86)
├─ Caller cleans stack
stdcall (Windows):
├─ Arguments: Right to left on stack
├─ Callee cleans stack
fastcall:
├─ First args in registers
├─ Remaining on stack
├─ Faster: Fewer memory ops
Stack Frame:
High addr → ┌─ Old ebp ├─ Local variables ├─ Saved registers ├─ Arguments Low
addr → └─ Return address
Chapter 6: Code Optimization Techniques
6.1 Classic Optimizations
Constant Folding:
├─ Evaluate constant expressions
├─ x = 5 + 3 → x = 8
├─ Compile-time computation
Dead Code Elimination:
├─ Remove unused code
├─ Unreachable statements
├─ Unused variables
Common Subexpression Elimination (CSE):
├─ a = b * c
├─ d = b * c
├─ Becomes:
├─ temp = b * c
├─ a = temp
├─ d = temp
Loop Optimization:
Loop Invariant Code Motion:
├─ Move constant computation outside loop
├─ for (i=0; i<n; i++) { x = a[0] + i }
├─ Becomes: t = a[0]; for (...) { x = t + i }
Loop Strength Reduction:
├─ Replace expensive operation
├─ for (i=0; i<n; i++) { x = i * 4 }
├─ Becomes: for (i=0; i<n*4; i+=4) { x = i }
Inlining:
├─ Copy function body at call site
├─ Eliminate function call overhead
├─ Trade-off: Code size
├─ Used for: Small functions, hot code
Register Allocation:
├─ Assign variables to registers
├─ Fast access
├─ Limited registers (typically 8-16)
├─ NP-complete problem!
6.2 Advanced Optimizations
Data Flow Analysis:
├─ Track values through program
├─ Reaching definitions: Which assignments reach this point?
├─ Live variables: Which variables used later?
├─ Use for: Optimization decisions
SSA-Based Optimizations:
├─ Sparse conditional constant propagation
├─ Dead code elimination
├─ Value numbering
├─ Better than traditional
Speculative Optimization:
├─ Assume common case
├─ Add guards for exceptions
├─ Optimize based on assumption
├─ Example: Assume object type (inline virtual call)
Just-In-Time Compilation:
├─ Compile at runtime
├─ Profile: Which functions hot?
├─ Compile hot functions
├─ Optimize for actual execution patterns
├─ Can outperform static compilation!
Chapters 7-12 (Abbreviated)
[Continued with Register Allocation, Runtime Systems, JIT Compilation, Garbage
Collection, Debugging Support, and Modern Language Features - full content would follow
same detailed pattern]
Conclusion
Compiler design combines theory (formal languages, automata) with practice (optimization,
code generation). Modern compilers like LLVM have revolutionized language
implementation.
Key takeaways: - Lexing: Regex to tokens - Parsing: Tokens to AST - Semantic analysis:
Type checking, symbol resolution - Intermediate code: Machine-independent representation
- Optimization: Improve performance significantly - Code generation: AST to machine code
- JIT: Runtime compilation for optimization - Garbage collection: Automatic memory
management - Profiling: Identify bottlenecks - Continuous evolution: New language
features require new techniques
Compiler design is both challenging and rewarding, blending theory and practice.