Table of Contents

1. Introduction
   1. Compiler and Runtime System Project
   2. Why Compiler or Runtime System Design?
   3. Overall Learning Goals
   4. Getting Started
2. Overview
   1. General Architectures
   2. Compiler Structure
   3. Runtime System Structure
3. Programming Language
   1. Language Specification
   2. Syntax Specification
   3. Extended Backus-Naur Form
   4. EBNF for Arithmetic Expressions
   5. Problematic Syntax
   6. Special EBNF Features
   7. Other Syntax Notations
   8. Syntax Summary
   9. Semantic Specification
   10. Our Programming Language J0
   11. Project Instructions
4. Lexer
   1. Task of a Lexer
   2. Tokens
   3. Regular Languages
   4. An Excursion in Language Theory
   5. Lexing Based on Finite Automaton
   6. Maximum Munch
   7. White Spaces
   8. Comments
   9. Token Representation
   10. The Lexer Implementation
   11. Scanning Integers
   12. Handling the Minimum Integer Literal
   13. Scanning Identifiers and Keywords
   14. Skipping Comments
   15. Scanning String Literals
   16. Error Handling
   17. Lexer Generators
   18. Project Instructions
5. Parser
   1. Context-Free Languages
   2. Task of a Parser
   3. Parse Tree
   4. Abstract Syntax Tree
   5. Parsing Strategies
   6. Recursive Descent Parser
   7. The Parser Implementation
   8. Predictive Direct Parsing
   9. The Lexer Implementation
   10. Parser Classification
   11. Parser Generators
   12. Abstract Syntax Tree Design
   13. Syntax Tree Construction
   14. Syntax Error Handling
   15. Undetected Errors in the Parser
   16. Syntax-Directed Translation
   17. Powerfulness of LR-Parsers
   18. Building an SLR-Parser
   19. Bottom-Up Parsing
       1. Adjusted Grammar
       2. State Machine
       3. Constructing the Parsing Table
       4. Running the Bottom-Up Parser
   20. Project Instructions
6. Semantic Checker
   1. Task of a Semantic Checker
   2. Symbol Table
   3. Shadowing
   4. Local Variable Scopes
   5. Symbol Table Design
   6. Predefined Declarations
   7. Semantic Checker Resolution
   8. Symbol Table Construction
   9. Type Resolution in Symbol Table
   10. Name Resolution
   11. Designator Resolution in the AST
   12. Type Resolution in AST
   13. Visitor-Based Type Resolution
   14. Semantic Checks
   15. Checking Declarations
   16. Method Calls
   17. Type Checking
   18. Reserved Type and Constant Names
   19. Unique Declarations
   20. Dynamic Rules
   21. Intermediate Representation
   22. Project Instructions
7. Code Generator
   1. Compiler Frontend and Backend
   2. Task of Code Generator
   3. Targeting a Virtual Machine
   4. Stack Processor
   5. Instruction Set
   6. Control Flow
   7. Metadata
   8. Bytecode Generation
   9. Bytecode Assembler
   10. Template-Based Code Generation
   11. Translating Structured Statements
   12. Code-Generation Implementation
   13. Conditional Evaluation
   14. Method Calls
   15. Potential Optimizations
   16. Project Instructions
8. Code Optimization
   1. Task of an Optimizer
   2. Arithmetic Optimization
   3. Algebraic Simplification
   4. Moving Loop-Invariant Code
   5. Common Subexpression Elimination
   6. Dead Code Elimination
   7. Copy Propagation
   8. Constant Propagation
   9. Partial Redundancy Elimination
   10. Optimization Techniques
   11. Static Single Assignment
   12. Peephole Optimization
   13. Dataflow Analysis
       1. Control Flow Graph
       2. Dataflow Computation
       3. Application to Constant Propagation
       4. Backwards Analysis
       5. Dataflow Analysis Classification
   14. Summary
   15. Project Instructions
9. Virtual Machine & Interpretation
   1. Virtual Machine
   2. Virtual Machine Design
   3. Loader
   4. Verifier
   5. Descriptors
   6. Code Patching
   7. VM Implementation
   8. Interpreter
   9. Procedural Support
   10. Managed Call Stack
   11. Unmanaged Call Stack
   12. Runtime Structures
   13. Security and Safety Measures
   14. Interpretation versus Compilation
   15. Project Instructions
10. Object-Oriented Runtime Support
    1. Compiler Support for Objects
    2. Out-Of-Scope Features
    3. Heap Management
    4. Object References
    5. Native Memory Access
    6. Object Layout
    7. Object-Specific Interpretation
    8. Array Support
    9. Simple Heap Design
    10. Upcoming Object-Oriented Support
    11. Project Instructions
11. Inheritance and Type Polymorphism
    1. Single Inheritance
    2. Code Reuse
    3. Type Polymorphism
    4. Efficient Type Tests and Casts
    5. Ancestor Tables
    6. Virtual Method Calls
    7. Virtual Tables
    8. Interface Polymorphism
    9. Multi-Inheritance
    10. Project Instructions
12. Garbage Collection
    1. Explicit Deallocation
    2. Dangling Pointer
    3. Memory Leak
    4. Definition of Garbage
    5. Reference Counting
    6. Garbage Collector
    7. Transitive Reachability
    8. Root Set
    9. Mark & Sweep Algorithm
    10. GC Implementation
    11. GC Trigger
    12. Stop-And-Go GC
    13. Root Set Collection
    14. Mark Flag
    15. Block Pointer Offsets
    16. GC Memory Footprint
    17. Free List
    18. Segregated Free Lists
    19. External Fragmentation
    20. Compacting GC
    21. Finalizers
    22. Resurrection
    23. Finalizer Implementation
    24. Finalizer Problems
    25. Weak References
    26. Incremental Garbage Collection
    27. Generational GC
    28. Partitioned GC
    29. Garbage Collection in C++?
    30. Project Instructions
13. Just-In-Time Compiler
    1. Task of the JIT-Compiler
    2. Hot Spots
    3. Profiling
    4. Intel 64 Architecture
    5. Instruction Set
    6. Cross-Compilation
    7. Template-Based Code Generation
    8. Register Allocation
    9. Local Register Allocation
    10. Register Clobbering
    11. Branch Instructions
    12. Global Register Allocation
    13. JIT-Compiler Implementation
    14. Allocation Consistency on Branches
    15. Register Pressure
    16. Optimal Global Register Allocation
    17. Assembler and Linker
    18. Native Stack Management
    19. Native Code Execution
    20. Other JIT-Compiler Aspects
    21. Project Instructions
14. Conclusion
    1. Out-of-Scope Topics
    2. Review of the Learning Goals
    3. Final Remark

• Appendix A: J0 Language Specification
• Appendix B: J0 Bytecode Specification
• Appendix C: AntLR 4 Grammar for J0
• Bibliography
• Index