词法分析器核心机制：Token、DFA与最长匹配回退

简介：面向计算机专业学生与编译原理初学者，这份北京邮电大学课程实验一的词法分析器实现材料，围绕编译器前端扫描器展开，聚焦从字符流中识别标识符、关键字、常量与运算符等词素，帮助读者理解词法规则定义、分词逻辑、符号栈管理与错误恢复等关键环节。压缩包共4个文件，约10KB，以2个txt文本和1个h头文件、1个cpp源文件为主；文本可承载实验说明与测试输入，头文件与源文件则对应规则声明、输入读取及扫描实现的主体代码。已有1000人学习下载，适合配合课程进度做代码阅读与实验复盘。读者可据此梳理词法分析器的基本结构，观察规则如何映射到词素类型，并借鉴测试用例与报错处理方式，为后续语法分析与语义分析学习打基础。

1. 词法分析器：为什么它的难点从来不是“认出 token”

多数人第一次做编译原理课程实验一，会觉得词法分析器是整个编译器里最容易的部分——不过就是一堆if-else认几个单词。真写下去才会发现麻烦的地方根本不在这里：难点是把“最长匹配、回退、错误恢复、行列号追踪、缓冲区边界”这几件互相牵连的事情，同时塞进一个确定性状态机里，并且保证它对任意字节流不崩、不死循环、不吞字符。它是整条编译链上唯一直接面对“任意输入”的环节，后面语法分析、语义分析全都默认它吐出的 token 流是干净的。这个契约一旦破了，后面所有阶段的报错都会指向错误的位置，排查成本成倍上升。搞懂它的底层机制，比把实验跑通更值钱。

2. 词法分析器的契约：Token 到底该带哪些字段

2.1 输入是字节流，输出是带位置的 token 序列

先把边界划清楚：词法分析器接收的是一段字节，输出的是一条 token 序列，没有别的。它不建语法树，不做类型检查，也尽量不修改全局状态。这个“只做一件事”的定位决定了它的接口长什么样——一个next_token()函数，每次调用消费若干个字符，返回一个 token，直到返回EOF为止。语法分析器拿着这个迭代器往前推，需要回看几个 token 就自己在外面做缓冲。

这里有个容易被忽略的设计点：token 里必须带位置。位置信息的价值不在于好看，而在于它是唯一的错误定位来源。语法分析器发现“这里应该有个分号”时，它能拿到的只有 token 上的行列号；如果词法层没记，后面就得靠数换行符来反推，那是血泪经验级别的错误做法。所以line和column是 token 的一等公民，不是可选项。

常见的实现思路是把位置记录拆成两件事：扫描器内部维护line、line_start两个游标，token 的列号用start - line_start + 1现算。这样每次消费字符只需要在遇到\n时更新一次，不必逐字符递增列号，省掉大量自增操作。

2.2 为什么 lexeme 和 value 必须分开

新手最容易把 token 设计成一个char*加一个类型，然后所有 token 的“值”都去解析这个字符串。这在标识符上没问题，但在数字和字符字面量上会重复解析：语法分析阶段要算一次atoi，语义分析阶段可能还要再算一次。

合理的结构是“原文切片 + 解析后的值”双轨制。原文切片用start指针加length表示，指向源缓冲区，不做拷贝；解析后的值放在 union 里，只有需要的时候才填。

typedef enum { TOK_EOF, TOK_IDENT, TOK_KEYWORD, TOK_INT, TOK_FLOAT, TOK_STRING, TOK_CHAR, TOK_OP, TOK_PUNCT, TOK_ERROR } TokenKind; typedef struct { TokenKind kind; const char *start; /* 指向源缓冲区，零拷贝 */ int length; /* lexeme 字节数，不含结尾 */ int line; /* 起始行号，1-based */ int column; /* 起始列号，1-based */ union { long long ival; /* TOK_INT 有效 */ double fval; /* TOK_FLOAT 有效 */ int op; /* TOK_OP：运算符表下标 */ } value; } Token;

start是指针而不是数组，前提是源文件被整块读进内存并在整个编译期间保持存活。这个前提必须写进注释，否则某天有人改成流式读取，所有 token 的 lexeme 会瞬间全部悬空。op存的是运算符表下标而不是字符串，因为运算符的识别在词法层已经完成了，后面语法分析只需要比较整数，比字符串比较快一个数量级。

注意：length不要用strlen(start)代替。字符串字面量里可能含有\0转义，strlen会截断。

2.3 驱动循环：一次读一个字符真的够吗

最朴素的扫描器是每次getchar()一个字符。逻辑正确，但在真实文件上性能很差——函数调用和缓冲区检查的开销远超实际的状态转移。工业实现几乎都用双缓冲：两块固定大小的缓冲区轮流填充，扫描指针在一块内滑动，滑到边界时把剩余部分搬到另一块开头再读入新数据。

再进一步是哨兵技巧：每块缓冲区末尾放一个EOF字符（真正的EOF或\0），这样内层循环就不需要每次检查“是否到缓冲区末尾”，只在读到哨兵时才走慢路径。这个技巧的收益在内层while里非常明显，因为省掉的分支判断恰好是最热的那条路径。

真正把这几件事串起来的是主循环：

Token next_token(Scanner *s) { for (;;) { skip_whitespace(s); /* 空白不产生 token */ if (peek(s) == '/' && peek2(s) == '/') { skip_line_comment(s); continue; } if (peek(s) == '/' && peek2(s) == '*') { skip_block_comment(s); continue; } break; } if (peek(s) == '\0') return make_eof(s); return scan_token(s); /* 分发到标识符/数字/运算符等分支 */ }

外层for(;;)的作用是“跳过不产生 token 的东西后重新判断”，注释和空白都走这条路。这里的continue不能写成递归调用，否则一个几千行的注释文件就能把栈打穿。skip_*系列函数必须是消费型的，保证每次循环至少前进一个字符，这是后面防死循环的第一道保险。

3. 从正则到 DFA：Thompson 构造和子集构造到底在做什么

3.1 每种 token 都是一条正则，正则先变成 NFA 片段

词法规则的本质是一组正则表达式：标识符是[A-Za-z_][A-Za-z0-9_]*，十进制整数是[0-9]+，浮点是[0-9]+\.[0-9]+。把这些正则直接翻译成代码当然可以，但那样每种 token 一套手写逻辑，规则一多就难以维护，且很难证明“没有遗漏”。

正规的做法是走一遍经典管线：正则 → NFA → DFA → 最小化 DFA → 转移表。中间每一步都有明确的算法，可以机械执行，出错概率低。

Thompson 构造的核心思想是“片段可拼接”：每个正则片段是一个带唯一入口start和唯一出口accept的子图，出口通过 ε 边连接到后续片段。字符、连接、选择、闭包四种构造各有固定模板：

class NFA: def __init__(self): self.trans = [] # trans[state][sym] = [dst...]，sym=None 表示 ε self.start = None self.accept = None def new_state(self): self.trans.append({}) return len(self.trans) - 1 def add(self, src, sym, dst): self.trans[src].setdefault(sym, []).append(dst) def char(self, c): # 单字符片段 s, a = self.new_state(), self.new_state() self.add(s, c, a) return s, a def concat(self, f1, f2): # 连接：f1 的出口 ε 到 f2 的入口 s1, a1 = f1; s2, a2 = f2 self.add(a1, None, s2) return s1, a2 def alt(self, f1, f2): # 选择：新入口分叉，出口合并 s1, a1 = f1; s2, a2 = f2 s, a = self.new_state(), self.new_state() self.add(s, None, s1); self.add(s, None, s2) self.add(a1, None, a); self.add(a2, None, a) return s, a def star(self, f): # 闭包：出口回到入口，同时允许跳过 s1, a1 = f s, a = self.new_state(), self.new_state() self.add(s, None, s1); self.add(s, None, a) self.add(a1, None, s1); self.add(a1, None, a) return s, a

trans用字典而不是二维数组，是因为 NFA 的转移天然稀疏，一个状态最多两三条出边。sym=None承担 ε 边的角色，这个约定后面eps_closure会反复用到。star那四行是整套构造里最容易写错的地方——出口既要有回边（继续匹配）又要有跳边（零次匹配），少一条就会漏掉空串或漏掉重复。

3.2 ε-closure 与子集构造：把“猜”变成“确定”

NFA 的问题是它需要“猜”。站在某个状态上，读入一个字符后可能同时存在多条可行路径，机器没法决定走哪条。子集构造解决的就是这个问题：把一个 NFA 状态集合当成 DFA 的单个状态，凡是集合内所有状态能到达的下一批状态，合并成新的 DFA 状态。这样“猜”变成了“同时走所有路”，结果确定。

前置操作是 ε-closure：从一个状态集合出发，沿 ε 边能免费到达的所有状态。它必须用显式栈做迭代，不能递归——ε 环在star构造里是常态，递归会直接栈溢出。

def eps_closure(nfa, states): stack, out = list(states), set(states) while stack: s = stack.pop() for t in nfa.trans[s].get(None, ()): # None 即 ε 边 if t not in out: out.add(t) stack.append(t) return frozenset(out) def subset_construction(nfa, alphabet): d0 = eps_closure(nfa, {nfa.start}) ids, order, rows = {d0: 0}, [d0], [] queue = [d0] while queue: cur = queue.pop(0) row = {} for sym in alphabet: nxt = set() for s in cur: nxt.update(nfa.trans[s].get(sym, ())) # 只沿非 ε 边移动 if not nxt: continue # 空集即死状态，整列省略 cl = eps_closure(nfa, nxt) if cl not in ids: ids[cl] = len(order) order.append(cl) queue.append(cl) row[sym] = ids[cl] rows.append((ids[cur], row)) return order, rows

ids把状态集合映射成整数编号，靠的是frozenset可哈希。nxt为空时省略整列，这样得到的 DFA 是“部分转移函数”，死状态不占表项——工程上比补全死状态省很多空间。queue.pop(0)在 Python 里是 O(n)，写成collections.deque的popleft()更好，这里为了可读性保留。

子集构造有个常被忽略的副产品：它天然支持“多个 token 的接受状态合并”。把所有 token 的正则用alt拼成一个大 NFA，一个 DFA 就能同时识别全部 token，接受状态上标注“这个状态接受哪个/哪些 token”。如果有多个 token 同时接受（比如=和==的中间状态），就在状态上挂一个集合，运行时按最长匹配规则裁决。

3.3 状态表怎么落地成代码：二维数组、等价类与行压缩

DFA 到手后，落地方式直接决定运行速度和表的大小。最直白的是二维数组dfa_trans[state][char]，行数是状态数，列数是 256（按字节）。几千个状态乘 256 就是几十万项，每项一个int，表能到几 MB，对课程实验无所谓，对真实编译器就太肥了。

常见的压缩手段有两级。第一级是字符等价类：把所有字节按“在任何状态下的转移目标是否一致”划分成若干类，常见结果是十几类而不是 256 类。构建方式是先按“出现在哪些转移里”给字符打签名，签名相同的合并。这一步能把表宽直接砍掉一个数量级。

第二级是行合并或默认转移：如果两行的转移完全一致，指向同一个状态，就合并成一行；或者给每个状态指定一个默认目标，表里只存例外项。

/* 压缩后的转移表：char_class 把 256 字节映射到十几个等价类 */ static const unsigned char char_class[256] = { /* ... */ }; static const short dfa_trans[DFA_STATE_COUNT][CLASS_COUNT] = { /* 状态 0：起始状态 */ { 1, 2, 3, 4, 0, /* ... */ }, /* ... */ };

short在状态数少于 32767 时够用，比int省一半。char_class的初值必须覆盖全部 256 项，否则遇到非 ASCII 字节会读到 0，被当成某个合法类，产生莫名其妙的 token——这是真实踩过的坑。表做完之后最好写一个自检：随机生成一批字符串，同时跑“表驱动”和“朴素正则匹配”，比对结果，一致才认为表是对的。

4. 最长匹配：为什么扫描器必须留一颗“后悔药”

4.1 maximal munch：为什么要回退到最后一个接受状态

DFA 驱动扫描的循环里，最关键的不是状态转移，而是“记住最后一次接受”。原因是 token 之间是前缀关系：>和>=共享前缀，1和1.5共享前缀，.和...共享前缀。扫描器读到>时无法判断这是完整 token 还是更长 token 的开头，只能继续往前读；读到=时才知道应该是>=；但如果读到的是a，那就得退回去，只认>。

这个“退回去”就是常说的后悔药，形式化名字叫 maximal munch：在所有可能的匹配中取最长的那一个。实现上只需要两个变量——最后一个接受状态、以及到达该状态时的输入位置。

Token scan_by_dfa(Scanner *s) { int state = DFA_START; TokenKind last_accept = TOK_NONE; const char *last_pos = NULL; const char *p = s->cursor; for (;;) { int cls = char_class[(unsigned char)*p]; int next = dfa_trans[state][cls]; if (next < 0) break; /* 无转移，停止 */ state = next; p++; TokenKind k = dfa_accept[state]; if (k != TOK_NONE) { /* 记录可接受位置 */ last_accept = k; last_pos = p; } } if (last_accept == TOK_NONE) { /* 一个字符都认不出 */ s->cursor++; /* 必须前进，防死循环 */ return make_error_token(s, p); } s->cursor = last_pos; /* 回退，把多吃的字符还回去 */ return make_token(s, last_accept, last_pos); }

last_pos和s->cursor的分离是整个函数的核心。p是探路指针，它可以一路吃到=后面去；s->cursor才是权威位置。函数返回前把s->cursor拉回last_pos，等于宣布“刚才多读的字符不算数，下次重新扫”。这一行如果漏了，>=会变成>加上一个被吞掉的=，语法分析器报的错会离真正的原因十万八千里。

char_class那张表在这里再出现一次，说明字符分类是扫描器的公共基础设施，不该散落在各个分支里。dfa_accept[state]存接受类型，TOK_NONE表示非接受状态，这个哨兵值选-1或枚举首项都行，但必须和有效 token 类型不重叠。

4.2 关键字不是词法规则，是标识符表的一次查表

一个很自然的想法是把if、while、return也写成正则，拼进大 DFA。技术上完全可行，工程上通常不这么做。

原因在于关键字的数量会变。语言加一个新关键字，就要改正则、重建 NFA、重跑子集构造和最小化，整张表重新生成。而且关键字和标识符在 DFA 里高度重叠，if的状态会和i、in、int的前缀状态纠缠，最小化之后状态数反而上升。

更常见的做法是：DFA 只认“标识符”这一条规则，扫出一个完整 lexeme 之后，拿整串去哈希表里查一次。命中就改 kind 为TOK_KEYWORD，没命中保持TOK_IDENT。

Token classify_ident(Scanner *s) { Token t = make_token(s, TOK_IDENT, s->cursor); const KeywordEntry *e = keyword_lookup(t.start, t.length); /* 带长度的哈希 */ if (e) { t.kind = TOK_KEYWORD; t.value.op = e->op; } return t; }

keyword_lookup必须接受长度参数，不能只接受char*然后内部strcmp。因为t.start指向的是源缓冲区内部，后面还有别的字符，用strcmp会把if后面的内容一起比进去。这个小细节在实验里翻车率极高。

注意：查表要在“最大匹配”之后做。先查表再匹配，ifdef会被拆成if和def两个 token。

4.3 注释、除号与未闭合注释：三个容易翻车的边界

/是词法分析里最不干净的一个字符。它同时是除号、行注释开头、块注释开头。手写扫描器通常用一个两字符前瞻解决：看到/就看下一个，是/走行注释，是*走块注释，否则就是除号。这意味着扫描器的某个分支需要 2 个字符的前瞻，而不是 DFA 那样的单字符转移——没关系，实现上把前瞻做成peek(1)、peek(2)就够了，不必强行塞进状态机。

真正麻烦的是块注释的收尾。/* ... */里可以出现任意字符，包括换行、字符串、/、*。扫描逻辑必须是“读到*再看下一个是不是/”，而不是“读到/就结束”，否则/* a/b */会在a/处提前终止。同时，块注释里的每一个\n都要累加到行号上，否则注释之后的全部报错行号整体偏小。

未闭合注释是必须显式处理的错误。文件读到EOF还没见到*/，正确做法是报一个“块注释未闭合，开始于第 N 行”，然后把游标推到文件末尾，让本次编译干净结束。错误的做法是让扫描循环继续找*/，它会一路吃到内存末尾，程序崩溃或者产生一条长得离谱的 token 流。

最后是嵌套注释。多数语言不支持嵌套，扫描器遇到第一个*/就收工，简单可靠。如果语言规范要求支持嵌套，就必须维护一个深度计数器，遇到/*加一、*/减一，减到零才结束。这个选择要在文档里写死，不能靠“碰巧能跑”。

5. 避坑与排查：词法分析器最常翻车的五个地方

5.1 五条踩坑记录：现象、原因、解决

第一条，死循环。现象是最外层驱动循环永远不返回，或者 token 流长度无限增长，程序卡死在某个位置再也不动。原因几乎总是同一条：错误分支里直接return error_token()，忘了推进s->cursor。调用方拿到一个错误 token，位置没变，下一次调用又走到同一个字符，又返回错误 token。解决方法是把“至少前进一个字符”写成不变量，所有返回路径都满足；Debug 版本加一句assert(s->cursor > old_cursor)，越界立刻暴露。

第二条，行号整体偏移。现象是前几个错误行号对得上，越往后偏差越大，最后能差出几十行。原因是某处消费了\n却没有更新line，最常见的是skip_block_comment里用memchr找\n却没统计个数，或者用strstr找*/之后忘了扫一遍中间的换行。解决办法是把所有消费字符的动作收敛到一个advance()函数里，换行计数只在那一个地方做，任何地方都绕不过去。

第三条，缓冲区边界越界。现象是最后一个 token 后面跟着几个垃圾字符，或者在某些文件上偶发崩溃、换个文件就好。原因是peek2()在文件末尾读到了缓冲区之外的内存，拿到的值是随机的，结果时对时错。解决办法是缓冲区尾部预留至少两个哨兵字节，并且保证peek(n)在越界时返回哨兵而不是原始内存。这个坑的隐蔽性在于它和输入内容相关，本地跑十个用例都正常，交上去评测挂了。

第四条，关键字被前缀切割。现象是ifdef、integer、whileLoop这类词被识别成关键字加标识符两段。原因是先查关键字表再匹配标识符，或者用了strncmp比较前几个字符就返回。解决办法是严格按最大匹配先扫出完整的标识符 lexeme，再拿“指针 + 长度”整串查表，长度不等一律不命中。

第五条，数字字面量的边界。现象是1..10这种数组范围写法被识别成浮点数1.后跟.10，或者0x后面没有十六进制数字时被识别成0加标识符x。原因是在数字状态里看到.就无条件进入小数部分，没有检查后面是不是数字。解决办法是在[0-9]+之后看到.时，必须前瞻一个字符确认是数字才进入浮点分支；0x分支同理，看到0和x之后必须至少消费一个十六进制数字，否则整体退化成0加错误。

5.2 一套从 token 流倒推问题的排查顺序

排查这类问题的顺序比技巧重要。第一步永远是打印 token 四元组——(kind, lexeme, line, column)，一行一个，把整段输入的 token 流完整看一遍。绝大多数问题在这一步就能定位到“从第几个 token 开始不对”，然后只需要看那个 token 往前一小段源码。

第二步是做最小化输入。把整段源码二分，留下前半段看问题是否复现，反复二分直到只剩几行。词法问题几乎都是局部问题，缩到十行以内基本就现形了。

第三步是对比状态轨迹。给扫描器加一个可选开关，把(state, char, next_state)打出来，和手工推演的 DFA 走位比对。分叉点就是 bug 所在——通常是某条转移在表里填错了，或者字符等价类把两个不该合并的字符合并了。

第四步是检查 lookahead 的所有权。谁读了peek2的那两个字符，谁负责把它们还回去或者算进 lexeme 长度。跨函数的 lookahead 最容易出现“这个字符到底算谁的”争议，一次漏算就是一个 token 的偏移，后面全乱。

6. 设计取舍：表驱动、手写扫描与生成器之间怎么选

走完上面这些机制，最后一个绕不开的问题是：到底该用哪种实现方式。三种方案各有明确的适用边界，没有普适答案。

手写扫描的优点是错误信息能做得非常具体，比如“字符串字面量在第 12 行第 8 列缺少结束引号”，这种信息表驱动很难给，因为 DFA 只知道“进了死状态”，不知道自己在哪个语义分支里。缺点是规则一多就难维护，几十种 token 的分支散在几百行代码里，加一条规则要动三处。

表驱动最大的价值在于可证明性。规则和代码彻底分离，正则改了就重新生成表，不会出现“代码和文档不一致”。代价是调试体验差，出问题时看到的是状态编号，得回头查表才知道对应哪条规则。

我一般的判断是：课程实验用表驱动，因为实验的核心目的就是走通“正则 → NFA → DFA”这条链，手写 switch 反而绕过了要考的东西；真实项目里如果 token 类型超过三十种，用生成器；少于十种，手写更快更可控。

这里还有一个常被低估的取舍：到底要不要在词法层处理字符串转义。把"a\nb"在词法层解成真正的换行符，语法分析拿到的就是干净的字符串，但报错时无法复现原文；只在词法层保证引号闭合、把原始 lexeme 原样传给后面，错误处理更简单，但后续阶段要自己再解一遍。我倾向后者，因为词法层的职责是切分，不是解释。

从那以后我每次写扫描器，都会先强制走一遍“四元组打印 + 最小输入二分”这两步，再开始怀疑状态转移表。这个习惯救过我很多次——绝大多数看起来玄学的 token 错位，最后都落在某个advance()忘了记换行、或者某个peek2越界上。希望帮到你。

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