Programming a basic Lisp interpreter in Python.

aka Some Strategies For Fast Lexical Analysis when Parsing Programming Languages, by Sean Barrett

Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.

"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."

"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."

Details the Recursive Descent, Shunting Yard and Precedence Climbing parsing algorithms.

"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

"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."

A series of articles delving into Linux executables and the ELF format, showing how to create your own executables by hand.

Why build a language? How does one create a programming language? This blog post is a good overview to start answering these questions.

Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.

"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."

"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."

"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

Learn C and build a LISP interpretter using a parser combinator library written by the author

Classic text on building a compiler by Niklaus Wirth

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."

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

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.

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."

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

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

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."

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

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

"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