The Lisp book introduces two languages with the expression formats - the language itself, comprised of symbolic expressions, and a meta language employing meta expressions. My plan is to implement both languages and bootstrap the whole thing from the definitions in the meta language on page 13.
I stay with the book structure, which follows the definition of Atoms with one for Symbolic Expressions, or S-Exps or sexps - the famous Lisp grammar with all the parenthesis. However, first I need to finish some tests for the atoms - I committed (and cpublished the previous article ;-)), but the book had more examples and one of the idea is to have all the examples from the book be used as test input. So, quickly add some testcases:
Everything green, so work on symbolic expressions can start. First, make sure that atoms can be parsed.
(To make it easier to connect book and test code, I am quoting from the book before I write a test. Yes, I’m tempted to go all-out literal programming here, but typing in the whole thing would slow me down too much :-))
The test runs green with a very simple parser:
and replacing the AST with:
On to the meat - we need to parse a sexp. The simplest test (again, from the book), looks like:
and in order to satisfy it, the parser is extended:
This compiles when we create a case class to hold S-expressions, giving:
The recursive parser definition is powerful enough to parse the other book examples, so just adding them completes the basic S-exp parser:
It’s fun to look back at the full parser definition at this point:
Just two lines of code implement a working Lisp parser!
The next installment will start with the meta language by implementing the basic function for constructing lists.
this article discusses this version of the code