简介面向高校编译原理课程实验场景的「NFA转DFA并最小化」配套资料适合正在完成有限自动机实验、需要对照代码与报告框架的本科生参考。压缩包共2个文件包含1份doc实验报告和1份cpp实现代码包体约722KB报告侧重实验目的、步骤与问题分析代码可用于复现子集构造法转换及DFA最小化流程。已有416人学习下载说明该实验需求较为集中。读者可据此理解NFA状态子集如何映射为DFA状态、如何识别并合并等价状态也能参考报告的组织方式记录实验过程、结果与排错思路便于将自动机理论落到C实现与课程提交中。1. 从一份实验报告翻车说起NFA转DFA并最小化到底在练什么A同学把编译原理实验交上去正则表达式能跑但一测最小化就多出两个状态报告里的DFA图跟程序输出对不上。问题不在算法而在子集构造阶段状态编号和空串闭包没对齐。这份实验包围绕NFA转DFA并最小化这条主线用C把Thompson构造、子集构造、等价类划分串成一条可调试的链路附带的实验报告把每一步中间结果都留了痕迹。适合正在做编译原理实验、想照着跑通再改造成词法分析器前端的人。代码不追求工程化但状态集、转移表、闭包这些关键结构都能单独拎出来看C基础够用就能顺着改。2. 项目结构与数据模型状态集、转移表、闭包怎么落地先把目录摊开看。这套材料不是单个main.cpp堆到底而是把NFA、DFA、最小化、测试输入分开实验报告单独放docs。常见做法是下面这种结构拿到手先对照一遍后面改代码不至于找不到入口。nfa2dfa-min/ ├── include/ │ ├── nfa.h # NFA状态、转移、Thompson构造声明 │ ├── dfa.h # DFA状态、转移表、子集构造声明 │ └── minimize.h # 最小化接口 ├── src/ │ ├── nfa.cpp # epsilon闭包、move、NFA构造 │ ├── dfa.cpp # 子集构造、DFA输出 │ ├── minimize.cpp # 等价类划分、重建转移表 │ └── main.cpp # 命令行入口读输入、串流程 ├── tests/ │ ├── case1.txt # 基础正则 (a|b)*abb │ ├── case2.txt # 含空串分支 │ └── case3.txt # 最小化可合并状态 ├── docs/ │ └── report.md # 实验报告目的、原理、测试、心得 ├── CMakeLists.txt └── README.md这个划分的好处是NFA相关逻辑只依赖nfa.hDFA子集构造只依赖dfa.h最小化再单独一层。调试时可以在main.cpp里按阶段打印不会把中间结果搅在一起。实验报告放在docs/report.md里面通常包含实验目的、算法原理、核心代码说明、测试用例与结果、复杂度分析、遇到的问题。报告不是装饰后面排查状态编号对不上时报告里的中间表就是对照物。2.1 用结构体表达NFA和DFA别一上来就上bitsetNFA的状态转移允许一个字符对应多个后继还允许空串转移DFA则要求每个状态对每个输入字符最多一个后继。数据模型要把这个差异表达清楚不然后面子集构造会写得很别扭。// include/nfa.h #pragma once #include vector #include string #include map const char EPS #; // 约定 # 表示空串输入字符集里不能出现 struct NFATrans { char ch; // 转移字符EPS 表示空串 int to; // 目标状态编号 }; struct NFAState { int id; bool isFinal false; std::vectorNFATrans trans; // 允许重复字符、多条空串边 }; struct NFA { int start 0; std::vectorNFAState states; std::vectorchar alphabet; // 显式字母表不含 EPS };NFATrans用vector存而不是mapchar, vectorint原因是Thompson构造会频繁追加边vector尾部插入更直接遍历时也不用先找key。alphabet单独存一份是为了最小化阶段划分等价类时按统一字母表扫描如果只从转移边里临时收集遇到某个字符在部分状态缺失就会漏判。EPS选#是实验里常见的占位做法输入正则时约定不出现这个字符即可。DFA这边更简单转移表用二维数组或map都行。状态数在实验规模下不会太大常见做法是用vectorvectorint行是DFA状态列对应字母表下标-1表示没有转移。// include/dfa.h #pragma once #include vector #include nfa.h struct DFAState { int id; bool isFinal false; std::vectorint nfaStates; // 这个DFA状态由哪些NFA状态组成调试用 }; struct DFA { int start 0; std::vectorDFAState states; std::vectorchar alphabet; std::vectorstd::vectorint table; // table[state][chIndex] 目标状态或 -1 };nfaStates这个字段很关键。子集构造出错时只看DFA编号很难定位把每个DFA状态对应的NFA状态集合打印出来能立刻看出是闭包漏了还是move算错了。table用-1表示缺失转移最小化之前要补一个死状态否则划分算法会把“没有转移”和“转移到某个状态”混为一谈。2.2 输入格式和实验报告的对应关系实验包一般用文本输入描述正则表达式或NFA。常见做法是支持两种模式一种直接给正则程序走Thompson构造另一种给NFA五元组跳过构造直接子集构造。tests/case1.txt这类文件里通常第一行是模式第二行是字母表后面是转移。regex (a|b)*abb alphabet a b如果是直接给NFA格式会写成nfa states 6 start 0 final 5 trans 0 # 1 1 a 2 2 # 3 ...main.cpp读第一行判断模式再分派。这个设计对实验报告友好报告里可以分别贴“正则输入”和“NFA输入”的测试结果说明Thompson构造和子集构造都能单独验证。字母表不要从正则里猜显式写出来最小化阶段才能稳定按列扫描。2.3 构建脚本别写太花能一键编译就行实验代码规模不大CMakeLists.txt保持朴素即可。把src下所有.cpp编进一个可执行文件头文件目录加上include。cmake_minimum_required(VERSION 3.10) project(nfa2dfa_min CXX) set(CMAKE_CXX_STANDARD 11) set(CMAKE_CXX_STANDARD_REQUIRED ON) include_directories(include) add_executable(nfa2dfa src/main.cpp src/nfa.cpp src/dfa.cpp src/minimize.cpp )C11足够用auto、范围for、std::set、std::map这些就能把子集构造写清楚。不追新标准是为了兼容实验室机器避免学弟拿老版本g编译报一屏错。编译命令后面第4章会给先记住入口是nfa2dfa参数用-f指定输入文件、-o指定输出文件即可。3. 核心链路拆解Thompson构造、子集构造、最小化三步走整条链路是“正则 → NFA → DFA → 最小DFA”。实验报告里通常把这三步分别叫Thompson构造、子集构造法、DFA最小化。代码上不要试图一个函数写完按阶段切函数中间结果都能落盘调试成本会低很多。3.1 Thompson构造把正则拆成带空串边的NFA片段Thompson构造的核心是每个正则子表达式对应一个NFA片段片段有唯一入口和唯一出口片段之间用空串边连接。实现时不必真的建“片段对象”用两个int表示入口和出口状态编号就够了。// src/nfa.cpp节选 int NFA::newState() { NFAState s; s.id static_castint(states.size()); states.push_back(s); return s.id; } void NFA::addEdge(int from, char ch, int to) { states[from].trans.push_back({ch, to}); } // 构造 a|b 的片段新入口 - a片段 / b片段 - 新出口 std::pairint,int NFA::buildUnion(std::pairint,int left, std::pairint,int right) { int in newState(); int out newState(); addEdge(in, EPS, left.first); addEdge(in, EPS, right.first); addEdge(left.second, EPS, out); addEdge(right.second, EPS, out); return {in, out}; }newState()只负责追加状态并返回编号addEdge()不检查重复边因为NFA本来就允许同一对状态之间有多条不同字符的边也允许重复空串边。buildUnion返回的是新片段的入口和出口调用方不需要知道内部结构。连接两个片段时常见做法是addEdge(left.second, EPS, right.first)把左出口用空串边接到右入口。星号闭包则额外加“跳过”和“回环”两条空串边。这里容易忽略的是字母表维护每遇到一个普通字符就把它加入alphabet并去重。不要在最后从所有边里扫因为空串边会混进来而且顺序不稳定会影响后面DFA转移表的列顺序。3.2 空串闭包和move子集构造的两块地基子集构造每一步都要算两个东西epsilonClosure(S)把集合S里所有状态沿空串边能到达的状态都收进来move(S, ch)把S里所有状态沿字符ch走一步得到的目标集合。这两个函数写错后面全错。// src/nfa.cpp节选 #include set #include stack std::setint NFA::epsilonClosure(const std::setint input) const { std::setint closure input; std::stackint work; for (int s : input) work.push(s); while (!work.empty()) { int cur work.top(); work.pop(); for (const auto e : states[cur].trans) { if (e.ch ! EPS) continue; if (closure.find(e.to) closure.end()) { closure.insert(e.to); work.push(e.to); // 新收进来的状态还要继续沿空串扩展 } } } return closure; } std::setint NFA::move(const std::setint input, char ch) const { std::setint result; for (int s : input) { for (const auto e : states[s].trans) { if (e.ch ch) result.insert(e.to); } } return result; }epsilonClosure先把输入集合整体放进closure再用栈做深度优先扩展。关键点是初始集合里的状态本身也要算在闭包里不能只扩展新状态。move只沿指定字符走一步不处理空串空串由闭包函数负责。两个函数都返回std::setint因为子集构造要把状态集合当作map的keyset天然有序比较和打印都稳定。参数上input传的是当前DFA状态对应的NFA状态集合ch必须是字母表里的字符不能传EPS。如果传了EPSmove会返回空集看起来像“没有转移”实际是调用方用错了函数。3.3 子集构造用队列把新状态一个个挖出来子集构造从NFA初始状态的空串闭包开始每遇到一个字母表字符就做一次move再求闭包得到的新集合如果没出现过就分配新DFA编号并入队。// src/dfa.cpp节选 #include queue #include map DFA subsetConstruction(const NFA nfa) { DFA dfa; dfa.alphabet nfa.alphabet; std::mapstd::setint, int idOf; // NFA状态集合 - DFA编号 std::queuestd::setint work; std::setint startSet nfa.epsilonClosure({nfa.start}); idOf[startSet] 0; work.push(startSet); dfa.states.push_back({0, false, {}}); dfa.start 0; while (!work.empty()) { std::setint cur work.front(); work.pop(); int curId idOf[cur]; // 当前集合里只要有一个NFA终态这个DFA状态就是终态 bool final false; for (int s : cur) { if (nfa.states[s].isFinal) { final true; break; } } dfa.states[curId].isFinal final; dfa.states[curId].nfaStates.assign(cur.begin(), cur.end()); for (char ch : nfa.alphabet) { std::setint nxt nfa.epsilonClosure(nfa.move(cur, ch)); if (nxt.empty()) continue; // 没有转移表里留 -1 if (idOf.find(nxt) idOf.end()) { int newId static_castint(dfa.states.size()); idOf[nxt] newId; dfa.states.push_back({newId, false, {}}); work.push(nxt); } // 后面统一建表时再填避免 table 行数变化导致越界 } } // 建转移表行数确定为 dfa.states.size()列数为字母表大小 dfa.table.assign(dfa.states.size(), std::vectorint(dfa.alphabet.size(), -1)); for (const auto kv : idOf) { int from kv.second; for (size_t i 0; i dfa.alphabet.size(); i) { char ch dfa.alphabet[i]; std::setint nxt nfa.epsilonClosure(nfa.move(kv.first, ch)); if (!nxt.empty()) dfa.table[from][i] idOf[nxt]; } } return dfa; }这段代码为了可读性做了两遍扫描第一遍只负责发现新集合、分配编号第二遍等dfa.states大小稳定后再建表。很多实验代码边发现边填表结果table行数随着push_back变化之前填的行被重新分配出现“转移表错位”的玄学问题。参数上idOf的key必须用有序容器std::setint可以直接比较如果换成vectorint入队前必须排序否则{1,2}和{2,1}会被当成两个状态DFA状态数直接翻倍。nxt.empty()时直接跳过表示该字符没有转移。这里不要急着补死状态死状态留到最小化阶段统一补子集构造阶段保持“部分转移”更贴近教材。3.4 最小化先补死状态再按等价类切分DFA最小化的划分法步骤不复杂先把状态分成终态组和非终态组然后反复检查每个组里状态对每个字符的转移是否落在同一个组不在就切开直到组数不再变化。最后每个组选一个代表重建转移表。// src/minimize.cpp节选 #include map #include set int ensureTrap(DFA dfa) { // 检查是否已有所有字符都回到自己的死状态没有就补一个 for (size_t i 0; i dfa.states.size(); i) { bool allSelf true; for (size_t c 0; c dfa.alphabet.size(); c) { if (dfa.table[i][c] ! static_castint(i)) { allSelf false; break; } } if (allSelf !dfa.states[i].isFinal) return static_castint(i); } int trap static_castint(dfa.states.size()); dfa.states.push_back({trap, false, {}}); dfa.table.push_back(std::vectorint(dfa.alphabet.size(), trap)); for (size_t i 0; i dfa.table.size(); i) { for (size_t c 0; c dfa.alphabet.size(); c) { if (dfa.table[i][c] -1) dfa.table[i][c] trap; } } return trap; }ensureTrap先找有没有现成的“全自环非终态”没有就追加一行全指向自己的状态再把所有-1补成trap。补完之后DFA变成完整转移函数划分算法才不会把“缺失转移”误判成等价。trap本身不参与最终保留最小化结束后可以从结果里删掉但中间计算必须留着。划分过程用std::mapint,int记录每个状态属于哪个组初始时终态一组、非终态一组。每轮按字母表逐列比较发现组内分裂就重新编号直到映射不再变化。std::vectorint groupOf(dfa.states.size(), 0); // 初始划分终态 1非终态 0 for (size_t i 0; i dfa.states.size(); i) groupOf[i] dfa.states[i].isFinal ? 1 : 0; bool changed true; while (changed) { changed false; std::mapstd::vectorint, int signatureId; std::vectorint newGroup(dfa.states.size(), 0); int nextId 0; for (size_t i 0; i dfa.states.size(); i) { std::vectorint sig; sig.push_back(groupOf[i]); // 当前组号也作为签名的一部分 for (size_t c 0; c dfa.alphabet.size(); c) sig.push_back(groupOf[dfa.table[i][c]]); if (signatureId.find(sig) signatureId.end()) signatureId[sig] nextId; newGroup[i] signatureId[sig]; if (newGroup[i] ! groupOf[i]) changed true; } groupOf newGroup; }签名里放当前组号是为了避免两个本来不同组的状态因为转移目标组号碰巧相同被合并。nextId每轮重新从0开始编号只要changed为真就继续。循环结束后groupOf相同的状态就是等价状态选每组第一个作为代表重建table即可。重建时注意起始状态所在的组要变成新的起始状态终态标记也要跟着组合并。4. 跑起来与验证编译命令、输入格式、测试用例怎么设计代码能编译不代表结果对。这个实验最怕“跑通了但DFA多两个状态”所以运行阶段要按阶段验证先看NFA构造对不对再看子集构造的DFA状态数最后看最小化前后的状态数变化。4.1 编译和运行的最小命令集用CMake走一遍命令不花哨mkdir -p build cd build cmake .. make -j4 ./nfa2dfa -f ../tests/case1.txt -o out.txt如果不想用CMake直接g也能编g -stdc11 -Iinclude src/*.cpp -o nfa2dfa ./nfa2dfa -f tests/case1.txt -o out.txt-f指定输入文件-o指定输出文件。main.cpp里建议加一个-v参数把NFA状态数、DFA状态数、最小化后状态数打到标准错误输出文件只放最终结果。这样跑测试脚本时能直接抓数字对比不用打开文件数行数。4.2 三个测试用例分别验证什么tests/case1.txt用(a|b)*abb这是教材里最常见的例子最小化前后状态数应该有明显下降。case2.txt带空串分支比如a(b|#)c专门验epsilonClosure有没有把初始状态自己算进去。case3.txt构造两个等价状态验证最小化确实合并了该合并的状态。regex (a|b)*abb alphabet a b跑完case1输出里DFA状态数常见是5个左右最小化后4个左右具体数字随构造方式略有差异不要死记。重点看两件事最小化后的DFA接受的语言和原NFA一致最小化后的状态数不大于最小化前。验证语言一致可以用一组正例和反例字符串写个简单脚本喂给程序看接受/拒绝是否符合预期。# 假设程序支持 -s 参数对单个字符串做模拟 for s in abb aabb babb abab baab; do ./nfa2dfa -f tests/case1.txt -s $s done如果main.cpp没实现字符串模拟可以在实验报告里手算两条路径对照。更稳的做法是加一个accepts(DFA, string)函数跑测试时直接断言。这个函数不长后面二次开发也能复用。4.3 输出格式让人和报告都能读输出不要只打一个状态数。常见做法是分三段NFA转移、DFA转移表、最小化后的转移表。每段用from --ch-- to的形式终态用[final]标出来。DFA start: 0 state 0 [final]: a-1 b-2 state 1: a-1 b-3 state 2: a-1 b-2 ...这种格式贴进实验报告不用再加工调试时也能直接肉眼追路径。如果输出给Graphviz用可以另加-d参数输出DOT但实验报告里手画状态图仍然需要DOT只是辅助。4.4 实验报告里该放哪些中间结果报告不要只贴最终DFA。至少放三张表NFA状态转移表、子集构造过程中每个DFA状态对应的NFA状态集合、最小化后的等价类划分。第一张表证明Thompson构造的边没连错第二张表证明子集构造的闭包和move算对了第三张表证明划分算法收敛到了稳定分组。这三张表一摆状态编号对不上的问题基本无处藏身。复杂度分析放在报告里也别写成套话。子集构造最坏情况是指数级因为DFA状态数最多到NFA状态集的幂集最小化划分法每轮至少合并或分裂一次轮数有上限实验规模下不用太担心。把这两句结合自己的测试数据说清楚比抄教材公式有说服力。5. 避坑与排查空串闭包、状态编号、死状态这几处最容易翻车这个实验的代码量不大但错一处就全盘皆错。下面几条是血泪经验里出现频率最高的每条按“现象 → 原因 → 解决”走一遍照着对照能省不少时间。5.1 现象DFA初始状态少了一个NFA状态原因通常是epsilonClosure只扩展了新遇到的状态没有把输入集合本身完整保留。比如初始状态0有一条空串边到11又到2如果闭包实现里先把0弹出再处理0自己可能没进结果集。解决是把输入集合整体复制进closure再把其中每个状态入栈扩展扩展时只对新加入的状态继续压栈。std::setint closure input; // 输入集合本身必须先算进去 std::stackint work; for (int s : input) work.push(s);排查时打印初始闭包集合和手算结果对一遍。如果初始闭包就少了后面不用看。5.2 现象DFA状态数比预期多很多出现大量相似状态原因多半是状态集合作为map key时用了无序容器或者用vectorint存集合但没排序。{1,2}和{2,1}被当成两个不同key子集构造就会重复发现“新状态”。解决是统一用std::setint做key或者在入队前对vector排序并去重。另一个隐蔽原因是move返回的集合没有再做闭包就拿来当key导致同一个DFA状态被拆成“闭包前”和“闭包后”两个。排查时把每个DFA状态的nfaStates打印出来看有没有两个状态的NFA集合元素完全相同但编号不同。有的话就是key比较出了问题。5.3 现象最小化后状态数没变甚至变多先检查有没有补死状态。DFA转移表里-1表示缺失转移划分算法按列比较时两个状态一个缺a转移、另一个有a转移如果缺失被当成“无”而不是“到死状态”签名会算错该合并的没合并。解决是在最小化前调用ensureTrap把所有-1补成死状态再参与划分。补完之后记得最终输出时把死状态从结果里去掉否则最小DFA会多一个无用状态。另一个原因是签名里没放“当前组号”只放了转移目标组号导致不同组的状态被误判成相同。把groupOf[i]加进签名第一维即可。5.4 现象最小化后的DFA起始状态不是0输出对不上子集构造时DFA起始状态通常编号为0但最小化重建转移表后如果按组号重新编号起始状态可能变成别的数字。解决是在重建阶段显式记录“起始状态所在的组”把它映射到新编号0或者输出时单独打印start字段不要假设起始状态永远是0。实验报告里的状态图也要以输出为准不要凭记忆画。5.5 现象字母表顺序不同导致两次运行结果不一致alphabet如果从std::setchar或map里收集顺序是稳定的如果从vector里边扫边加遇到重复字符去重方式不同列顺序会变。列顺序一变转移表打印出来就不一样看起来像结果错了。解决是构造NFA时统一维护alphabet每遇到新字符先查重再追加或者最后统一排序。最小化阶段按dfa.alphabet的固定顺序扫描不要临时从转移边里收集字符。排查时把alphabet打印出来两次运行对比。顺序不一致就先修字母表维护别急着怀疑划分算法。6. 二次开发从实验代码到可复用词法分析器前端这份代码作为实验作业是完整的但真要拿去做词法分析器前端还差几块。最值得先做的是把“正则输入”接口稳定下来让buildNFA(regex)返回NFA后面子集构造和最小化不变。这样改词法规则时只动正则层DFA层不用碰。常见做法是加一个RegexParser把|、*、()、字符转义处理好再调Thompson构造。解析器不用写完整实验规模下递归下降足够。第二块是输出DOT方便把最小DFA贴进文档或可视化检查。改造点在minimize.cpp后面加一个导出函数遍历dfa.table输出边终态用双圆框。代码不长void exportDot(const DFA dfa, std::ostream os) { os digraph DFA {\n; os rankdirLR;\n; os start [shapepoint];\n; os start - dfa.start ;\n; for (const auto s : dfa.states) { os s.id [shape (s.isFinal ? doublecircle : circle) ];\n; } for (size_t i 0; i dfa.table.size(); i) { for (size_t c 0; c dfa.alphabet.size(); c) { int to dfa.table[i][c]; if (to 0) { os i - to [label\ dfa.alphabet[c] \];\n; } } } os }\n; }参数就是最小化后的DFA和输出流边标签用字母表字符。导出后拿任意DOT查看器打开能快速看出有没有漏边。第三块是性能实验规模用std::set没问题状态上千后子集构造会明显变慢可以把状态集合换成std::bitset或vectoruint64_t做位图epsilonClosure和move改成位运算。这个改造不影响接口但要把mapsetint,int换成哈希或排序后的位图key测试用例得补一个状态数较大的场景确认优化前后接受的语言一致。验证方法不要只靠肉眼。加一个accepts函数对最小化前后的DFA跑同一组正例反例结果必须一致再对比最小化前后状态数只允许变小或不变。每次改完子集构造或最小化先跑case1到case3再看输出状态数有没有异常波动。从那以后我每次动闭包或划分的代码都强制先把三个用例的中间表打出来对一遍再谈优化。希望帮到你。本文还有配套的精品资源点击获取 
长河君 · 2026/10/24 4:42:21 · 阅读 1.2k NFA转DFA并最小化：C++实现与编译原理实验避坑指南
简介面向高校编译原理课程实验场景的「NFA转DFA并最小化」配套资料适合正在完成有限自动机实验、需要对照代码与报告框架的本科生参考。压缩包共2个文件包含1份doc实验报告和1份cpp实现代码包体约722KB报告侧重实验目的、步骤与问题分析代码可用于复现子集构造法转换及DFA最小化流程。已有416人学习下载说明该实验需求较为集中。读者可据此理解NFA状态子集如何映射为DFA状态、如何识别并合并等价状态也能参考报告的组织方式记录实验过程、结果与排错思路便于将自动机理论落到C实现与课程提交中。1. 从一份实验报告翻车说起NFA转DFA并最小化到底在练什么A同学把编译原理实验交上去正则表达式能跑但一测最小化就多出两个状态报告里的DFA图跟程序输出对不上。问题不在算法而在子集构造阶段状态编号和空串闭包没对齐。这份实验包围绕NFA转DFA并最小化这条主线用C把Thompson构造、子集构造、等价类划分串成一条可调试的链路附带的实验报告把每一步中间结果都留了痕迹。适合正在做编译原理实验、想照着跑通再改造成词法分析器前端的人。代码不追求工程化但状态集、转移表、闭包这些关键结构都能单独拎出来看C基础够用就能顺着改。2. 项目结构与数据模型状态集、转移表、闭包怎么落地先把目录摊开看。这套材料不是单个main.cpp堆到底而是把NFA、DFA、最小化、测试输入分开实验报告单独放docs。常见做法是下面这种结构拿到手先对照一遍后面改代码不至于找不到入口。nfa2dfa-min/ ├── include/ │ ├── nfa.h # NFA状态、转移、Thompson构造声明 │ ├── dfa.h # DFA状态、转移表、子集构造声明 │ └── minimize.h # 最小化接口 ├── src/ │ ├── nfa.cpp # epsilon闭包、move、NFA构造 │ ├── dfa.cpp # 子集构造、DFA输出 │ ├── minimize.cpp # 等价类划分、重建转移表 │ └── main.cpp # 命令行入口读输入、串流程 ├── tests/ │ ├── case1.txt # 基础正则 (a|b)*abb │ ├── case2.txt # 含空串分支 │ └── case3.txt # 最小化可合并状态 ├── docs/ │ └── report.md # 实验报告目的、原理、测试、心得 ├── CMakeLists.txt └── README.md这个划分的好处是NFA相关逻辑只依赖nfa.hDFA子集构造只依赖dfa.h最小化再单独一层。调试时可以在main.cpp里按阶段打印不会把中间结果搅在一起。实验报告放在docs/report.md里面通常包含实验目的、算法原理、核心代码说明、测试用例与结果、复杂度分析、遇到的问题。报告不是装饰后面排查状态编号对不上时报告里的中间表就是对照物。2.1 用结构体表达NFA和DFA别一上来就上bitsetNFA的状态转移允许一个字符对应多个后继还允许空串转移DFA则要求每个状态对每个输入字符最多一个后继。数据模型要把这个差异表达清楚不然后面子集构造会写得很别扭。// include/nfa.h #pragma once #include vector #include string #include map const char EPS #; // 约定 # 表示空串输入字符集里不能出现 struct NFATrans { char ch; // 转移字符EPS 表示空串 int to; // 目标状态编号 }; struct NFAState { int id; bool isFinal false; std::vectorNFATrans trans; // 允许重复字符、多条空串边 }; struct NFA { int start 0; std::vectorNFAState states; std::vectorchar alphabet; // 显式字母表不含 EPS };NFATrans用vector存而不是mapchar, vectorint原因是Thompson构造会频繁追加边vector尾部插入更直接遍历时也不用先找key。alphabet单独存一份是为了最小化阶段划分等价类时按统一字母表扫描如果只从转移边里临时收集遇到某个字符在部分状态缺失就会漏判。EPS选#是实验里常见的占位做法输入正则时约定不出现这个字符即可。DFA这边更简单转移表用二维数组或map都行。状态数在实验规模下不会太大常见做法是用vectorvectorint行是DFA状态列对应字母表下标-1表示没有转移。// include/dfa.h #pragma once #include vector #include nfa.h struct DFAState { int id; bool isFinal false; std::vectorint nfaStates; // 这个DFA状态由哪些NFA状态组成调试用 }; struct DFA { int start 0; std::vectorDFAState states; std::vectorchar alphabet; std::vectorstd::vectorint table; // table[state][chIndex] 目标状态或 -1 };nfaStates这个字段很关键。子集构造出错时只看DFA编号很难定位把每个DFA状态对应的NFA状态集合打印出来能立刻看出是闭包漏了还是move算错了。table用-1表示缺失转移最小化之前要补一个死状态否则划分算法会把“没有转移”和“转移到某个状态”混为一谈。2.2 输入格式和实验报告的对应关系实验包一般用文本输入描述正则表达式或NFA。常见做法是支持两种模式一种直接给正则程序走Thompson构造另一种给NFA五元组跳过构造直接子集构造。tests/case1.txt这类文件里通常第一行是模式第二行是字母表后面是转移。regex (a|b)*abb alphabet a b如果是直接给NFA格式会写成nfa states 6 start 0 final 5 trans 0 # 1 1 a 2 2 # 3 ...main.cpp读第一行判断模式再分派。这个设计对实验报告友好报告里可以分别贴“正则输入”和“NFA输入”的测试结果说明Thompson构造和子集构造都能单独验证。字母表不要从正则里猜显式写出来最小化阶段才能稳定按列扫描。2.3 构建脚本别写太花能一键编译就行实验代码规模不大CMakeLists.txt保持朴素即可。把src下所有.cpp编进一个可执行文件头文件目录加上include。cmake_minimum_required(VERSION 3.10) project(nfa2dfa_min CXX) set(CMAKE_CXX_STANDARD 11) set(CMAKE_CXX_STANDARD_REQUIRED ON) include_directories(include) add_executable(nfa2dfa src/main.cpp src/nfa.cpp src/dfa.cpp src/minimize.cpp )C11足够用auto、范围for、std::set、std::map这些就能把子集构造写清楚。不追新标准是为了兼容实验室机器避免学弟拿老版本g编译报一屏错。编译命令后面第4章会给先记住入口是nfa2dfa参数用-f指定输入文件、-o指定输出文件即可。3. 核心链路拆解Thompson构造、子集构造、最小化三步走整条链路是“正则 → NFA → DFA → 最小DFA”。实验报告里通常把这三步分别叫Thompson构造、子集构造法、DFA最小化。代码上不要试图一个函数写完按阶段切函数中间结果都能落盘调试成本会低很多。3.1 Thompson构造把正则拆成带空串边的NFA片段Thompson构造的核心是每个正则子表达式对应一个NFA片段片段有唯一入口和唯一出口片段之间用空串边连接。实现时不必真的建“片段对象”用两个int表示入口和出口状态编号就够了。// src/nfa.cpp节选 int NFA::newState() { NFAState s; s.id static_castint(states.size()); states.push_back(s); return s.id; } void NFA::addEdge(int from, char ch, int to) { states[from].trans.push_back({ch, to}); } // 构造 a|b 的片段新入口 - a片段 / b片段 - 新出口 std::pairint,int NFA::buildUnion(std::pairint,int left, std::pairint,int right) { int in newState(); int out newState(); addEdge(in, EPS, left.first); addEdge(in, EPS, right.first); addEdge(left.second, EPS, out); addEdge(right.second, EPS, out); return {in, out}; }newState()只负责追加状态并返回编号addEdge()不检查重复边因为NFA本来就允许同一对状态之间有多条不同字符的边也允许重复空串边。buildUnion返回的是新片段的入口和出口调用方不需要知道内部结构。连接两个片段时常见做法是addEdge(left.second, EPS, right.first)把左出口用空串边接到右入口。星号闭包则额外加“跳过”和“回环”两条空串边。这里容易忽略的是字母表维护每遇到一个普通字符就把它加入alphabet并去重。不要在最后从所有边里扫因为空串边会混进来而且顺序不稳定会影响后面DFA转移表的列顺序。3.2 空串闭包和move子集构造的两块地基子集构造每一步都要算两个东西epsilonClosure(S)把集合S里所有状态沿空串边能到达的状态都收进来move(S, ch)把S里所有状态沿字符ch走一步得到的目标集合。这两个函数写错后面全错。// src/nfa.cpp节选 #include set #include stack std::setint NFA::epsilonClosure(const std::setint input) const { std::setint closure input; std::stackint work; for (int s : input) work.push(s); while (!work.empty()) { int cur work.top(); work.pop(); for (const auto e : states[cur].trans) { if (e.ch ! EPS) continue; if (closure.find(e.to) closure.end()) { closure.insert(e.to); work.push(e.to); // 新收进来的状态还要继续沿空串扩展 } } } return closure; } std::setint NFA::move(const std::setint input, char ch) const { std::setint result; for (int s : input) { for (const auto e : states[s].trans) { if (e.ch ch) result.insert(e.to); } } return result; }epsilonClosure先把输入集合整体放进closure再用栈做深度优先扩展。关键点是初始集合里的状态本身也要算在闭包里不能只扩展新状态。move只沿指定字符走一步不处理空串空串由闭包函数负责。两个函数都返回std::setint因为子集构造要把状态集合当作map的keyset天然有序比较和打印都稳定。参数上input传的是当前DFA状态对应的NFA状态集合ch必须是字母表里的字符不能传EPS。如果传了EPSmove会返回空集看起来像“没有转移”实际是调用方用错了函数。3.3 子集构造用队列把新状态一个个挖出来子集构造从NFA初始状态的空串闭包开始每遇到一个字母表字符就做一次move再求闭包得到的新集合如果没出现过就分配新DFA编号并入队。// src/dfa.cpp节选 #include queue #include map DFA subsetConstruction(const NFA nfa) { DFA dfa; dfa.alphabet nfa.alphabet; std::mapstd::setint, int idOf; // NFA状态集合 - DFA编号 std::queuestd::setint work; std::setint startSet nfa.epsilonClosure({nfa.start}); idOf[startSet] 0; work.push(startSet); dfa.states.push_back({0, false, {}}); dfa.start 0; while (!work.empty()) { std::setint cur work.front(); work.pop(); int curId idOf[cur]; // 当前集合里只要有一个NFA终态这个DFA状态就是终态 bool final false; for (int s : cur) { if (nfa.states[s].isFinal) { final true; break; } } dfa.states[curId].isFinal final; dfa.states[curId].nfaStates.assign(cur.begin(), cur.end()); for (char ch : nfa.alphabet) { std::setint nxt nfa.epsilonClosure(nfa.move(cur, ch)); if (nxt.empty()) continue; // 没有转移表里留 -1 if (idOf.find(nxt) idOf.end()) { int newId static_castint(dfa.states.size()); idOf[nxt] newId; dfa.states.push_back({newId, false, {}}); work.push(nxt); } // 后面统一建表时再填避免 table 行数变化导致越界 } } // 建转移表行数确定为 dfa.states.size()列数为字母表大小 dfa.table.assign(dfa.states.size(), std::vectorint(dfa.alphabet.size(), -1)); for (const auto kv : idOf) { int from kv.second; for (size_t i 0; i dfa.alphabet.size(); i) { char ch dfa.alphabet[i]; std::setint nxt nfa.epsilonClosure(nfa.move(kv.first, ch)); if (!nxt.empty()) dfa.table[from][i] idOf[nxt]; } } return dfa; }这段代码为了可读性做了两遍扫描第一遍只负责发现新集合、分配编号第二遍等dfa.states大小稳定后再建表。很多实验代码边发现边填表结果table行数随着push_back变化之前填的行被重新分配出现“转移表错位”的玄学问题。参数上idOf的key必须用有序容器std::setint可以直接比较如果换成vectorint入队前必须排序否则{1,2}和{2,1}会被当成两个状态DFA状态数直接翻倍。nxt.empty()时直接跳过表示该字符没有转移。这里不要急着补死状态死状态留到最小化阶段统一补子集构造阶段保持“部分转移”更贴近教材。3.4 最小化先补死状态再按等价类切分DFA最小化的划分法步骤不复杂先把状态分成终态组和非终态组然后反复检查每个组里状态对每个字符的转移是否落在同一个组不在就切开直到组数不再变化。最后每个组选一个代表重建转移表。// src/minimize.cpp节选 #include map #include set int ensureTrap(DFA dfa) { // 检查是否已有所有字符都回到自己的死状态没有就补一个 for (size_t i 0; i dfa.states.size(); i) { bool allSelf true; for (size_t c 0; c dfa.alphabet.size(); c) { if (dfa.table[i][c] ! static_castint(i)) { allSelf false; break; } } if (allSelf !dfa.states[i].isFinal) return static_castint(i); } int trap static_castint(dfa.states.size()); dfa.states.push_back({trap, false, {}}); dfa.table.push_back(std::vectorint(dfa.alphabet.size(), trap)); for (size_t i 0; i dfa.table.size(); i) { for (size_t c 0; c dfa.alphabet.size(); c) { if (dfa.table[i][c] -1) dfa.table[i][c] trap; } } return trap; }ensureTrap先找有没有现成的“全自环非终态”没有就追加一行全指向自己的状态再把所有-1补成trap。补完之后DFA变成完整转移函数划分算法才不会把“缺失转移”误判成等价。trap本身不参与最终保留最小化结束后可以从结果里删掉但中间计算必须留着。划分过程用std::mapint,int记录每个状态属于哪个组初始时终态一组、非终态一组。每轮按字母表逐列比较发现组内分裂就重新编号直到映射不再变化。std::vectorint groupOf(dfa.states.size(), 0); // 初始划分终态 1非终态 0 for (size_t i 0; i dfa.states.size(); i) groupOf[i] dfa.states[i].isFinal ? 1 : 0; bool changed true; while (changed) { changed false; std::mapstd::vectorint, int signatureId; std::vectorint newGroup(dfa.states.size(), 0); int nextId 0; for (size_t i 0; i dfa.states.size(); i) { std::vectorint sig; sig.push_back(groupOf[i]); // 当前组号也作为签名的一部分 for (size_t c 0; c dfa.alphabet.size(); c) sig.push_back(groupOf[dfa.table[i][c]]); if (signatureId.find(sig) signatureId.end()) signatureId[sig] nextId; newGroup[i] signatureId[sig]; if (newGroup[i] ! groupOf[i]) changed true; } groupOf newGroup; }签名里放当前组号是为了避免两个本来不同组的状态因为转移目标组号碰巧相同被合并。nextId每轮重新从0开始编号只要changed为真就继续。循环结束后groupOf相同的状态就是等价状态选每组第一个作为代表重建table即可。重建时注意起始状态所在的组要变成新的起始状态终态标记也要跟着组合并。4. 跑起来与验证编译命令、输入格式、测试用例怎么设计代码能编译不代表结果对。这个实验最怕“跑通了但DFA多两个状态”所以运行阶段要按阶段验证先看NFA构造对不对再看子集构造的DFA状态数最后看最小化前后的状态数变化。4.1 编译和运行的最小命令集用CMake走一遍命令不花哨mkdir -p build cd build cmake .. make -j4 ./nfa2dfa -f ../tests/case1.txt -o out.txt如果不想用CMake直接g也能编g -stdc11 -Iinclude src/*.cpp -o nfa2dfa ./nfa2dfa -f tests/case1.txt -o out.txt-f指定输入文件-o指定输出文件。main.cpp里建议加一个-v参数把NFA状态数、DFA状态数、最小化后状态数打到标准错误输出文件只放最终结果。这样跑测试脚本时能直接抓数字对比不用打开文件数行数。4.2 三个测试用例分别验证什么tests/case1.txt用(a|b)*abb这是教材里最常见的例子最小化前后状态数应该有明显下降。case2.txt带空串分支比如a(b|#)c专门验epsilonClosure有没有把初始状态自己算进去。case3.txt构造两个等价状态验证最小化确实合并了该合并的状态。regex (a|b)*abb alphabet a b跑完case1输出里DFA状态数常见是5个左右最小化后4个左右具体数字随构造方式略有差异不要死记。重点看两件事最小化后的DFA接受的语言和原NFA一致最小化后的状态数不大于最小化前。验证语言一致可以用一组正例和反例字符串写个简单脚本喂给程序看接受/拒绝是否符合预期。# 假设程序支持 -s 参数对单个字符串做模拟 for s in abb aabb babb abab baab; do ./nfa2dfa -f tests/case1.txt -s $s done如果main.cpp没实现字符串模拟可以在实验报告里手算两条路径对照。更稳的做法是加一个accepts(DFA, string)函数跑测试时直接断言。这个函数不长后面二次开发也能复用。4.3 输出格式让人和报告都能读输出不要只打一个状态数。常见做法是分三段NFA转移、DFA转移表、最小化后的转移表。每段用from --ch-- to的形式终态用[final]标出来。DFA start: 0 state 0 [final]: a-1 b-2 state 1: a-1 b-3 state 2: a-1 b-2 ...这种格式贴进实验报告不用再加工调试时也能直接肉眼追路径。如果输出给Graphviz用可以另加-d参数输出DOT但实验报告里手画状态图仍然需要DOT只是辅助。4.4 实验报告里该放哪些中间结果报告不要只贴最终DFA。至少放三张表NFA状态转移表、子集构造过程中每个DFA状态对应的NFA状态集合、最小化后的等价类划分。第一张表证明Thompson构造的边没连错第二张表证明子集构造的闭包和move算对了第三张表证明划分算法收敛到了稳定分组。这三张表一摆状态编号对不上的问题基本无处藏身。复杂度分析放在报告里也别写成套话。子集构造最坏情况是指数级因为DFA状态数最多到NFA状态集的幂集最小化划分法每轮至少合并或分裂一次轮数有上限实验规模下不用太担心。把这两句结合自己的测试数据说清楚比抄教材公式有说服力。5. 避坑与排查空串闭包、状态编号、死状态这几处最容易翻车这个实验的代码量不大但错一处就全盘皆错。下面几条是血泪经验里出现频率最高的每条按“现象 → 原因 → 解决”走一遍照着对照能省不少时间。5.1 现象DFA初始状态少了一个NFA状态原因通常是epsilonClosure只扩展了新遇到的状态没有把输入集合本身完整保留。比如初始状态0有一条空串边到11又到2如果闭包实现里先把0弹出再处理0自己可能没进结果集。解决是把输入集合整体复制进closure再把其中每个状态入栈扩展扩展时只对新加入的状态继续压栈。std::setint closure input; // 输入集合本身必须先算进去 std::stackint work; for (int s : input) work.push(s);排查时打印初始闭包集合和手算结果对一遍。如果初始闭包就少了后面不用看。5.2 现象DFA状态数比预期多很多出现大量相似状态原因多半是状态集合作为map key时用了无序容器或者用vectorint存集合但没排序。{1,2}和{2,1}被当成两个不同key子集构造就会重复发现“新状态”。解决是统一用std::setint做key或者在入队前对vector排序并去重。另一个隐蔽原因是move返回的集合没有再做闭包就拿来当key导致同一个DFA状态被拆成“闭包前”和“闭包后”两个。排查时把每个DFA状态的nfaStates打印出来看有没有两个状态的NFA集合元素完全相同但编号不同。有的话就是key比较出了问题。5.3 现象最小化后状态数没变甚至变多先检查有没有补死状态。DFA转移表里-1表示缺失转移划分算法按列比较时两个状态一个缺a转移、另一个有a转移如果缺失被当成“无”而不是“到死状态”签名会算错该合并的没合并。解决是在最小化前调用ensureTrap把所有-1补成死状态再参与划分。补完之后记得最终输出时把死状态从结果里去掉否则最小DFA会多一个无用状态。另一个原因是签名里没放“当前组号”只放了转移目标组号导致不同组的状态被误判成相同。把groupOf[i]加进签名第一维即可。5.4 现象最小化后的DFA起始状态不是0输出对不上子集构造时DFA起始状态通常编号为0但最小化重建转移表后如果按组号重新编号起始状态可能变成别的数字。解决是在重建阶段显式记录“起始状态所在的组”把它映射到新编号0或者输出时单独打印start字段不要假设起始状态永远是0。实验报告里的状态图也要以输出为准不要凭记忆画。5.5 现象字母表顺序不同导致两次运行结果不一致alphabet如果从std::setchar或map里收集顺序是稳定的如果从vector里边扫边加遇到重复字符去重方式不同列顺序会变。列顺序一变转移表打印出来就不一样看起来像结果错了。解决是构造NFA时统一维护alphabet每遇到新字符先查重再追加或者最后统一排序。最小化阶段按dfa.alphabet的固定顺序扫描不要临时从转移边里收集字符。排查时把alphabet打印出来两次运行对比。顺序不一致就先修字母表维护别急着怀疑划分算法。6. 二次开发从实验代码到可复用词法分析器前端这份代码作为实验作业是完整的但真要拿去做词法分析器前端还差几块。最值得先做的是把“正则输入”接口稳定下来让buildNFA(regex)返回NFA后面子集构造和最小化不变。这样改词法规则时只动正则层DFA层不用碰。常见做法是加一个RegexParser把|、*、()、字符转义处理好再调Thompson构造。解析器不用写完整实验规模下递归下降足够。第二块是输出DOT方便把最小DFA贴进文档或可视化检查。改造点在minimize.cpp后面加一个导出函数遍历dfa.table输出边终态用双圆框。代码不长void exportDot(const DFA dfa, std::ostream os) { os digraph DFA {\n; os rankdirLR;\n; os start [shapepoint];\n; os start - dfa.start ;\n; for (const auto s : dfa.states) { os s.id [shape (s.isFinal ? doublecircle : circle) ];\n; } for (size_t i 0; i dfa.table.size(); i) { for (size_t c 0; c dfa.alphabet.size(); c) { int to dfa.table[i][c]; if (to 0) { os i - to [label\ dfa.alphabet[c] \];\n; } } } os }\n; }参数就是最小化后的DFA和输出流边标签用字母表字符。导出后拿任意DOT查看器打开能快速看出有没有漏边。第三块是性能实验规模用std::set没问题状态上千后子集构造会明显变慢可以把状态集合换成std::bitset或vectoruint64_t做位图epsilonClosure和move改成位运算。这个改造不影响接口但要把mapsetint,int换成哈希或排序后的位图key测试用例得补一个状态数较大的场景确认优化前后接受的语言一致。验证方法不要只靠肉眼。加一个accepts函数对最小化前后的DFA跑同一组正例反例结果必须一致再对比最小化前后状态数只允许变小或不变。每次改完子集构造或最小化先跑case1到case3再看输出状态数有没有异常波动。从那以后我每次动闭包或划分的代码都强制先把三个用例的中间表打出来对一遍再谈优化。希望帮到你。本文还有配套的精品资源点击获取