从正则表达式到最小DFA：Python词法分析器实现与避坑

简介：这份西南科技大学编译原理实验报告围绕词法分析程序的设计展开，面向正在学习编译原理、需要完成设计型实验或撰写实验报告的高校学生。内容从正则表达式描述词法规则入手，依次梳理NFA构造、合并、确定化与最小化DFA的过程，并结合TEST语言给出标识符、保留字、无符号整数、分界符、运算符和注释符的分类及单词输出方案。资源包共1个doc文件，大小约444KB，适合作为实验报告排版与内容组织的参考。目前已有477人学习，读者可重点查看其中的DFA状态转移表、Python词法分析程序框架以及词法规则到自动机的推导思路，用于对照复现实验、理解状态迁移逻辑，并补充错误处理、缓冲区管理等实现细节。

1. 一份能直接跑通的词法分析实验报告，长什么样

拆开这个压缩包，里面是《编译系统综合设计》实验一的完整产出：TEST 语言的六类词法规则、每条规则对应的正则表达式、NFA 合并与确定化、最小化 DFA 的状态图，以及一份用 Python 写的词法分析程序、lex.txt 输出样例和一份调试记录。它解决的不是"编译原理是什么"，而是"给定一套词法规则，怎么从正则一路推到能跑的代码"。适合正在被词法分析实验卡住、或者想把 DFA 那套纸面推导演成可调试程序的人。下面按"规则怎么定 → DFA 怎么落成表 → 代码怎么写 → 怎么验证 → 哪里会翻车 → 怎么改成能用的东西"走一遍。

2. 拆骨架：TEST 语言的六类词法规则与最小 DFA 的推导链路

这份报告最有价值的部分不是代码，是那条从正则到 DFA 的链路。它把"文本长什么样"一步步压成"状态怎么跳"，而后面所有代码都只是这张状态转移表的翻译。链路走通了，代码就只是体力活；链路没走通，代码写出来也是错的，而且错得很隐蔽。

2.1 六类词法规则落成正则表达式：标识符和无符号整数最容易写歪

报告里把 TEST 语言的单词分成关键字、标识符、无符号整数、分界符、运算符、注释符六类，每类一条正则。看着简单，但有两处是新手必踩的：无符号整数的前导零问题，以及运算符里双字符符号的优先级问题。

注意保留字那一行。很多人第一反应是给if、while各画一个自动机，然后和标识符的自动机合并，结果 DFA 状态数直接翻倍。合格的工程做法是：标识符自动机照常跑，识别出int、while这样的字符串之后，去一张关键字表里查一次，命中就改判成 KEYWORD。这样自动机只有一份，扩展关键字也只是往集合里加一个字符串。报告里那条"保留字"规则本质上就是这么处理的，只是它没把这件事讲透。

还有运算符。>和>=共享前缀，=和==共享前缀，!只在!=里合法。这三组如果不用最长匹配处理，x >= 1会被切成>、=、1三个 token，语法分析阶段立刻就炸。

2.2 从 NFA 到最小 DFA：合并、子集构造、分割法三步走

报告里的顺序是：每条正则先用 Thompson 构造法画一个 NFA，然后新增一个起始状态用 ε 边连到所有 NFA 的初态完成合并，再对合并后的 NFA 做子集构造确定化，最后用分割法最小化。纸面上画图很直观，但状态一多就容易抄错边，我更倾向把这三步写成代码，让机器去算。

# NFA 用五元组描述：move[状态][字符] = {后继状态集合}，ε 边用空串 '' 作键 def epsilon_closure(states, move): """求状态集合的 ε 闭包：沿 ε 边能走到的所有状态""" stack, closure = list(states), set(states) while stack: s = stack.pop() for nxt in move.get(s, {}).get('', set()): if nxt not in closure: closure.add(nxt) stack.append(nxt) return closure def subset_construction(start, move, finals, alphabet): """子集构造：NFA 状态集合 -> DFA 状态编号""" d0 = frozenset(epsilon_closure({start}, move)) index = {d0: 0} # 子集 -> DFA 状态号 dfa_move = {0: {}} # DFA 转移表 queue = [d0] while queue: cur = queue.pop(0) for c in alphabet: # alphabet 是合并后的字符类集合 nxt = set() for s in cur: nxt |= move.get(s, {}).get(c, set()) if not nxt: continue nxt = frozenset(epsilon_closure(nxt, move)) if nxt not in index: # 新子集，登记成新状态 index[nxt] = len(index) dfa_move[index[nxt]] = {} queue.append(nxt) dfa_move[index[cur]][c] = index[nxt] # 只要子集里含任一 NFA 终态，这个 DFA 状态就是终态 dfa_finals = {index[s] for s in index if s & finals} return dfa_move, dfa_finals

epsilon_closure干的事就是"不算输入字符，光走空边能到哪儿"，这是子集构造的地基，写错了后面全错。subset_construction里alphabet不是 128 个 ASCII 字符，而是你在 2.1 里归好的字符类（字母、数字、斜杠、赋值号、运算符、分界符、其他），类别越少，转移表越小，这一点在 3.2 会体现得很明显。

跑完之后得到的 DFA 大致收敛成这么几个状态，也就是报告里那张最小化 DFA 图的表格版：

最小化的意义在这里很实在：不做最小化，if的自动机和标识符自动机会留下大量等价状态，手写代码时状态名一堆，改一个规则要动十处；最小化之后每个状态职责唯一，代码里一个字典就装得下。

2.3 单词分类与输出方案：先把 token 长什么样定死，再动笔写代码

报告里把单词分成 7 类（关键字、标识符、无符号整数、分界符、运算符、注释符、保留字），并且给出了明确的输出格式：Keyword: int、Identifier: x、Delimiter: ;。这一步看着像走过场，实际是整个实验里性价比最高的决定——输出格式定死了，你才知道词法分析函数该返回什么结构，才知道错误信息里要不要带行号。

报告给的示例源程序是：

int x; if (x > 0) { write x + 1; }

对应的输出是Keyword: int、Identifier: x、Delimiter: ;、If: if、Parenthesis: (……一路列到Curly Brace: }。这里有个小瑕疵：If: if和Keyword: int用了两套命名，同一个类别出现两种写法，写代码时分类常量就会打架。我一般统一成KEYWORD / IDENT / NUM / OPERATOR / DELIMITER / COMMENT六个大写常量，输出时再映射成人话，这样代码里判等不会写错。

顺带说一句，输出方案里定下"注释符要输出"还是"注释符直接丢弃"，会直接影响后面 lex.txt 的内容。报告的处理是把注释整行吞掉不输出，只在错误清单里体现——这也是绝大多数真实编译器的做法，注释在词法阶段就该消失。

3. 把 DFA 写成代码：状态转移表加主循环的逐段拆解

报告正文贴出的那段 Python 我原样抄下来跑过一遍，结果和它自己贴的输出对不上。这不是报告作者的问题，是这类实验报告的通病：代码是后补的，输出是手写的。所以这一章我不照抄，而是拿它当反面教材，把能跑通的版本一段段写出来。

3.1 报告原版代码的三个硬伤

原版的核心是get_char_category加一张dfa字典，思路没错，但有三处会在真实输入上翻车。第一处，get_char_category里'+', '-', '*', '/', '>'这一批字符被一起归进OPERATOR_DELIMITER，而判断/的那个elif char == '/'分支排在它后面，永远进不去——/从头到尾都被当成运算符。这就是报告"调试记录"里写的"遇到符号/时无法判断是单行注释符还是除运算符号"，但它的解决方案是"增加判断语句"，没动根子上的分类顺序。

第二处，dfa['ID']里写了'OPERATOR_DELIMITER': 'ID'，意思是标识符状态遇到运算符还继续吃。于是int x;if这种没有空格分隔的写法会被并成一个 ID token，x;也出不来分号。第三处更基础：整段代码没有关键字回填，int、if识别出来全都是 Identifier，可它贴的输出里明明写着Keyword: int。

我把这三条列出来不是为了挑刺，是因为它们属于同一类错误的三个面：状态机的接受条件没想清楚。下面重写。

3.2 字符分类与转移表：把 DFA 落成两个字典

第一步是把字符压成类别。类别划分的粒度直接决定转移表的大小，也决定/这类歧义字符能不能被单独拎出来。

# 字符类：字母、数字、斜杠、赋值号、普通运算符、分界符，其余归 OTHER def get_char_category(ch): if ch.isalpha(): return 'ALPHA' if ch.isdigit(): return 'DIGIT' if ch == '/': return 'SLASH' # 单独一类，注释和除号在这里分岔 if ch == '=': return 'ASSIGN' # '=' 既能单独成符，也能和 > < ! 组合 if ch in '+-*<>!': return 'OP' if ch in '(){};,:': return 'DELIM' return 'OTHER'

SLASH和ASSIGN单独立类，是整个词法分析器能写对的前提。/后面跟/是注释、跟=是除等号、跟别的就是除号；=单独出现是赋值，跟在>、<、!后面就组成>=、<=、!=。字符分类一旦把它们混进大桶，后面就只能靠字符串比较去补救，越补越乱。

转移表本身写成嵌套字典，TRANSITION[当前状态][字符类] = 下一状态，查不到键就当"走不动"处理：

TRANSITION = { # 初态：按首字符决定进入哪个子自动机 'START': {'ALPHA': 'ID', 'DIGIT': 'NUM', 'SLASH': 'SLASH0', 'ASSIGN': 'OP', 'OP': 'OP', 'DELIM': 'DELIM'}, 'ID': {'ALPHA': 'ID', 'DIGIT': 'ID'}, # 标识符吃掉后续字母数字 'NUM': {'DIGIT': 'NUM'}, # 整数只吃数字 'SLASH0': {'SLASH': 'COMMENT', 'ASSIGN': 'OP2'}, # // 注释；/= 双字符运算符 'OP': {'ASSIGN': 'OP2'}, # >= <= != == 的第二跳 'OP2': {}, 'DELIM': {}, 'COMMENT': {}, } # 哪些状态是"收尾状态"，走到这里就可以吐 token 了 ACCEPT = {'ID': 'IDENT', 'NUM': 'NUM', 'OP': 'OPERATOR', 'OP2': 'OPERATOR', 'DELIM': 'DELIMITER'} # 合法的运算符全集，用来拦住单独的 '!' 这种半截符号 LEGAL_OPS = {'+', '-', '*', '/', '=', '<', '>', '>=', '<=', '==', '!='}

表里没有ERROR状态，因为"走不动"本身就是一个信号——这一步查不到键，就说明当前 token 到头了。这比原版代码里挂一个永不离开的ERROR状态要干净：错误不是一种状态，是一次转移失败。

3.3 主循环：最长匹配就是"走不动了再回退一步"

真正的词法分析主循环只有十几行，核心是"贪婪地往前吃，吃到走不动为止，然后回头确认这个状态能不能收 token"。这套逻辑有个正式名字叫最长匹配（maximal munch），报告讨论题里问的"是否满足最长匹配原则"，答案就藏在这几行里。

def tokenize(source): tokens, errors = [], [] i, line, col, n = 0, 1, 1, len(source) def consume(text): """统一维护行列号，换行后列号归 1""" nonlocal line, col for c in text: if c == '\n': line, col = line + 1, 1 else: col += 1 while i < n: ch = source[i] if ch in ' \t\r\n': # 空白只做分隔，不产 token consume(ch); i += 1 continue start, s_line, s_col = i, line, col state = 'START' while i < n and state != 'COMMENT': nxt = TRANSITION[state].get(get_char_category(source[i])) if nxt is None: # 转移失败，当前 token 结束 break state = nxt i += 1 if state == 'COMMENT': # 注释吞到行尾，整段丢弃 while i < n and source[i] != '\n': i += 1 text = source[start:i] if i == start: # 首字符就走不动：非法字符 errors.append(Err(s_line, s_col, ch, '非法字符')) consume(ch); i += 1 continue consume(text) if state == 'COMMENT': continue kind = ACCEPT.get(state) if kind == 'IDENT' and text in KEYWORDS: # 关键字回填 kind = 'KEYWORD' if kind == 'OPERATOR' and text not in LEGAL_OPS: errors.append(Err(s_line, s_col, text, '非法运算符')) continue tokens.append(Token(kind, text, s_line, s_col)) return tokens, errors

nxt is None那一行是整个函数的心脏。比如输入>=，读>进OP状态，再读=进OP2，再读下一个字符不管是啥都走不动了，于是停下来，text是>=，ACCEPT['OP2']给出 OPERATOR。如果输入是>x，读完>之后x是 ALPHA，TRANSITION['OP']里没有这个键，立刻 break，text是>，照样正确。所以"回退"其实不需要真的挪指针，只要不在吃不动的时候把 i 加上去就行。

关键字回填那两行是刻意放在最后的：词法分析器永远先按标识符的规则吃满，再回头查表，intx不会被误判成关键字int加标识符x。同理text not in LEGAL_OPS这一句拦住了单独的!——它走了OP状态并被 ACCEPT，但不在合法集合里，判成错误比放过去更安全。

3.4 输出 lex.txt 与错误清单：行列号从哪来

报告要求"将合法单词存入 lex.txt，并报告词法错误及其位置"。位置这件事只有两个数：行号和列号，都得在扫描过程中跟着走，事后补是补不出来的。

def dump(tokens, errors, token_path='lex.txt', err_path='lex_err.txt'): with open(token_path, 'w', encoding='utf-8') as f: for t in tokens: # 定长对齐，方便肉眼比对，也方便后面 grep f.write(f'{t.line:>4}\t{t.col:>4}\t{t.kind:<10}\t{t.text}\n') with open(err_path, 'w', encoding='utf-8') as f: for e in errors: f.write(f'第 {e.line} 行 第 {e.col} 列：{e.text!r} -> {e.msg}\n')

encoding='utf-8'这个参数在国内环境里不是可选项。Windows 上open默认走 GBK，源程序里只要有一个中文注释，写文件时就会抛UnicodeEncodeError，而且报错信息指向的是write那一行，看着像逻辑 bug，其实是编码问题。列号我用的是 token 起始位置而不是结束位置，因为报错时告诉用户"从第几列开始出错"比"错在第几列结束"更有用。

4. 跑通与验证：从空目录到一份能对得上的 lex.txt

代码写完只是开始。词法分析器最怕的是"看着对"，因为它的输出是一长串 token，人眼扫过去很难发现少了一个或者多切了一个。验证必须靠构造对照用例。

4.1 环境与最小运行骨架

只需要 Python 3.8 以上，不装任何第三方库。把前面几段拼成lexer.py，再写一个main.py作为入口：

# 目录结构建议 # proj/ # lexer.py 词法分析核心 # main.py 入口 # cases/ 测试源程序 mkdir -p proj/cases && cd proj python -V # 确认 3.8+

# main.py import sys from lexer import tokenize, dump src = open(sys.argv[1], encoding='utf-8').read() tokens, errors = tokenize(src) dump(tokens, errors) print(f'共 {len(tokens)} 个合法单词，{len(errors)} 处词法错误')

运行方式是python main.py cases/test.src，跑完当前目录下多出lex.txt和lex_err.txt两个文件。这一步别急着看结果，先确认没有抛异常——抛异常八成是编码或者文件路径的问题，跟词法逻辑无关。

4.2 用示例程序对拍，逐行核 token 序列

先拿报告里那个短例子验证基本路径，int x;if (x > 0) { write x + 1; }。正确输出应该是KEYWORD int、IDENT x、DELIMITER ;、KEYWORD if、DELIMITER (、IDENT x、OPERATOR >、NUM 0、DELIMITER )、DELIMITER {、KEYWORD write、IDENT x、OPERATOR +、NUM 1、DELIMITER ;、DELIMITER }，一共 16 个 token。

对不上的话按这个顺序查：先看关键字有没有被识别成 IDENT，有就是回填那一步漏了；再看;有没有黏在标识符后面，有就是ID状态多了一条不该有的转移；最后看>和0之间有没有多出 token，有就是运算符状态没及时收尾。这三条覆盖了九成的初学者错误。

4.3 造错误用例：$、@、2a、012345各代表一类问题

报告里给的那段测试程序本身就是为了踩雷设计的：

{ //This a test program. int abc123$; int 123@; int 2a; abc = 012345; for (i = 1; i <= n; i = I + 1) { if(i != n) abc = ab c* i else abc = abc / i; } }

四个错误点各有各的类型。abc123$是标识符后面跟了非法字符$，正确的行为是切出IDENT abc123再单独报$非法，而不是把整串判错——这是最长匹配带来的好处。123@是数字后面跟非法字符，同理。2a是数字后面跟字母，报告判定为"不符合标识符命名规则"，准确的报法应该是"数字后紧跟字母"，因为2a完全可以在语法上被切成NUM 2和IDENT a，词法阶段选择报错是为了让错误更早暴露。012345则要看你的实现有没有前导零检查，加了就报一条 warning，不加就当一个普通整数放过。

还值得单独测的是abc / i;和//This a test program.这两行，它们是同一个字符/的两个分支，一漏就全漏。

5. 避坑与排查：注释符、除号和最长匹配踩过的五个坑

这一节按"现象 → 原因 → 解决"写，都是我在跑这份代码和自己重写时真实撞过的。

5.1 字符分类顺序引发的两个坑

坑一：所有/都被当成除号，注释整行被切成乱码。

现象：输入//This a test program.，输出里出现OPERATOR /、OPERATOR /、IDENT This、IDENT a、IDENT test一堆 token，注释内容全进了 lex.txt。原因：get_char_category里'/'被包含在'+-*/<>=!'那个分支里，判断'/'的分支排在后面永远走不到。解决：把/单独提成一个字符类SLASH，让它在转移表里从START进SLASH0，再由下一个字符决定走COMMENT还是OP2。分类函数里把特判放在通配之前，这条顺序在很多语言的分词器里都是铁律。

坑二：!被当成合法运算符放过去，到语法分析阶段才炸。

现象：源程序里写了!x，词法分析没报错，输出了OPERATOR !。原因：!在TRANSITION['START']['OP']里有转移，走完OP状态就被 ACCEPT 收下了，没有校验它是否属于合法运算符集合。解决：在吐 token 之前加一道if kind == 'OPERATOR' and text not in LEGAL_OPS的检查。这类"半截符号"在自动机层面看不出问题，只能靠一张白名单兜底。

5.2 状态机与最长匹配的两个坑

坑三：标识符状态吃掉分号，x;if变成一个 token。

现象：输入int x;if (x>0)，输出里出现一整个IDENT x;if。原因：原版代码在dfa['ID']里写了'OPERATOR_DELIMITER': 'ID'，本意大概是"标识符后面跟符号时继续走"，但 DFA 里每个状态只能有一组出边，标识符状态就该只吃字母和数字。解决：ID状态只保留ALPHA和DIGIT两条转移，遇到分号立刻 break，靠外层循环重新从START起步。这条经验很通用：接受状态不要有"顺手多走一步"的边，多走的每一步都会变成一个黏连的 token。

坑四：关键字识别不出来，int全是 Identifier。

现象：输出里只有IDENT int，没有任何 KEYWORD。原因：只做了标识符的自动机，没做关键字回填，而报告正文贴的输出里又有Keyword: int，代码和输出对不上。解决：识别完标识符后查一次KEYWORDS集合，命中就改判。改的时候注意别在自动机里给关键字单独建状态，那样每加一个关键字就要动一次转移表。

5.3 输出与文件层面的一个坑

坑五：lex.txt 写不出来，报UnicodeEncodeError。

现象：程序跑到写文件那一步直接抛异常，报错行是f.write(...)。原因：源程序里有中文注释，open没指定编码，Windows 默认 GBK 编不出来。解决：open(..., 'w', encoding='utf-8')，读源文件时同样指定encoding='utf-8'。顺带提醒一句，open('lex.txt','w')是覆盖写，想保留多次运行的结果要么换文件名，要么用'a'追加，别跑第二遍发现上一次的结果没了还以为程序出 bug。

提示：排查这类词法分析器的问题，最快的办法不是读代码，是把输入缩到最短。一个字符一个字符地喂，看状态怎么跳，比盯着两百行代码猜要快得多。

6. 二次开发：把它改成一个能进项目的词法器

这份实验代码离"能用"还差三件事，改起来都不难。第一件是 token 结构，现在用的是元组或简单对象，建议换成一个@dataclass的Token(kind, text, line, col, end_line, end_col)，加上结束位置，后面写语法错误提示时可以下划线定位。第二件是字符集，实验里只认 ASCII 字母，改成ch.isalpha()之后中文标识符会自动被放进来，如果不想支持（多半不想），就在分类函数里显式判'a' <= ch <= 'z'，别留模糊地带。第三件是注释，现在只支持//，加块注释/* */只要在SLASH0后面接一个STAR状态，再让COMMENT状态在遇到*/时退出——注意块注释要额外维护一个"上一个字符是什么"的标志位，因为 DFA 只看当前字符。

验证方法我一般用对拍：准备二十个语料文件，每个文件第一行注释写清楚期望的 token 数量和错误数量，跑一个脚本批量比对。改一次转移表就跑一遍，比人工看输出靠谱得多。

改NUM状态那条我吃过亏。加了十六进制之后0x1F能认，但0后面跟x的非法写法0xg会被切成一个 NUM0加一个 IDENTxg，表面上不报错，实际上是个静默错误。从那以后我每次动数字相关的状态，都强制走一遍"合法、边界、非法"三组用例，跑通了才敢往下写。

希望帮到你。

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