Building Programming Languages with Rust

From Lexers to LLVM: A Complete Guide to Language Implementation

Introduction: The Language Builder’s Journey

1. Why Build a Language?
2. Why Rust?
3. What Is Rune?
4. How This Book Is Structured
5. What You Need to Know
6. How to Use the Code
7. A Note on Scope
8. The Journey Ahead

Chapter 1: Why Build a Language? The Landscape and the Vision

1. What Is a Programming Language, Really?
2. The Rust Advantage for Language Implementation
3. Survey of Existing Languages Built in Rust
4. Designing Rune: Goals and Non-Goals
5. Project Structure and Tooling Setup
6. Chapter Summary
7. Exercises

Chapter 2: Language Design Fundamentals

1. Syntax Philosophy: Minimalism Versus Expressiveness
2. Core Semantic Model
3. Type System Design Choices
4. Memory and Ownership Semantics
5. The Standard Library Blueprint
6. Chapter Summary
7. Exercises

Chapter 3: Formal Grammars and Lexical Analysis

1. Regular Expressions and Token Definitions
2. Building the Lexer: State Machine Approach
3. Error Recovery in Lexing
4. Unicode and Source Encoding
5. Lexer Benchmarks and Optimization
6. Chapter Summary
7. Exercises

Chapter 4: Recursive Descent Parsing

1. Context-Free Grammars and Parse Trees
2. AST Node Design in Rust
3. Writing the Parser
4. Expression Parsing and Operator Precedence
5. Error Reporting with Source Spans
6. Chapter Summary
7. Exercises

Chapter 5: Advanced Parsing – Pratt Parsers and Parser Generators

1. The Pratt Parser Algorithm
2. Integrating Pratt Parsing into Rune
3. Parser Generators in Rust: LALRPOP Deep Dive
4. Nom and Combinator-Based Parsing
5. Choosing Your Parser Strategy
6. Chapter Summary
7. Exercises

Chapter 6: Abstract Syntax Trees and Tree Transformations

1. Arena Allocation for AST Nodes
2. Desugaring Passes
3. Tree-Walking Patterns
4. Source Maps and Debug Information
5. AST Serialization and Caching
6. Chapter Summary
7. Exercises

Chapter 7: Semantic Analysis and Symbol Tables

1. Scope Chains and Symbol Resolution
2. Building the Symbol Table
3. Name Mangling and Uniqueness
4. Semantic Error Detection
5. Cross-Module Name Resolution
6. Chapter Summary
7. Exercises

Chapter 8: Type Systems and Type Checking

1. Type Representation in Rust
2. The Type Checker Architecture
3. Type Inference with Unification
4. Generics and Monomorphization
5. Trait Resolution and Dispatch
6. Chapter Summary
7. Exercises

Chapter 9: Error Reporting and Recovery

1. The Anatomy of a Good Error Message
2. Building the Diagnostics Engine
3. Parse Recovery Strategies
4. Type Error Messages That Help
5. Error Collection and Summarization
6. Chapter Summary
7. Exercises

Chapter 10: The Interpreter

1. Evaluation Semantics
2. Environment and Closure Implementation
3. Built-in Functions and Foreign Function Interface
4. Garbage Collection for the Interpreter
5. REPL Implementation
6. Chapter Summary
7. Exercises

Chapter 11: Bytecode Virtual Machine

1. Instruction Set Architecture Design
2. Rune’s Instruction Set
3. Code Generation from AST to Bytecode
4. The VM Execution Engine
5. Performance: Bytecode vs Tree Walking
6. Chapter Summary
7. Exercises

Chapter 12: Native Code Generation with LLVM

1. LLVM Architecture Overview
2. Inkwell: The Rust LLVM Binding
3. Codegen for Expressions and Statements
4. Optimization Passes
5. Linking and Runtime Support
6. Chapter Summary
7. Exercises

Chapter 13: Memory Management Strategies

1. Manual Memory Management Model
2. Tracing Garbage Collection in Rust
3. Region-Based Memory Management
4. Ownership and Borrowing for Scripting Languages
5. Memory Profiling and Debugging
6. Chapter Summary
7. Exercises

Chapter 14: Optimization Techniques

1. Peephole Optimizations
2. Data Flow Analysis
3. Loop Optimizations
4. Inline Caching and Monomorphization
5. Profiling-Guided Optimization
6. Chapter Summary
7. Exercises

Chapter 15: Concurrency Model

1. Threads vs Green Threads vs Actors
2. Rune’s Concurrency Primitives
3. Implementing Async/Await
4. Shared-State Concurrency
5. Parallel Compilation
6. Chapter Summary
7. Exercises

Chapter 16: Modules, Packages, and the Standard Library

1. Module System Design
2. Package Manager Architecture
3. Building the Standard Library
4. Foreign Function Interface
5. Documentation System
6. Chapter Summary
7. Exercises

Chapter 17: Macros and Metaprogramming

1. Macro Design Philosophy
2. Token-Based Macros
3. Hygienic Macro Implementation
4. Compile-Time Evaluation
5. Macro Debugging and Error Reporting
6. Chapter Summary
7. Exercises

Chapter 18: Tooling – Formatter, Linter, and Language Server

1. Automatic Code Formatting
2. Static Analysis Linter
3. Language Server Protocol Implementation
4. Debugger Architecture
5. IDE Integration
6. Chapter Summary
7. Exercises

Chapter 19: Testing, Benchmarking, and Quality Assurance

1. Test Infrastructure
2. Property-Based Testing for Compilers
3. Fuzzing the Parser and VM
4. Performance Benchmarking
5. Continuous Integration Pipeline
6. Chapter Summary
7. Exercises

Chapter 20: Packaging, Distribution, and Maintenance

1. Cross-Platform Compilation
2. Installer and Package Distribution
3. Documentation Strategy
4. Semantic Versioning for Languages
5. Community and Ecosystem Building
6. Chapter Summary

Conclusion: The Language Builder’s Path Forward

References

Glossary

Appendix A: Complete Cargo Workspace Configuration

Appendix B: Rune Language Specification Summary

Appendix C: Building and Running Rune