Lesson 1.6 — Disambiguation: maximal munch, rule priority and Reps' linear-time munch

Techniques: maximal munch (longest match), rule priority (first rule wins ties), the quadratic worst case of naive maximal munch and Reps' linear-time memoized algorithm · Pebble implements: maximal munch with priority in the hand-written lexer (E2) and in the ★ table-driven lexer of the lab · Prerequisites: Lessons 1.2 and 1.5 · Time: 3–4 hours

A set of token rules rarely splits an input in only one way. <= could be < then =; iff could be the keyword if then an identifier f; 1..2 could be 1. then .2 if floats allowed a trailing point. Every lexer resolves this with two rules that go back to the first compilers: take the longest prefix any rule matches, and among rules that match that longest prefix, take the first one. This lesson makes the rules precise, shows the cost they can hide (a quadratic worst case), and gives Reps' algorithm that removes it.

1. Problem and motivation

The token rules define a language of tokens; the input is a word over that language in more than one way, or in no way at all. The lexer must pick one tokenization, deterministically, without the parser's help, and in linear time.

Maximal munch

"At each point, take the longest token" is the rule stated by the C standard (translation phase 3: "the next preprocessing token is the longest sequence of characters that could constitute a preprocessing token") and by virtually every language definition, including Pebble's (spec §3.6). It is simple, it needs only local information, and programmers can predict it. It is also sometimes wrong for the programmer's intent (a+++++b in C), and it can fail to tokenize an input that has a valid tokenization.

Rule priority

When two rules match the same longest prefix (the keyword if and the identifier rule on if), the earlier rule in the specification wins. Lex introduced this convention [FLEX-Manual]; lexer generators implement it by tagging each DFA state with the smallest rule index it accepts. Hand-written lexers get the same effect by looking up an identifier in a keyword table after scanning it (Lesson 1.8).

Reps' linear-time maximal munch

A DFA scanner that backs up to the last accepting position can re-read the same bytes from many token starts: \(\Theta(n^{2})\) on adversarial rule sets. Reps [Rep98] showed that memoizing which (state, position) pairs have already failed makes maximal munch linear in the input for every rule set. Production lexers do not need it (their rules have bounded backup), but it closes the gap between "DFA" and "linear time".

2. Definitions and algorithms

Definition 1.6.1 (Tokenization)

Let \(r_1, \dots, r_k\) be token rules with \(\varepsilon \notin L(r_i)\) and \(T = \bigcup_i L(r_i)\). A tokenization of \(w\) is a sequence \(w = t_1 t_2 \cdots t_m\) with every \(t_j \in T\). \(w\) may have zero, one or many tokenizations.

Definition 1.6.2 (Maximal-munch tokenization)

The maximal-munch tokenization of \(w\), \(\mathrm{MM}(w)\), is defined greedily: if \(w = \varepsilon\) it is empty; otherwise let \(t\) be the longest nonempty prefix of \(w\) in \(T\) and \(\mathrm{MM}(w) = t \cdot \mathrm{MM}(w')\) where \(w = t w'\). If no nonempty prefix is in \(T\), the lexer reports an error at this position (Pebble and the lab emit a one-byte error token and continue).

Definition 1.6.3 (Rule priority)

The kind of a token \(t\) is \(\mathrm{kind}(t) = \min \{\, i \mid t \in L(r_i) \,\}\). In a lexer DFA (the subset construction of the union of the rules, Algorithm 1.2.5 with rule tags), the tag of a state \(S\) is \(\min\{\, i \mid S\) contains an accepting NFA state of \(r_i \,\}\).

Definition 1.6.4 (Scan cost)

The cost of a scanner on \(w\) is the number of bytes it feeds to the DFA, counting the byte that leads to the dead state. A scanner backs up when it returns a token shorter than the prefix it has read.

Definitions on Pebble

With Pebble's punctuators, <= has tokenizations < = and <=; maximal munch picks <=. For a<<=b, MM gives a, <<, =, b (spec §3.6), because <<= is not a token. For iff, MM gives the single token iff, kind identifier; for if, both the keyword rule and the identifier rule match the whole prefix, and priority gives kw_if.

Maximal munch

Algorithm 1.6.5 (Maximal munch with backup)

• Input: a lexer DFA (states tagged per Definition 1.6.3, dead state \(\bot\)); input \(w\).
• Output: \(\mathrm{MM}(w)\) with kinds, or error tokens where no rule matches.
• Precondition: no rule matches ε.
• Postcondition: tokens as in Definitions 1.6.2 and 1.6.3 (Proposition 1.6.8).
• Invariant: at the top of the outer loop, the tokens emitted so far are \(\mathrm{MM}\) of the consumed prefix \(w_{0..\mathit{pos}}\).

function MaximalMunch(D, w):
    pos ← 0;  out ← []
    while pos < |w|:
        q ← q0;  i ← pos;  last ← none          # last = (tag, end) of the longest accepted prefix
        while i < |w|:
            q ← δ(q, w[i])
            if q = ⊥: break
            i ← i + 1
            if tag(q) ≠ none: last ← (tag(q), i)
        if last = none:
            append (error, w[pos]) to out;  pos ← pos + 1
        else:
            append (rule last.tag, w[pos .. last.end)) to out;  pos ← last.end   # back up
    return out

Maximal munch in Clang: a+++++b

Reproduce (clang 23.1.2; any OS):

printf 'int f(int a, int b) { return a+++++b; }\n' > t1.c
clang-23 -fsyntax-only -Xclang -dump-tokens t1.c 2>&1 | sed -n '12,16p'
clang-23 -fsyntax-only t1.c

Output (complete):

identifier       'a'                             Loc=<t1.c:1:30>    [LeadingSpace]
plusplus         '++'                            Loc=<t1.c:1:31>   
plusplus         '++'                            Loc=<t1.c:1:33>   
plus             '+'                             Loc=<t1.c:1:35>   
identifier       'b'                             Loc=<t1.c:1:36>   
t1.c:1:33: error: expression is not assignable
    1 | int f(int a, int b) { return a+++++b; }
      |                              ~~~^
1 error generated.

What to notice: a+++++b has the tokenization a ++ + ++ b, which would parse as (a++) + (++b). Maximal munch does not look for it: at each step it takes the longest token, so it produces a ++ ++ + b, and the parser then rejects (a++)++ because a++ is not an lvalue. The lexer never consults the grammar (Definition 1.6.2 is greedy by design).

Rule priority

Algorithm 1.6.6 (Priority by state tags)

• Input: rules \(r_1, \dots, r_k\) in priority order.
• Output: a lexer DFA whose states carry the tag of Definition 1.6.3; and, for the generator, the list of rules that can never win.
• Precondition: as Algorithm 1.2.5.
• Postcondition: a DFA state's tag is the kind of every word leading to it that is a token (Proposition 1.6.9); rule \(j\) is reported unmatchable iff no reachable state has tag \(j\).
• Invariant: every reachable DFA state \(S\) satisfies \(S = \hat\Delta(u)\) for the words \(u\) leading to it (Theorem 1.2.10).

function LexerDFA(r1, …, rk):
    N ← new start state s with ε-edges to Thompson(ri).start for i = 1..k,
        accept state of Thompson(ri) tagged i
    D ← SubsetConstruction(N)                      # Algorithm 1.2.5
    for S in D.states: tag(S) ← min { i | S contains the accept state tagged i } (none if empty)
    for j in 1..k: if no S has tag(S) = j: warn "rule j cannot be matched"
    return Minimize(D) with the initial partition by tag   # Lesson 1.4

flex warns when priority makes a rule dead

Reproduce (flex 2.6.4; any OS):

cat > prio.l <<'EOF'
%option noyywrap nodefault
%%
[a-z]+   { return 1; }
"if"     { return 2; }
.|\n     { return 3; }
%%
EOF
flex -o prio.c prio.l

Output (complete):

prio.l:4: warning, rule cannot be matched

What to notice: the identifier rule comes first, so every DFA state that accepts if also accepts rule 1 and gets tag 1 (Definition 1.6.3). No state has tag 2, and flex reports it: the last loop of Algorithm 1.6.6. Swap the two rules and the warning disappears; this is why keyword rules come before the identifier rule in every lexer specification.

Reps' linear-time maximal munch

Algorithm 1.6.7 (Reps' memoized maximal munch)

• Input: as Algorithm 1.6.5.
• Output: the same token sequence.
• Precondition: as Algorithm 1.6.5.
• Postcondition: same output as Algorithm 1.6.5 (Theorem 1.6.10), with cost \(O(\lvert Q \rvert \cdot \lvert w \rvert)\) (Proposition 1.6.12).
• Invariant: every pair \((q, i) \in \mathit{Failed}\) is hopeless: running the DFA from state \(q\) at position \(i\) never reaches an accepting state before dying or reaching the end of the input.

function RepsMunch(D, w):
    Failed ← {};  pos ← 0;  out ← []
    while pos < |w|:
        q ← q0;  i ← pos;  last ← none;  trail ← []
        while i < |w| and (q, i) ∉ Failed:
            append (q, i) to trail
            q ← δ(q, w[i])
            if q = ⊥: break
            i ← i + 1
            if tag(q) ≠ none: last ← (tag(q), i);  trail ← []      # the pairs before an accept are not hopeless
        Failed ← Failed ∪ trail                                   # everything after the last accept failed
        emit exactly as Algorithm 1.6.5
    return out

Failed is a bit table of \(\lvert Q \rvert \times (\lvert w \rvert + 1)\) bits, or a hash set.

flex reports the rules that force backing up

Reproduce (flex 2.6.4; any OS):

cat > munch.l <<'EOF'
%option noyywrap nodefault
%%
"."          { return 1; }
"..."        { return 2; }
[0-9]+       { return 3; }
.|\n         { return 4; }
%%
EOF
flex -b -o munch.c munch.l
cat lex.backup

Output (complete):

State #7 is non-accepting -
 associated rule line numbers:
    4
 out-transitions: [ . ]
 jam-transitions: EOF [ \000--  /-\377 ]

Compressed tables always back up.

What to notice: after .. the scanner is in state 7, which accepts nothing (.. is not a token) but can still reach .... On ..x it reads x, dies, and backs up to the . it accepted after one character: Algorithm 1.6.5's backup. flex does not memoize failures, so a rule set whose backing-up states can chain (the {a, a*b} family of §5) gives it quadratic behavior; Reps' Failed table is the fix. Here the backup is bounded (at most two bytes), which is why production lexers do not bother.

3. Worked example

Maximal munch

Rules int = [0-9]+, float = [0-9]+\.[0-9]+, dot = \., dotdot = \.\. (Pebble's number/range fragment). The oracle's lexer DFA (states named in discovery order, classes "other", ., digit):

state	other	.	digit	tag
→ A	–	B	C
B	–	D	–	dot
C	–	E	C	int
D	–	–	–	dotdot
E	–	–	F
F	–	–	F	float

Maximal munch on 1..2:

token start	DFA run (state after each byte)	last accept	token	reads
0	A →1 C (int) →. E →. dead	(int, 1)	int:1 (backs up 1 byte)	3
1	A →. B (dot) →. D (dotdot) →2 dead	(dotdot, 3)	dotdot:..	3
3	A →2 C (int) → end	(int, 4)	int:2	1

Seven reads for four bytes. The first scan shows why Pebble requires digits on both sides of the point (spec §3.4): state E, "digits and a point", is not accepting, so 1. is never a token and 0..10 stays a range.

Try it

./course drill maximal-munch --seed 2 --difficulty medium: the == rule without an = rule makes a lone = an error token after backing up.

Rule priority

Rules if (1) and [a-z]+ (2) on if iff. The DFA state after if contains the accepting states of both rules: tag \(\min\{1, 2\} = 1\), kind kw_if. After iff only rule 2 accepts: identifier. With the rules in the opposite order, the state after if would get tag 1 = the identifier rule, and the keyword rule would never win (the flex box above).

Reps' linear-time maximal munch

Rules a (1) and ab = a*b (2), input \(a^{8}\), no b anywhere. Naive maximal munch (oracle maximal_munch):

token start	bytes read before dying at the end	token	reads
0	positions 0–7 (hoping for a b)	a:a	8
1	1–7	a:a	7
2	2–7	a:a	6
…	…	…	…
7	7	a:a	1

Total \(8 + 7 + \cdots + 1 = 36 = \frac{8 \cdot 9}{2}\) reads. Reps' algorithm (oracle maximal_munch_reps) scans from 0 to the end once and marks as hopeless the seven (state, position) pairs it visited after its last accept (at position 1); from then on each scan stops two bytes in, at a marked pair:

token start	reads	new hopeless pairs	total marked
0	8	7	7
1	2	1	8
2	2	1	9
3	2	1	10
4	2	1	11
5	2	1	12
6	2	1	13
7	1	0	13

21 reads instead of 36; for \(a^{32}\) the counts are 528 and 93 (Proposition 1.6.11 and 1.6.12).

4. Invariants and correctness

Maximal munch

Proposition 1.6.8 (Maximal munch is well defined, deterministic, and sometimes too greedy)

(i) \(\mathrm{MM}(w)\) is unique, and Algorithm 1.6.5 computes it. (ii) There are rule sets and inputs with a tokenization but for which \(\mathrm{MM}\) fails.

Proof

(i) The longest prefix in \(T\) is unique when it exists, so the greedy definition determines one sequence; by induction on the number of emitted tokens (the invariant), each outer iteration emits exactly the longest accepted prefix, by Proposition 1.5.12 applied to the lexer DFA. (ii) Rules a, ab, bc and input abc: the tokenization a bc exists, but the longest first token is ab and c matches no rule. \(\square\)

Rule priority

Proposition 1.6.9 (State tags give the kind)

In the lexer DFA of Algorithm 1.6.6, if \(\hat\delta(q_0, t) = S\) and \(t \in T\), then \(\mathrm{tag}(S) = \mathrm{kind}(t)\). Minimization with the initial partition by tag preserves this.

Proof

By Theorem 1.2.10, \(S = \hat\Delta(t)\), the set of NFA states reachable on \(t\). The accepting state of rule \(i\)'s Thompson fragment is in \(S\) iff \(t \in L(r_i)\) (Theorem 1.1.10, the fragments being disjoint below the fresh start). So the minimum tag in \(S\) is \(\min\{i \mid t \in L(r_i)\} = \mathrm{kind}(t)\). Minimization merges only states with the same tag (initial partition), and the quotient preserves the tag of every class. \(\square\)

Reps' linear-time maximal munch

Theorem 1.6.10 (Reps' algorithm is correct)

Algorithm 1.6.7 emits the same tokens as Algorithm 1.6.5, and its invariant holds throughout.

Proof sketch (full proof: [Rep98, §3])

Invariant: a pair is added to Failed only if it was visited after the last accepting configuration of a scan that then died or hit the end of the input (the trail is reset at every accept). From such a pair the deterministic run is the remainder of that scan, which reaches no accepting state: the pair is hopeless. If the scan stopped because it met a pair already in Failed, the pairs on its trail lead deterministically into a hopeless pair without an accept in between, so they are hopeless too. Equivalence: at any token start, the naive scan and the memoized scan follow the same DFA path; the memoized one stops early only at a hopeless pair, beyond which the naive scan would find no further accept. Both therefore end with the same last, and emit the same token.

5. Complexity

Variables: \(n = \lvert w \rvert\); \(\lvert Q \rvert\) = lexer DFA states; \(b\) = maximal backup (the longest distance from an accepting configuration to the byte where the scan dies), when bounded.

Technique	Cost (worst)	Cost (typical)	Space
Maximal munch (Algorithm 1.6.5)	\(\Theta(n^{2})\)	\(O(n \cdot (1 + b))\) with bounded backup	\(O(1)\)
Rule priority (tags)	no run-time cost	–	one tag per state
Reps (Algorithm 1.6.7)	\(O(\lvert Q \rvert \cdot n)\)	\(O(n)\)	\(O(\lvert Q \rvert \cdot n)\) bits, or a hash set of visited pairs

Proposition 1.6.11 (Naive maximal munch is quadratic)

For rules a and a*b and input \(a^{n}\), Algorithm 1.6.5 reads exactly \(n(n+1)/2\) bytes.

Proof

Every token is a (no b exists), so there are \(n\) token starts \(0, \dots, n-1\). From start \(i\), the DFA stays alive through all remaining \(a\)'s because a*b could still match, and dies only at the end of the input: \(n - i\) reads, with the last accept after the first byte. \(\sum_{i=0}^{n-1} (n - i) = n(n+1)/2\). The oracle measures 10, 36, 136, 528 for \(n = 4, 8, 16, 32\). \(\square\)

Proposition 1.6.12 (Reps' algorithm is linear)

Algorithm 1.6.7 feeds at most \((\lvert Q \rvert + 1)(n + 1)\) bytes to the DFA.

Proof

Each read happens from a pair \((q, i)\) with \(i < n\), just appended to a trail, and each scan's reads split at its last accept. Reads before the last accept (from positions \(\mathit{pos}, \dots, \mathit{last.end} - 1\)) are one per byte of the emitted token, and each byte of the input belongs to exactly one token: at most \(n\) in total. Reads after the last accept, including the read that leads to \(\bot\), come from pairs on the final trail (it is reset at every accept, and a scan without any accept keeps all its pairs), and the whole trail goes into Failed. A pair in Failed stops every later scan before it is read from, so each of the at most \(\lvert Q \rvert\, n\) pairs with \(i < n\) is read from at most once in this role. Total: at most \(\lvert Q \rvert\, n + n \le (\lvert Q \rvert + 1)(n + 1)\). \(\square\)

Pathological input. \(\Theta(n^{2})\) needs a rule whose prefixes are all non-accepting "promises" (a*b) next to a short rule (a). Real token sets have bounded backup (C: .. before ...; Pebble: 1. before 1.5, at most one byte), so \(b \le 2\) and naive maximal munch is linear in practice.

At scale. The lab's table lexer (naive backup) runs Pebble at 90 MB/s (ch01-regexbench); Pebble's rules back up at most one byte (1. then .).

6. Variants and refinements

Maximal munch

• Exceptions in the standard (C++ [lex.pptoken]p3): <:: is lexed as < :: unless followed by : or >, so std::vector<::std::string> works; Clang implements it in the '<' case of LexTokenInternal. Such exceptions are hand-written special cases.
• Parser-driven splitting: C++ >> in templates is lexed as one token and split by the parser (Lesson 1.7); the lexer stays greedy.

Rule priority

• Explicit priorities (some generators allow numeric priorities instead of textual order), and longest-then-priority (the standard) vs priority-then-longest (PEG-style ordered choice, where the first rule that matches wins regardless of length).
• Keyword lookup after the fact (hand-written lexers): scan an identifier, then consult a keyword table (Lesson 1.8); priority becomes "keywords win when the whole identifier is a keyword".

Reps' linear-time maximal munch

• Bounded-backup analysis (flex -b): detect at generation time which states can back up, and how far; if bounded, the naive algorithm is linear with constant \(b\).
• Tokenization by regular-expression parsing (Sulzmann–Lu POSIX submatching with derivatives [SL14]): compute the longest-match split of a whole input as one POSIX parse of \((r_1 \mid \cdots \mid r_k)^{*}\), whose disambiguation rule is maximal munch; linear in the input for a fixed expression.

7. In real compilers

Maximal munch

• Clang clang/lib/Lex/Lexer.cpp — the lookahead ladders in LexTokenInternal ('+', '<', '.' cases); the <:: exception is in the '<' case (LLVM 23.1.2) [CLANG-Lexer]; box in §2.
• Pebble spec §3.6 and solutions/pebble/lib/Lex/src/Lexer.cpp (&-, <<, ..).

Find where LLVM does it. In clang/lib/Lex/Lexer.cpp at llvmorg-23.1.2, find the comment quoting "C++0x [lex.pptoken]p3" in LexTokenInternal. Question: what does Clang return for <:: when the next character is neither : nor >? (Quiz llvm-lex-pptoken-exception.)

Rule priority

• flex: textual order, and the "rule cannot be matched" warning (flex 2.6.4) [FLEX-Manual]; box in §2.
• re2c: the same convention; re2c also warns about unreachable rules.
• The course ★ lab: labs/ch01-regex/inputs/pebble.lexspec lists the 21 keywords before identifier.

Reps' linear-time maximal munch

• flex -b generates lex.backup (flex 2.6.4) [FLEX-Manual]; box in §2. We know of no production lexer that implements Reps' table: bounded backup makes it unnecessary.
• The course oracle tools/course/lib/regex.py — maximal_munch and maximal_munch_reps; the maximal-munch drill (hard) asks for the naive read count.

8. Comparison

Technique	Power / precision	Speed	Output / error quality	Implementation effort	Typical use
Maximal munch	deterministic; may miss a valid tokenization	\(O(n)\) with bounded backup, \(\Theta(n^{2})\) worst	predictable for programmers; errors surface in the parser (a+++++b)	trivial on a DFA	every lexer
Rule priority	resolves equal-length ties	free at run time	generators can warn about dead rules	trivial	keywords vs identifiers
Reps' memoized munch	same tokens as maximal munch	\(O(\lvert Q \rvert n)\) worst	same	small (a failure table)	theory; tools that accept arbitrary rule sets

Choose maximal munch with priority always; it is what language specifications mean. Add Reps' memoization when users supply arbitrary rule sets (a lexer generator library, a regex tokenizer) and you cannot bound the backup.

9. Assessment

Technique	Quiz ids	Drill	Flashcard tag	Exercises
Maximal munch	munch-tokens, llvm-lex-pptoken-exception	./course drill maximal-munch	maximal-munch	E2
Rule priority	priority-order, munch-tokens	./course drill maximal-munch --difficulty easy	rule-priority	Lab L7 ★
Reps' linear-time maximal munch	reps-reads, munch-quadratic	./course drill maximal-munch --difficulty hard (asks the naive read count)	reps	—

Pitfall

Maximal munch is not "the tokenization the parser needs". It is local and greedy; when it disagrees with the grammar (a+++++b, C++ >>), the fix is either a special case in the lexer or a parser that splits tokens, never a smarter global search in the lexer.

References

See the chapter references.