When several token rules match at one position, how does a maximal-munch scanner pick the token it emits?

middlemust knowfreq 58%

answer

longest wins, not first
order only settles equal length
keep scanning past an accepting state
rewind to last accepting position
overlapping prefixes defeat it

basics

~10 s

It takes the longest prefix starting at that position that any rule accepts, not the first rule that matches. If two rules accept the same longest prefix, the rule declared earlier wins.

solid answer

~40 s

Maximal munch means longest match first. At each position the scanner keeps consuming characters while any rule could still accept, remembering the last position at which some rule did accept, then rewinds to that position and emits that token. Only when two rules accept the same longest prefix does declaration order decide - which is why a keyword rule is declared before the identifier rule. Longest match is what stops iffy from becoming if followed by fy, and >= from becoming > followed by =. It is a rule, not a law of nature: where a language has a genuine overlap, such as a number rule that accepts a trailing dot meeting a range operator .., longest match produces the wrong split and the rule set has to be constrained.

Maximal munch means **longest match first**. At each position the scanner keeps consuming characters while any rule could still accept, remembering the last position at which some rule did accept, then rewinds to that position and emits that token. Only when two rules accept the *same* longest prefix does declaration order decide - which is why a keyword rule is declared before the identifier rule. Longest match is what stops `iffy` from becoming `if` followed by `fy`, and `>=` from becoming `>` followed by `=`. It is a rule, not a law of nature: where a language has a genuine overlap, such as a number rule that accepts a trailing dot meeting a range operator `..`, longest match produces the wrong split and the rule set has to be constrained.

code

pseudocode · 18 lines

pseudocode

scan_one(input, pos):
    state = start_state
    cursor = pos
    best_rule = none
    best_end  = pos

    while cursor < length(input) and state is not dead:
        state = step(state, input[cursor])
        cursor = cursor + 1
        if accepting(state):
            best_rule = rule_of(state)   # earliest-declared rule on a tie
            best_end  = cursor           # remember, but keep scanning

    if best_rule is none:
        report "no rule matches here" at pos
        return none, pos + 1

    return token(best_rule, text(input, pos, best_end)), best_end

go deeper

for a junior

Remember the phrase longest match: the scanner takes the longest run of characters any rule accepts, which is why a two-character operator is one token rather than two.

for a middle

Explain the scan loop - keep going past an accepting state, remember the last accepting end, rewind - and say that declaration order only ever breaks a tie between equal-length matches.

for a senior

Show a case where longest match gives the wrong split and argue for the repair: constrain the pattern, add bounded lookahead, or let the parser split a compound token when it has the context to know.

for a principal

Treat the rule set as an interface with global behaviour: adding one operator can re-tokenize existing sources. Decide where overlaps get resolved and what that costs consumers of the language.

The rule itself

Maximal munch (also called the longest-match rule) resolves the ambiguity every scanner faces: at a given position, several token rules may accept a prefix of what follows, and the prefixes may have different lengths. The rule is:

Among all rules, find the longest prefix starting here that any of them accepts.
If exactly one rule accepts that prefix, emit its token.
If several rules accept the same longest prefix, break the tie by declaration order - the rule written first wins.
If no rule accepts any prefix, that is a lexical error at this position.

Step 3 is the only place where order matters, and it is the mechanism that makes keywords work when they are written as their own rules: if is accepted both by the keyword rule and by the identifier rule at the same length, and the keyword rule is declared first.

How a scanner implements it

The rules are combined into one recogniser whose accepting states are labelled with the rule that accepted. Scanning one token then looks like this:

start at the current position in the start state;
step the machine one character at a time, remembering (rule, end) every time the machine is in an accepting state;
keep going even after accepting, because a longer match may still be ahead;
stop when the machine can make no further move, or at end of input;
rewind to the last remembered end and emit the last remembered rule.

That rewind is the only backtracking a conventional scanner does, and it is bounded by the length of the token, not by the length of the file. It is also why an implementation must track the last accepting position rather than stopping at the first one.

Why longest wins

Without longest match, almost every multi-character construct falls apart:

iffy would be the keyword if followed by the identifier fy;
>= would be > followed by =;
123 would be three separate one-digit numbers if the number rule accepts a single digit;
// opening a line comment would be two division operators.

Each of these is a real prefix relationship: the shorter token's pattern is a prefix of the longer one's. Longest match is precisely the rule that says a prefix never wins over the whole.

Where longest match is wrong

The rule is a heuristic about what humans usually mean, and it can be defeated by a rule set with a genuine overlap.

Input	Rules present	Munch emits	Probably intended
`>>`	`>` and `>>`	`>>`	`>` then `>` when closing two nested type arguments
`1..5`	number accepting a trailing dot, and `..`	`1.` then the rest	`1`, `..`, `5`
`a---b`	`--` and `-`	`a`, `--`, `-`, `b`	depends entirely on the author

There are three standard repairs, and which one is used is a language-design choice:

Constrain the rule so the overlap disappears - require a digit after the dot, so 1. is no longer a number and 1..5 splits correctly. This is the cleanest fix and costs nothing at scan time.
Add bounded lookahead to the rule - accept a trailing dot only when the next character is not another dot. The scanner stays one pass; the rule stops being a plain pattern.
Let the parser split the token - emit >> and allow the parser, which knows it is closing type arguments, to break it into two > tokens. This moves the problem across the stage boundary and is the usual answer for the nested-angle-bracket case.

The consequence for rule sets

Because longest match is global over all rules, adding a rule can silently change how existing input is tokenized: introducing a .. operator to a language whose numbers may end in a dot changes what 1..5 means. The practical discipline is to look, for each new rule, at whether its pattern overlaps an existing one at a shared prefix, and to fix the overlap in the rule set rather than in the tie-break order - order only ever settles a tie at equal length, so it cannot rescue a case where the wrong rule matched longer.

## The rule itself **Maximal munch** (also called the longest-match rule) resolves the ambiguity every scanner faces: at a given position, several token rules may accept a prefix of what follows, and the prefixes may have different lengths. The rule is: 1. Among all rules, find the **longest** prefix starting here that any of them accepts. 2. If exactly one rule accepts that prefix, emit its token. 3. If several rules accept the same longest prefix, break the tie by **declaration order** - the rule written first wins. 4. If no rule accepts any prefix, that is a lexical error at this position. Step 3 is the only place where order matters, and it is the mechanism that makes keywords work when they are written as their own rules: `if` is accepted both by the keyword rule and by the identifier rule at the same length, and the keyword rule is declared first. ## How a scanner implements it The rules are combined into one recogniser whose accepting states are labelled with the rule that accepted. Scanning one token then looks like this: - start at the current position in the start state; - step the machine one character at a time, remembering `(rule, end)` every time the machine is in an accepting state; - keep going even after accepting, because a longer match may still be ahead; - stop when the machine can make no further move, or at end of input; - rewind to the last remembered `end` and emit the last remembered rule. That rewind is the only backtracking a conventional scanner does, and it is bounded by the length of the token, not by the length of the file. It is also why an implementation must track the last accepting position rather than stopping at the first one. ## Why longest wins Without longest match, almost every multi-character construct falls apart: - `iffy` would be the keyword `if` followed by the identifier `fy`; - `>=` would be `>` followed by `=`; - `123` would be three separate one-digit numbers if the number rule accepts a single digit; - `//` opening a line comment would be two division operators. Each of these is a real prefix relationship: the shorter token's pattern is a prefix of the longer one's. Longest match is precisely the rule that says a prefix never wins over the whole. ## Where longest match is wrong The rule is a heuristic about what humans usually mean, and it can be defeated by a rule set with a genuine overlap. | Input | Rules present | Munch emits | Probably intended | |---|---|---|---| | `>>` | `>` and `>>` | `>>` | `>` then `>` when closing two nested type arguments | | `1..5` | number accepting a trailing dot, and `..` | `1.` then the rest | `1`, `..`, `5` | | `a---b` | `--` and `-` | `a`, `--`, `-`, `b` | depends entirely on the author | There are three standard repairs, and which one is used is a language-design choice: 1. **Constrain the rule** so the overlap disappears - require a digit after the dot, so `1.` is no longer a number and `1..5` splits correctly. This is the cleanest fix and costs nothing at scan time. 2. **Add bounded lookahead to the rule** - accept a trailing dot only when the next character is not another dot. The scanner stays one pass; the rule stops being a plain pattern. 3. **Let the parser split the token** - emit `>>` and allow the parser, which knows it is closing type arguments, to break it into two `>` tokens. This moves the problem across the stage boundary and is the usual answer for the nested-angle-bracket case. ## The consequence for rule sets Because longest match is global over all rules, adding a rule can silently change how existing input is tokenized: introducing a `..` operator to a language whose numbers may end in a dot changes what `1..5` means. The practical discipline is to look, for each new rule, at whether its pattern overlaps an existing one at a shared prefix, and to fix the overlap in the rule set rather than in the tie-break order - order only ever settles a tie at equal length, so it cannot rescue a case where the wrong rule matched *longer*.

Two rules accept exactly the same characters at one position. What decides which token is emitted?
Declaration order: the rule written first in the specification wins. This is the only role order plays, because longest match has already eliminated every shorter candidate. It is how a keyword rule beats the identifier rule on `if`, and it means the order of rules is part of the specification rather than a formatting detail.
Why must the scanner keep reading after it has already reached an accepting state?
Because a longer match may still lie ahead. Stopping at the first acceptance turns `>=` into `>` then `=`, and `iffy` into `if` then `fy`. The scanner therefore records the most recent accepting position, continues until no rule can extend, then rewinds to that record - a backtrack bounded by one token's length.
A language adds a `..` range operator while its number rule already accepts a trailing dot. What breaks?
`1..5` mis-tokenizes: the longest prefix at position zero is `1.`, so that is emitted and the intended `..` never forms. The repair belongs in the rule set - require a digit after the dot, or accept a trailing dot only when the next character is not a dot - because tie-break order cannot help when the wrong rule matched longer.

Reading a handwritten shopping list with no gaps: you take the longest word your dictionary knows, so saltpeter is one item rather than salt plus a name. That is right almost always, and wrong exactly when the writer really did mean two things run together.

saying these in an interview costs you the question

Thinks rules are tried in order and the first match wins outright
Stops the scan at the first accepting state reached
Believes reordering rules can fix a wrong longest match
Says maximal munch is always the split the author intended
Claims the rewind makes scanning worse than linear in file size

When several token rules match at one position, how does a maximal-munch scanner pick the token it emits?

§ answer

basics

solid answer

code

§ go deeper

▾level notes4 levels

▾deep dive~4 min

The rule itself

How a scanner implements it

Why longest wins

Where longest match is wrong

The consequence for rule sets

▾common follow-ups3 questions

▾analogy~20 s

▾red flags5 flags

The rule itself

How a scanner implements it

Why longest wins

Where longest match is wrong

The consequence for rule sets

answer

go deeper