Building a Language: The Lexer

In the previous entry I defined Codexivo's tokens and promised that the next one would cover the parser. First, a correction: between the text and the parser there's a piece I haven't written about yet. The lexer, the part that reads the code and produces those tokens.

A quick note on the examples: Codexivo is a language in Spanish, so the code is in Spanish too. variable declares a variable, si means if, y and o are and and or, and año means year.

Reading one character at a time

A lexer takes text and returns a list of tokens. To the computer, variable año = 2023; has no words in it: it's a row of twenty characters. The lexer walks through it from left to right, one at a time, deciding where each piece ends and what it is.

At every character the lexer asks itself the same question: does this continue what I'm reading, or does something new start here? A v starts a name, and the name goes on while there are letters. When it hits the space, the word is complete: variable. Only then does it check whether it's a keyword. It is, so the token is LET. The space produces nothing, = is a token on its own, and 2023 is read just like variable, only with digits.

Even the end of the program counts: the lexer emits an EOF token so the parser knows nothing else is coming.

The first version

I'm building it while taking a course on how to create a programming language. The course builds a basic version of Python inside Python; I take what's the same in any language (tokens, tree, evaluation) and write it in TypeScript, with Spanish words.

Codexivo's first commit was little more than that: the lexer, the tokens, and their tests. The lexer was a chain of ifs comparing the current character against one regular expression per symbol:

if (/^=$/.test(this.character))
  token = new Token(TokenType.ASSIGN, this.character);
else if (/^\+$/.test(this.character))
  token = new Token(TokenType.PLUS, this.character);
// …and so on, one symbol after another

Not elegant. But it already kept a promise from the first post: the function that recognizes letters accepted accents and the ñ from day one.

private isLetter(character: string): boolean {
  return /^[a-zA-Z_áéíóúÁÉÍÓÚñÑ]$/.test(character);
}

Thanks to that line, año (year) is a valid name. Because of the same line, pingüino (penguin) isn't: I left the ü out. It's on the list.

When orden became o and rden

Two days later I replaced the chain of ifs with a table. Each symbol pointed to its token type, and two-character ones (==, <=, !=) listed which character had to follow:

const tokenPatterns = {
  "=": [TokenType.ASSIGN, ["=", TokenType.EQ]],
  "<": [TokenType.LT, ["=", TokenType.LT_EQ]],
  // …
  y: [TokenType.AND],
  o: [TokenType.OR],
};

The last two lines looked reasonable. y and o are one-letter operators, just as + is a one-character one. If the table already handled symbols, why not put them there?

Because the lexer checked the table before asking whether it was starting a word. Any name beginning with o or y got split in two. orden (order) was one of them.

variable orden = 1; produced an o operator followed by a variable named rden. The parser got variable followed by an operator and replied with this:

se esperaba que el siguiente token fuera IDENT pero se obtuvo OR

"Expected the next token to be IDENT but got OR." Correct, and no help at all. Nobody reads that and thinks "oh, my variable starts with an o."

I fixed it the next day: y and o moved to the keyword list, next to si, mientras (while), and variable. That's where I learned the rule almost every lexer follows: read the whole word first, the longest one possible, and only then decide what it is. orden is a word, and it isn't a keyword, so it's a name. A lone o between spaces is.

Put that way it sounds obvious. But it's exactly the kind of bug that never shows up in the examples you write to test. My first tests used x, y, suma… until a variable was called orden.

The other problem: knowing where you are

The first lexer juggled two cursors: position, the current character, and readPosition, the next one. To read a word it moved forward until it found something that wasn't a letter, then stepped back one, because it had gone too far:

this.position -= 1;
this.readPosition -= 1;

That step back was fragile. A few days later I found that if a program didn't end with ;, the lexer fell into an infinite loop. That day's fix changed how both cursors moved when they reached the end of the text. The lesson was broader: in a lexer, almost every bug lives at the edges, and the end of the file is the easiest edge to forget.

Later I added a line and column to every token so that errors can say where they are. A tab counts as three columns, so in tab-indented code the positions drift. For a console it's good enough, for now.

What stays

The lexer is the smallest part of the interpreter, and still it's where the language decides what counts as a word. That has consequences: año is a name, orden doesn't split in two, and a lone o is an operator.

There's still work left. The ü isn't a letter yet, so pingüino isn't a valid name. Columns drift as soon as there are tabs. And errors, when they show up, are reported by the parser, far from their cause.

That last one matters most to me. In a language meant for learning, someone's first error is almost always lexical: a missing quote, a symbol that doesn't exist. If the message they get is "expected the next token to be IDENT but got OR," all they learn is that they don't understand anything. A lexer that says exactly where the problem is and what to check is one of the things I want Codexivo to get right.

Try it

Below is the Codexivo interpreter, not an animation. The tokens view shows what the lexer produces for this code; open it to change it and try to break it.

variable orden = 10;
variable año = 2023;

Next time: the parser, the piece that takes this flat list of tokens and decides what goes with what.