Maximal Munch and the Boundary Between Tokens

A source file arrives as a sequence of bytes. The grammar that describes the language is written over symbols that are not bytes. Something has to place the cuts between them, and the rule that places the cuts is not derived from the grammar at all: at each position the lexer takes the longest prefix of the remaining input that matches any of its token patterns. When two patterns match the same longest prefix, the one listed first wins.

Maximal munch is the name of that rule, and most surprises in tokenization follow from it.

The rule, with its tie-break

A lexer specification is a list of patterns, each a regular expression, each labelled with a token kind. Whitespace and comments normally appear in that list too, labelled as something to discard. The scanning loop is mechanical:

1. At offset i, test every pattern against the input beginning at i.
2. Keep the longest of the matches.
3. If several patterns matched that same longest length, take the earliest in the list.
4. Emit a token covering i to i + L, advance, repeat.

The priority order is load-bearing only for exact ties. if matches both a keyword pattern and the identifier pattern over the same three characters, so the two matches are the same length and length cannot separate them; the specification must. One way is to list the keyword rules ahead of the identifier rule, so that the earlier rule wins the tie. The other is to drop the keyword rules from the automaton entirely, recognise every letter sequence as an identifier, and let the lexer look the text up in a keyword table before emitting the token.

This explains why = and == may be listed in either order without changing behaviour. == is longer, so it wins wherever both match. Ordering matters only when two patterns match the same number of characters, which for a well-formed specification means the patterns are indistinguishable on that prefix.

Why the grammar is not allowed to decide

It is tempting to let the parser place the cuts, since the parser knows what shape it expects next. It cannot, for two reasons.

The grammar is written over token kinds. Asking it about characters requires arbitrary lookahead into the byte stream, which destroys the bounded-lookahead property that predictive parsers depend on. And the machinery that makes lexing fast is a finite automaton, which carries no memory of what the parser expects; it knows only its current state.

The separation is structural rather than stylistic. Regular languages are closed under union, concatenation, and Kleene star, so an arbitrary set of token patterns compiles into one automaton that recognises all of them at once. Context-free languages are not closed under intersection or complement, so the same trick does not extend upward. The lexer is the part of the front end that can be a table, and it is kept that way deliberately.

Keywords are identifiers that lost a lookup

Lexically, if is an identifier: letters followed by more letters. Languages with reserved words handle this by recognising the identifier pattern first and then consulting a keyword table, usually a hash table or a perfect hash built at compile time. The alternative, listing each keyword as its own pattern ahead of the identifier pattern, produces the same result through rule priority. Determinism merges the keyword patterns into the identifier pattern wherever they coincide, so the automaton grows by at most a few states per keyword, at the far end of the spelling, rather than by a full path.

Either way the cost is one lookup per identifier token, so it scales with identifier count rather than byte count. A table with as many buckets as there are keywords keeps the average probe count near one; below that, some chains form and the lookups that hit them do a second comparison.

The consequence reaches into language design. A reserved word cannot also be an ordinary variable name, because the decision is made before the parser runs and no syntactic context is available to undo it. Languages that want both, such as those with raw identifier syntax, introduce a separate lexical form whose pattern is distinct from the keyword.

Three splits that surprise readers

Maximal munch produces token sequences that a reader would not predict from the text.

In C, a+++b becomes a, ++, +, b. The lexer never considers +++ as a unit, and at the first + the longest match is the two-character increment operator. Similarly a---b becomes a, --, -, b.

In C++, <: is a digraph for [, so the plain longest-match rule would read a<::b as a, <:, :, b rather than the comparison a < ::b. The standard closes that hole with an explicit exception: when the next three characters are <:: and the character after them is neither : nor >, the < is a token on its own. The exception exists precisely because maximal munch is otherwise unconditional, and it is the clearest evidence that the rule needs patching when a digraph collides with an operator.

In Rust, 1..2 becomes 1, .., 2. The range operator takes the two dots first, and the lexer has an explicit rule that keeps the dots out of a numeric literal; without it, an immediately following . would be read as the start of a float fractional part and the range would never appear. C’s preprocessing number rule is looser and admits several periods with no such exception, so after preprocessing the same text can arrive at the parser as one malformed numeric token, and the diagnostic appears later and further from the cause.

What the rule costs to implement

Two implementations are common, and they trade differently. Both need a table or a set of patterns that associates each match with a rule number, and both must prefer the rule declared first when two matches end at the same offset.

A deterministic automaton makes one pass over the input. Each byte advances the machine by one state, and the driver remembers the last accepting state together with its offset. When the machine reaches a state with no transition for the current byte, the driver rewinds to the remembered offset and emits that token. The scan is linear in the input length, the rewind distance is bounded by the longest token the language admits, and no byte is examined twice except within a single token.

The other implementation tries patterns in order of decreasing length with ordinary regular-expression matching. It is easier to write by hand and much easier to extend with code actions, but the worst case is worse: a failed attempt rescans the same prefix, and nested quantifiers can make a single token’s match superlinear.

Both need a buffer that holds at least one whole token, and string literals have no length bound, so that buffer grows with the input in the worst case. A generated lexer normally emits the token’s text as a range into the input rather than copying it, which keeps per-token allocation to one small record.

Tokens that no finite automaton can match

Some languages contain tokens whose extent depends on information outside the character stream, and no amount of table building will produce them.

Nested comments are the standard example. A comment form that opens with (* and closes with *), and nests, requires a counter; the language of balanced nested comments is not regular. A hand-written lexer keeps an integer and increments and decrements it. A generated lexer either refuses the pattern or approximates it with a fixed number of start conditions, at the cost of accepting the wrong set of comments, so a nested comment form usually needs a hand-written hook in the scanner loop.

C’s #include <stdio.h> is a second case: the header name is a token only inside a directive, and the same characters outside one are a comparison and an identifier. C’s typedef names are a third, resolved through the symbol table. Haskell’s layout rule and Python’s indentation are fourth and fifth, where line structure becomes braces and semicolons. All of them are cases where the lexer needs a mode, a counter, or an answer from the parser.

Those mechanisms are the subject of context-dependent lexing. For everything else, maximal munch is sufficient, and the automaton that implements it is built by the constructions described in From Regular Expression to DFA Table.

A hand-written scan of the same rule

The longest-match rule does not require a generator. A hand-written scanner encodes it as a small state machine with a remembered accept position, which is compact enough to show directly.

import re

# re alternation is first-match, not longest-match, so the ordering below is
# what makes "++" win over "+" at the same offset.
TOKEN = re.compile(r"""
    (?P<plusplus>\+\+)
  | (?P<pluseq>\+=)
  | (?P<plus>\+)
  | (?P<ident>[A-Za-z_][A-Za-z0-9_]*)
  | (?P<space>[ \t\r\n]+)
""", re.VERBOSE)

def tokens(text):
    pos = 0
    while pos < len(text):
        m = TOKEN.match(text, pos)
        if m is None:
            raise SyntaxError(f"no token at offset {pos}")
        pos = m.end()
        if m.lastgroup != "space":
            yield m.lastgroup, m.group()

The ordering trick works only because the alternatives are known to be prefix-related in a simple way. Once patterns can match the same length through different paths, or once a pattern can match a prefix of another and then fail, the ordering argument collapses and the scanner needs the remembered-accept loop that a generated automaton uses. That is the point at which writing the table becomes the cheaper option.