5.3 Longest Match, Lexer Mode, and Generators: How Multiple Rules Collaborate
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
- Apply maximal munch and break equal-length ties by rule priority;
- Understand why a composite automaton must track the last accepting position;
- Use lexer modes to scan 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:
- Record the starting position of the token;
- Advance as far as possible along the DFA;
- Whenever reaching an accepting state, save the current position and the highest-priority token kind;
- At a missing transition, a trap state from which no accepting state is reachable, or EOF, return to the last accepting position and restore its line and column;
- If no accepting state is ever reached, emit an error and consume the minimal safe unit.
Suppose the rules are integer [0-9]+, decimal [0-9]+\.[0-9]+, and dot \.. On 1..2, the scanner reads the first dot while trying the decimal rule, then fails at the second dot and returns to the end of integer 1. The full result is INTEGER(1), DOT, DOT, INTEGER(2). By contrast, ifx never returns to if: the identifier state keeps accepting at later positions. Rollback restores a saved position snapshot, including line and column, not just the cursor.
3. flex Rules and Actions
These three files form a runnable ASCII example. Save the rules as scanner.l:
%option noyywrap nodefault yylineno noinput nounput never-interactive
%{
#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;
<<EOF>> return TOK_EOF;
%%Add the shared token definitions and the driver, which reads standard input:
/* tokens.h */
#ifndef TOKENS_H
#define TOKENS_H
enum TokenKind {
TOK_EOF, TOK_ERROR, TOK_IDENTIFIER, TOK_INTEGER,
TOK_KW_IF, TOK_EQUAL, TOK_ASSIGN
};
#endif/* driver.c */
#include <stdio.h>
#include "tokens.h"
int yylex(void);
extern char *yytext;
extern int yyleng;
int main(void) {
const char *names[] = {
"EOF", "ERROR", "IDENTIFIER", "INTEGER", "KW_IF", "EQUAL", "ASSIGN"
};
int kind;
while ((kind = yylex()) != TOK_EOF) {
printf("%s ", names[kind]);
if (fwrite(yytext, 1, (size_t)yyleng, stdout) != (size_t)yyleng) return 1;
if (putchar('\n') == EOF) return 1;
}
return fflush(stdout) == EOF ? 1 : 0;
}With flex and a C compiler installed, run these commands in the directory containing the three files (tested with flex 2.6.4):
flex -o lex.yy.c scanner.l
cc -std=c17 -Wall -Wextra lex.yy.c driver.c -o scan
printf 'if ifx == = 12 @\n' | ./scanKW_IF if
IDENTIFIER ifx
EQUAL ==
ASSIGN =
INTEGER 12
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.
yytext and yyleng expose the current match bytes and length; copy text that must survive the next scanner operation. This example does not produce complete token source positions: yylineno tracks the current scanning line, so a multiline token needs a separately saved starting line.
A generator compiles rules into automata and table-driven C code. Unicode policy, token values, source positions, diagnostics, modes, ownership, and the parser interface still need explicit decisions.
4. Modes Add Finite Context to State
String interpolation example:
"hello ${user.name}"The state transitions include:
DEFAULT → encounter opening quote → STRING
STRING → encounter ${ → INTERPOLATION
INTERPOLATION → match corresponding } → STRING
STRING → encounter closing quote → DEFAULTMode remains a finite-state control mechanism. If nested braces are allowed within interpolation expressions, counting or parser collaboration is required. A single boolean mode is insufficient.
Flex start conditions control which rules are active. An inclusive %s condition also enables unqualified rules; an exclusive %x condition normally enables only rules qualified for that condition. The default rule has separate behavior, so define error and EOF handling explicitly. Hand-written scanners typically use an enum and branches.
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.
When designing a teaching language, a simplified pipeline of "preprocess into a character stream, then perform 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. Diagnostics need both a spelling location and an expansion location 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 | Tool generates matching code; rule intent still needs validation |
| 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 neededThis 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 a regular-expression literal 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.
One forward DFA walk is linear; an entire lexer with rollback is not automatically linear. With only rules a and a*b, a long input of a characters may be scanned to EOF before falling back to a single a token, then scanned again from each following position. The repeated work is quadratic. Examine rule-induced backup, and use a total scanning-step budget or an implementation that avoids repeating failed searches where needed.
Even with linear boundary detection, constructing an integer with billions of digits can consume substantial CPU and memory. Token boundary detection and value conversion can have separate budgets.
Common Misconceptions
- Longest match always prefers 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
- Write rules for
> >= >> >>=and list the longest matching result for each input. - Use flex or another generator to test keyword priority when a keyword and identifier match the same length.
- Design a state diagram for string interpolation modes and explain how nested braces are delegated for processing.
- 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.