5.3 最长匹配、Lexer Mode 与生成器：多条规则怎样协作

单条 token 规则很容易。困难来自规则竞争：= 与 == 都能从同一位置开始，if 同时具有标识符形状，/ 可能是除法，也可能开启注释。lexer 必须给这种竞争一套确定规则。

本课目标

• 准确执行 maximal munch 与同长优先级；
• 理解组合自动机为什么要记录最后接受状态；
• 使用 lexer mode 处理字符串、注释和插值；
• 判断手写扫描器与生成器的真实取舍。

1. 最长匹配不是“先命中的规则”

从当前位置开始，lexer 通常选择能匹配的最长前缀，也叫 maximal munch。若多条规则匹配同样长的前缀，再按规则顺序或显式优先级决定 token kind。

设规则：

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

结果：

输入前缀	结果	原因
if	KW_IF	两条规则同长，关键字优先
ifx	IDENT(ifx)	标识符匹配更长
==	EQUAL	两字符比一字符长
=	ASSIGN	只有一字符规则接受

2. DFA 扫描器要记住最后一次接受

组合所有规则后，一个 DFA 状态可能标记一个或多个 token kind。扫描流程：

1. 记录 token 起点；
2. 沿 DFA 尽可能前进；
3. 每到接受状态，保存当前位置与最高优先级 kind；
4. 遇到无转移字符、不能再通往接受状态的陷阱状态或 EOF 时，回到最后接受位置，同时恢复行列号；
5. 若从未到达接受状态，发射错误并消费最小安全单位。

例如，规则是整数 [0-9]+、小数 [0-9]+\.[0-9]+ 和点号 \.。扫描 1..2 时，读过第一个点后仍在尝试小数，第二个点却让尝试失败，于是回退到整数 1 的末尾。完整结果是 INTEGER(1), DOT, DOT, INTEGER(2)。ifx 不会回到 if，因为标识符状态一路保持接受且位置更远。回退用的是此前保存的位置快照，不能只移动游标而把行列号留在未来。

3. flex 规则与动作

下面三个文件构成一个可运行的 ASCII 示例。先保存 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;
%%

补齐共享 token 定义和读取标准输入的驱动：

/* 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;
}

安装 flex 和 C 编译器后，在这三个文件所在目录运行（此例已用 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' | ./scan

KW_IF if
IDENTIFIER ifx
EQUAL ==
ASSIGN =
INTEGER 12
ERROR @

flex 采用最长匹配；同样长度时，较早规则优先。因此关键字规则放在标识符之前。最后的 . 提供可见错误路径，nodefault 避免未匹配字符被默认回显。

yytext 与 yyleng 提供当前匹配的字节和长度；需要长期保存的文本应在下一次扫描操作前复制。示例未生成 token 的完整源位置：yylineno 记录当前扫描行，跨行 token 的起始行仍需单独保存。

生成器可以把规则编译成自动机与表驱动 C 代码，但不会替你决定 Unicode 规范、token value、源位置、诊断、mode、内存所有权和 parser 接口。

4. Mode 把有限上下文纳入状态

字符串插值示例：

"hello ${user.name}"

至少涉及：

DEFAULT → 读到开引号 → STRING
STRING  → 读到 ${     → INTERPOLATION
INTERPOLATION → 匹配对应 } → STRING
STRING  → 读到闭引号 → DEFAULT

mode 仍是有限状态控制。插值表达式内部若允许嵌套花括号，还需计数或由 parser 协作，不能只靠一个布尔 mode。

flex 的 start conditions 可以控制规则在哪种模式中生效：%s 是包含模式，未标注条件的规则仍参与；%x 是排他模式，通常只启用该条件标记的规则。默认规则另有行为，必须明确错误与 EOF 的处理。手写扫描器通常用枚举和分支表达。

5. C 预处理不能概括成“词法之前全部完成”

C 翻译有预处理 token、宏展开、头文件包含和后续 token 转换等多个阶段。预处理器本身也需要识别预处理 token；#include 不是简单地在 lexer 启动前凭空消失。

实现教学语言时可以采用“先预处理成字符，再普通词法分析”的简化管线，但应标明这是架构选择，不是完整 C 标准模型。

宏展开还会让 token 的物理位置和逻辑来源不同。高质量诊断需要 spelling location（拼写来源位置）与 expansion location（展开位置），才能同时指出宏调用位置和定义来源。

6. 手写还是生成

维度	手写扫描器	生成器
规则表达	控制流直接、可定制	声明式、集中
复杂状态	mode 与特殊字面量易定制	依赖工具机制与动作代码
自动机正确性	自己负责	工具生成匹配实现，规则含义仍需验证
构建依赖	少	需固定工具版本与生成流程
调试	可逐行跟踪	要理解规则、生成代码和运行时
性能	可针对工作负载优化	表示与选项决定，不保证天然更快

“生成器一定比手写快一两个数量级”没有普遍依据。分支预测、字符分类、表压缩、缓存、token 动作和输入方式都会影响结果。应使用真实源代码语料基准测试吞吐、延迟和内存。

7. Lexer 与 parser 的接口

常见拉取式接口：

parser 调用 next_token()
lexer 返回 kind + span + value
parser 需要时请求下一个

优点是内存小、控制简单。IDE 可能需要缓存 token，以便增量重词法分析；并行工具也可能先生成 token buffer。

mode 有时由 parser 反馈。例如 / 在某些语言里可能开启正则字面量，也可能是除法。反馈会增加耦合，应把状态转换和恢复规则写进接口契约。

8. 资源与安全边界

面对不受信任源码，lexer 应限制：

• 文件总大小；
• 单个 token 长度；
• 注释或插值嵌套深度；
• 数值字面量位数；
• 诊断数量；
• mode 堆栈深度。

一次 DFA 前进是线性的，不代表带回退的整次词法分析必然线性。例如规则只有 a 与 a*b，输入是 a 的长串：每次都可能尝试到 EOF，再退回只发射一个 a，重复扫描使总工作量达到二次量级。应检查规则造成的回退，必要时限制总扫描步数或采用能避免重复失败搜索的实现。

即使边界识别已保证线性，构造一个含数亿位的整数值仍可能消耗巨大 CPU 和内存。token 边界识别与值转换可分开，并在两处各设预算。

常见误区

• 最长匹配会优先关键字：先比较长度，同长才比较规则优先级。
• 生成器自动解决全部 lexer 问题：它主要生成匹配核心，接口与诊断仍需设计。
• mode 可以处理任意嵌套：有限 mode 不等于无界栈。
• 线性扫描不会被拒绝服务：超长 token、值转换和诊断洪泛仍有成本。

练习

1. 为 > >= >> >>= 写规则并列出每个输入的最长匹配结果。
2. 用 flex 或其他生成器实现关键字与标识符同长优先级测试。
3. 设计字符串插值的 mode 状态图，并说明嵌套花括号交给谁处理。
4. 为 lexer 制定五项资源上限及触发后的诊断策略。

小结

多规则 lexer 的核心是可重复的决策顺序：最长前缀优先，同长时按规则优先级。mode 处理有限上下文，生成器负责自动机骨架，源位置、错误恢复与资源限制仍是编译器作者的工作。

下一章接过 token 流，把线性序列恢复成树，并让错误输入也能产出足够结构供后续诊断使用。

参考资料

• flex: matching rules
• flex: start conditions
• Clang SourceManager: spelling and expansion locations