词法扫描的最长匹配与优先级

形式陈述

词法扫描的输入是字符序列 $s[0..n)$ ，输出是带类别、原文区间和必要字面量值的 token 序列。先固定字符编码层已经完成；本页字母表为 ASCII，位置是字符索引，区间统一左闭右开。Unicode 归一化、字符串转义、缩进和嵌套注释各有额外状态，不暗含在此模型中。

词法规格是一组有顺序的正则语言 $(L_1,\ldots,L_k)$ 。每一项还带“发出类别”或“忽略空白”的动作，较小下标优先。所有 $L_i$ 必须排除空字：否则一次成功可能不推进输入。处在未处理位置 $p$ 时，取所有满足 $s[p..q)\in L_i$ 的 $q>p$ ；选择最大的 q，再在该 q 上选择最小的 i。没有候选就报告位置 p 的词法错误。优先级只比较同样长的候选，不能让短关键字截断长标识符。

把这些正则语言合为一台带输出标签的 DFA。一个接受态可以代表多个规则，预先记录其中最小的规则编号；非接受态记录空标签。自动机构造复用子集构造，保留原 NFA 接受态的规则身份；普通“接受/拒绝”一位信息不足以决定输出类别。

text

scan_one(p):
  q = initial_state; j = p; last = none
  while j < n:
    q_next = transition(q, s[j])
    if q_next is dead: break
    q = q_next; j = j + 1
    if label(q) exists: last = (j, label(q))
  if last is none: fail at p
  (end, rule) = last
  perform rule's action on s[p:end]
  return end

外层从 p=0 重复调用，直到 p=n，然后发出 EOF。忽略空白也必须返回新的 end。循环中的 j 可以越过最后接受位置，下一轮 token 从 end 重新开始，而不是从失败处 j 开始。EOF 不是默认成功：若当前从未接受，则仍为错误。

循环不变量有两部分。状态 q 恰等于 DFA 读过 $s[p..j)$ 后的状态；last 若存在，记录此前所有接受前缀中最长的一个以及该长度最高优先级规则。每次转移保留第一部分，遇接受态覆盖 last 保留第二部分。到死状态后不存在更长可接受延伸；到输入末端也已检查完全部前缀，所以返回正好实现规格。每次成功至少推进一个字符，有限输入保证外层终止。

直觉

正则表达式回答“一段字符是否属于某类 token”，扫描器还得回答“这一段在哪里结束”。读到可以接受的位置，未必该立刻停下：= 后面还可能有另一个 =，let 后面还可能跟着 x。last 就是允许继续试探、又能退回的书签。

优先级回答另一个问题。let 既符合关键字规则，也符合标识符规则；它们占用相同三个字符时，选择关键字。letx 占四个字符，因而先由长度胜出，不应被拆成关键字和一个字母。

例子与边界

同一段输入，三个决策

按优先级规定：关键字 let；标识符 [A-Za-z_][A-Za-z_0-9]*；整数 [0-9]+；==；=；;；非空空白。考虑 let letx=10==2;，字符位置依次为 0 到 14。

原文区间	文本	发出类别	理由
[0,3)	let	LET	与 ID 同长，关键字优先
[3,4)	空格	忽略	消耗一个字符
[4,8)	letx	ID	比关键字 let 更长
[8,9)	=	EQ	后面是数字，不能继续成 ==
[9,11)	10	INT	第二个数字延长接受前缀
[11,13)	==	EQEQ	比单个 = 更长
[13,14)	2	INT	在分号前停止
[14,15)	;	SEMI	单字符 token

在位置 11，扫描第一个等号时 last=(12,EQ)，第二个等号后改成 (13,EQEQ)。随后数字使该分支进入死状态，发出 [11,13)，下一 token 仍从 13 开始。若“第一次接受就停”，会发出两个 EQ；若失败时把那个数字也吞掉，会丢失 INT 2。

输入 let @ 先得到 LET 和空白，随后在位置 4 失败；不能把 @ 当作空白跳过。输入 123abc 在本规格下合法地切成 INT 123、ID abc，是否允许二者相邻由后续语法决定。若语言要把整个串报成非法数值，应修改词法规格；扫描器不会为了帮助解析成功而回头选择更短 token。

DFA 的线性执行不等于整段扫描线性

令规则为 a 和 a*b，输入为 $a^m$ 。从每个起点出发，第一字符已允许 token a，扫描器仍会一直试到 EOF，期待最后出现 b；失败后只提交一个 a。成功转移总数为 $m+(m-1)+\cdots+1=m(m+1)/2$ 。例如 m=4，得到四个 a token，却执行 10 次成功转移。每次查表常数时间，整个算法仍为二次。

设实际转移尝试数为 T，输出 token 数为 t。上面的实现时间为 $O(T+t)$ ，随机访问输入之外只需常数扫描状态；若保存完整 token 文本而不是区间，复制成本还需按复制的字符数收费。固定 DFA 下最坏 T 为 $O(n^2)$ 。流式输入还必须缓冲尚不能提交的前瞻，不能把随机访问数组的常数附加空间结论照搬。

Reps 的线性扫描方法记录“状态、输入位置”这类已知无法再到接受位置的失败配置，避免反复探索同一后缀。[2] 这是另一项算法优化；本页 checker 实测回退次数，不声称已经实现该优化。固定规格若能证明最大回退长度为常数，才可直接给本页简单算法线性界。

推论与应用

词法输出为解析提供类别序列和源位置，而不是直接提供绑定关系。两处 ID 都写成 x，并不表示它们绑定到同一声明；那是名字解析的工作。保留 span 可把后续未绑定错误重新指向源文件，即使空白已不进入 AST。

迁移任务：在上述规格加入 >= 与 >，扫描 letx>=10。答案为 ID [0,4)、GE [4,6)、INT [6,8)；关键字 LET 没有胜出。把 ID 规则移到 LET 前面，letx 不变而独立 let 变成 ID。再让任一规则接受空字，指出为什么外层推进证明失效，而不能仅用“EOF 处理过了”掩盖死循环。

源程序到显式求值次序的终点任务给出完整源串与 token 检查器，并复用已有解析接口。本页不新建第二套 LL/LR 理论。

参考资料

[1] Andrew Myers，Cornell CS 4120，Spring 2023，Automating Lexical Analysis，节 “Building an efficient lexer”：保留 token 优先级、最后接受位置与回退。本文位置表及 a | a*b 反例为独立教学实例。

[2] Thomas Reps，Maximal-Munch Tokenization in Linear Time，ACM TOPLAS 20(2)，1998，259–273，DOI。本页仅以 [1] 中明确给出的失败配置记忆方法说明改进方向，未复述或声称重证原文算法。

形式陈述 ​

同一段输入，三个决策 ​

DFA 的线性执行不等于整段扫描线性 ​

反向链接

形式陈述

同一段输入，三个决策

DFA 的线性执行不等于整段扫描线性