3.2 Maximal Munch, Keywords, Identifiers, Literals, Comments

A lexer often has several rules that can match the same source prefix. The scanner needs a deterministic policy for choosing one token. Most programming languages use maximal munch, also called longest match: from the current position, choose the longest prefix accepted by any token rule. If several rules match the same longest prefix, use rule priority or a keyword table.

This policy is not a minor detail. It decides whether ifx is one identifier or IF followed by IDENT(x). It decides whether == is one equality operator or two assignment operators. It decides how numeric and string boundaries behave. The parser assumes the lexer has already made these decisions consistently.

Longest Match Before Priority

Suppose we have:

IF    = if
IDENT = [A-Za-z_][A-Za-z0-9_]*
EQEQ  = ==
EQ    = =

For input ifx, both IF and IDENT begin matching at the current position, but IDENT matches length 3 while IF matches length 2. Longest match chooses IDENT(ifx). For input if, both IF and IDENT match length 2. Now priority decides. Many lexers put keyword rules before IDENT, or scan IDENT first and then rewrite it through a keyword table.

The priority rule should be explicit in the language implementation. Hidden priority bugs are painful because tokenization errors create misleading parser errors. If ifx is split incorrectly, the parser may complain about an unexpected identifier after an if, even though the real bug is in the lexer.

Keywords and Identifiers

Keywords are often the most visible example of lexical conflict. There are two common strategies.

First, a lexer can give keyword patterns higher priority:

IF     = if
ELSE   = else
RETURN = return
IDENT  = [A-Za-z_][A-Za-z0-9_]*

Second, it can scan every keyword-shaped word as IDENT, then consult a keyword table:

kind = keywords.get(lexeme) ?? IDENT

The table approach is easy to extend and avoids writing many separate automaton accepting labels. The priority approach can be natural in lexer generators. Both are valid. The essential tests are the same: if should become a keyword, while ifx, if_, and if2 should remain identifiers.

Literals and Comments Are Stateful Edges

Numeric literals, string literals, and comments are still lexical structures, but they often require careful state behavior.

A numeric scanner must decide whether:

2.

is a floating literal, an integer followed by dot, or an invalid decimal. A string scanner must handle escapes, closing quotes, and newlines. A comment scanner must know whether // ends at newline, whether /* */ exists, and whether nested block comments are allowed.

These decisions directly affect diagnostics. An unterminated string is not just "invalid text." The compiler should usually point at the opening quote, show the scanned range, and explain whether the string reached a newline or end of file before closing. An unterminated block comment may consume the rest of the file, so recovery policy must be conservative.

Boundary Cases Define the Language

Write a decision table before coding token rules. For a language with dot member access and decimal numbers, decide all of 1., .5, 1..2, a.b, and 1e+. Is 1. a float or an integer followed by dot? Is .5 legal? Does 1..2 mean a range operator after an integer? The answer must be reflected in ordered scanning states and tests; “longest match” only chooses among patterns you have deliberately made legal.

Strings need similarly explicit choices: permitted escapes, raw versus cooked strings, continuation across a newline, Unicode escapes, and whether an invalid escape consumes to the closing quote or stops immediately. Block comments force a language decision about nesting. A regex-like /* .*? */ intuition is not a sufficient implementation model when comments nest or when diagnostics must point back to the opening delimiter.

Test Matrix

• Adjacent operators: =, ==, ===, >>, >>=.

• Keyword boundaries: if, ifx, _if, if2.

• Literal failures: invalid digit, incomplete exponent, bad escape, newline/EOF before quote.

• Comment adjacency: /, //x, /*x*/y, /* unterminated.