Skip to content

Chapter 1

Hello, compiler

A compiler is a program that reads a program. It reads text that a person wrote, and it writes a program that a machine can run. This chapter is about the first step: how text becomes a tree.

TEXT double x = x + x TREE define double + x x PROGRAM This chapter is about the first arrow. The second arrow takes the rest of the book.

Words first

To a computer, a program is one long line of characters. The letters d, o, u, b, l, e are six characters. They are not yet a word.

The first thing the compiler does is to read the characters and to group them into words. A programmer calls these words tokens. double is a token. So is =, and so is +. A space between two tokens is not a token. It only keeps them apart.

This step is small, and the compiler does it fast. The interesting part comes next.

A tree, not a list

Read this sentence: the cat sleeps on the book. You did not read it as six separate words. You read the cat as one thing, on the book as another, and sleeps as the action that connects them. The words have a shape.

A program has a shape too. In double x = x + x, the + connects two things, and the = connects a name to a body. The compiler finds this shape. The result is a tree: one node at the top, and smaller pieces below it. The part of the compiler that does this is the parser.

Here is the parser of aihc. Write a little Haskell on the left, and look at the tree on the right.

double x = x + x

greeting = "hello"

Try this

  • Add a third line: big = double (double 10). The parentheses become a node of their own.
  • Remove the = from the first line. The parser tells you where it got lost.
  • Write answer = if True then 1 else 0. An if has exactly three children. Find them.

What the tree does not show

The tree on the right hides a few things. Each node also knows the line and the column where it came from. The compiler keeps them for error messages, so that a message can point at the right place. The tree also hides small tags, such as whether a number was written with a hash. A reader does not need them, so the playground leaves them out.

One more thing is missing, and it is important. The tree has two nodes that say x. The parser does not know whether they are the same x. It does not know what + is, or where double came from. A parser finds the shape of the text, and nothing else. Finding out who is who is the next job.

Next chapterWho is who