简介：这是一份面向高校编译原理课程学习者与编译器前端入门者的词法分析器实验包，围绕北京邮电大学课程实验场景，提供从词法规则定义到分词逻辑实现的练习素材，可用于理解扫描器如何将字符流切分为标识符、关键字、常量与运算符等词素。压缩包共4个文件，以2个txt文本、1个h头文件和1个cpp源文件为主，体量约10KB，文本可承载实验说明与测试输入，头文件和源文件则对应词法分析器的核心代码结构。已有1000人学习下载，说明其在课程实验与期末复盘中有一定参考面。读者可借此梳理输入处理、符号栈管理、错误处理与测试调试等环节，结合测试样例观察分词结果，进而理解词法规则描述与实现之间的对应关系，为后续语法分析学习打基础。

1. 词法分析器：为什么最没技术含量的一步反而最难改

很多人第一次做编译原理课程实验，都会觉得词法分析器是最容易过的一关：不过是把字符流切成一个个单词，写几条正则匹配就能交差。真正写下去才会发现事情反过来了——整个前端里最难改的就是它。语法分析器报的错，八成要追溯到扫描器切错了 token；语义分析报的错，如果行列号偏了一位，整条诊断链就废了。某高校课程实验里这份词法分析器值得逐行去读的地方，不是它能跑通多少个用例，而是它把「正则式 → 状态机 → token 流」这条链路完整地摊开在源码里。你以后遇到的任何一个 lexer，不管手写还是用工具生成，本质上都是这条链路的一次具体实现，差别只在状态机是编译期算出来的还是运行期现推的。搞懂这条链路，等于拿到了读所有前端工具的钥匙。

2. 从正则到状态机：词法规则为什么必须被「编译」成 DFA

写词法规则的时候，人脑里想的是id = letter(letter|digit)*这种形式；但扫描器运行时手里拿到的不能是正则表达式，因为对每个 token 都跑一遍正则匹配，代价是「规则条数 × 回溯深度」，一条写得不好的规则就能把整个编译过程拖成多项式级的灾难。所以词法分析器真正的第一步，是把所有规则编译成一台确定有限自动机（DFA）：一次读一个字符，走一条边，绝不回头。这一步的输入是一组正则式，输出是两张表——转移表和接受表。

2.1 一条 token 规则是怎么变成一台状态机的

从正则式到自动机的经典路径是 Thompson 构造：把正则式的语法结构拆成五种基本拼装，每种拼装对应一个「片段」，片段有一个入口状态和一个唯一出口状态，片段之间用 ε 边（空转移）粘起来。字符类是一个片段，连接是两个片段首尾相接，选择是新建入口分叉、新建出口汇合，闭包是加一条回边和一条跳过边。

NFA 的存储结构不需要真的建对象图，用数组加邻接表就够了，这样后面做子集构造时遍历成本低得多：

# nfa.py —— NFA 的紧凑表示：只存边，不存状态对象 class NFA: def __init__(self): self.eps = [] # eps[s] = [t, ...] ε 转移的目标集合 self.trans = [] # trans[s] = {ch: [t, ...]} 字符转移 self.accept = [] # accept[s] = token_id 或 -1，接受态打标 self.start = 0 # 全局唯一入口 def new_state(self): self.eps.append([]) self.trans.append({}) self.accept.append(-1) return len(self.accept) - 1 def add_eps(self, s, t): self.eps[s].append(t) def add_char(self, s, ch, t): self.trans[s].setdefault(ch, []).append(t) # 每个构造器返回一个片段 (start, end)，end 是片段的唯一出口 def frag_char(nfa, ch): s, t = nfa.new_state(), nfa.new_state() nfa.add_char(s, ch, t) return s, t def frag_concat(nfa, a, b): nfa.add_eps(a[1], b[0]) # 前一片段的出口 ε 连到后一片段的入口 return a[0], b[1] def frag_star(nfa, a): s, t = nfa.new_state(), nfa.new_state() nfa.add_eps(s, a[0]) # 进入片段 nfa.add_eps(a[1], a[0]) # 回边：再来一次 nfa.add_eps(a[1], t) # 正常退出 nfa.add_eps(s, t) # 跳过：零次也算匹配 return s, t

这段代码里最值得琢磨的是end的唯一性约束。Thompson 构造之所以要求每个片段只有一个出口，是为了让「粘合」这件事变成一次 ε 边的添加——如果片段有多个出口，连接操作就得对每个出口分别连到后一个片段的所有入口，组合数立刻炸开。唯一的代价是 ε 边变多，而 ε 边在下一步会被整体消掉，不影响运行时。

accept用数组而不是给状态挂对象，是因为子集构造阶段要对「一个 DFA 状态里包含的所有 NFA 接受态」做优先级比较，数组下标天然可比，省掉一轮映射。所有规则的正则式最后会被拼成一个大 NFA：新建一个总入口，向每条规则的入口各连一条 ε 边；每条规则的终点在accept里打上自己的 token 编号。

2.2 子集构造：为什么 DFA 的状态是 NFA 状态的集合

NFA 的问题在于「同时处于多个状态」。读到字符a时它可能同时站在三个状态上，只要有任意一条路径最终到达接受态就算匹配——这正是它表达能力更强的原因，也是它不能直接跑的原因：你得在运行时维护一个状态集合，每个字符都做一次集合推进，复杂度是 O(n×|S|)，而且没法用一张定长表表示。

子集构造（subset construction）做的事，就是把这个「集合」在编译期算出来，变成 DFA 里的一个普通状态。关键的两个操作是 ε-closure 和 move：前者求「不做任何字符输入就能到达的所有状态」，后者求「读入某个字符后能到达的所有状态」，两者交替直到不动点。一个 DFA 状态就是一个 NFA 状态的 frozenset，所以 DFA 的状态数上界是 2 的 NFA 状态数次方——听着吓人，实际工程里因为规则高度相似（大量 token 开头都是字母），真实状态数通常只有几十个。

def eps_closure(nfa, states): stack, seen = list(states), set(states) while stack: s = stack.pop() for t in nfa.eps[s]: if t not in seen: seen.add(t) stack.append(t) return frozenset(seen) def build_dfa(nfa, rule_priority): start = eps_closure(nfa, {nfa.start}) dfa_states = {start: 0} # frozenset -> dfa 状态编号 trans, accept = [], [] work = [start] while work: cur = work.pop() idx = dfa_states[cur] while len(trans) <= idx: trans.append({}) accept.append(-1) # 一个 DFA 状态可能同时包含多个接受态，按规则定义顺序取优先级最高的 hits = [nfa.accept[s] for s in cur if nfa.accept[s] >= 0] if hits: accept[idx] = min(hits, key=lambda t: rule_priority[t]) chars = {ch for s in cur for ch in nfa.trans[s]} for ch in chars: nxt = eps_closure(nfa, [t for s in cur for t in nfa.trans[s].get(ch, [])]) if nxt not in dfa_states: dfa_states[nxt] = len(dfa_states) work.append(nxt) trans[idx][ch] = dfa_states[nxt] return trans, accept

frozenset在这里不是风格问题，而是正确性问题：用 list 当字典的键会直接抛异常，用 tuple 又得保证顺序一致（{1,2}和{2,1}会被当成两个不同的 DFA 状态，状态数直接翻倍）。rule_priority那行是很多实验报告里被忽略的一笔——当=和==的第一条规则都能接受=这个前缀时，合并后的 DFA 状态会同时带着两个 token 编号，取谁决定了「优先级」语义，几乎所有语言都规定：先定义的规则优先，同时被最长匹配覆盖。

2.3 最小化与字符类合并：把状态表压到能塞进缓存

子集构造出来的 DFA 通常还是偏大。Hopcroft 划分最小化做的事情很朴素：先把状态按「接受哪个 token」分组，然后反复检查每个组内的状态在各个字符上的转移目标是否落在同一个组里，不一致就拆开，直到不再变化。这一步能把等价的状态（比如多个 token 共用的标识符前缀路径）合并成一坨，状态数往往能砍掉三分之一以上。

比最小化更影响实际性能的是字符类合并。转移表如果是trans[state][256]的二维数组，状态数一百就是两万五千个格子；但词法规则里真正出现的字符种类通常不到 40 种——所有字母在规则里都等价，所有数字都等价。做法是扫描全部规则，把字符映射到一个类编号，转移表退化成trans[state][num_classes]，运行时先查一次char_class[ch]再查表。

提示：字符类合并要在最小化之后做，否则两个本该等价的状态会因为在原始 256 字符表上的差异被判成不同组，最小化效果会大打折扣。这是我在一个模拟项目里调了两天才发现的顺序依赖。

3. 最长匹配与回退：扫描器怎么在多个接受态之间做决定

把 DFA 建好之后，扫描器看起来就只剩下「顺着边走」这一件事。但真正让手写词法分析器翻车的从来不是状态机构造，而是「什么时候停下来」这个决定。int和integer都以i开头，>和>=都以>开头，读到某一步时状态机已经处于接受态了，但继续读下去可能有更长的匹配——这时不能立刻返回。

3.1 maximal munch：只在「能停」的位置记账，走不动了再退回来

业界通行的规则叫最长匹配（maximal munch）：在整条扫描路径上，记下最后一次处于接受态的位置和对应的 token 类型，然后继续往前走，直到状态机进入死状态再回退到那个记账位置。如果这一整条路径上从来没经过接受态，说明第一个字符就非法，直接报错。

这个「记账 + 回退」的机制解释了两件事。第一，词法分析器的运行成本不是严格的每个字符一次，而是「最后一个接受位置」到「死状态」之间的那几步会被重复扫一遍——但这几步的长度上限是一个 token 的最大长度，是个常量，所以整体仍是 O(n)。第二，输入不能是单向流式的（比如直接读 stdin 管道），必须是可随机访问的字符串或可回退的缓冲区，否则回退就得靠ungetc这类不可靠的手段硬撑。

注意：回退的单位是「位置」不是「字符数」。如果缓冲区按字节存、列号按字符算，回退时混用两套下标，中文注释一出现列号就会整体漂移。

3.2 前瞻一位远远不够：那些必须看两个字符的地方

很多人以为词法分析只需要 peek 一个字符，因为「看到=再看一眼是不是=」就够了。实际上最长匹配天然处理了这些情况，真正需要额外注意的是那些跨状态才有意义的场景：/是除号、//是行注释、/*是块注释，三条规则共享同一个前缀，只要 DFA 建对了就不用手写判断；数字1.5和范围符号1..10（某些语言语法）需要.后面的字符参与决策，也是同一个 DFA 的事。

真正麻烦的是「词法上合法但语义上荒谬」的输入，比如123abc。按最长匹配，扫描器会先切出123，再切出abc，两个都是合法 token，语法分析器随后报一个莫名其妙的错，位置还指着abc，让人完全看不出问题出在数字后面粘了字母。变量声明int x和intx之间的差别，靠状态机本身是表达不出来的——这是词法层的表达能力边界，得靠「数字后面紧跟字母就报错」这种附加检查补上。

3.3 表驱动扫描主循环

把前三节的东西拼起来，扫描器的主循环其实很短，短到很多人写完之后不相信它能工作：

class Scanner: def __init__(self, src, trans, accept, char_class): self.src, self.pos, self.line, self.col = src, 0, 1, 1 self.trans, self.accept, self.char_class = trans, accept, char_class def _advance(self, ch): if ch == '\n': self.line += 1 self.col = 1 else: self.col += 1 def next_token(self): src, n = self.src, len(self.src) # 跳过空白，同时维护行列号（换行必须走 _advance，不能直接 pos += 1） while self.pos < n and src[self.pos] in ' \t\r\n': self._advance(src[self.pos]) self.pos += 1 if self.pos >= n: return Token(Token.EOF, '', self.line, self.col) start, pos = self.pos, self.pos state, last_pos, last_type = 0, -1, None while pos < n: cls = self.char_class.get(src[pos], 0) # 0 是"其他字符"类，必然落到死状态 nxt = self.trans[state].get(cls) if nxt is None: # 走不动了，跳出 break state = nxt pos += 1 if self.accept[state] >= 0: # 只在"能停"的位置记账 last_pos, last_type = pos, self.accept[state] if last_type is None: raise LexError('非法字符', self.line, self.col, src[start]) line, col = self.line, self.col # 先记位置，再推进 lexeme = src[start:last_pos] for ch in lexeme: self._advance(ch) self.pos = last_pos return Token(last_type, lexeme, line, col)

参数里trans[state]是一个dict，键是字符类编号，值是下一状态；用dict而不是二维数组，是为了让None天然表示「没有这条边」即死状态，避免再约定一个-1哨兵。char_class缺省返回 0，意味着任何没在规则里出现过的字符（比如中文、控制字符）都会走这个类，直接落到死状态并被last_type is None捕获成「非法字符」——这正是你希望的行为：不认识的东西要早失败，而不是被当成标识符吞下去。

主循环里三处细节值得单独说。last_pos和last_type必须成对更新，如果只更新位置不更新类型，回退后拿到的是上一次的 token 类型，a>=b会被切出一个类型为>但字面量为>=的畸形 token。推进行列号的循环用的是lexeme而不是整段src[start:pos]，因为后者包含了被回退掉的那部分字符，把它们计入行号会让换行统计偏多。Token里带的是扫描开始前的行列号，符号起始位置，这样报错时编辑器跳转能精确指到 token 的第一个字符上。

4. Token 的返回值设计：为什么不能只扔回一个字符串

很多初版实现里next_token()返回的是一个str，语法分析器拿到之后用if s == "if"这种字符串比较做分派。能跑，但跑不远。字符串比较是 O(长度) 的，每个 token 都要比一遍；更致命的是字符串里没有位置信息，报错的时候只能说「这里有语法错误」，说不出第几行第几列；也没有地方挂常量值，0x1F这种字面量要等到语法分析阶段再回头解析一遍。

4.1 类型编号、字面量、位置、值：四个字段各管一件事

一个能撑住后续阶段的 token，至少要有四个字段：

from dataclasses import dataclass @dataclass class Token: kind: int # token 类型编号，语法分析器按它 switch / 查预测表 lexeme: str # 原始字面量，报错回显和调试输出用 line: int col: int value: object = None # 已求值的常量：int / float / 转义后的字符串 KEYWORDS = {'if', 'else', 'while', 'for', 'return', 'int', 'void'} # 精确、大小写敏感

kind用整数而不是字符串，是为了让语法分析器的预测表能直接用二维数组下标访问，也为了让 token 流的比较变成整数比较。lexeme保留原文是必须的——报错信息里"expected ';' but found 'int'"比"expected 12 but found 3"有用一百倍，而且符号表里存的名字也得是原文。value在词法阶段就算好，是把「字符串转数字」这种纯粹和字符打交道的活留在最合适的地方；这一手还有个副作用，常量折叠可以在词法阶段就把1e3归一成1000.0，后面省一次转换。

lexeme和value分开还解决了一个隐蔽问题：标识符的value可以是符号表下标，这样语法分析阶段判断「两个标识符是不是同一个」只需要比整数，不用比字符串。

4.2 保留字：查表还是单独走状态

保留字（关键字）和标识符在字符层面完全同构，if完全符合letter(letter|digit)*。有三种处理方式，取舍很清楚。

第一种是给每个关键字单独写一条规则，让 DFA 里出现i→f这样一条专用路径。优点是识别是「免费」的，走到接受态就知道是关键字；缺点是每加一个关键字都要重新构造整台 DFA，而且这些路径和标识符的前缀高度重叠，最小化之后省不掉多少，状态表反而会膨胀。

第二种是统一按标识符扫，扫完拿lexeme去一张静态表里查，命中就改kind。这是大多数手写扫描器和自动生成工具的做法，代码只有三行，加关键字只改一个set字面量。代价是每个标识符多一次哈希查找——但哈希查找本来就要做（符号表插入），顺手查一次关键字表几乎不增加成本。

第三种是折中：把关键字表做成 perfect hash 或者按首字母分桶的小数组，避免字符串哈希。这在教学实验里属于过度设计，但要处理几十个关键字、每秒几百万 token 的场景时，这一步确实能省下来一截。

某高校这份实验代码选的是第二种，KEYWORDS是一个普通set，判断逻辑就是if lexeme in KEYWORDS: kind = KEYWORD_ID。这里有个必须强调的点：查表必须区分大小写。见过太多实现为了「友好」用了lower()，结果If、WHILE全被吸成关键字，写错的关键字反而不报错，学生调半天找不到问题。

4.3 注释、字符串与符号表的交界

注释是词法分析里最特殊的东西：它需要被正确识别，但不产生 token。块注释/* ... */在 DFA 里是一条从/出发、经过*、然后在「非*」上自环、遇到*转到「可能结束」状态的路径，这条路径上的所有字符都被消费掉但不产生任何输出。行注释更简单，读到换行为止，注意换行本身要留给主循环去处理行列号。

字符串字面量则踩在另一个边界上："a\"b"里的\"不能算字符串结束，转义处理必须在词法阶段完成，但转义序列的合法性（"\q"合不合法）算词法错误还是语法错误，各家语言规定不一样。比较稳妥的做法是词法阶段只处理结构（找到真正的结束引号），把转义序列的语义校验留在后面，这样扫描器不用背着语言规范跑。

符号表交互的关键是「标识符首次出现时插入，之后返回同一个编号」。这个动作放在词法阶段还是语法阶段，是个会影响架构的选择：放在词法阶段，扫描器要持有符号表引用，职责变重，但语法分析器拿到的标识符天然带唯一编号；放在语法阶段，扫描器保持纯粹，但要额外提供lexeme，让上层自己去查。这份实验代码走的是后者，扫描器只负责切词和给位置，符号表由上层驱动——这个划分让扫描器可以被单独测试，输入一段源码、输出一串 token，中间不依赖任何全局状态。

5. 常见问题排查：手写词法分析器的五个翻车现场

5.1 最长匹配没做回退，a>=b被切成三个 token

现象：源码里写if a>=b，语法分析器报「期望表达式，遇到=」，位置指在>后面那个字符上，而源码里根本没有单独的=。

原因：扫描器在>的接受态就立刻返回了，压根没看下一个字符。>=这条规则虽然在 DFA 里存在，但永远走不到它的接受态。

解决：引入last_pos/last_type记账，只在死状态才回退。改完之后要专门测三个用例：a>=b、a>b、a>>=b（如果语言支持移位赋值），确认单字符、双字符、三字符运算符都切对。

5.2 未闭合的块注释吞掉整个文件

现象：注释少写了一个*/，编译器报「非法字符」或者干脆不报错，位置指向文件最后一行，前面几百行代码全都「消失」了。

原因：块注释状态是一个自环，只要没读到*/就一直吃字符，读到 EOF 时循环自然结束，扫描器把这个状态当成正常结束，返回 EOF。语法分析器拿到一个空 token 流，报的错自然莫名其妙。

解决：在 EOF 处检查当前是否仍在注释或字符串状态，如果是，用注释开始的位置报「块注释未闭合」。位置一定要用起始位置而不是 EOF 位置，否则报错指向文件末尾，等于没报。

5.3\r\n、Tab 和 UTF-8 让行列号整体漂移

现象：报错说第 12 行第 5 列有错，编辑器跳过去却停在别的地方，有时候差一行，有时候差好几列。

原因：三个独立问题叠在一起。\r\n被当成两个字符，\r计一次列、\n计一次行，行号看起来对但列号在 Windows 换行的文件上完全错位；Tab 被计作一列，而编辑器按 4 或 8 列显示；源码含中文时，若缓冲区按字节索引、列号按字符算，一个汉字占三字节会让列号翻三倍。

解决：把「字符位置」和「显示列」分开维护，\r\n在扫描前统一归一成\n，Tab 和宽字符的列宽由上层展示逻辑处理，扫描器只保证字符级准确。测试时准备一份 CRLF 文件、一份含中文注释的文件，报错位置必须和编辑器一致。

5.4 关键字判断写成了大小写不敏感

现象：If (x) ...不报错，被当成关键字处理；或者反过来，用户定义的变量Int被识别成类型关键字，符号表插入失败。

原因：查关键字表时用了lexeme.lower()或者strcasecmp。这在只测规范用例时完全看不出来，一旦有人写了大写开头的变量名就炸。

解决：关键字表用精确匹配，in一个set就够了，别做任何归一化。同时补一个用例：定义变量if_、If、IN，确认它们都变成普通标识符。

5.5 接受态冲突时选错了规则优先级

现象：=和==在某些上下文里被切反，==变成一个=加一个=；或者+和++混乱。

原因：合并 NFA 后，某个 DFA 状态同时是两条规则的接受态，build_dfa里取的是「编号最小的 token 类型」，而编号顺序恰好和规则书写顺序不一致。代码不报错，测试用例如果只覆盖单字符运算符也发现不了。

解决：给每条规则一个显式的优先级序号，接受态冲突时按优先级取，而不是按 token 编号。更好的做法是让最长匹配先兜住大部分情况，优先级只在「同样长度、多个规则都能接受」时起作用——这两种机制是叠加的，不是替代的。

6. 表驱动还是手写：一次关于可维护性的取舍与验证

做到最后一定会面对这个问题：到底该用表驱动的 DFA，还是老老实实写一堆if/else和switch的递归下降扫描器。这两种写法在功能上等价，差别全在「以后改起来疼不疼」。

我的判断标准很简单：规则数量超过二十条、或者预期会被反复修改，就走表驱动；规则不到十条、还有大量「需要看上下文才能决定」的特殊情况（比如某些语言的缩进敏感、模板字符串嵌套），手写反而更省事。表驱动最容易被低估的好处不是速度，而是「规则和实现分离」——加一个运算符只要在规则表里加一行，不用去翻主循环里那段嵌了三层的if。

验证一个扫描器有没有静默切错，光靠跑通样例是不够的。我一般会做三件事。第一件是给扫描器加一个 token dump 模式，把每个 token 的类型名、字面量、行列号打到标准错误输出，然后拿同一份源码和有详细输出的成熟工具对照——不需要完全一致，但差异必须每一条都能解释清楚。第二件是构造「对抗性输入」：只差一个字符的运算符对（</<=/<</<<=）、数字后面粘字母、只有*/没有/*、字符串里带转义引号、文件末尾没有换行、注释里嵌注释符号。第三件是做一个极简的随机输入 fuzz：随机拼字符跑一万次，要求扫描器要么正常返回 EOF，要么抛出带行列号的LexError，绝不能死循环或者抛未捕获异常。第三条抓出来的 bug 比前两条加起来还多，尤其是那些「回退位置算错导致pos不前进」的死循环。

那份实验资源里除了扫描器本体，还附了从正则定义到状态机构造的完整推导和成套的测试输入，一边读代码一边拿它对上面这三条验证方法，比自己从零猜要快得多。资料里的规则定义、构造过程、扫描主循环是同一套思路的三段落地，顺着读下来，前面几章讲的那些「为什么必须这么设计」会在源码里一一对上号，想接着往下钻的话，直接去翻那份源码里的构造部分就行。

踩过最疼的一次是：我写完扫描器，样例全过，信心满满地交上去，结果被一份带 CRLF 和中文注释的测试文件打回来，报错位置全错，我还以为是编辑器的问题，查了整整一个下午。从那以后我每次写完扫描器，都会先强制跑一遍「CRLF + Tab + 中文注释 + 文件末尾无换行」这份脏数据，再去看业务用例。希望帮到你。

本文还有配套的精品资源，点击获取