Lexing: From Text to Tokens

Before Lantern can answer author:"le guin" AND year>1970, it has to see that those 30 characters are seven things: a word, a colon, a phrase, an operator, another word, a comparison and a number. Lexing is that first pass. Every language does it the same way, from Python and SQL to a shell and Lantern's search box: read the characters once, group them into tokens and discard what carries no meaning.

It is the cheapest stage of running a language, and the one whose small decisions users feel first. Whether and is a keyword, where a phrase ends, whether Le Guin and le guin are the same thing: each is settled here, in a few lines of code, and each shows up as a search that works or one that quietly returns nothing. This chapter follows Lantern's query through four stages, and this is the first.

Characters Are Not Words

The obvious first attempt is to split the query on spaces. Python's own split does it in one call and returns four pieces: author:"le, guin", AND and year>1970. Only the third is right. The phrase has been cut in half at its space, and the comparison has been glued into one piece because it contains no space at all. Whitespace is the wrong boundary twice in 30 characters.

A lexer groups characters by meaning instead. It knows that a double quote opens a phrase that runs to the next double quote, spaces included, and that a word ends at the first character that cannot be part of a word, such as a colon or a comparison sign.

The figure shows the result on the canonical query. Characters 0 to 5 are a word, character 6 is a colon, 7 to 15 are a phrase including both quotes, 17 to 19 are the AND operator, then a word, a greater-than sign and a number. The two spaces between tokens belong to no token, and the one inside the phrase is part of the phrase. A final END token marks where the input stops, so later stages never have to ask whether there is more.

Token Kinds, Values and Positions

A token is three things: a kind, a value and the position it started at. Lantern's kinds are word, phrase and number, the three operator keywords, the colon, the four comparisons and the two parentheses. The value is the text that matters: the phrase without its quotes, the number as written. The position is a character offset into the query, kept so that any later stage can point at the character that caused a problem.

WORD 'author' @0
COLON ':' @6
PHRASE 'le guin' @7
AND @17
WORD 'year' @21
GT '>' @25
NUMBER '1970' @26
END @30

The list above is that output, one token per line: the kind, the value in quotes where there is one, and the starting position after the at sign. Notice what the lexer does not know. It reports author as a word, not as a field name. Whether a word names a field is a question about names, answered by the checker two topics from now. The lexer's only job is to say what kind of thing each piece of text is.

Keywords are a lexer decision too. Lantern recognizes AND, OR and NOT only in capitals, and never inside quotes. So title:"And Then There Were None" lexes as one phrase, and a search for the lowercase word "and" still works: the lexer reports it as an ordinary word.

The Lexer as a Small Machine

The lexer reads one character at a time and decides what to do by the state it is in. Between tokens, a space is skipped, a letter starts a word, a digit starts a number, and a double quote starts a phrase. Inside a word it keeps going while characters can belong to a word. Inside a phrase it keeps going until the closing quote, whatever comes before it. When a token ends, the lexer emits it and returns to the between-tokens state.

One rule settles every ambiguity about where a token stops: always take the longest token that fits, a rule called maximal munch. When the lexer sees a greater-than sign, it looks one character ahead, and if an equals sign follows it produces one "greater than or equal" token, not two. Python, C and SQL lexers all follow the same rule.

The loop the figure draws is a finite state machine, the idea Chapter 14 makes formal. It looks at every character once and never goes back, so its cost is linear in the length of the query. A lexer this shape is the reason no language pays much for reading its own source.

Normalization at the Boundary

As each word and phrase is produced, Lantern case-folds it and applies the same Unicode normalization the 02:00 index build uses, the one the Unicode topic in Chapter 2 describes. Le Guin, LE GUIN and le guin all become the value "le guin", which is the form the index stored. In Lantern the whole rule is one function, called on both sides.

The query side and the index side must run the same function, because a mismatch is not an error. A query term normalized differently from the index is a lookup for a term the index never stored. The lookup succeeds, finds nothing, and Lantern shows an empty results page with no warning anywhere.

Where Whitespace Is Syntax

In Lantern, whitespace only separates tokens. In Python it carries structure. Python's tokenizer compares each line's indentation with a stack of the indentation levels it has seen: a deeper line pushes a level and emits an INDENT token, and a shallower one pops levels and emits one DEDENT token for each. By the time the parser runs, blocks look like brackets.

So a lexer can keep a little memory of its own, and Python's is why a line indented to a level that was never opened fails before any code runs. The error is reported by the tokenizer, at the offending line, because only the tokenizer tracks indentation.

Errors, Unfinished Input and the Cost

A phrase with no closing quote, such as author:"le guin, is a lexing error at a known place. Lantern's lexer reports "unterminated phrase" at position 7, where the quote that was never closed opens, and the search box can underline that character. The position on each token is what makes such a message possible.

Autocomplete makes this case normal. It fires on every keystroke after the second character, on 90 kiosks and the website, so Lantern lexes half-typed queries constantly. For those calls the lexer runs in a partial mode that treats an open phrase at the end of the input as still being typed: given author:"le gu, it returns a phrase token with the value "le gu" instead of failing.

Lexing the canonical query took about 5 microseconds on Python 3.15 in a measurement on one laptop, and lexing, parsing and checking it together about 10. Reading postings lists for a search takes milliseconds. The price of lexing shows only where a language re-lexes all the time: an editor highlighting on every keystroke, a search box at typing speed, a lexer that rescans a large file from the start after every change.