Register
handmade.network Library

Compilers & Interpreters

On writing program languages.

Article

  • (How to Write a (Lisp) Interpreter (in Python)) by Peter Norvig
    ★ 0 0
    Programming a basic Lisp interpreter in Python.
  • Avoiding branchy loops in lexers with FSMs
    ★ 0 0
    aka Some Strategies For Fast Lexical Analysis when Parsing Programming Languages, by Sean Barrett
  • Eli Bendersky: A Recursive Descent Parser with an Infix Operator
    ★ 0 0
    Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
  • Eli Bendersky: Parsing Expressions by Precedence Climbing
    ★ 0 0
    "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
    ★ 0 0
    "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
    ★ 0 0
    Details the Recursive Descent, Shunting Yard and Precedence Climbing parsing algorithms.
  • How to Write a Lisp Interpreter in JavaScript by Mary Rose Cook
    ★ 0 0
    "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
    ★ 0 0
    "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?
    ★ 0 0
    A series of articles delving into Linux executables and the ELF format, showing how to create your own executables by hand.

Blog

  • Eli Bendersky: A Recursive Descent Parser with an Infix Operator
    ★ 0 0
    Details how to add a shunting yard parser into a recursive descent parser. Examples in Python.
  • Eli Bendersky: Parsing Expressions by Precedence Climbing
    ★ 0 0
    "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
    ★ 0 0
    "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
    ★ 0 0
    "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
    ★ 1 0
    Learn C and build a LISP interpretter using a parser combinator library written by the author
  • Compiler Construction
    ★ 0 0
    Classic text on building a compiler by Niklaus Wirth
  • Programming Languages: Application and Interpretation by Shriram Krishnamurthi
    ★ 0 0
    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
    ★ 0 0
    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
    ★ 1 0
    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
    ★ 0 0
    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
    ★ 0 0
    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)
    ★ 0 0
    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
    ★ 0 0
    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
    ★ 0 0
    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)
    ★ 0 0
    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
    ★ 0 0
    "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