handmade.network Library
Compilers & Interpreters
On writing program languages.
Article
-
(How to Write a (Lisp) Interpreter (in Python)) by Peter Norvig
Programming a basic Lisp interpreter in Python.
-
Avoiding branchy loops in lexers with FSMs
aka Some Strategies For Fast Lexical Analysis when Parsing Programming Languages, by Sean Barrett
-
Eli Bendersky: A Recursive Descent Parser with an Infix Operator
Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
-
Eli Bendersky: Parsing Expressions by Precedence Climbing
"It's not necessary to be familiar with the other algorithms for expression parsing in order to understand precedence climbing. In fact, I think that precedence climbing is the simplest of them all. To explain it, I want to first present what the algorithm is trying to achieve. After this, I will explain how it does this, and finally will present a fully functional implementation in Python."
-
Eli Bendersky: Top-Down Operator Precedence Parsing
"The third article describes a method that combines RD [recursive descent] parsing with a different algorithm for parsing expressions to achieve better results. This method is actually used in the real-world, for example in GCC and Parrot (source). An alternative parsing algorithm was discovered by Vaughan Pratt in 1973. Called Top Down Operator Precedence, it shares some features with the modified RD parser, but promises to simplify the code, as well as provide better performance."
-
Expression Parsing
Details the Recursive Descent, Shunting Yard and Precedence Climbing parsing algorithms.
-
How to Write a Lisp Interpreter in JavaScript by Mary Rose Cook
"Little Lisp is an interpreter that supports function invocation, lambdas, lets, ifs, numbers, strings, a few library functions, and lists. I wrote it for a lightning talk at the Recurse Center to show how easy it is to write an interpreter. The code is 116 lines of JavaScript. I will explain how it works."
There is also a video version of this article: https://youtu.be/hqnTvuvXPCc
Article Series
-
My First Language Frontend with LLVM Tutorial
"Requirements: This tutorial assumes you know C++, but no previous compiler experience is necessary. [...] Here we run through the implementation of a simple language [...]This tutorial will get you up and running fast and show a concrete example of something that uses LLVM to generate code."
-
What's in a Linux executable?
A series of articles delving into Linux executables and the ELF format, showing how to create your own executables by hand.
Blog
-
Build your own programming language
Why build a language? How does one create a programming language? This blog post is a good overview to start answering these questions.
-
Eli Bendersky: A Recursive Descent Parser with an Infix Operator
Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
-
Eli Bendersky: Parsing Expressions by Precedence Climbing
"It's not necessary to be familiar with the other algorithms for expression parsing in order to understand precedence climbing. In fact, I think that precedence climbing is the simplest of them all. To explain it, I want to first present what the algorithm is trying to achieve. After this, I will explain how it does this, and finally will present a fully functional implementation in Python."
-
Eli Bendersky: Top-Down Operator Precedence Parsing
"The third article describes a method that combines RD [recursive descent] parsing with a different algorithm for parsing expressions to achieve better results. This method is actually used in the real-world, for example in GCC and Parrot (source). An alternative parsing algorithm was discovered by Vaughan Pratt in 1973. Called Top Down Operator Precedence, it shares some features with the modified RD parser, but promises to simplify the code, as well as provide better performance."
-
How to Write a Lisp Interpreter in JavaScript by Mary Rose Cook
"Little Lisp is an interpreter that supports function invocation, lambdas, lets, ifs, numbers, strings, a few library functions, and lists. I wrote it for a lightning talk at the Recurse Center to show how easy it is to write an interpreter. The code is 116 lines of JavaScript. I will explain how it works."
There is also a video version of this article: https://youtu.be/hqnTvuvXPCc
Book
-
Build Your Own Lisp
Learn C and build a LISP interpretter using a parser combinator library written by the author
-
Compiler Construction
Classic text on building a compiler by Niklaus Wirth
-
Programming Languages: Application and Interpretation by Shriram Krishnamurthi
Abstract: "Programming language ‘‘paradigms’’ are a moribund and tedious legacy of a bygone age. Modern language designers pay them no respect, so why do our courses slavishly adhere to them? This paper argues that we should abandon this method of teaching languages, offers an alternative, reconciles an important split in programming language education, and describes a textbook that explores these matters."
-
Programming and Programming Languages
From the introduction:
"Many people would regard this as being two books in one. One book is an introduction to programming, teaching you basic concepts of organizing data and the programs that operate over them, ending in the investigation of universally useful algorithms. The other book is an introduction to programming languages: a study, from one level up, of the media by which we structure these data and programs. Obviously, these are not unrelated topics. We learn programming through one or more languages, and the programs we write then become natural subjects of study to understand languages at large. Nevertheless, these are considered sufficiently different topics that they are approached separately. This is how we approached them, too."
by Shriram Krishnamurthi, Benjamin S. Lerner, Joe Gibbs Politz
Online Book
-
Crafting Interpreters
This book contains everything you need to implement a full-featured, efficient scripting language. You’ll learn both high-level concepts around parsing and semantics and gritty details like bytecode representation and garbage collection.
-
Programming Languages: Application and Interpretation by Shriram Krishnamurthi
Abstract: "Programming language ‘‘paradigms’’ are a moribund and tedious legacy of a bygone age. Modern language designers pay them no respect, so why do our courses slavishly adhere to them? This paper argues that we should abandon this method of teaching languages, offers an alternative, reconciles an important split in programming language education, and describes a textbook that explores these matters."
-
Programming and Programming Languages
From the introduction:
"Many people would regard this as being two books in one. One book is an introduction to programming, teaching you basic concepts of organizing data and the programs that operate over them, ending in the investigation of universally useful algorithms. The other book is an introduction to programming languages: a study, from one level up, of the media by which we structure these data and programs. Obviously, these are not unrelated topics. We learn programming through one or more languages, and the programs we write then become natural subjects of study to understand languages at large. Nevertheless, these are considered sufficiently different topics that they are approached separately. This is how we approached them, too."
by Shriram Krishnamurthi, Benjamin S. Lerner, Joe Gibbs Politz
Repository
-
Doug Crockford - Top Down Operator Precedence (aka Pratt Parsing)
In this Youtube video, the "top down operator precedence" method of parsing is discussed. In a nutshell, TDOP, also known as "Pratt parsing" is sort of like a combination of precedence climbing parsers and recursive descent parsers. Notably TDOP does not use a grammar, which makes it somewhat unique among other parser techniques. A working example by the author can be found here: https://github.com/douglascrockford/TDOP
Website
-
Programming Languages: Application and Interpretation by Shriram Krishnamurthi
Abstract: "Programming language ‘‘paradigms’’ are a moribund and tedious legacy of a bygone age. Modern language designers pay them no respect, so why do our courses slavishly adhere to them? This paper argues that we should abandon this method of teaching languages, offers an alternative, reconciles an important split in programming language education, and describes a textbook that explores these matters."
-
Programming and Programming Languages
From the introduction:
"Many people would regard this as being two books in one. One book is an introduction to programming, teaching you basic concepts of organizing data and the programs that operate over them, ending in the investigation of universally useful algorithms. The other book is an introduction to programming languages: a study, from one level up, of the media by which we structure these data and programs. Obviously, these are not unrelated topics. We learn programming through one or more languages, and the programs we write then become natural subjects of study to understand languages at large. Nevertheless, these are considered sufficiently different topics that they are approached separately. This is how we approached them, too."
by Shriram Krishnamurthi, Benjamin S. Lerner, Joe Gibbs Politz
YouTube Video
-
Doug Crockford - Top Down Operator Precedence (aka Pratt Parsing)
In this Youtube video, the "top down operator precedence" method of parsing is discussed. In a nutshell, TDOP, also known as "Pratt parsing" is sort of like a combination of precedence climbing parsers and recursive descent parsers. Notably TDOP does not use a grammar, which makes it somewhat unique among other parser techniques. A working example by the author can be found here: https://github.com/douglascrockford/TDOP
-
How to Write a Lisp Interpreter in JavaScript by Mary Rose Cook
"Little Lisp is an interpreter that supports function invocation, lambdas, lets, ifs, numbers, strings, a few library functions, and lists. I wrote it for a lightning talk at the Recurse Center to show how easy it is to write an interpreter. The code is 116 lines of JavaScript. I will explain how it works."
There is also a video version of this article: https://youtu.be/hqnTvuvXPCc