A handrolled language parser

In my previous post about building a custom lexer I mentioned that, for educational purposes, I created a simple toy programming language (still unnamed). There, I talked about building a tokenizer and lexer from scratch. In this post I’ll discuss building a parser that is responsible for generating an abstract syntax tree (AST) for my language. This syntax tree can then be passed to other language components such as a scope and type resolver, and finally an interpreter.

The parser I made is a recursive descent packrat parser that uses backtracking. Short of memoizing found AST, there aren’t any other real optimizations. The goal was to create a working parser, not a production parser to distribute or use (or reuse) in any professional sense. Like the lexer, this is an academic exercise to try and hit on some of the points covered by Terence Parr’s Language Implementation Patterns book that … Read more

, , , , ,

Tracing computation expressions

This article was originally published at

F# has a novel syntax feature called computation expressions, which lets you build complex monadic expressions with minimal syntax. Commonly shied away from, a monad is simple: it’s a function whose input is some state. A monad usually manipulates the state and returns a new state (which can be handed off to another monad).

Monad’s are maybe best known from Haskell, but they exist in scheme, ML, clojure, scala, and even show up in C# and other imperative languages.

While the computation expression syntax is cool, short of the maybe monad, and the baked-in async keyword, I wasn’t sure what I could do with this. Thankfully, I found an interesting post by Luis Diego Fallas who posted an F# code sample leveraging computation expressions to read binary formatted files. However, if you are like me, and trying to better understand … Read more