5.3 Longest Match, Lexer Mode, and Generators: How Multiple Rules Collaborate

When multiple token rules can match the current position, the Tower's lexer must apply a fixed set of rules to resolve the conflict.

A single token rule is straightforward. The challenge arises from rule competition: = and == can both start at the same position, if shares the shape of an identifier, and / might be a division operator or could begin a comment. The lexer must establish a deterministic rule set to handle such conflicts.

Learning Objectives

• Accurately apply maximal munch with length precedence;
• Understand why a composite automaton must track the final accepting state;
• Use lexer mode to parse strings, comments, and interpolations;
• Evaluate the real trade-offs between hand-written and generated scanners.

1. Longest match is not "the first rule that matches"

A lexer typically selects the longest prefix that matches, also known as maximal munch. If multiple rules match prefixes of the same length, the token type is determined by rule order or explicit precedence.

Consider the following rules:

KW_IF       "if"
IDENT       [A-Za-z_][A-Za-z0-9_]*
EQUAL       "=="
ASSIGN      "="

Results:

Input prefix	Result	Reason
if	KW_IF	Two rules match the same length; keyword rule takes precedence
ifx	IDENT(ifx)	Identifier matches a longer prefix
==	EQUAL	Two-character prefix is longer than one-character
=	ASSIGN	Only the single-character rule accepts this input

2. A DFA Scanner Must Remember Its Last Accepting State

After combining all rules, a DFA state may mark one or more token kinds. The scanning process proceeds as follows:

1. Record the starting position of the token;
2. Advance as far as possible along the DFA;
3. Whenever reaching an accepting state, save the current position and the highest-priority token kind;
4. Upon encountering a character with no transition, return to the last accepting position;
5. If no accepting state is ever reached, emit an error and consume the minimal safe unit.

If rules involve competing prefixes such as 1. and 1..2, the scanner might accept 1 and then attempt further matching, ultimately failing and reverting to the last accepting position. In contrast, ifx will not revert to if, because the identifier state remains accepting throughout and occupies a farther position.

3. flex Rules and Actions

A simplified flex file:

%option noyywrap nodefault yylineno

%{
#include "tokens.h"
%}

IDENT_START    [A-Za-z_]
IDENT_CONT     [A-Za-z0-9_]

%%
"if"                            return TOK_KW_IF;
{IDENT_START}{IDENT_CONT}*       return TOK_IDENTIFIER;
[0-9]+                          return TOK_INTEGER;
"=="                            return TOK_EQUAL;
"="                             return TOK_ASSIGN;
[ \t\r\n]+                     /* skip trivia */
.                               return TOK_ERROR;
%%

Flex uses longest match; when matches are of equal length, earlier rules take precedence. Therefore, keyword rules are placed before identifier rules. The final . provides a visible error path, while nodefault prevents unmatched characters from being silently echoed back.

The generator can compile rules into NFA/DFA forms and table-driven C code, but it does not decide for you: Unicode specifications, token values, source positions, diagnostics, mode handling, memory ownership, or the parser interface.

4. Mode Incorporating Finite Context into State

String interpolation example:

"hello ${user.name}"

At least involves:

DEFAULT → encounter opening quote → STRING
STRING  → encounter ${     → INTERPOLATION
INTERPOLATION → match corresponding } → STRING
STRING  → encounter closing quote → DEFAULT

Mode remains a finite-state control mechanism. If nested braces are allowed within interpolation expressions, counting or parser collaboration is required, relying on a single boolean mode is insufficient.

Mechanisms like flex start conditions or ANTLR lexer modes can restrict a set of rules to apply only within a specific mode. Hand-written scanners typically use enums and branching logic to manage state transitions.

5. C Preprocessing Cannot Be Reduced to "Everything Completed Before Lexical Analysis"

The C translation process involves multiple stages: preprocessing tokens, macro expansion, header file inclusion, and subsequent token transformation. The preprocessor itself must recognize preprocessing tokens; #include does not simply vanish before the lexer begins, its presence and behavior are integral to the preprocessing phase.

When designing a teaching language, a simplified pipeline of "preprocess tokens into characters, then perform standard lexical analysis" can be adopted. However, this approach should be clearly labeled as an architectural choice, not a complete realization of the C standard model.

Macro expansion can cause a token's physical location to differ from its logical origin. High-quality diagnostics require both expansion span and spelling span to simultaneously identify where a macro call occurs and where its definition originates.

6. Hand-Write or Generate

Dimension	Hand-Written Scanner	Generator
Rule Expression	Direct control flow, fully customizable	Declarative, centralized
Complex State	Easily customized with mode and special literals	Relies on tooling mechanisms and action code
Automaton Correctness	Responsibility lies with the developer	Regular expression correctness is handled by the tool
Build Dependencies	Minimal	Requires fixed tool versions and defined generation workflows
Debugging	Line-by-line traceability available	Requires understanding of rules, generated code, and runtime behavior
Performance	Can be optimized for specific workloads	Performance depends on representation and options; no inherent speed advantage

"The generator is always at least two orders of magnitude faster than hand-written code" is not a general rule. Factors such as branch prediction, character classification, table compression, caching, token actions, and input methods all influence performance. Real source code corpora should be used to benchmark throughput, latency, and memory usage.

7. Lexer and Parser Interface

Common pull-based interface:

parser calls next_token()
lexer returns kind + span + value
parser requests the next token when needed

This approach has low memory overhead and simple control flow. IDEs may need to cache tokens to enable incremental lexical analysis, and parallel tools might pregenerate a token buffer.

The mode can sometimes be influenced by parser feedback. For example, / in certain languages might enable regular literal syntax or could indicate a division operator. Such feedback increases coupling, so state transitions and recovery rules should be explicitly defined in the interface contract.

8. Resource and Security Boundaries

When dealing with untrusted source code, the lexer should enforce limits on:

• Total file size;
• Length of individual tokens;
• Nesting depth of comments or interpolations;
• Number of digits in numeric literals;
• Number of diagnostic messages generated;
• Depth of the mode stack.

Even though the automaton's scanning process is linear, constructing a numeric value with billions of digits could consume enormous CPU and memory resources. Token boundary detection and value conversion should be separated, with independent budgets applied at each stage.

Common Misconceptions

• Longest match takes precedence over keywords: Length is compared first; only if lengths are equal are rule priorities evaluated.
• Generators automatically resolve all lexer issues: They primarily generate matching logic; interfaces and diagnostics still require explicit design.
• Mode can handle arbitrary nesting: A finite mode does not imply an unbounded stack.
• Linear scanning is immune to denial-of-service: Extremely long tokens, value transformations, and diagnostic flooding still incur performance costs.

Exercise

1. Write rules for > >= >> >>= and list the longest matching result for each input.
2. Implement a keyword-and-identifier-length-equality test using flex or another generator, ensuring equal priority.
3. Design a state diagram for string interpolation modes and explain how nested braces are delegated for processing.
4. Define five resource limits for the lexer and specify diagnostic strategies to trigger when those limits are exceeded.

Summary

The core of a multi-rule lexer is a repeatable decision sequence: longest prefix first, with ties broken by rule priority. Mode handling manages limited context, while generators build the automaton structure. Source location tracking, error recovery, and resource constraints remain the compiler author's responsibility.

The next chapter takes the token stream and reconstructs the linear sequence into a tree, ensuring that even malformed input produces sufficient structure for subsequent diagnostics.