从正则到最小DFA：Python词法分析器实验复现

简介：这份西南科技大学编译原理实验一报告围绕“设计词法分析程序”展开，适合正在学习编译原理前端、需要完成词法分析实验或复习正则表达式与有限自动机的高校学生参考。包内仅含1个doc文件，压缩包约444KB，篇幅集中于实验报告正文，便于直接查阅实验目的、设计思路、过程记录与程序实现。报告完整梳理了TEST语言词法规则的正则表达式描述、NFA构造与合并、确定化及最小化DFA的推导，并给出关键字、标识符、无符号整数、分界符、运算符和注释符的分类与输出方案。程序实现部分还提供了基于Python状态转移表的词法分析框架，涉及字符类别判断、状态迁移及错误处理等要点，可辅助读者理解DFA落地方式并对照完善自己的实验代码。目前已有477人学习，适合作为课程实验参考与查漏补缺材料。

1. 一份实验报告能跑出什么：词法分析从纸面 DFA 到可执行代码

拆到这份《编译系统综合设计》实验一的实验报告时，我一开始也只当它是纸面作业：几条正则、几张 NFA 图、一个合并后确定化再最小化的 DFA，交完就完事。真把它里面的状态转移表原样抄进 Python 字典跑了一遍，才发现这条链子是通的——正则表达式描述词法规则，NFA 承接，子集构造确定化，Hopcroft 化简，最后落成一张能直接驱动扫描器的转移表，加上单词输出方案和 lex.txt 落盘，一台最小可用的词法分析器就站起来了，还能顺带报出123@、2a这类词法错误的行列位置。这份实验包适合两类人：正在赶编译原理实验、想照着跑通并交差的同学，和想给自研 DSL、配置语言、日志解析器找个手写扫描起点的开发者。后面我把这套东西拆成能直接复制的代码和能复现的验证步骤。

2. 项目骨架与技术选型：正则到最小 DFA 的四步链路怎么落到文件

2.1 实验包的产出物与目录组织

这类实验包最容易被忽略的是"产出物清单"，很多人下载完只看报告正文，结果代码和图示对不上号。按这份报告的流程，一份完整的词法分析实验至少要有七类东西：规则的正则写法、单条规则的 NFA、合并后的 NFA、确定化后的 DFA、最小化后的 DFA、扫描器源码、以及源程序跑出来的 lex.txt。我一般会把它们整理成下面这种结构，规整一点，二次开发时不用来回翻 Word：

值得注意的是nfa/和dfa_min.png这两个目录：它们看着像"为交作业而画"，其实是整个项目唯一的设计文档。后面代码写歪了，比如除号和注释符分不开，回到 DFA 图上一看就知道是哪个状态的出边画错了。我见过不少人图是图、代码是代码，两套逻辑，调起来就是玄学。

链路上的四步是固定的：正则 → NFA（Thompson 构造）→ DFA（子集构造）→ 最小 DFA（Hopcroft 或划分法）。前两步是纸面功夫，第三、四步才是真正决定扫描器能不能写对的地方，因为只有确定化之后，每个状态对每个输入字符才有唯一去向，才谈得上"查表跳转"。

2.2 为什么最后落在 Python 字典状态机上

同一个词法分析器，写法至少有三种，选哪种取决于你要的是"能交差"还是"能改"。

这份报告选了表驱动，理由很实在：DFA 本身就是一张二维表，行是状态、列是输入字符类别，把它直接翻译成{状态: {字符类别: 次态}}的嵌套字典，几乎是一比一映射，中间没有语义损耗。而且表驱动有个隐性好处——你想加日志，只需要在跳转那一行打印(当前状态, 输入类别, 次态)，整条扫描轨迹就出来了，比在十个 if 分支里各插一句 print 舒服得多。

代价也有：表驱动把"字符分类"和"状态转移"拆成两个函数，一旦分类函数写错，比如把/归到了运算符类里，转移表里那条注释边就永远走不到。这份报告里的调试记录恰好踩的就是这个坑，后面第 3 章会把它拎出来讲。

2.3 TEST 语言的七类词法规则与正则写法

报告把 TEST 语言的单词分成七类：关键字、标识符、无符号整数、分界符、运算符、注释符、保留字。其中"关键字"和"保留字"其实是同一批东西（int、if、else、for、while、do、write、read），报告里两处列法不一致，是这类文档的常见毛病，代码里统一按一张关键字表处理就行。

把每条规则翻成可执行的正则，是这样的：

几个必须记住的细节。第一，关键字和标识符的正则天然重叠，int既匹配标识符也匹配关键字，所以判定顺序要么把关键字排在前面，要么（我更推荐）先全按标识符扫出来，再去关键字哈希表里查一次，O(1) 查表比在 DFA 里画八条关键字边省事得多。第二，>=、<=、==、!=这类双字符运算符必须排在单字符之前，否则>=会被切成>和=，最长匹配原则当场失效。第三，注释//必须排在除号/之前，这是这份实验报告里唯一被明确记录下来的 bug，值得单独说一遍。

报告里把注释符写成/|/，是 Word 排版把//拆开了，实际规则是"两个斜杠开头到行尾"。凡是看到报告里这种断开的符号，都要回到上下文确认一遍，别照着错的抄。

2.4 Thompson 构造、子集构造、Hopcroft 各干什么

三步算法各自解决一个问题，混在一起讲容易糊。

Thompson 构造把正则变成 NFA：每个基本字符是一个"三状态小片段"（入边、出边、中间一条标着字符的边），连接用 ε 边串起来，选择用 ε 边分叉再汇合，闭包*用一条回指的 ε 边。它的特点是简单、机械、状态数线性增长，缺点是带大量 ε 边，一个状态对同一个字符可能有多个去向，机器没法直接跑。

子集构造解决"没法直接跑"：把 NFA 的状态集合当成 DFA 的一个状态，从 ε 闭包的起始集合出发，对每个输入字符算出能到达的集合，直到不再产生新集合。做完这一步，DFA 的每一行就是一张确定的转移表，行数可能比 NFA 状态数多，但每格只有一个次态。

Hopcroft（划分法）解决"表太大"：把所有状态先按"终态 / 非终态"切成两块，然后反复检查每块里的状态对每个输入字符是否落到同一块，不一致就继续切，直到切不动。合并同类项之后，状态数最少。

落到这张表上是这个样子（把运算符和分界符合成一列只是示意，实际代码里是分开的）：

表格里"回退输出"四个字是整个扫描器的灵魂。终态遇到一个不属于本状态的字符时，不能把它吃掉，要退回去，让下一个 token 从头开始扫。这份实验报告的原始代码没做这件事，后面会看到它因此把x;整个吞成了一个标识符。

3. 核心代码拆解：dfa 转移表与 lex_analysis 主循环

3.1 get_char_category：字符分类是第一道闸门

报告里的字符分类函数长这样：

# 定义输入字符类别 def get_char_category(char): if char.isalpha(): return 'ALPHABET' elif char.isdigit(): return 'DIGIT' elif char in {'+', '-', '*', '/', '>', '<', '=', '!', '(', ')', '{', '}', ';'}: return 'OPERATOR_DELIMITER' elif char.isspace(): return 'WHITESPACE' elif char == '/': return 'SLASH' else: return 'OTHER'

参数只有一个字符，返回一个类别字符串，逻辑看着没问题，实际上藏着一个致命顺序错误：第三个分支的集合里已经包含了/，所以任何斜杠在第二个elif就被判成OPERATOR_DELIMITER返回了，第四个分支elif char == '/': return 'SLASH'是一行永远不会被执行的死代码。

这正好对上报告调试记录里的第一条问题——"代码运行结果中不能处理除运算符号/"。现象是除号不识别，根因却在分类函数，这种"症状在 A、病灶在 B"的情况在表驱动实现里特别常见，因为转移表本身是对的，错的是喂给它的输入类别。

修正很简单，把/从运算符集合里摘出去，让它单独成类：

OPER_CHARS = set('+-*=<>(){};:,') DELIM_CHARS = set('(){};:,') def char_class(ch): """返回字符类别，作为 DFA 转移表的列索引""" if ch.isalpha() or ch == '_': return 'ALPHA' if ch.isdigit(): return 'DIGIT' if ch == '/': return 'SLASH' # 必须先于运算符判断 if ch in OPER_CHARS: return 'OPER' if ch.isspace(): return 'SPACE' return 'OTHER'

这里还有个建模层面的问题：报告把运算符和分界符合并成OPERATOR_DELIMITER一类，但它的单词输出方案里明明把Operator、Delimiter、Parenthesis、Curly Brace分得清清楚楚。分类粒度和输出粒度对不上，最后只能靠字符串内容二次判断，等于转移表白建了一半。我一般会在字符类别上就分开，OPER一列、DELIM一列，代价是转移表多一列，收益是输出阶段不用再猜。

3.2 dfa 转移表逐行读

原始的转移表：

dfa = { 'START': {'ALPHABET': 'ID', 'DIGIT': 'NUM', 'OPERATOR_DELIMITER': 'OPERATOR', 'SLASH': 'COMMENT', 'OTHER': 'ERROR'}, 'ID': {'ALPHABET': 'ID', 'DIGIT': 'ID', 'OPERATOR_DELIMITER': 'ID', 'SLASH': 'ID', 'OTHER': 'ERROR'}, 'NUM': {'ALPHABET': 'ERROR', 'DIGIT': 'NUM', 'OPERATOR_DELIMITER': 'ERROR', 'SLASH': 'ERROR', 'OTHER': 'ERROR'}, # ... 其余状态略 }

START那一行是标准答案：字母进 ID、数字进 NUM、运算符进 OPERATOR、斜杠进 COMMENT、其他进错误态。问题出在ID这一行——它对OPERATOR_DELIMITER、SLASH的次态都写成了ID，意思是"标识符状态遇到运算符还是留在标识符状态"。

这行一写，x + 1里的x、空格、+会被拼成一个 token 吗？不会，因为空格被主循环跳过了。但x+1、x;、abc=1这种不带空格的写法就完了：x后面跟;，;属于OPERATOR_DELIMITER，次态仍是ID，于是;被追加到当前 token 上，继续往后吃，直到碰到一个表里没有的类别或者输入结束。最后吐出来的 token 是('ID', 'x;')，分号凭空消失。

正确写法是：终态只对自己该接受的字符类别有出边。ID只接ALPHABET和DIGIT，遇到别的字符一律没有转移，主循环看到"没有转移"就回退一步、输出当前 token、把状态重置为START。也就是说，ID行应该只留两条：

TRANS = { # 只保留"本状态真正接受"的出边，其余用 .get() 返回 None 表示回退 ('START', 'ALPHA'): 'ID', ('START', 'DIGIT'): 'NUM', ('START', 'OPER'): 'OP', ('START', 'DELIM'): 'DELIM', ('START', 'SLASH'): 'SLASH', ('ID', 'ALPHA'): 'ID', ('ID', 'DIGIT'): 'ID', ('NUM', 'DIGIT'): 'NUM', ('SLASH', 'SLASH'): 'COMMENT', # 第二个 / 才确认是注释 }

用二元组(状态, 类别)当键，而不是嵌套字典，好处是查不到时直接拿到None，不用写if cat in dfa[state]这种两层判断，也顺手把"缺项"和"不该转移"统一成了同一种语义。

3.3 lex_analysis 主循环与回退逻辑

原始主循环：

def lex_analysis(input_string): current_state = 'START' current_token = '' tokens = [] for char in input_string: category = get_char_category(char) if category in dfa[current_state]: current_state = dfa[current_state][category] current_token += char else: if current_state not in {'WHITESPACE', 'COMMENT', 'ERROR'}: tokens.append((current_state, current_token)) current_state = 'START' current_token = '' if category != 'WHITESPACE': current_state = dfa[current_state][category] current_token += char if current_state not in {'WHITESPACE', 'COMMENT', 'ERROR'}: tokens.append((current_state, current_token)) return tokens

for char in input_string这种按字符推进的写法，天然没有"往回退一个字符"的能力，所以它只能用"当前字符类别在不在转移表里"来判断 token 边界。这个判断成立的前提是转移表足够精确——而 3.2 里那张表不精确，ID行对所有类别都有出边，于是边界永远判不出来，整段源码会被吞成一个巨型 token。

第二处问题是那句if current_state not in {'WHITESPACE', 'COMMENT', 'ERROR'}。排除集合里没有START，所以当扫描器刚重置、还没吃到任何字符时就撞上一个不认识的字符，它会 append 一个('START', '')的空 token。同样的判断在函数末尾又出现一次，输入以空白结尾时也会吐空 token。

第三处是最长匹配的实现方式。报告在讨论区里说"读取到>时再读下一个符号，是=就识别为>="，方向是对的，但代码里并没有这个"再读一个"的动作，靠的是OPERATOR状态自环把连续运算符吃进去。>后面跟=能勉强凑对，>后面跟;就会变成('OPERATOR', '>;')。这类问题在实验里不明显，换成真实代码立刻翻车。

我一般用"双指针 + 最近接受位置"来实现回退，这是最长匹配的后悔药：

def scan_one(src, i): """从 i 开始扫一个 token，返回 (结束位置, 状态)。 没有接受过任何字符时返回 (i, None)，交给错误恢复处理。""" state = 'START' j = i last_accept = -1 # 最近一次处于终态时的位置 while j < len(src): nxt = TRANS.get((state, char_class(src[j]))) if nxt is None: # 没有出边：不能再吃了 break state = nxt j += 1 if state in ACCEPT: # 记下这个位置，将来可以退回来 last_accept = j if last_accept < 0: return i, None return last_accept, state

i是 token 起点，j是一直往前探的探针，last_accept记住"上一次停在合法终态"的位置。探到走不动时，把i拉到last_accept，中间的字符就是最长匹配的结果，多探出去的那几个字符留给下一轮。这样x>=1的处理是：x走到>时无出边停下，last_accept停在x之后；下一轮从>开始，>=>里的>=两层都能走通，last_accept停到=之后，输出>=。

3.4 关键字识别：ID 到 KEYWORD 的二次判定

关键字要不要画进 DFA，是个值得说清楚的设计选择。画进去的话，int、if、else每个都要从START拉一条独立路径，八条关键字就是几十条边，NFA 合并图和最小化 DFA 图会瞬间糊成一团，加一个关键字还得重画整张图、重算最小化。这份报告显然没画，因为它扫描int x;时输出的类型是Keyword，那是靠输出阶段的字符串比对补的。

更常见的做法是在 DFA 外面挂一张哈希表：

KEYWORDS = {'int', 'if', 'else', 'for', 'while', 'do', 'write', 'read'} def classify(text): """DFA 只负责切出"形似标识符"的串，这里做二次判定""" if text in KEYWORDS: return 'KEYWORD' if text.isidentifier(): return 'ID' if text.isdigit(): return 'NUM' if text in ('>=', '<=', '==', '!='): return 'OP' if text in '+-*/=<>': return 'OP' return 'DELIM'

这样做有个前提：关键字的正则必须是标识符正则的子集。TEST 语言的八个关键字都是纯字母，满足条件，所以先扫 ID 再查表完全等价。如果语言里有if-else这种带符号的关键字，就不成立了，得在 DFA 里单独开路。判断标准一句话：关键字能不能被标识符的正则整体覆盖，能就查表，不能就画图。

.isidentifier()这个 Python 内置方法顺手解决了一部分边界，但它认 Unicode 字母，中文变量名也会返回 True。如果 TEST 语言规定标识符只能是 ASCII 字母数字，就得换成re.fullmatch(r'[A-Za-z][A-Za-z0-9]*', text)，别图省事。

4. 单词输出方案与结果落盘：Token 结构、lex.txt 与错误定位

4.1 单词分类与 Token 三元组设计

报告的单词输出方案是按类别逐行打印的：

Keyword: int Identifier: x Delimiter: ; Operator: > Unsigned Integer: 0

人类读着舒服，机器用起来难受，因为丢了位置信息，也没法直接喂给语法分析器。工程上我一般定义成带行列号的四元组，类别名用短标签，一是省文件体积，二是跟后面的语法分析阶段好对接：

注释这一行值得强调：注释是词法规则的一部分，但不是语法成分，扫描器扫到就跳过，不产出 token，也不写进 lex.txt 的合法单词区。报告原始代码把COMMENT放进排除集合，思路是对的，只是它那个COMMENT状态根本走不到，因为斜杠在分类阶段就被吃掉了。

Token 的数据结构，Python 里用dataclass比裸元组可读性好太多，tokens[3]和token.line的区别在调试时体现得淋漓尽致：

from dataclasses import dataclass @dataclass class Token: kind: str # KEYWORD / ID / NUM / OP / DELIM text: str # 原始词素，保留原文大小写 line: int # 1-based 行号 col: int # 1-based 列号

把text原样保留，不做小写归一，原因是后面语法阶段报错还得把原文回显给用户；需要归一（比如关键字不分大小写）的时候再单独做一层text.lower()，别在扫描阶段就破坏原始信息。

4.2 扫描器完整实现与逐段说明

把前面几节的东西拼成一个能跑的版本。为了便于对照报告里的输出，我在结构上保留了"先切词素、再分类"的两段式，只是把边界判断换成了显式的最长匹配：

# -*- coding: utf-8 -*- """TEST 语言词法分析器：源程序 -> Token 流 + 错误清单""" from dataclasses import dataclass KEYWORDS = {'int', 'if', 'else', 'for', 'while', 'do', 'write', 'read'} SINGLE_OP = set('+-*/=<>') DELIM = set('(){};:,') @dataclass class Token: kind: str text: str line: int col: int def tokenize(src: str): tokens, errors = [], [] i, n = 0, len(src) line, col = 1, 1 def step(k=1): """前移 k 个字符，同时维护行列号""" nonlocal i, line, col for _ in range(k): if i < n and src[i] == '\n': line += 1 col = 1 else: col += 1 i += 1 while i < n: ch = src[i] if ch in ' \t\r\n': step() continue sl, sc = line, col # 记下 token 起点，出错时报这个位置 # 1) 注释：// 到行尾，整段丢弃 if src.startswith('//', i): while i < n and src[i] != '\n': step() continue # 2) 标识符 / 关键字：字母开头，后跟字母数字 if ch.isalpha() or ch == '_': j = i while j < n and (src[j].isalnum() or src[j] == '_'): j += 1 word = src[i:j] kind = 'KEYWORD' if word in KEYWORDS else 'ID' tokens.append(Token(kind, word, sl, sc)) step(j - i) continue # 3) 无符号整数：这里顺手拦一下 2a 这种非法标识符 if ch.isdigit(): j = i while j < n and src[j].isdigit(): j += 1 if j < n and (src[j].isalpha() or src[j] == '_'): k = j while k < n and (src[k].isalnum() or src[k] == '_'): k += 1 errors.append((sl, sc, '非法标识符 %r：不能以数字开头' % src[i:k])) step(k - i) continue tokens.append(Token('NUM', src[i:j], sl, sc)) step(j - i) continue # 4) 双字符运算符必须先判，保证最长匹配 two = src[i:i + 2] if two in ('>=', '<=', '==', '!='): tokens.append(Token('OP', two, sl, sc)) step(2) continue # 5) 单字符运算符 if ch in SINGLE_OP: tokens.append(Token('OP', ch, sl, sc)) step() continue # 6) 分界符 if ch in DELIM: tokens.append(Token('DELIM', ch, sl, sc)) step() continue # 7) 兜底：非法字符单独记账，不中断整个扫描 errors.append((sl, sc, '非法字符 %r' % ch)) step() return tokens, errors

逐段说一下。step()是整个函数里唯一改动i、line、col的地方，这样行列号不会因为某个分支忘了加而漂移，第 5 章那条行号错乱的血泪记录就是这么来的。注释分支放在最前面，因为//的第一个字符/也是运算符，先判注释就自动获得了最长匹配的语义。标识符分支用isalnum()一次性把字母和数字都收了，跟正则[A-Za-z0-9]*等价。数字分支里那段"后面还跟着字母"的判断，专门对付报告里2a那个错误用例，报错位置取的是数字本身的起点，跟编译器习惯一致。

运算符部分只判了四种双字符，!单独出现时没有对应规则，会掉进兜底分支报"非法字符"，这比静默吞掉好。真要支持!单目运算，加一条规则就行。

step(k)的参数是"要前进的字符数"，不是目标位置。传j - i是因为j是探针、i是起点，两者之差正好是本次消费的长度。这个约定用起来容易忘，第一次写的时候我在标识符分支传了j，结果直接跳过半行源码，查了十分钟。

4.3 lex.txt 落盘与错误报告格式

结果写文件这块，报告要求"合法单词存入 lex.txt，并报告词法错误及其位置"。两段式输出最省事，合法 token 一区、错误清单一区，中间空一行，人读机器读都还行：

def dump(tokens, errors, path='lex.txt'): with open(path, 'w', encoding='utf-8') as f: for t in tokens: f.write('{:>4}:{:<4} {:<10} {}\n'.format( t.line, t.col, t.kind, t.text)) if errors: f.write('\n--- 词法错误 ---\n') for ln, cl, msg in errors: f.write('{:>4}:{:<4} {:<10} {}\n'.format(ln, cl, 'ERROR', msg))

格式串里{:>4}右对齐行号、{:<4}左对齐列号、{:<10}留给类别，这样即使 token 文本长度差异很大，文件在编辑器里也是对齐的，扫一眼就能看出哪一行有问题。encoding='utf-8'必须显式写，Windows 上默认是 GBK，遇到中文注释直接抛UnicodeEncodeError，这个坑不需要踩第二次。

拿报告里那段带错误的源程序跑一遍，lex.txt大概长这样：

1:1 KEYWORD int 1:5 ID abc123 1:12 ERROR 非法字符 '$' 1:13 DELIM ; 2:1 KEYWORD <p> <a href="https://download.csdn.net/download/m0_65436422/88754609" style="color:#ec7500;font-size:14px;"> 本文还有配套的精品资源，点击获取 </a> <img alt="menu-r.4af5f7ec.gif" src="https://csdnimg.cn/release/wenkucmsfe/public/img/menu-r.4af5f7ec.gif" style="width:16px;margin-left:4px;vertical-align:text-bottom;cursor:text;"> </p>