As a first step in attempting to make some sense of it, the scanner breaks the text up into a sequence of chunks that are slightly more sensible than a plain old character. These chunks are called tokens and they are generally very simple themselves. I simply configured it to understand my brand of tokens and off I went. Parsing the parser Before I dive into how the parser is implemented, let's take a moment to consider how one would represent a Lisp program 6 internally. It turns out to be very useful to regard everything as one polymorphic object.
Function calls are similarly a simple list.
This uniformity allows for a very simple parser. It has to recognize simple literals and open and close parentheses. When it encounters an open parenthesis, it recursively calls itself to parse the contents of the list until it encounters a close parenthesis. For ease of later discussion, a parsed expression is called an S-expression 7 . An S-expression can be as simple as a single integer literal or as complex as a function call whose arguments are function calls, whose arguments are function calls, ad infinitum.