北邮编译原理实验一：从正则到最小化DFA的词法分析器实现

简介这份资源是北京邮电大学编译原理课程实验一的词法分析器实现包面向正在学习编译原理、需要完成词法分析实验的高校学生与自学者。词法分析器是编译器前端的关键模块负责将源代码字符流切分为标识符、关键字、常量、运算符等词素本包可帮助读者理解词法规则定义、输入处理、分词逻辑与错误恢复的完整实现思路。压缩包共4个文件以cpp源代码与h头文件为核心另附txt格式的说明与测试用例整体约10KB体量轻便便于快速阅读与本地编译调试。目前已有1000人学习下载适合作为课程实验的参考实现读者可借此对照自身代码梳理扫描器的规则组织方式与符号管理策略为后续语法分析与语义分析打下基础。1. 北邮编译原理实验一词法分析器从正则到 DFA 的完整落地如果你正在上编译原理这门课大概率会在第三周左右收到一份实验任务书要求实现一个词法分析器。北邮的编译原理课程实验一就是这个节点上的经典任务——给定一段类 C 语言的源程序输出每个单词的种别码和属性值。听起来简单但真正动手时你会发现从正则表达式到 NFA 再到 DFA 最后到最小化 DFA每一步都有让人翻车的细节。这份资源包里的词法分析器实现覆盖了从正规式定义、子集构造法、DFA 最小化到最终扫描器的完整链路适合正在做实验但卡在状态转换或种别码映射上的同学也适合想重新梳理词法分析流程的开发者拿来对照。它不是那种只给一个main函数就完事的代码而是把每个阶段的中间结果都保留了下来方便你调试和验证。2. 词法分析器的核心构造从正规式到最小化 DFA2.1 为什么不能直接写正则匹配很多同学第一反应是用re模块或者手写一堆if-else来识别标识符、关键字和运算符。这样做确实能跑通简单样例但实验评分往往要求你展示自动机的构造过程。北邮的实验一通常要求提交 DFA 的状态转换表或者状态图直接调库会被判定为未完成核心步骤。所以正确的路径是先为每种 token 定义正规式用 Thompson 构造法把正规式转成 NFA再用子集构造法把 NFA 确定化为 DFA最后用 Hopcroft 算法做最小化。这条链路虽然长但每一步都有明确的算法可以落地而且中间结果可以互相验证。常见做法是先把所有 token 的正规式合并成一个大正则用|连接然后统一构造 NFA。这样做的好处是只需要构造一次自动机扫描时不用回退。但要注意关键字和标识符的正规式有重叠比如if既是关键字也符合标识符的规则。解决办法是在 DFA 最小化之后对接受状态做二次判断如果匹配到的字符串在关键字表里就输出关键字种别码否则输出标识符种别码。2.2 Thompson 构造法把正规式变成 NFAThompson 构造法的核心思想是递归地拆解正规式为每个基本单元生成一个小的 NFA 片段然后用 ε 转移把它们串起来。下面是一个简化版的 Python 实现展示了如何为单个字符和连接操作构造 NFA 片段。class NFAState: def __init__(self): self.transitions {} # 字符 - 状态列表 self.epsilon [] # ε 转移目标 self.is_end False def build_nfa_for_char(c): 为单个字符 c 构造 NFA 片段 start NFAState() end NFAState() start.transitions[c] [end] end.is_end True return start, end def build_nfa_for_concat(nfa1, nfa2): 连接两个 NFA 片段nfa1 的终点通过 ε 转移到 nfa2 的起点 start1, end1 nfa1 start2, end2 nfa2 end1.epsilon.append(start2) end1.is_end False return start1, end2 def build_nfa_for_union(nfa1, nfa2): 并操作新建起点和终点用 ε 转移连接两个片段 start NFAState() end NFAState() start1, end1 nfa1 start2, end2 nfa2 start.epsilon.extend([start1, start2]) end1.epsilon.append(end) end2.epsilon.append(end) end1.is_end False end2.is_end False end.is_end True return start, end这段代码里NFAState用字典存字符转移用列表存 ε 转移。build_nfa_for_char是最基本的单元build_nfa_for_concat把两个片段首尾相连build_nfa_for_union则新建一对起止状态来分支。实际写的时候还需要处理闭包*和可选?思路类似闭包就是让终点的 ε 转移指回起点同时终点也能直接跳到新终点。参数方面transitions的键是单个字符如果要支持字符集比如[a-z]可以在构造前展开成多个字符分别建转移或者用一个特殊标记表示范围在子集构造时再展开。2.3 子集构造法NFA 到 DFA 的确定化NFA 的不确定性体现在同一个状态对同一个输入可能有多个转移目标还有 ε 转移。子集构造法的做法是把 NFA 状态的集合当作 DFA 的一个状态。具体步骤是从 NFA 的起始状态的 ε 闭包开始对每个输入字符计算转移后的 ε 闭包如果这个集合没出现过就加入 DFA 状态列表直到没有新状态产生。def epsilon_closure(states): 计算状态集合的 ε 闭包 stack list(states) closure set(states) while stack: s stack.pop() for next_s in s.epsilon: if next_s not in closure: closure.add(next_s) stack.append(next_s) return closure def move(states, char): 计算状态集合在字符 char 上的转移目标 result set() for s in states: if char in s.transitions: result.update(s.transitions[char]) return result def nfa_to_dfa(nfa_start): 子集构造法主流程 start_closure epsilon_closure({nfa_start}) dfa_states [start_closure] dfa_transitions {} unmarked [start_closure] while unmarked: current unmarked.pop() # 收集所有可能的输入字符 chars set() for s in current: chars.update(s.transitions.keys()) for c in chars: next_set epsilon_closure(move(current, c)) if not next_set: continue if next_set not in dfa_states: dfa_states.append(next_set) unmarked.append(next_set) dfa_transitions[(dfa_states.index(current), c)] dfa_states.index(next_set) # 标记接受状态包含原 NFA 终态的集合 dfa_end_states [i for i, s in enumerate(dfa_states) if any(state.is_end for state in s)] return dfa_states, dfa_transitions, dfa_end_statesepsilon_closure用栈来避免递归深度问题move计算字符转移后的原始状态集合主循环里用unmarked列表管理待处理状态。dfa_transitions的键是(状态索引, 字符)的元组值是对应的目标状态索引。这里有个容易忽略的点NFA 的终态可能不止一个所以判断 DFA 状态是否接受时要检查集合里是否有任意一个原终态。参数上如果输入字符集很大chars的收集可以提前固定成字母表避免每次动态扫描。2.4 DFA 最小化与种别码映射得到 DFA 之后状态数可能偏多尤其是合并了多个 token 的正规式之后。Hopcroft 算法的思路是先把状态划分成接受态和非接受态然后不断细分如果两个状态在同一个输入字符下转移到不同的划分块就把它们分开。重复直到划分不再变化。最小化之后每个划分块合并成一个状态转移关系重新映射。种别码映射是实验报告里必须体现的部分。通常做法是维护一张关键字表和一个 token 类型枚举。扫描器在 DFA 上跑每读一个字符就查转移表如果当前状态是接受态就记录一下继续读直到无法转移然后回退到最后一个接受态的位置截取字符串。如果字符串在关键字表里返回关键字种别码否则根据接受态对应的 token 类型返回标识符、常数或运算符的种别码。KEYWORDS {if: 1, else: 2, while: 3, int: 4, return: 5} TOKEN_TYPES {ID: 10, NUM: 11, OP: 12} def scan(source, dfa_transitions, dfa_end_states, state_token_map): 基于 DFA 的扫描器 pos 0 tokens [] while pos len(source): state 0 last_accept -1 last_pos pos while pos len(source) and (state, source[pos]) in dfa_transitions: state dfa_transitions[(state, source[pos])] pos 1 if state in dfa_end_states: last_accept state last_pos pos if last_accept -1: raise SyntaxError(f非法字符 at {pos}: {source[pos]}) lexeme source[last_pos - (pos - last_pos):last_pos] if False else source[last_pos:last_pos] # 实际实现中需要根据 last_accept 和 last_pos 正确截取 token_type state_token_map.get(last_accept, ID) if lexeme in KEYWORDS: tokens.append((KEYWORDS[lexeme], lexeme)) else: tokens.append((TOKEN_TYPES.get(token_type, 10), lexeme)) pos last_pos return tokens上面这段扫描器代码里last_accept记录最近一次到达接受态的状态编号last_pos记录对应的位置。当无法继续转移时回退到last_pos并截取lexeme。注意lexeme的截取逻辑需要根据实际的位置变量调整这里只是示意。state_token_map是一个从 DFA 状态到 token 类型的映射通常在最小化之后根据每个划分块包含的原接受态类型来确定。参数方面source是输入字符串dfa_transitions是(状态, 字符) - 状态的字典dfa_end_states是接受态集合。3. 实验环境搭建与代码运行从零跑通词法分析器3.1 目录结构与依赖确认拿到资源包后先别急着运行。解压之后通常能看到几个关键文件nfa.py或automata.py负责自动机构造lexer.py或scanner.py是扫描器主逻辑tokens.py定义种别码和关键字表可能还有一个test_cases目录放测试用例。北邮的实验一般要求用 Java 或 C 提交但这份资源如果是 Python 版本可以用来快速验证算法逻辑再移植到课程要求的语言。依赖方面纯算法实现通常不需要第三方库标准库的collections和sys就够。如果资源里用了graphviz来画状态图需要额外装一下但这不是运行必需。常见做法是先跑一遍python lexer.py test.c看看输出格式。如果报ModuleNotFoundError检查一下文件是不是都在同一级目录或者有没有__init__.py缺失。我一般会先建一个虚拟环境把 Python 版本锁定在 3.8 以上避免字典有序性之类的兼容问题。3.2 输入文件格式与命令行参数词法分析器的输入通常是一个源程序文件输出是 token 序列。资源包里的入口脚本一般支持命令行参数指定输入文件和可选的输出格式。下面是一个典型的调用方式# 基本用法分析 test.c 并打印 token 序列 python lexer.py test.c # 输出到文件 python lexer.py test.c -o tokens.txt # 显示 DFA 状态转换表调试用 python lexer.py test.c --dump-dfa如果资源包里没有argparse相关的代码可以自己加一个简单的参数解析。-o参数把结果写到文件--dump-dfa用来打印中间状态表方便对照实验报告。输入文件的编码建议用 UTF-8如果源程序里有中文注释不加编码声明可能会在读取时报UnicodeDecodeError。参数方面test.c是待分析的源文件路径-o后面跟输出文件路径--dump-dfa是一个布尔开关。3.3 测试用例设计与预期输出跑通之后需要设计几组测试用例来验证正确性。至少覆盖纯关键字、标识符与关键字混合、数字常量整数和小数、运算符和界符、注释和空白字符。下面是一个简单的测试源文件示例int main() { int count 10; while (count 0) { count count - 1; } return 0; }预期输出应该包含int、main、(、)、{、int、count、、10、;等 token每个 token 带种别码。如果输出里main被识别成了关键字说明关键字表里多加了或者匹配逻辑有问题。如果10被拆成了1和0说明数字的正规式没有正确处理多位数字。测试的时候建议先用最短的输入定位问题比如只输入一个int看输出是否符合预期再逐步加长。4. 避坑与排查词法分析器实验中的五个血泪教训4.1 现象DFA 状态数爆炸最小化后没变化原因子集构造法里 ε 闭包计算不完整导致很多本该合并的状态被拆开了。常见的是epsilon_closure只做了一层没有递归处理新加入状态的 ε 转移。解决检查epsilon_closure里的while stack循环确保每个新加入的状态都被展开。另外如果正规式里用了或*闭包计算要特别小心建议先用一个小正则比如a*单独测试闭包函数。4.2 现象扫描器在标识符后面多读了一个字符原因回退逻辑写错了。扫描器在无法转移时应该回退到last_pos但有些实现里pos和last_pos的更新顺序不对导致多读了一个字符。解决在每次成功转移后更新pos在到达接受态时更新last_accept和last_pos。当循环因为无法转移而退出时把pos重置为last_pos。注意last_pos记录的是接受态之后的位置不是接受态本身的位置。4.3 现象关键字被识别成标识符原因关键字表和标识符的优先级没处理好。如果 DFA 的接受态只标记了“标识符”类型扫描器在截取字符串后没有二次查关键字表就会把if当成普通标识符。解决在扫描器的输出阶段加一层判断if lexeme in KEYWORDS就返回关键字种别码。另外关键字表建议用set而不是list查找更快也避免重复。4.4 现象注释里的内容被当成 token 输出原因注释的正规式没有合并到主自动机里或者合并了但接受态没有正确标记为“忽略”。解决为//和/* */分别写正规式合并到 NFA 时给它们的接受态打一个特殊标记扫描器遇到这种接受态时直接跳过不输出 token。注意/* */要支持跨行//只到行尾。如果注释里出现了*/之外的字符不要提前结束。4.5 现象数字常量识别错误比如1.2.3被接受原因浮点数的正规式写得太宽松比如[0-9]\.[0-9]没有限制小数点只能出现一次。解决把数字的正规式拆成整数和小数两部分小数部分用[0-9]*\.[0-9]或者[0-9]\.[0-9]*确保小数点最多一个。如果实验要求支持科学计数法再加[eE][-]?[0-9]。测试的时候专门构造1.2.3、1..2、.5这类边界输入看扫描器是否报错或正确截断。5. 进阶技巧用状态表驱动和可视化验证 DFA5.1 把 DFA 导出成表格方便写实验报告实验报告里通常要求附上 DFA 的状态转换表。与其手动画不如在代码里加一个导出函数把dfa_transitions转成二维表格。下面是一个简单的实现def export_dfa_table(dfa_states, dfa_transitions, dfa_end_states, alphabet): 导出 DFA 状态转换表为 Markdown 表格 lines [] header | 状态 | | .join(alphabet) | 接受 | lines.append(header) lines.append(| ---| * (len(alphabet) 2)) for i in range(len(dfa_states)): row [str(i)] for c in alphabet: target dfa_transitions.get((i, c), -1) row.append(str(target) if target ! -1 else -) row.append(是 if i in dfa_end_states else 否) lines.append(| | .join(row) |) return \n.join(lines)这个函数接收 DFA 状态列表、转移字典、接受态集合和字母表输出 Markdown 格式的表格。alphabet可以取所有出现过的输入字符的并集也可以手动指定成[a, b, 0, 1, ...]。导出之后直接贴进实验报告比截图清晰得多。参数方面dfa_states是子集构造法返回的状态列表dfa_transitions的键是(状态索引, 字符)dfa_end_states是接受态的索引集合。5.2 用 Graphviz 可视化 NFA 和 DFA如果实验报告允许附图用 Graphviz 把自动机画出来会加分不少。Python 的graphviz库可以很方便地生成 DOT 文件。下面是一个导出 DFA 的示例from graphviz import Digraph def visualize_dfa(dfa_states, dfa_transitions, dfa_end_states, filenamedfa): 生成 DFA 的可视化图 dot Digraph(commentDFA) for i in range(len(dfa_states)): shape doublecircle if i in dfa_end_states else circle dot.node(str(i), shapeshape) for (src, char), dst in dfa_transitions.items(): dot.edge(str(src), str(dst), labelchar) dot.render(filename, formatpng, cleanupTrue) return filename .pngDigraph创建有向图doublecircle表示接受态circle表示普通状态。dot.edge添加带标签的边标签就是输入字符。render会生成 PNG 文件。如果字符是特殊符号比如或\需要转义一下否则 DOT 语法会报错。我一般会在label里把空格和换行替换成可见的符号避免图太乱。5.3 一个容易忽略的验证习惯从那以后我每次写完自动机构造代码都会先用一个极简的正则比如a|b跑一遍手动检查 NFA 的状态数和 DFA 的状态数是否符合预期。a|b的 NFA 应该有 6 个状态两个字符各 2 个加上新建的起止各 1 个DFA 最小化后应该有 3 个状态起始、接受 a、接受 b。如果数字对不上说明构造或最小化有 bug这时候再去调复杂的正则会浪费很多时间。这个习惯帮我省下了不少深夜 debug 的功夫。希望帮到你。本文还有配套的精品资源点击获取