As I mentioned in an [earlier post]({% post_url 2017-08-16-tapl %}), I’ve been working through Types and Programming Languages in Rust. Chapters 5 to 7 of TAPL discuss untyped lambda calculus through an implementation of a simple expression-based language. Chapter 5 lays the foundations; chapter 6 focuses more on one of the concepts introduced in chapter 5; de Bruijn index and chapter 7 explores an ML implementation of the said language, but only how to evaluate the terms, and not how to parse them. The accompanying OCaml implementation’s parser is generated automatically from a Yacc grammar.

I’ve had good experiences writting parsers in Haskell using parsec and attoparsec before, so I started looking for parser-combinators in Rust. There seem to be three capable options:

Combine even has the combine-language extension which is very similar to Parsec’s Text.Parsec.Token which would’ve simplified the task of parsing lexical elements but I couldn’t add it as a dependency to my project—due to compile errors which I’m sure has been because of my ignorance and lack of familiarity with Rust and Cargo. At the end I ended up choosing using layman’s metrics, number of GitHub stars and nom won by a huge margin.