2.5 词法分析中的 Regex 到 NFA 到 DFA

现在可以把理论连接到第一个真实编译阶段了。词法分析器（lexer）接收源文本并生成词法单元（token）。词法分析器生成器（lexer generator）接收词法单元种类的正则表达式，并生成执行扫描的代码。标准路线是：

token regexes
  -> NFA fragments
  -> combined NFA
  -> DFA by subset construction
  -> minimized/compressed DFA
  -> table-driven or code-generated scanner

并不是每个生产词法分析器都会在运行时字面执行所有步骤，手写词法分析器也可能直接使用条件判断而不是生成表。但是这条路线解释了为什么正则表达式、NFA、DFA、优先级（priority）和最长匹配（longest match）必须放在一起理解。

从 Regex 构造 NFA

Thompson 构造（construction）通过组合片段来构造 NFA。每个片段有一个入口和一个出口。符号片段消耗一个字符。并（union）增加一个新入口，并用 ε 边分支到不同片段。连接（concatenation）把一个片段的出口连接到下一个片段的入口。星号（star）增加 ε 边，允许零次、一次或多次重复。

对于 regex：

(a | b)* abb

构造先从 a 和 b 的片段开始，把它们组合成并，再把并包进星号，然后连接 a、b、b 三个片段。结果不一定很小，但它容易正确构造。这个阶段正确性比漂亮更重要，因为后续子集构造和最小化可以重新塑造自动机。

合并词法单元规则

词法分析器通常不会为每个词法单元单独构造一个自动机然后分别尝试。常见构造会创建一个新的合并开始状态，用空转移进入每个词法单元的 NFA。每个词法单元 NFA 的接受状态标记对应词法单元种类和优先级。

例如：

IF      = if
IDENT   = [A-Za-z_][A-Za-z0-9_]*
INT     = [0-9]+
EQEQ    = ==
EQ      = =
WS      = [ \t\r\n]+

合并后的 NFA 可以从同一源码位置探索所有词法单元模式。转换成 DFA 后，一个确定性机器就表示了所有相互竞争的词法单元语言。有些 DFA 状态可能对应多个 NFA 接受状态，这意味着多个词法单元规则匹配了同一个前缀。

这时就需要词法分析器策略（lexer policy）。

最长匹配与优先级

多数编程语言词法分析器使用 最长匹配（maximal munch，又称 longest match）。从当前源码位置开始，扫描器消耗能被任意词法单元规则匹配的最长前缀。如果多个规则匹配同样长的最长前缀，就使用优先级打破平局，常见方式是声明顺序。

这个策略可以避免糟糕的分词。假设输入是：

ifx

如果扫描器看到 if 就贪心返回 IF，剩下的 x 会变成 IDENT(x)。但大多数语言希望 ifx 是一个标识符。最长匹配会选择 IDENT(ifx)，因为它比 IF 更长。

再考虑：

if

IF 和 IDENT 都匹配长度 2。最长匹配无法决定，所以由优先级决定。如果 IF 优先级高于 IDENT，词法单元就是 IF。另一种常见设计是先扫描成 IDENT(if)，再查关键字表并改写成 IF。只要一致且经过测试，两种策略都合理。

扫描器输出与错误边界

词法分析器不应该只是接受或拒绝整个文件。它应该产生带源码跨度（source span）的词法单元流：

FN     "fn"     line 1, col 1..2
IDENT  "main"   line 1, col 4..7
LPAREN "("      line 1, col 8
RPAREN ")"      line 1, col 9
ARROW  "->"     line 1, col 11..12
IDENT  "int"    line 1, col 14..16

源码跨度让诊断（diagnostic）成为可能。如果词法分析器发现未知字符、未终止字符串或非法数字字面量，它应该报告问题从哪里开始，通常也要说明扫描在哪里恢复。语法分析器和类型检查器后续会依赖这些跨度生成自己的诊断。

有些词法单元规则会被跳过而不是输出。空白和注释通常会影响行列号追踪，但不会成为语法分析器可见的词法单元。某些语言中换行有语义意义，这时词法分析器必须输出换行，或者合成 INDENT、DEDENT 这样的缩进词法单元。

一个合并自动机服务多条词法单元规则

生成器通常不为每条规则单跑一个 DFA。它为每个模式建 NFA，给接受状态标记词法单元种类/优先级，再以共享开始状态的空转移合并，确定化后最小化或压缩。一个 DFA 状态可包含多条接受规则，最终选最长接受前缀中的最高优先级。

输入 >= 时机器可能先接受 >，再接受 >=，扫描器记录两个位置并返回更远者；ifx 时标识符长度三，关键字长度二，标识符在优先级前就已胜出。必须把这些调用轨迹写进测试，而不是只靠直觉。

生成扫描器提示

• 尽量压缩为字符类（character class），而不是完整 Unicode 列。

• 无规则匹配时必须清晰报错并保证前进。

• 元数据应保留规则名称/源码跨度，方便追溯谁赢了竞争。