5.3 最长匹配、Lexer Mode 与生成器：多条规则怎样协作
当多条 token 规则都能匹配当前位置时，高塔的扫描器必须用一套固定规则裁决竞争。
单条 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。扫描流程：
- 记录 token 起点；
- 沿 DFA 尽可能前进；
- 每到接受状态，保存当前位置与最高优先级 kind；
- 遇到无转移字符时，回到最后接受位置；
- 若从未到达接受状态，发射错误并消费最小安全单位。
若规则包含 1. 与 1..2 之类前缀竞争，机器可能在接受 1 后继续尝试，最终失败再回到最后接受点。ifx 则不会回到 if，因为标识符状态一路保持接受且位置更远。
3. flex 规则与动作
一个简化 flex 文件：
%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 采用最长匹配；同样长度时，较早规则优先。因此关键字规则放在标识符之前。最后的 . 提供可见错误路径，nodefault 避免未匹配字符被默认回显。
生成器可以把规则编译成 NFA/DFA 与表驱动 C 代码，但不会替你决定：Unicode 规范、token value、源位置、诊断、mode、内存所有权和 parser 接口。
4. Mode 把有限上下文纳入状态
字符串插值示例：
"hello ${user.name}"至少涉及：
DEFAULT → 读到开引号 → STRING
STRING → 读到 ${ → INTERPOLATION
INTERPOLATION → 匹配对应 } → STRING
STRING → 读到闭引号 → DEFAULTmode 仍是有限状态控制。插值表达式内部若允许嵌套花括号，还需计数或由 parser 协作，不能只靠一个布尔 mode。
flex start conditions、ANTLR lexer modes 等机制可以限制某组规则只在特定 mode 生效。手写扫描器则通常用枚举和分支表达。
5. C 预处理不能概括成“词法之前全部完成”
C 翻译有预处理 token、宏展开、头文件包含和后续 token 转换等多个阶段。预处理器本身也需要识别预处理 token；#include 不是简单地在 lexer 启动前凭空消失。
实现教学语言时可以采用“先预处理成字符，再普通词法分析”的简化管线，但应标明这是架构选择，不是完整 C 标准模型。
宏展开还会让 token 的物理位置和逻辑来源不同。高质量诊断需要 expansion span 与 spelling span，才能同时指出宏调用位置和定义来源。
6. 手写还是生成
| 维度 | 手写扫描器 | 生成器 |
|---|---|---|
| 规则表达 | 控制流直接、可定制 | 声明式、集中 |
| 复杂状态 | mode 与特殊字面量易定制 | 依赖工具机制与动作代码 |
| 自动机正确性 | 自己负责 | 工具负责正则部分 |
| 构建依赖 | 少 | 需固定工具版本与生成流程 |
| 调试 | 可逐行跟踪 | 要理解规则、生成代码和运行时 |
| 性能 | 可针对工作负载优化 | 表示与选项决定，不保证天然更快 |
“生成器一定比手写快一两个数量级”没有普遍依据。分支预测、字符分类、表压缩、缓存、token 动作和输入方式都会影响结果。应使用真实源代码语料基准测试吞吐、延迟和内存。
7. Lexer 与 parser 的接口
常见拉取式接口：
parser 调用 next_token()
lexer 返回 kind + span + value
parser 需要时请求下一个优点是内存小、控制简单。IDE 可能需要缓存 token，以便增量重词法分析；并行工具也可能先生成 token buffer。
mode 有时由 parser 反馈。例如 / 在某些语言里可能开启正则字面量，也可能是除法。反馈会增加耦合，应把状态转换和恢复规则写进接口契约。
8. 资源与安全边界
面对不受信任源码，lexer 应限制：
- 文件总大小；
- 单个 token 长度；
- 注释或插值嵌套深度；
- 数值字面量位数；
- 诊断数量；
- mode 堆栈深度。
即使自动机扫描是线性的，构造一个含数亿位的整数值也可能消耗巨大 CPU 和内存。token 边界识别与值转换可分开，并在两处各设预算。
常见误区
- 最长匹配会优先关键字：先比较长度，同长才比较规则优先级。
- 生成器自动解决全部 lexer 问题：它主要生成匹配核心，接口与诊断仍需设计。
- mode 可以处理任意嵌套：有限 mode 不等于无界栈。
- 线性扫描不会被拒绝服务：超长 token、值转换和诊断洪泛仍有成本。
练习
- 为
> >= >> >>=写规则并列出每个输入的最长匹配结果。 - 用 flex 或其他生成器实现关键字与标识符同长优先级测试。
- 设计字符串插值的 mode 状态图，并说明嵌套花括号交给谁处理。
- 为 lexer 制定五项资源上限及触发后的诊断策略。
小结
多规则 lexer 的核心是可重复的决策顺序：最长前缀优先，同长时按规则优先级。mode 处理有限上下文，生成器负责自动机骨架，源位置、错误恢复与资源限制仍是编译器作者的工作。
下一章接过 token 流，把线性序列恢复成树，并让错误输入也能产出足够结构供后续诊断使用。