Imagine trying to read an entire book while
focusing on only one or two words at a time
We use compilers every day to parse our code, find our programming mistakes and then help us fix them. But how do compilers read and understand our code? What does our code look like to them?
We tend to read code like we would read a human language like English. We don’t see letters; we see words and phrases. And in a very natural way we use what we just read, the proceeding sentence or paragraph, to give us the context we need to understand the following text. And sometimes we just skim over text quickly to gleam a bit of the meaning without even reading every word.
Compilers aren’t as smart as we are. They can’t read and understand entire phrases or sentences all at once. They read text one letter, one word at at time, meticulously building up a record of what they have read so far.
I was curious to learn more about how compilers parse text, but where should I look? Which compiler should I study? Once again, like in my last few posts, Crystal was the answer.
Crystal: A Compiler Accessible to Everyone
Crystal is a unique combination of simple, human syntax inspired by Ruby, with the speed and robustness enabled by static types and the use of LLVM. But for me the most exciting thing about Crystal is how the Crystal team implemented both its standard library and compiler using the target language: Crystal. This makes Crystal’s internal implementation accessible to anyone familiar with Ruby. For once, you don’t have to be a hard core C or C++ developer to learn how a compiler works. Reading code not much more complex than a Ruby on Rails web site, I can take a peek under the hood of a real world compiler to see how it works internally.
Not only did the Crystal team implement their compiler using Crystal, they also wrote it by hand. Parsing is such a tedious task that often developers use a parser generator, such as GNU Bison, to automatically generate the parse code given a set of rules. This is how Ruby works, for example. But the Crystal team wrote their parser directly in Crystal, which you can read in parser.cr.
Along with a readable compiler, I need a readable program to compile. I decided to reuse the same array snippet from my last post:
arr = [12345, 67890] puts arr
This tiny Crystal program creates an array of two numbers and then prints out the second number. Simple enough: You and I can read and parse these two lines of code in one glance and in a fraction of a second understand what it does. Even if you’re not a Crystal or Ruby developer this syntax is so simple you can still understand it.
But the Crystal compiler can’t understand this code as easily as we can. Parsing even this simple program is a complex task for a compiler.
How the Crystal Compiler Sees My Code
Before parsing or running the code above, Crystal converts it into a series of tokens. To the Crystal compiler, my program looks like this:
IDENT token corresponds to the
arr variable at the beginning of the
first line. You can also see two
NUMBER tokens: the Crystal tokenizer
converted each series of numerical digits into single tokens, one for 12345 and
the other for 67890. Along with these tokens you can also see other tokens for
punctuation used in Crystal syntax, like the equals sign and left and right
square brackets. There is also a new line token and one for the end of the
Reading a Book One Word at a Time
To understand my code, Crystal processes these tokens one at a time, stepping tediously through the entire program. What a slow, painful process!
How would we read if we could only see one word at a time? I imagine covering the book I’m trying to read with a piece of paper or plastic that had a small hole in it… and that through the hole I could only see one word at a time. How would I read one entire page? Well, I’d have to move the paper around, showing one word and then another and another. And how would I know where to move the paper next? Would I simply move the paper forward one word at at time? What if I forgot some word I had seen earlier? I’d have to backtrack - but how far back to go? What if the meaning of the word I was looking at depended on the words that followed it? This sounds like a nightmare.
To read like this, if it was even possible at all, I’d have to have a well thought out strategy. I’d have to know exactly how to move that plastic screen around. When you can only read one word at a time, deciding which word to read next becomes incredibly important. I would need an algorithm to follow.
This is what a parser algorithm is: Some set of rules the parse code can use to interpret each word, and, equally important, to decide which word to read next. Crystal’s parse code is over 6000 lines long, so I won’t attempt to completely explain it here. But there’s an underlying, high level algorithm the parse code uses:
First, the parser compares the current token, and possibly the following or previous tokens as well, to a series of expected patterns. These patterns define the syntax the parser is reading. Second, the parser recurses. It calls itself to parse the next token, or possibly multiple next tokens depending on which pattern the parser just matched. Finally, the parser records what it saw: which pattern matched the current token and the results of the recursive calls to itself, for future reference.
Matching a Pattern
The best way to understand how this works is to see it in action. Let’s follow along with the Crystal compiler as it parses the code I showed above:
arr = [12345, 67890] puts arr
Recall Crystal already converted this code into a token stream:
(To be more accurate, Crystal actually converts my code into tokens as it goes. The parse code calls the tokenizer code each time it needs a new token. But this timing isn’t really important.)
As you might expect, Crystal starts with the first token,
What does this mean? How does Crystal interpret
IDENT is short for
identifier, but what role does this identifier play? What meaning does
in my code?
To decide on the correct meaning, the Crystal parser compares the
with a series of patterns. For example Crystal looks for patterns like:
a ternary expression
a ? b : c
an expression using a binary operator, such as:
a + b, etc.
and many more…
It turns out none of these patterns apply in this case, and Crystal ends up
selecting a default pattern which handles the most common code pattern: a
function call. Crystal decides that when I wrote
arr I intended to call a
I often tell people I work with at my day job that I have really bad memory.
And it’s true. I constantly have to google the syntax or return values of
functions. I often forget what some code means even just a month after I wrote
it. And the Crystal compiler is no better: As soon as it processes that
token above, it has to write down what it decided that token meant or else it
To record the function call, Crystal creates an object:
As we’ll see in a moment, Crystal builds up a tree of these objects, called an Abstract Syntax Tree (AST). The AST will later serve as a record of the syntactic structure of my code.
Recursively Calling Itself
Parsing is inherently a recursive process. Unlike English text, Crystal expressions can be nested one inside another to any depth. Although I suppose English grammar is somewhat recursive and can be nested to some degree. I wonder if the grammars for some other human languages are more recursive than English? Interesting question.
For parsing a programming language like Crystal, the simplest thing for the parser code to do is recursively call itself. And it does this based on the pattern it just matched. For example, if Crystal had parsed a plus sign, it would need to recursively call itself to parse the values that appeared before and after the plus.
In this example, Crystal has to decide what arguments to pass to this call to
arr function. Did I write
arr(1, 2, 3) or just
arr()? What were
the values 1, 2 and 3? Each of these could be a complex expression in their own
right, maybe appearing inside of parentheses, a compound value like an array or
maybe yet another function call.
To find the arguments of the function call, inside the recursive call to the parse code Crystal proceeds forward to process the next two tokens:
Crystal skips over the space, and then encounters the equals sign. Suddenly
Crystal realizes it was wrong! The
arr identifier wasn’t a reference to a
function at all, it was a variable declaration. Yes, sometimes compilers change
their minds while reading, just like we do!
Recording an AST Node
To record this new, revised syntax, Crystal changes the
Call AST node it
created earlier to an
Assign AST node, and creates a new
Var AST node to
record the variable being assigned to:
Now the AST is starting to resemble a tree. Because of the recursive nature of parse algorithm, this tree structure is an ideal way of record what the compiler has parsed so far. Trees are recursive too: Each branch is a tree in its own right.
Rinse and Repeat
But what value should Crystal assign to that variable? What should appear in
the AST as the value attribute of the
To find out, the Crystal compiler recursively calls the same parsing algorithm
again, but starting with the
Following the pattern match, record and recurse process, the Crystal compiler
once again matches the new token,
[, with a series of expected patterns. This
time, Crystal decides that the left bracket is the start of literal array
expression and records a new AST node:
But before inserting it into the syntax tree, Crystal recursively calls itself to parse each of the values that appear in the array. The array literal pattern expects a series of values to appear separated by spaces, so Crystal proceeds to process the following tokens, looking for values separated by commas:
After encountering the comma, Crystal recursively calls the same parse code again on the previous token or tokens that appeared before the comma, because the array value before the comma could be another expression of arbitrary depth and complexity. In this example, Crystal finds a simple numeric array element, and creates a new AST node to represent the numeric value:
After reading the comma, Crystal calls its parser recursively again, and finds the second number:
Remember Crystal has a bad memory. With all these new AST nodes, Crystal will quickly forget what they mean. Fortunately, Crystal reads in the right square bracket and realizes I ended the array literal in my code:
Now those recursive calls to the parse code return, and Crystal assembles these new AST nodes:
…and then places them inside the larger, surrounding AST:
After this, these recursive calls return and the Crystal compiler moves on to parse the second line of my program.
A Complete Abstract Syntax Tree
After following the Crystal parser for a while, I added some debug logging code to the compiler so I could see the result. Here’s my example code again:
arr = [12345, 67890] puts arr
And here’s the complete AST the Crystal compiler generated after parsing my code. My debug logging indented each line to indicate the AST structure:
<Crystal::Expressions exp_count=3 > <Crystal::Require string=prelude > <Crystal::Assign target=Crystal::Var value=Crystal::ArrayLiteral > <Crystal::Var name=arr > <Crystal::ArrayLiteral element_count=2 of=Nil name=Nil > <Crystal::NumberLiteral number=12345 kind=i32 > <Crystal::NumberLiteral number=67890 kind=i32 > <Crystal::Call obj= name=puts arg_count=1 > <Crystal::Call obj=arr name= arg_count=1 > <Crystal::Var name=arr > <Crystal::NumberLiteral number=1 kind=i32 >
Each of these values is a subclass of the
Crystal defines all of these in the
file. Some interesting details to note:
The top level node is called
Expressions, and more or less holds one expression per line of code.
The second node, the first child node of
Expressions, is called
Require. The surprise here is that I didn’t even put a
requirekeyword in my program! Crystal silently inserts
require preludeto the beginning of all Crystal programs. The “prelude” is the Crystal standard library, the code that defines
Stringmany other core classes. Reading the AST allows us to see how the Crystal compiler does this automatically.
The third node and its children are the nodes we saw Crystal create above for my first line of code, the array literal and the variable it is assigned to.
Finally, the last branch of the tree shows the call to
puts. This time Crystal’s default guess about identifiers being function calls was correct. Another interesting detail here is that the inner call to the
function was not generated by an identifier, but by the
[token. This was one of the patterns the Crystal parser checked for after one of the recursive parse calls.
What’s the point of all of this? What does the Crystal compiler do next with the AST? This tree structure is a fantastic summary of how Crystal parsed my code, and, as we’ll see later, also provides a convenient way for Crystal later to process my code and transform it in different ways.
When I have time, I plan to write a few more posts about more of the inner workings of the Crystal compiler and the LLVM framework, which Crystal later uses to generate my x86 executable program.