简介这是一份面向高校编译原理课程学习者与编译器前端入门者的词法分析器实验包围绕北京邮电大学课程实验场景提供从词法规则定义到分词逻辑实现的练习素材可用于理解扫描器如何将字符流切分为标识符、关键字、常量与运算符等词素。压缩包共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, keylambda 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, acceptfrozenset在这里不是风格问题而是正确性问题用 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 类型ab会被切出一个类型为但字面量为的畸形 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 最长匹配没做回退ab被切成三个 token现象源码里写if ab语法分析器报「期望表达式遇到」位置指在后面那个字符上而源码里根本没有单独的。原因扫描器在的接受态就立刻返回了压根没看下一个字符。这条规则虽然在 DFA 里存在但永远走不到它的接受态。解决引入last_pos/last_type记账只在死状态才回退。改完之后要专门测三个用例ab、ab、ab如果语言支持移位赋值确认单字符、双字符、三字符运算符都切对。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在扫描前统一归一成\nTab 和宽字符的列宽由上层展示逻辑处理扫描器只保证字符级准确。测试时准备一份 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的递归下降扫描器。这两种写法在功能上等价差别全在「以后改起来疼不疼」。维度表驱动 DFA手写扫描器生成器规则文件加一条 token 规则改规则定义重建表加一个分支改状态跳转改规则文件重新生成单字符处理成本两次数组查找一次分支预测同表驱动边界情况调试打断点看状态编号较抽象直接看代码路径直观需要看生成后的代码前置依赖需要实现子集构造和最小化无需要外部工具适合场景规则多、规则会变规则少、要极致性能或特殊处理工业级语言实现我的判断标准很简单规则数量超过二十条、或者预期会被反复修改就走表驱动规则不到十条、还有大量「需要看上下文才能决定」的特殊情况比如某些语言的缩进敏感、模板字符串嵌套手写反而更省事。表驱动最容易被低估的好处不是速度而是「规则和实现分离」——加一个运算符只要在规则表里加一行不用去翻主循环里那段嵌了三层的if。验证一个扫描器有没有静默切错光靠跑通样例是不够的。我一般会做三件事。第一件是给扫描器加一个 token dump 模式把每个 token 的类型名、字面量、行列号打到标准错误输出然后拿同一份源码和有详细输出的成熟工具对照——不需要完全一致但差异必须每一条都能解释清楚。第二件是构造「对抗性输入」只差一个字符的运算符对///、数字后面粘字母、只有*/没有/*、字符串里带转义引号、文件末尾没有换行、注释里嵌注释符号。第三件是做一个极简的随机输入 fuzz随机拼字符跑一万次要求扫描器要么正常返回 EOF要么抛出带行列号的LexError绝不能死循环或者抛未捕获异常。第三条抓出来的 bug 比前两条加起来还多尤其是那些「回退位置算错导致pos不前进」的死循环。那份实验资源里除了扫描器本体还附了从正则定义到状态机构造的完整推导和成套的测试输入一边读代码一边拿它对上面这三条验证方法比自己从零猜要快得多。资料里的规则定义、构造过程、扫描主循环是同一套思路的三段落地顺着读下来前面几章讲的那些「为什么必须这么设计」会在源码里一一对上号想接着往下钻的话直接去翻那份源码里的构造部分就行。踩过最疼的一次是我写完扫描器样例全过信心满满地交上去结果被一份带 CRLF 和中文注释的测试文件打回来报错位置全错我还以为是编辑器的问题查了整整一个下午。从那以后我每次写完扫描器都会先强制跑一遍「CRLF Tab 中文注释 文件末尾无换行」这份脏数据再去看业务用例。希望帮到你。本文还有配套的精品资源点击获取
简介这是一份面向高校编译原理课程学习者与编译器前端入门者的词法分析器实验包围绕北京邮电大学课程实验场景提供从词法规则定义到分词逻辑实现的练习素材可用于理解扫描器如何将字符流切分为标识符、关键字、常量与运算符等词素。压缩包共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, keylambda 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, acceptfrozenset在这里不是风格问题而是正确性问题用 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 类型ab会被切出一个类型为但字面量为的畸形 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 最长匹配没做回退ab被切成三个 token现象源码里写if ab语法分析器报「期望表达式遇到」位置指在后面那个字符上而源码里根本没有单独的。原因扫描器在的接受态就立刻返回了压根没看下一个字符。这条规则虽然在 DFA 里存在但永远走不到它的接受态。解决引入last_pos/last_type记账只在死状态才回退。改完之后要专门测三个用例ab、ab、ab如果语言支持移位赋值确认单字符、双字符、三字符运算符都切对。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在扫描前统一归一成\nTab 和宽字符的列宽由上层展示逻辑处理扫描器只保证字符级准确。测试时准备一份 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的递归下降扫描器。这两种写法在功能上等价差别全在「以后改起来疼不疼」。维度表驱动 DFA手写扫描器生成器规则文件加一条 token 规则改规则定义重建表加一个分支改状态跳转改规则文件重新生成单字符处理成本两次数组查找一次分支预测同表驱动边界情况调试打断点看状态编号较抽象直接看代码路径直观需要看生成后的代码前置依赖需要实现子集构造和最小化无需要外部工具适合场景规则多、规则会变规则少、要极致性能或特殊处理工业级语言实现我的判断标准很简单规则数量超过二十条、或者预期会被反复修改就走表驱动规则不到十条、还有大量「需要看上下文才能决定」的特殊情况比如某些语言的缩进敏感、模板字符串嵌套手写反而更省事。表驱动最容易被低估的好处不是速度而是「规则和实现分离」——加一个运算符只要在规则表里加一行不用去翻主循环里那段嵌了三层的if。验证一个扫描器有没有静默切错光靠跑通样例是不够的。我一般会做三件事。第一件是给扫描器加一个 token dump 模式把每个 token 的类型名、字面量、行列号打到标准错误输出然后拿同一份源码和有详细输出的成熟工具对照——不需要完全一致但差异必须每一条都能解释清楚。第二件是构造「对抗性输入」只差一个字符的运算符对///、数字后面粘字母、只有*/没有/*、字符串里带转义引号、文件末尾没有换行、注释里嵌注释符号。第三件是做一个极简的随机输入 fuzz随机拼字符跑一万次要求扫描器要么正常返回 EOF要么抛出带行列号的LexError绝不能死循环或者抛未捕获异常。第三条抓出来的 bug 比前两条加起来还多尤其是那些「回退位置算错导致pos不前进」的死循环。那份实验资源里除了扫描器本体还附了从正则定义到状态机构造的完整推导和成套的测试输入一边读代码一边拿它对上面这三条验证方法比自己从零猜要快得多。资料里的规则定义、构造过程、扫描主循环是同一套思路的三段落地顺着读下来前面几章讲的那些「为什么必须这么设计」会在源码里一一对上号想接着往下钻的话直接去翻那份源码里的构造部分就行。踩过最疼的一次是我写完扫描器样例全过信心满满地交上去结果被一份带 CRLF 和中文注释的测试文件打回来报错位置全错我还以为是编辑器的问题查了整整一个下午。从那以后我每次写完扫描器都会先强制跑一遍「CRLF Tab 中文注释 文件末尾无换行」这份脏数据再去看业务用例。希望帮到你。本文还有配套的精品资源点击获取
平方复杂度无法被常规优化消除｜TaoToken 统一 Key 通道实测)
