Building a Parser

Neat article.

If you’re interested in more material, there is also Ruslan’s phenomenal 17 part series that walks thru how to build an interpreter.

https://ruslanspivak.com/lsbasi-part1/

I ran into “Make Your Own Lisp Interpreter in 10 Steps”[0] recently, and I’ve enjoyed walking through it. It works through a basic repl to macros, tail recursion, and finally self hosting! (I haven’t made it that far yet)

The guide [1] has been interesting to follow, and I appreciate the author’s approach to building a Lisp interpreter as a way to pick up a new language. For example, his interpreter, mal, has implementations in every thing from ada, nasm, and bash, to C, Ruby, rust, python and everything between.

Videos walking through the guide are available too [2], [3]

[0] https://github.com/kanaka/mal

[1] https://github.com/kanaka/mal/blob/master/process/guide.md

[2] https://www.youtube.com/watch?v=jVhupfthTEk

[3] https://www.youtube.com/watch?v=X5OQBMGpaTU

Shameless plug: Awhile back I did a couple blog posts on recursive descent parsing, working from recognizing balanced parentheses all the way to building a parser generator and using it to implement a simple programming language.

The first of the pair is at:

https://reindeereffect.github.io/2018/12/08/recursive-descen...

Some readers might be interested in “parsing with derivatives” and a recent generalization by Conal Elliot (references in there): http://conal.net/papers/convolution/

This paper is somewhat abstract/mathematical, but the earlier papers should be more concrete. Lots of blog posts too, if you search for the phrase.

I've written a number of parsers in my time. Eventually, I got tired of writing them by hand (and debugging them!) and switched to Bison. Nowadays I just use Ragel [1] because it's lightning fast and supports a lot of languages.

[1] https://en.wikipedia.org/wiki/Ragel

I wrote a JSON parser in Elixir for fun. [1] If you've never written a parser, I recommend giving it a go!

[1] https://hexdocs.pm/json_momoa/JSONMomoa.html