How does a language begin with a few characters?

When we use a programming language, we tend to see words: let, print, variable names. At first, the computer only has characters. Turning them into meaningful pieces is an early step in running a language.

A small example

let answer = 42;

We could read this character by character: l, e, t, a space… A more useful representation for the next stage is:

LET        let
IDENT      answer
EQUAL      =
NUMBER     42
SEMICOLON  ;

Each piece is a token. The component that produces them is a lexer, also called a scanner. Here, LET is the token kind and let is the text in the source: its lexeme.

What does a lexer know?

A lexer knows which characters form a number, where a name ends and that let is a keyword. Depending on the language, whitespace may be skipped or processed separately. This example skips whitespace and // comments.

It does not yet decide whether answer has been defined. It could produce tokens for 2 + * 3; deciding whether that sequence follows the grammar is the parser’s job.

A lexer asks: “What are these pieces?” A parser asks: “How do they form a structure?”

Is the token kind enough?

The kind NUMBER does not tell us whether the number is 42 or 900. We need its text too. A helpful error message also needs a location.

struct Token<'a> {
    kind: TokenKind,
    lexeme: &'a str,
    start: usize,
}

This design borrows the token text from the source. The source must outlive the tokens. That gives Rust’s lifetime concept a concrete purpose.

Try it

Write let answer = 2 + 3 * 4; on paper and split it into tokens. Change the variable’s name, add whitespace and consider an unrecognized character such as @. Which changes affect the token count? Which would require a lexer error?

Vocabulary

Token: a meaningful unit in the language. Lexeme: the corresponding text in the source.

A lexer groups characters into tokens. The parser gives those tokens a structure.

Further reading: Crafting Interpreters — Scanning. This is an independent starting note, not a translation of the book.