Programming Language Implementation: A Practical Introduction with Python

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