Programming Language Implementation: A Practical Introduction with Python
Author: Lutz Hamel
Copyright: 2024
Binding: Paperback
Page Count: 408
Security policy
Delivery policy
Return policy
The approach to implementing programming languages has shifted noticeably over the past two decades. The success of Java, with its virtual-machine approach, has paved the way for alternative methods of implementing mainstream languages, diverging from traditional machine-language targeted compilation. Since then, many successful modern programming languages such as JavaScript, Ruby, and Python have offered alternative implementation techniques such as incremental interpreters, virtual machines, and just-in-time compilers.
The rise of domain-specific languages, sometimes called “little languages,” has likewise been influenced and supported by this shift. Domain-specific languages can solve problems in specific problem areas within their specialized domains, unlike general-purpose languages such as Python or C++, which solve problems in a wide spectrum of domains.
In this book we explore the various techniques and perspectives brought about by this shift in programming language implementation. We particularly focus on domain-specific languages, which rarely use full-blown compilers for implementation in favor of an interpretation or virtual-machine approach.
-
- A “from day one” approach gets students started with implementing programming languages right away.
- Small, realistic languages are used to cover interpretation, virtual machines, and compilers.
- Implementation is “from scratch,” so all steps are transparent and accessible to the student.
TABLE OF CONTENTS
Chapter 1: Programming Languages and their Processors
1.1 Language Classifications
1.2 The Structure of Programming Languages
1.3 The Behavior of Programming Languages
1.4 Language Processors
1.4.1 Building Blocks
1.4.2 Architectures
1.4.3 Processing Java
Chapter 2: Parsing and Lexing
2.1 Grammars
2.1.1 The Basics
2.1.2 Derivations
2.1.3 Parse Trees
2.2 Our Exp0 Language
2.3 Parsers
2.3.1 Top-Down Parsing
2.3.2 Building Recursive Descent Parsers
2.3.3 A Recursive Descent Parser for Exp0
2.3.4 Recursive Descent Parsers Are LL(1)
2.3.5 Lookahead Sets
2.3.6 Not All Grammars are LL(1)
2.4 Our First Language Processor Based on Exp0
2.5 Lexical Analysis
2.5.1 Lexical Analysis by Example: The calc Language
2.5.2 Regular Expressions
Chapter 3: Syntax-Directed Processing
3.1 What is Syntax-Directed Interpretation?
3.2 The Exp1 Language
3.3 A Syntax-Directed Interpreter for Exp1
3.3.1 The Parser
3.3.2 Extending the Parser for Interpretation
3.3.3 Testing the Interpreter
3.4 Another Take on Syntax-Directed Processing: A Pretty Printer for Exp1
3.4.1 Extending the Parser with Formatting Code
3.4.2 Testing the Pretty Printer
Chapter 4: Interpretation with Intermediate Representations
4.1 Limits of Syntax-Directed Interpretation
4.1.1 Introducing the Exp1bytecode Language
4.1.2 Syntax-Directed Interpretation Fails!
4.2 Decoupling Syntax Analysis and Semantic Processing
4.2.1 The Exp1bytecode Abstract Machine
4.3 Implementing Exp1Bytecode
4.3.1 The Abstract Machine State
4.3.2 The Front End
4.3.3 The Instruction Interpreter
4.3.4 Putting It All Together
Chapter 5: Tree-Based Intermediate Representations
5.1 Abstract Syntax Trees
5.1.1 The Tuple Representation of Abstract Syntax Trees
5.2 The Cuppa1 Programming Language
5.2.1 Eliminating Left-Recursion
5.2.2 Embedding Operator Precedence
5.3 A Cuppa1 Front End
5.3.1 Statements
5.3.2 Statement Lists
5.3.3 Expressions
5.3.4 Generating ASTs
5.4 Tree Walking
5.4.1 A Simple Tree Walker
5.4.2 Tree Walkers are Plug ’n’ Play
5.5 An Interpreter for Cuppa1
5.5.1 The Tree Walker
5.5.2 The Top-Level Driver Function
5.5.3 Running the Interpreter
5.6 A Cuppa1 Pretty Printer with a Twist
5.6.1 Architecture of the Pretty Printer
5.6.2 Testing the Pretty Printer
Chapter 6: Compilers
6.1 A Basic Compiler
6.1.1 Architecture of the Basic Compiler
6.1.2 The Code Generation Tree Walker
6.1.3 Formatting the Output
6.1.4 Running the Compiler
6.2 Compiler Correctness
6.3 Optimization
6.3.1 Constant Folding
6.3.2 Peephole Optimization
6.4 An Optimizing Compiler for Cuppa1
Chapter 7: Symbol Tables and Scope
7.1 The Cuppa2 Language
7.2 A Symbol Table for Supporting Scope
7.2.1 Symbol Table Design
7.3 A Cuppa2 Interpreter
7.3.1 Test Driving the Interpreter
7.4 Syntactic vs. Semantic Errors
7.5 Compiling Scoped Code
7.6 A Cuppa2 Compiler
7.6.1 The Symbol Table and Front End
7.6.2 The Code Generator
7.6.3 Testing the Compiler
Chapter 8: Functions
8.1 A Closer Look at Functions
8.1.1 Argument Correspondence
8.1.2 Argument Value Transmission
8.2 The Cuppa3 Language
8.2.1 Grammar Design
8.2.2 Cuppa3 Programs
8.2.3 Function-Local Scope
8.2.4 Static vs. Dynamic Scoping
8.3 A Cuppa3 Interpreter
8.3.1 Front End
8.3.2 Symbol Table
8.3.3 Tree Walker
8.3.4 Driver Function
8.3.5 Testing the Interpreter
Chapter 9: Function Calls on Real and Virtual Machines
9.1 Exp2bytecode: A Virtual Machine with Function Calls
9.1.1 Grammar Design and Front End
9.1.2 The Virtual Machine
9.1.3 Running the Machine
9.2 A Cuppa3 Compiler
9.2.1 Compiling Global Code
9.2.2 Compiling Functions
9.2.3 Compiler Architecture and Implementation
9.2.4 Testing the Compiler
9.3 Function Calls on Real Machines
Chapter 10: Compiling for Real Machines
10.1 Real Machines
10.2 Our Runtime System: TinyRTS
10.3 The Cuppa3/x86_64 Compiler
10.3.1 Generating x86_64 Instructions
10.4 Generating the Data Segment
10.5 Putting it All Together
Chapter 11: Type Systems
11.1 A Brief Introduction to Types
11.1.1 Subtypes
11.1.2 Type Coercion
11.1.3 Type Equivalence
11.1.4 Polymorphism
11.2 Type Checking with Type Propagation
11.2.1 A Closer Look at Type Propagation
11.3 The Cuppa4 Language
11.4 A Cuppa4 Interpreter with Static Type Checking
11.4.1 Front End
11.4.2 Type Checker
11.4.3 Interpreter
11.4.4 Exercising the Interpreter
11.5 Notes on Static Type Checking and Compilation
Chapter 12: Structured Data Types
12.1 The Syntax and Semantics of Arrays
12.2 The Cuppa5 Language and Its Interpreter
12.2.1 The Cuppa5 Front End
12.2.2 Type Checking
12.2.3 Interpretation
12.2.4 Test Drive
12.3 Notes on Compiling Arrays
Chapter 13: Parser Generators
13.1 Bottom-Up Parsing
13.2 PLY—Python Lex and Yacc
13.2.1 The Parser Specification
13.2.2 The Lexer Specification
13.2.3 Running the Parser
13.2.4 Adding Actions
13.3 A Cuppa1 Interpreter Using Yacc and Lex
13.4 Parser Conflicts
13.4.1 Shift/Reduce Conflicts
13.4.2 Reduce/Reduce Conflicts
Chapter 14: LLVM: A Compiler Back-End Framework
14.1 LLVM Architecture and IR
14.2 An LLVM-Based Cuppa1 Compiler
14.2.1 Generating LLVM IR
14.2.2 Generating Target Code from an LLVM IR Module
14.2.3 Running the Compiler
Appendix: An Ontology of Our Languages
Bibliography
Index