编译原理实验报告避坑：正则→NFA→DFA→Python词法分析器

简介：这份西南科技大学编译原理实验报告围绕“设计词法分析程序”展开，面向正在学习编译原理、需要完成课程实验或复盘词法分析流程的高校学生。内容从实验目的、实验设计、实验过程到程序实现依次组织，重点梳理正则表达式描述词法规则、由正则表达式构造NFA、合并并确定化为DFA、进一步最小化DFA，以及单词分类与输出方案的完整链路。报告中结合TEST语言给出标识符、保留字、无符号整数、分界符、运算符和注释符等规则示例，并附有基于Python状态转移表的词法分析程序框架，便于读者理解状态机如何识别不同Token，同时提示错误处理、缓冲区管理和回溯等后续完善方向。资源包共1个doc文件，约444KB，适合作为实验报告参考和考前复习材料。已有479人学习，可帮助读者快速把握编译原理实验一的核心任务与实现思路。

1. 编译原理实验报告踩坑实录：套用这份设计型报告前，先弄清楚“正则→NFA→DFA→代码”各环节的衔接

编译原理实验报告最容易卡在两个环节：NFA 画得出来，DFA 却确定化失败；DFA 画得出来，代码却跑不对。这份围绕 TEST 语言编写词法分析程序的设计型实验报告，走的是最传统也最稳妥的链路——先用正则描述六类词法规则，再用 Thompson 构造法生成 NFA，然后合并、子集构造确定化、划分法最小化，最后用一张状态转移表写成 Python 分析器，附带把合法单词写入 lex.txt、把词法错误连同行列号报告出来。

它本质上是一份可以直接拿来对照的工程底稿，而非单纯讲解概念的教材。你卡在哪个格子，就翻到对应那一节。适合三类人：正在交这份实验报告的人、想从零手写第一个 lexer 却停在状态表上的人、以及想搞清楚“//和/为什么总打架”的后端或工具链方向开发者。

2. 正则到 NFA：六类词法规则先整理成便于计算的表示

这一章最容易被跳过去，因为正则写起来太像“自然会做的事”。但词法分析里绝大部分纠缠不清的问题，都出在正则阶段没把歧义处理干净——直接带着歧义进入 DFA，后面画多少张图都白搭。下面按规则拆分、构造、合并三步来看。

2.1 先把 TEST 语言的六类词拆成正则与优先级

报告里给出的规则是标识符、保留字、无符号整数、分界符、运算符、注释符六类。原文那几行正则写得比较口语，实操时需要补充精确化，主要补充两个地方：注释符那条写成/|/明显是笔误，应当是//[^\n]*；保留字那条和后面的单词分类表是重叠的——分类表里int同时出现在“关键字”和“保留字”里，if/else/while也两边都列。这种笔误交作业时很常见，但在实现层面必须先选定一种方案。

我的习惯是让正则层面只保留“标识符”，保留字不参与 NFA 构造，识别出标识符之后再回查一张哈希表。理由很直接：保留字在字符构成上完全是标识符的子集，如果你给它单独构造 NFA，合并之后i、in、int这些前缀重合的路径会让子集构造多出一堆互不可分的状态，而最小化阶段又会因为终态标签不同而分不开，最终带来不必要的麻烦。回查一张表只需要一次字典查找，代价几乎为零。

落实到字符类简写，优先级从高到低大致是这样：

这张表里最值得琢磨的是优先级 1 和 2。注释和除号的首字符都是/，双字符运算符和单字符运算符互为前缀，这两组如果在正则层面不区分开，后面状态表里就会出现“某一格既该去 A 又该去 B”的情况。教材上的标准答案是靠最长匹配加规则优先来解决，但落到代码里，最省事的做法是在进入状态机之前做一次定长前瞻，具体在 4.3 节展开。

提示：0|[1-9][0-9]*这条正则背后的意思是“不允许前导零”。报告里那个abc = 012345;的例子，如果你按字面写[0-9]+，012345会被整体识别成一个大整数；按上面这条正则，它会被拆成0和12345两个 token。两种都不算错，但你在实验报告里得说清楚自己按哪一种处理，否则结果对不上。

2.2 Thompson 构造：每条正则怎么生成带 ε 边的 NFA

正则到 NFA 的转换有现成套路，不需要自己设计。Thompson 构造只依赖三条基本规则加一条组合规则：单个字符a对应两个状态一条标a的边；连接就是把上一段的接受状态用 ε 边接到下一段的初态；选择就是在分叉处加新初态，两条 ε 边分别进两个分支，两个分支的接受态再用 ε 边汇到新终态；闭包*则是在分支前后各加一条 ε 回边。

拿标识符这条最常用的规则走一遍，[a-zA-Z][a-zA-Z0-9]*展开后是一个“先一个字母，再任意多个字母或数字”的结构：

严格按 Thompson 构造，*结构外面还会多套两层 ε 状态，上面这张表已经是压过一道的版本。这一步的化简在纸面上做掉不亏：每省一个状态，后面子集构造就少算一次闭包，而且手工演算时更不容易抄错。

无符号整数那条0|[1-9][0-9]*因为带选择，NFA 会长成一个两分支结构：新初态用 ε 分叉，一路到单个0的接受态，一路进[1-9]再循环[0-9]。双字符运算符>=|<=|==|!=同理，是四条两字符路径的并联。这两类规则状态数不多，但 ε 边多，手算闭包时最容易被漏掉。

构造完这一轮，你会得到一个状态数在几十这个量级的分散 NFA 集合。注意这个量级不是巧合——六类规则里状态最多的是双字符运算符和分界符，各自都是短路径，真正让状态数膨胀的是 ε 边的密度，而不是分支本身。

2.3 合并 NFA：一个统一初态省掉后面的重复活

分散的 NFA 没法直接确定化，得先合并。标准做法是新建一个初态 S0，用 ε 边分别指向每一条规则 NFA 的初态，其余结构原样保留。这样从 S0 出发的一步闭包就能同时覆盖“第一个字符可能是字母、数字、运算符、括号、斜杠”的所有情形，正好对应词法分析器面对源码时的真实处境。

合并时有一个必须做的动作：给每个终态打上类别标签。标识符的接受态标ID，整数的标NUM，运算符的标OP，分界符的标DELIM。没有这个标签，确定化之后你只知道“这个子集里含接受态”，却不知道它到底该输出哪种 token，前面的构造全白做。

注意：合并时不要图省事把所有终态用 ε 边汇到一个统一终态上。那样做确实能让图看起来干净，但代价是终态信息全部丢失，最小化阶段ID和NUM会被并成一类，最后abc和123输出同一个类型。这是新手最常踩的一个“看起来更优雅”的坑。

合并完之后可以数一下规模：六类规则加一个统一初态，状态总数大致在三十到四十之间，ε 边占了将近一半。这个数字决定了下一章手算子集构造的工作量——如果超过五十个状态还没有化简，基本都是正则写宽松了，比如把保留字也单独构造进去。

3. NFA 确定化与最小化：子集构造和划分法怎么手算不糊

从 NFA 到能写进代码的状态表，中间隔着确定化和最小化两道工序。课本上的算法描述都很简短，真正动手时会发现麻烦在于“闭包算漏一个状态就得整表重来”。这一章把两道工序拆成可以逐步核对的步骤。

3.1 子集构造：ε-closure 与 move 的三步循环

子集构造的核心是两个函数：ε-closure(T)求集合 T 里所有状态经任意条 ε 边能到达的状态集合，move(T, a)求集合 T 里所有状态经一条标a的边能到达的状态集合。确定化就是一个不断“取闭包、走一步、再取闭包”的循环。

写成代码更好核对，下面这段只做演示，不追求性能：

# 演示用的闭包计算，eps 是 {状态: [后继状态, ...]} 的邻接表 def eps_closure(states, eps): stack = list(states) out = set(states) while stack: s = stack.pop() for t in eps.get(s, ()): # 沿 ε 边走 if t not in out: out.add(t) stack.append(t) # 新状态也要继续展开 return frozenset(out) # 走一条标 a 的边，得到目标状态集合（不含闭包） def move(states, a, trans): out = set() for s in states: for (sym, t) in trans.get(s, ()): if sym == a: out.add(t) return out

eps_closure用显式栈而不是递归，是因为 NFA 里存在 ε 回路（闭包结构必然产生），递归写法在环上会直接爆栈。move里那个sym == a的判断是子集构造唯一需要区分输入符号的地方，其余全是集合运算。

主循环的写法是：把eps_closure({S0})作为第一个集合，标记为未处理；反复取一个未处理集合 T，对字母表里每个符号 a 算出U = eps_closure(move(T, a))，如果 U 非空且没出现过就加入集合族，同时在转移表里记下T --a--> U；直到所有集合都处理完。

这里的字母表是关键参数。别拿完整 ASCII 当字母表，那会出来上百列，手工算根本算不完。按 2.1 节的字符类压缩成六类就够：ALPHA、DIGIT、OP、DELIM、SPACE、OTHER。压缩之后转移表的列数从 128 降到 6，行数也就是确定化出来的子集个数，通常十几到二十几行，一张 A4 纸画得下。

下面是从合并 NFA 确定化出来后，几个关键子集的样子（符号用上面六类简写）：

表里那个E（错误态）值得单独留一格。很多同学画 DFA 时把未定义的转移直接省略，结果写代码的时候遇到@、$这种字符就不知道往哪走，程序要么抛异常要么死循环。显式保留一个错误状态，反而让代码结构更干净。

手工演算时有一个自检办法：数一下确定化之后的行数，如果比 NFA 的状态数还多，八成是某个集合的闭包算错了，多生成了不该存在的子集。正常的确定化，子集个数一般不超过原状态数。

3.2 最小化：初始划分和反复分裂的判定条件

确定化出来的 DFA 往往还有冗余状态——两个状态对所有输入符号的反应完全相同，那就没有分开的必要。划分法最小化就是不断把“行为一致”的状态合并到一起的迭代过程。

第一刀是初始划分，这是最容易做错的地方。教材上的标准写法是按“终态 / 非终态”分成两组，但词法分析的 DFA 不能这么分。原因前面提过一次：终态带着类别标签，ID和NUM都是终态，但对同一个输入符号的反应完全不同（ID 吃字母，NUM 吃数字），合并之后类型信息就丢了。正确的初始划分是按标签分组：{ID 组}、{NUM 组}、{OP 组}、{DELIM 组}、{非终态组}，一共五组。

之后的每一轮，对每个组里的每个状态，检查它对每个输入符号的去向是否仍落在同一个组里。如果有状态在某一个符号上跑到了别的组，这个组就要拆。拆到某一轮没有任何组发生变化，划分就稳定了。

手工做的时候用一张表对着勾最清楚：

真实规模下这个表大概要迭代三四轮。每轮都要把所有组、所有状态、所有输入符号过一遍，纸面上大概要写满一页。这一步没什么捷径，但有个省力办法：先把明显不同的组拆开（起始态和中间态对几乎所有符号的反应都不同），剩下那些“看起来差不多”的状态才需要逐符号比对。

最小化完成之后，状态数通常会从二十几降到七八个。报告里最终那张表的七个状态——START、ID、NUM、OPERATOR、DELIMITER、COMMENT、ERROR——就是这个量级，说明前面的构造和确定化没有多走路。

3.3 把最小 DFA 转成状态转移表：状态名怎么起才方便调试

从图到表是最后一步纸面工作，也是最影响后面写代码体验的一步。状态名建议直接起成语义名而不是q0、q1，理由是调试阶段你会在日志里看到大量状态名，q7这种编号过两天自己都认不出来。

命名沿用报告里的那套就挺好，只做一点调整：把COMMENT状态拿掉，理由在 4.1 节解释。剩下六个状态，接受态集合是{ID, NUM, OPERATOR, DELIMITER}，START和ERROR不是接受态。

转移表按字符类做列，写出来是这样（空表示无转移，会触发回退）：

OPERATOR和DELIMITER两行全空，看起来像没写完，其实是正确的：一个运算符或分界符读到一个字符就该结束，多读一个就得回退。这张表最大的价值不是它填了什么，而是它明确地把“这些位置什么都没有”写了出来——写代码时dict.get()返回None，回退逻辑自然就触发了。

提示：ID那行只有ALPHA和DIGIT两格有转移。如果哪天你发现自己在ID行的OP或DELIM列上填了ID，那就是把“标识符后面跟分号”当成一个 token 了。报告原文里那张表恰好就有这个问题，第 5 章会展开讲。

4. 表驱动词法分析器：一张转移表加一个回退循环

纸面上的 DFA 转成代码，核心就三样东西：字符分类函数、转移表字典、带最长匹配的主循环。这一章按这三样逐层展开，代码可以直接跑。

4.1 字符分类函数与/单独处理的必要性

字符分类函数决定了转移表的列数，也决定了 DFA 的粒度。粒度太细（按 ASCII 每个字符一列）表会大到没法维护，粒度太粗（只分字母和“其他”）又识别不出运算符。按 2.1 节压缩出来的五类正好：

def char_class(ch): if ch.isalpha(): return 'ALPHA' if ch.isdigit(): return 'DIGIT' if ch in '+-*/<>=!': return 'OP' if ch in '(){};:,': return 'DELIM' return 'OTHER'

isalpha()而不是'a' <= ch <= 'z'，是因为前者对大小写都成立，跟 2.1 节的[a-zA-Z]对得上。OP里把/和!一起放进去，看起来和注释符的特殊地位矛盾，但这是有意的：让/在状态机层面和别的运算符一样走OPERATOR状态、单字符接受，注释的判定放在状态机外层用两字符前瞻处理，比在转移表里塞一个SLASH中间态要稳。

原因是 DFA 天然不擅长表达“读到这个字符后还得看下一个字符”这件事。你当然可以加一个SLASH状态，让它对OP类转移到一个LINECOMMENT状态，但LINECOMMENT要接受任意非换行字符，等于在表里开了一整行通配，最小化阶段这一行会把周围的状态全搅在一起。实际工程里的词法分析器几乎都用前瞻代替——代价是两行代码，收益是转移表干净。

注意：char_class里没有处理空白和换行。它们在主循环开头就被拦掉，不进状态机。这样做的结果是转移表少两列，代价是主循环多两个if。这个交换很划算，因为空白的处理逻辑（换行要重置列号）本来就该独立于状态机。

4.2 从最小 DFA 抄出转移表，哪些格子必须改

把 3.3 节那张表原样写成字典，就是下面这段。注意None的用法——它表示“这个格子没有转移”，和“这个格子指向错误态”是两回事，前者触发回退，后者直接报错。

TRANS = { # 起始态：看到什么字符就进什么状态 'START': {'ALPHA': 'ID', 'DIGIT': 'NUM', 'OP': 'OPERATOR', 'DELIM': 'DELIMITER', 'OTHER': None}, # 标识符：只吃字母和数字，其余一律无转移（触发回退） 'ID': {'ALPHA': 'ID', 'DIGIT': 'ID', 'OP': None, 'DELIM': None, 'OTHER': None}, # 整数：只吃数字 'NUM': {'ALPHA': None, 'DIGIT': 'NUM', 'OP': None, 'DELIM': None, 'OTHER': None}, # 运算符与分界符：单字符即接受，不再往后吃 'OPERATOR': {'ALPHA': None, 'DIGIT': None, 'OP': None, 'DELIM': None, 'OTHER': None}, 'DELIMITER':{'ALPHA': None, 'DIGIT': None, 'OP': None, 'DELIM': None, 'OTHER': None}, } ACCEPT = {'ID': 'Identifier', 'NUM': 'UnsignedInt', 'OPERATOR': 'Operator', 'DELIMITER': 'Delimiter'}

ACCEPT这个字典把状态名映射到输出类型名，是 3.3 节“终态带标签”的代码版本。单独抽出来而不是写死在状态名里，好处是输出格式要改（比如实验报告要求输出中文类型名）时只动这一处。

最关键的修正在ID那一行。报告原文给出的转移表里，ID状态对运算符、分界符、斜杠都填了ID，意味着x;会被整段吃成一个标识符。按上面这张表，ID状态读到;时get('DELIM')返回None，循环立刻停下来，回退到上一个接受位置，x和;就分开了。

4.3 最长匹配的具体实现：接受状态加回退

状态机本身只能“走一步看一步”，最长匹配需要在外面套一层：记录最近一次经过接受状态时的位置，走到没路可走时回退到那个位置。

KEYWORDS = {'int', 'if', 'else', 'while', 'for', 'do', 'write', 'read'} TWO_CHAR_OPS = {'>=', '<=', '==', '!='} def tokenize(src): tokens, errors = [], [] i, n = 0, len(src) line, col = 1, 1 while i < n: ch = src[i] # 1) 空白与换行：只推进位置，不产出 token if ch in ' \t\r': i += 1; col += 1; continue if ch == '\n': i += 1; line += 1; col = 1; continue # 2) 注释：必须先于除号判断，否则 / 会被当成运算符 if src.startswith('//', i): k = src.find('\n', i) if k == -1: i = n # 注释一直到文件末尾 else: col += <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>