27. Tokens and lexemes

Characters are too small

Here is a line of Drip:

let speed = 10.5;

The parser’s job, coming up in chapter 30, is to recognise the shape of this line: “a let, then a name, then =, then a value, then ;”. Now imagine it had to do that one character at a time. Is l the start of let, or of a name like lemon? Is 1 a whole number, or the start of 10.5? Every rule of the grammar would have to worry about spelling.

So the pipeline splits the work. The scanner deals with spelling once, and hands the parser a list of whole words. Those words are called tokens.

Cutting a line into tokens

Step through two lines being cut up. Watch the card: every token has the same four parts.

In the companion code a token is a plain object. This is the interface from companion/ts/src/token.ts, with its comments removed:

interface Token {
  type: TokenType;
  lexeme: string;
  literal: string | number | null;
  line: number;
}

Lexeme and literal are easy to mix up, and strings make the difference clearest. For the Drip source "fast", the lexeme is six characters, quote marks included. The literal is the four-letter text fast, which is what print will show.

The list of token types

Why bother with a type at all, if the lexeme already says everything? Because the parser thinks in categories. Its rule is “a let is followed by any name”, not “followed by speed, or x, or total…”. Thousands of different lexemes share the one type identifier.

Here is every token type Drip has, from token.ts, rewrapped to fit:

type TokenType =
  // single-character tokens
  | '(' | ')' | '{' | '}' | ',' | '.'
  | '-' | '+' | ';' | '/' | '*'
  // one or two character tokens
  | '!' | '!=' | '=' | '=='
  | '>' | '>=' | '<' | '<='
  // literals
  | 'identifier' | 'string' | 'number'
  // keywords
  | 'and' | 'class' | 'else' | 'false'
  | 'fn' | 'for' | 'if' | 'nil' | 'or'
  | 'print' | 'return' | 'super'
  | 'this' | 'true' | 'let' | 'while'
  | 'eof';

It is a union of string literal types, from chapter 14. That buys two things. TypeScript rejects a typo such as 'eqaul', because it isn’t in the union. And the names are easy to read: for punctuation and keywords, the type is the spelling, so the token for <= has type '<='. Only for names, numbers and strings do the type and the lexeme differ.

The last type, eof, means “end of file”. The scanner always finishes with one, so the parser can keep asking “what’s the next token?” and get a clear answer when the program has run out.

Where did it come from?

A token also remembers where it was found. When something goes wrong much later, say in the parser, that is the only way to tell you where.

print "one";
let x = 1;
print x +;

The parser reports line 3, which it read from the ; token. Notice also that one is never printed. The front end checks the whole program before any of it runs, so a mistake in line 3 stops line 1 too.

Drip’s tokens record only the line, because Drip’s error messages, which follow the Lox test suite, name only the line^[1]. Many compilers go further and print the offending line with a caret ^ under the exact spot. For that a token needs its column too, which is what you’ll compute in the exercise.

Your turn

The core exercise turns a position in the source, counted in characters, into a line and a column. The extra one uses that to draw a caret under an error.

function locate(src, offset) {
  // your code here
}

console.log(locate('ab\ncd', 4));

function pointAt(src, line, col) {
  // your code here
}

const src = 'let x = 1;\nprint x +;';
console.log(pointAt(src, 2, 10));

What you learned

• A token is one meaningful word of source. Its lexeme is the exact characters, its token type is its category, and numbers and strings also carry a literal value.
• Drip’s TokenType is a union of 39 string literal types. For punctuation and keywords the type is the spelling itself. The list always ends with eof.
• Whitespace and comments separate tokens but never become tokens.
• A source location (line, and often column) lets later stages report errors in the right place. Drip records the line.

Next: the scanner itself, the loop that makes all these tokens.