Writing a Lexer
· 9 min read
I had heard of a lexer before beginning this journey but honestly had no idea what it was or how it works. Before diving in on this article let’s get a working definition of a lexer in place:
A lexer (or lexical analyzer) is a tool that reads raw character input and breaks it into smaller meaningful chunks called tokens all while discarding unnecessary characters.
I want to break this down in two examples
var x = 10;In the above Golang example we have an expression that defines a variable called x and assigns the value to the variable as the integer 10. That is fine and dandy for you and me, but for a computer that reads ones and zeros this means nothing.
What the interpreter is going to do is create tokens out of these characters so it can tell the pieces apart. Every token holds two things: the literal text it was built from, and a type naming what that text is. Run that line through the lexer and you get this:
// token/token.go
type TokenType string
type Token struct {
Literal string
Type TokenType
}
const (
// Identifiers + literals
IDENT = "IDENT"
INT = "INT"
// Keywords
VAR = "VAR"
// Operators
ASSIGN = "="
// Delimiters
SEMICOLON = ";"
)
// Output for var x = 10
// { Literal: "var", Type: VAR },
// { Literal: "x", Type: IDENT },
// { Literal: "=", Type: ASSIGN },
// { Literal: "10", Type: INT },
// { Literal: ";", Type: SEMICOLON },Splitting input into labeled pieces is not only a programming problem. The same move works on plain language:
Buzz and Woody saved the day!Now we have an example in the English language. Being that I am starting to teach English as a second language I found this to be an interesting application outside of computer science. A nonnative English speaker has no idea how to identify the words in the above sentence. What is a “Buzz”? Who is a “Woody”? Yet we do have a way in which we tokenize the English language, and it is one of the first things they learn: how to identify what each word in a sentence is. Their brain is constructing its own English interpreter on the fly.
{ Literal: "Buzz", Type: NOUN },
{ Literal: "and", Type: CONJUNCTION },
{ Literal: "Woody", Type: NOUN },
{ Literal: "saved", Type: VERB },
{ Literal: "the", Type: ARTICLE },
{ Literal: "day", Type: NOUN },
{ Literal: "!", Type: PUNCTUATION },The sole purpose of lexical analysis is to break down the input into tokens that the greater system can later act upon. A lexer is not going to pay any attention at all to the grammatical correctness or if the input compiles to valid code. It is just there to tokenize the input.
Designing the Language
Before you can write a lexer you have to know what the language looks like. Every syntax decision lands directly on the lexer’s desk: whatever you decide is meaningful has to become a token, and whatever you decide is noise gets thrown out.
If you have ever spent any time programming in C and Python you will know their lexers treat whitespace very differently. Python gives a whole lot of F’s about whitespace, turning indentation and line breaks into actual tokens. C could not care less: its lexer uses whitespace only to tell where one token stops and the next starts.
In C the indentation is decoration:
void greet(char *name) {
if (name) {
printf("hello");
}
}Squash all of it onto one line and the compiler does not blink:
void greet(char *name){if(name){printf("hello");}}The braces and semicolons carry the structure, and the lexer emits them as plain tokens. The spaces and newlines never survive lexing at all.
Python cannot do that, because there the indentation is the structure:
def greet(name):
if name:
print("hello")Take the indentation away and you do not get a compressed version of the same program, you get a syntax error:
def greet(name):
if name:
print("hello")Python’s lexer has to count the leading spaces on every line and emit tokens for them, which is work C’s lexer never does.
Monkey lands on the C side of that fence. Ball made these calls long before I opened the book, and the result is close enough to Go and JavaScript to feel familiar:
let add = fn(x, y) {
x + y;
};Braces mark blocks, semicolons end statements, and whitespace exists only to keep the words apart. Which means my lexer gets the easier job: skip the whitespace, and let the parser sort out later what the braces and semicolons actually mean.
Writing the Lexer
The examples so far were borrowed to explain the idea. The lexer I am actually building from Thorsten’s book is for Monkey, so from here on the tokens are Monkey’s: let, fn, braces, and the rest.
The obvious first instinct is to split the input on spaces and call each piece a token. That falls apart fast. x=10; has no spaces in it at all, and == would split into two separate = tokens, which is a different operator entirely. Whitespace is not a reliable boundary, so the lexer cannot lean on it. It walks the input one character at a time instead.
Walking one character at a time raises a question the moment you reach ==. Sitting on the first =, the lexer cannot decide what it has yet. It could be an assignment, or it could be the start of an equality check. So it tracks two spots: the character it is looking at, and the one right after. That second spot lets it peek ahead without committing.
case '=':
if l.peekChar() == '=' {
// consume both characters, emit an EQ token
} else {
tok = newToken(token.ASSIGN, l.ch)
}That decision lives in NextToken, which is more or less the whole lexer in one method. Each call skips any whitespace, looks at the current character, and returns one token. Single characters like ; or + map straight across. Names and numbers are runs of characters, so the lexer keeps reading until the run ends and hands back the whole thing.
Keywords are not special-cased in the scanner. The lexer reads a whole word the same way whether it is let or foobar, then checks it against a small table of reserved words. If it is in the table it becomes a LET or FUNCTION token, otherwise it is an IDENT. That keeps the scanning loop simple and puts all the keyword knowledge in one place.
Whitespace never becomes a token. The lexer skips it, which puts Monkey on the same side of that earlier line as C: spaces and newlines only separate tokens, they are not tokens themselves. One more shortcut worth naming is that the lexer reads bytes, not runes, so Monkey is ASCII only. It is a deliberate trade for simpler code, not an oversight, and it is the bytes-versus-runes trap from the prologue showing up in the wild.
This is where the testing warm-up pays off. A lexer is almost made for table-driven tests: hand it a string of source, list the tokens you expect back, and let it run. The test reads like a small spec for the language.
func TestNextToken(t *testing.T) {
input := `let x = 10;`
tests := []struct {
wantType token.TokenType
wantLiteral string
}{
{token.LET, "let"},
{token.IDENT, "x"},
{token.ASSIGN, "="},
{token.INT, "10"},
{token.SEMICOLON, ";"},
{token.EOF, ""},
}
l := lexer.New(input)
for i, tt := range tests {
tok := l.NextToken()
if tok.Type != tt.wantType {
t.Fatalf("tests[%d]: want type %q, got %q", i, tt.wantType, tok.Type)
}
if tok.Literal != tt.wantLiteral {
t.Fatalf("tests[%d]: want literal %q, got %q", i, tt.wantLiteral, tok.Literal)
}
}
}Every chapter after this one adds tokens, and every new token is one more row in a test like that.
Writing the REPL
With the lexer working, I need a way to actually use it. That is the REPL, though calling it that is generous right now. A REPL is a read-eval-print loop. You have likely used one before as most languages have a REPL (e.g. iex, irb, node, python).
Building it before there is anything to run feels backwards, but it is the first point where I have some interactive feedback with the language. I can type at a prompt and get a response, even if the response is only a list of tokens. It is proof the lexer sees what I see, and it is the loop I will keep using as the language grows.
>> let five = 5;
{Literal: "let", Type: LET}
{Literal: "five", Type: IDENT}
{Literal: "=", Type: ASSIGN}
{Literal: "5", Type: INT}
{Literal: ";", Type: SEMICOLON}It cannot add those numbers or store that variable yet. It only names the parts, which is all chapter one is trying to do.
Wrap Up
The lexer takes a string of Monkey source and gives back a stream of tokens, and the REPL lets me watch it happen one line at a time. What it does not do is judge. Feed it let x = ; and it will tokenize that without complaint, because noticing that nothing follows the = is not the lexer’s problem. That is the parser’s job, and the parser is the next step.
The code for this chapter is tagged in the companion repo if you want the full implementation instead of the pieces I pulled out here.
Until next time,
Cody