Writing an Interpreter in Go

 Acknowledgments....5

Introduction....6

The Monkey Programming Language & Interpreter....7

Why Go?....9

How to Use this Book....10

Lexing....11

1.1 - Lexical Analysis....11

1.2 - Defining Our Tokens....12

1.3 - The Lexer....14

1.4 - Extending our Token Set and Lexer....22

1.5 - Start of a REPL....27

Parsing....30

2.1 - Parsers....30

2.2 - Why not a parser generator?....32

2.3 - Writing a Parser for the Monkey Programming Language....33

2.4 - Parser's first steps: parsing let statements....34

2.5 - Parsing Return Statements....46

2.6 - Parsing Expressions....48

Expressions in Monkey....49

Top Down Operator Precedence (or: Pratt Parsing)....50

Terminology....50

Preparing the AST....51

Implementing the Pratt Parser....54

Identifiers....55

Integer Literals....58

Prefix Operators....61

Infix Operators....65

2.7 - How Pratt Parsing Works....71

2.8 - Extending the Parser....79

Boolean Literals....81

Grouped Expressions....84

If Expressions....86

Function Literals....91

Call Expressions....95

Removing TODOs....99

2.9 - Read-Parse-Print-Loop....102

Evaluation....105

3.1 - Giving Meaning to Symbols....105

3.2 - Strategies of Evaluation....106

3.3 - A Tree-Walking Interpreter....107

3.4 - Representing Objects....108

Foundation of our Object System....110

Integers....110

Booleans....111

Null....111

3.5 - Evaluating Expressions....112

Integer Literals....113

Completing the REPL....115

Boolean Literals....116

Null....118

Prefix Expressions....118

Infix Expressions....122

3.6 - Conditionals....127

3.7 - Return Statements....129

3.8 - Abort! Abort! There's been a mistake!, or: Error Handling....133

3.9 - Bindings & The Environment....138

3.10 - Functions & Function Calls....142

3.11 - Who's taking the trash out?....152

Extending the Interpreter....154

4.1 - Data Types & Functions....154

4.2 - Strings....154

Supporting Strings in our Lexer....155

Parsing Strings....157

Evaluating Strings....158

String Concatenation....160

4.3 - Built-in Functions....162

len....162

4.4 - Array....166

Supporting Arrays in our Lexer....167

Parsing Array Literals....168

Parsing Index Operator Expressions....171

Evaluating Array Literals....174

Evaluating Index Operator Expressions....176

Adding Built-in Functions for Arrays....179

Test-Driving Arrays....182

4.5 - Hashes....183

Lexing Hash Literals....184

Parsing Hash Literals....186

Hashing Objects....190

Evaluating Hash Literals....194

Evaluating Index Expressions With Hashes....197

4.6 - The Grand Finale....200

Resources....202

Feedback....204

Changelog....205

In this book we will create a programming language together. We'll start with 0 lines of code and end up with a fully working interpreter for the Monkey programming language.

Step by step. From tokens to output. All code shown and included. Fully tested.

Buy this book to learn:

• How to build an interpreter for a C-like programming language from scratch
• What a lexer, a parser and an Abstract Syntax Tree (AST) are and how to build your own
• What closures are and how and why they work
• What the Pratt parsing technique and a recursive descent parser is
• What others talk about when they talk about built-in data structures
• What REPL stands for and how to build one

Why this book?

This is the book I wanted to have a year ago. This is the book I couldn't find. I wrote this book for you and me. So why should you buy it? What's different about it, compared to other interpreter or compiler literature?

• Working code is the focus. Code is not just found in the appendix. Code is the main focus of this book.
• It's small! It has around 200 pages of which a great deal are readable, syntax-highlighted, working code.
• The code presented in the book is easy to understand, easy to extend, easy to maintain.
• No 3rd party libraries! You're not left wondering: "But how does tool X do that?" We won't use a tool X. We only use the Go standard library and write everything ourselves.
• Tests! The interpreter we build in the book is fully tested! Sometimes in TDD style, sometimes with the tests written after. You can easily run the tests to experiment with the interpreter and make changes.

This book is for you if you...

• learn by building, love to look under the hood
• love programming and to program for the sake of learning and joy!
• are interested in how your favorite, interpreted programming language works
• never took a compiler course in college
• want to get started with interpreters or compilers…
• ... but don't want to work through a theory-heavy, 800 pages, 4 pounds compiler book as a beginner
• kept screaming "show me the code!" when reading about interpreters and compilers
• always wanted to say: "Holy shit, I built a programming language!"