编译原理实验：正则表达式转NFA与Lex扫描程序完整实现

简介面向编译原理课程的实验报告完整记录了在 Engintime CP Lab 平台上完成的两项核心实验从正则表达式到非确定有限自动机NFA的转换以及使用 Lex 工具自动生成扫描程序。报告以暨南大学本科实验报告为模板先讲解正则运算符、*、|对应的状态转移及 ε 转移的作用再结合 main.c、RegexpToPost.c、NFAFragmentStack.c 等源码细致梳理 re2post、post2nfa、CreateNFAState、MakeNFAFragment 等关键函数的实现逻辑并说明 NFA 片段栈这一核心数据结构适合计算机科学与技术专业学生复习编译原理、完成同类实验时参考。资源为单个 doc 文档共 1 个文件大小约 1.75MB内容覆盖实验环境使用、项目生成、语法错误定位、演示模式调试等完整记录。已有 1471 人学习浏览实用性较强。报告不仅包含实验步骤与源代码分析还穿插了观察点转储、函数调用与返回信息等调试细节便于读者对照理解正则表达式到自动机转换及词法分析器生成的全过程。1. 编译原理实验从 CP Lab 平台到正则表达式转 NFA 的整条链路编译原理课最劝退的点往往不是理论难而是你对着书背熟了 Thompson 构造法打开 IDE 却不知道从哪里下手。这份实验报告给出了一条完整可跑通的路在 Engintime CP Lab 平台上从 CodeCode.net 领任务、克隆工程项目到本地用观察点调试模式把正则表达式转 NFA 的每一步都可视化出来再用 Lex 自动生成扫描程序。它解决的是纸上会推状态图、代码写不出来的断层问题适合正在做编译原理课程设计、被实验报告困住的计算机系本科生也适合想快速上手 CP Lab 平台、想找一套能直接改的实验骨架的从业者。下文按我的实际拆解顺序从环境、源码、排错到 Lex 扩展逐步过一遍重点讲透 post2nfa 的四个操作符分支和 Lex 规则文件的三段式结构。2. 把工程环境跑通CP Lab 平台配置与观察点调试机制的底层逻辑CP Lab 这个平台和普通 IDE 最大的区别在于两件事一是它的演示模式调试机制二是以 CodeCode.net 为任务分发源的工作流。如果这两点没理解透后面看代码会一直觉得隔了一层。2.1 从领任务到本地克隆CodeCode.net 与本地代码的对应关系实验的第一步不是在本地新建工程而是先到 CodeCode.net 平台领取任务。这一步的本质是获取一个远端仓库地址CP Lab 会把任务内容克隆到本地工作区。克隆完成后你的本地目录里会有一个完整的 C 工程骨架而不是空项目这点和 GitHub Classroom 的做法类似。工程骨架包含核心文件三个头文件 RegexpToNFA.h、RegexpToPost.h、NFAFragmentStack.h以及三个 C 源文件 main.c、RegexpToPost.c、NFAFragmentStack.c。其中 main.c 承担了三件事栈初始化、调用 re2post 把正则表达式转成后序序列、调用 post2nfa 把后序序列转成 NFA。这个三段式流程和书上的理论完全对齐re2post 对应中缀转后缀post2nfa 对应用栈构造状态图。有一点值得注意工程骨架里的 post2nfa 是被刻意留空的。也就是说实验最大的工作量不是理解别人写好的逻辑而是自己把 NFA 构造代码填进去。我在第一次做的时候没意识到这一点还以为是去看代码就行结果生成项目后提示找不到 post2nfa 的定义这才反应过来设计意图。2.2 生成项目与语法错误定位F7 增量构建的工作方式CP Lab 的生成项目快捷键是 F7编译输出会实时显示在输出窗口中这个窗口类似于 Visual Studio 的输出面板。增量编译机制意味着你改一个文件CP Lab 只会重建受影响的部分而不是全量重编。实际体验下来这个机制对源码级别的调试非常友好因为改一次查一次的错误反馈周期很短。定位语法错误的操作方式是在输出窗口双击错误信息光标会自动跳到出错代码行。这个交互很关键因为 CP Lab 的错误输出格式和 VS 接近行号、列号、错误描述三段式。如果定位不了错误可以尝试先点击生成菜单下的清除解决方案再做全量重建否则容易出现改了代码但编译的是旧文件的假象。# CP Lab 生成项目的常用操作菜单路径 生成 - 生成项目 # 快捷键 F7增量构建 生成 - 重新生成解决方案 # 全量重编适合排查诡异问题 调试 - 启动调试 # 快捷键 F5配合演示模式使用参数说明F7 走增量编译适合大多数情况全量重编适合代码大量调整后的一次性验证。我一般会在改动头文件结构后做一次全量重编避免隐式声明之类的坑。2.3 观察点函数与转储信息把黑匣子变成可观察的白盒CP Lab 最有特色的机制是观察点函数。以本实验的正则表达式转 NFA 为例每个操作符的分支比如 |、*、?、都会对应一个观察点。当你开启演示模式并启动调试后CP Lab 会自动打开演示流程窗口逐行执行观察点函数忽略函数体内的真实代码用平台自带的演示功能把执行过程展示出来。同时转储信息窗口会实时列出三类信息函数调用信息、函数返回信息、重要的数据信息。数据信息里最关键的是栈的状态描述包括 NFA 片段的状态名称用数字表示从 1 开始、转换标志比如 VoidTrans 空转换、以及转换到的目标状态。这一步把书上的状态图推演搬到了屏幕上每一步出栈、建新状态、改 AcceptFlag 的过程都看得清清楚楚。我在实际操作中观察到构造单字符 NFA 片段时栈里只有一个片段遇到连接操作符时会先弹两个片段再压入新片段。每按一次 F5栈的变化就被打印一次。这种逐步可视化的调试方式比自己在纸上画十遍状态图都更有说服力。3. 核心代码复现post2nfa 函数里四个操作符分支的完整拆解理解了环境和调试机制后真正的硬骨头是 post2nfa 函数。这个函数接受 re2post 生成的后序序列用 NFAFragmentStack 栈存放中间片段每遇到一个字符或操作符就进行对应的 NFA 片段构造。下面按操作符逐一拆解代码可以直接抄进实验骨架里。3.1 选择操作符 |双片段合并与两个新状态遇到 | 时栈顶的两个片段出栈构造一个新的 NFA 片段。核心逻辑是新建一个开始状态和一个接受状态两个待合并片段的起始状态都通过空转换指向新的开始状态两个片段的接受状态都改为指向新建的接受状态。case |: // 构造选择 NFA 片段 // 栈顶的两个片段出栈构造新的 NFA 片段 fragment2 PopNFAFragment(FragmentStack); fragment1 PopNFAFragment(FragmentStack); // 构造新的开始和结束状态 NewStartState CreateNFAState(); NewAcceptState CreateNFAState(); // 空转换 NewStartState-Transform VoidTrans; NewStartState-Next1 fragment1.StartState; NewStartState-Next2 fragment2.StartState; // 接受状态的 AcceptFlag 1 NewAcceptState-AcceptFlag 1; // 片段1 fragment1.AcceptState-AcceptFlag 0; fragment1.AcceptState-Transform VoidTrans; fragment1.AcceptState-Next1 NewAcceptState; // 片段2 fragment2.AcceptState-AcceptFlag 0; fragment2.AcceptState-Transform VoidTrans; fragment2.AcceptState-Next1 NewAcceptState; fm MakeNFAFragment(NewStartState, NewAcceptState); PushNFAFragment(FragmentStack, fm); break;逻辑说明这里的关键在于每个 NFA 状态有 Transform、Next1、Next2 三个字段。VoidTrans 代表空转移即不消费字符就能跳转。参数说明fragment1 和 fragment2 是从栈里弹出的两个 NFAFragment各自含有 StartState 和 AcceptState。新建的 NewStartState 通过 Next1 和 Next2 分别指向两个片段的起始状态实现二选一的分叉效果。两个片段的接受状态经过修改后都指向同一个 NewAcceptState实现了两个分支汇合到同一终点。3.2 闭包操作符 *自环构造与回流指针* 操作符的处理更巧妙它只需要弹出一个片段新建开始和接受状态然后让原片段的接受状态既能回到自己也能走向新接受状态从而实现零次或多次匹配的循环。case *: // 构造星号 NFA 片段 // 栈顶的片段出栈构造新的 NFA 片段 fragment PopNFAFragment(FragmentStack); // 构造新的开始和结束状态 NewStartState CreateNFAState(); NewAcceptState CreateNFAState(); // 空转换 NewStartState-Transform VoidTrans; NewStartState-Next1 fragment.StartState; NewStartState-Next2 NewAcceptState; // 接受状态的 AcceptFlag 1 NewAcceptState-AcceptFlag 1; // 片段 fragment.AcceptState-AcceptFlag 0; fragment.AcceptState-Transform VoidTrans; fragment.AcceptState-Next1 fragment.StartState; // 关键自环 fragment.AcceptState-Next2 NewAcceptState; fm MakeNFAFragment(NewStartState, NewAcceptState); PushNFAFragment(FragmentStack, fm); break;逻辑说明闭包的核心语义是零次或多次因此 NewStartState 必须同时提供两条路一条直接到 NewAcceptState代表零次另一条经过 fragment代表至少一次。参数说明fragment.AcceptState-Next1 指向自身起始状态这在有向图里就是自环配合 Next2 指向 NewAcceptState实现多次循环后跳出。这个自环指针容易写丢一旦漏写闭包就会退化为最多一次验证时表现是输入 aaa 只匹配首个字符。3.3 可选操作符 ? 与一次或多次操作符 指针指向的对称关系? 和 是 | 和 的一种组合变体。? 实现零次或一次 实现零次或多次 实现一次或多次三者共享同一个新建开始状态和新建接受状态的骨架差别只在指针的指向方式。case ?: // 构造问号 NFA 片段 fragment PopNFAFragment(FragmentStack); NewStartState CreateNFAState(); NewAcceptState CreateNFAState(); NewStartState-Transform VoidTrans; NewStartState-Next1 fragment.StartState; NewStartState-Next2 NewAcceptState; NewAcceptState-AcceptFlag 1; fragment.AcceptState-AcceptFlag 0; fragment.AcceptState-Transform VoidTrans; fragment.AcceptState-Next1 NewAcceptState; fm MakeNFAFragment(NewStartState, NewAcceptState); PushNFAFragment(FragmentStack, fm); break; case : // 构造加号 NFA 片段 fragment PopNFAFragment(FragmentStack); NewAcceptState CreateNFAState(); NewAcceptState-AcceptFlag 1; fragment.AcceptState-AcceptFlag 0; fragment.AcceptState-Transform VoidTrans; fragment.AcceptState-Next1 NewAcceptState; // 结束状态指回片段开始状态形成闭环 NewAcceptState-Transform VoidTrans; NewAcceptState-Next1 fragment.StartState; fm MakeNFAFragment(fragment.StartState, NewAcceptState); PushNFAFragment(FragmentStack, fm); break;逻辑说明? 和 在代码结构上都只需弹出一个片段。? 的特点是原片段的接受状态只指向新接受状态不产生回路配合 NewStartState 的两条路径实现走或不走的选择。 的特点是接受状态会指回片段起始状态形成必须至少走一次的闭环。参数说明注意 ? 的 MakeNFAFragment 用的是新建开始状态而 用的则是 fragment.StartState因为 的语义是至少一次起始状态沿用原片段即可不需要额外的新起点。这个差异是实验里最容易抄错的地方。3.4 字符与连接操作符的处理顺序为什么边界字母不需要额外分支除了四个显式操作符post2nfa 还需要处理两类情况单字符匹配和隐式连接。在代码里单字符的处理方式是创建两个状态起始和接受中间通过字符转换连接然后压栈。隐式连接则发生在相邻两个片段之间把前一个片段的接受状态改为指向后一个片段的起始状态。关键点在于re2post 已经处理了运算符优先级所以 post2nfa 按顺序扫描后序序列时遇到操作数就压栈遇到操作符就弹栈组合不需要再考虑优先级问题。我在复写时一开始试图在 post2nfa 里判断优先级结果弄巧成拙后来才发现优先级已经由 re2post 转后缀时消化干净了post2nfa 只需要像一个计算器一样机械执行。4. 常见问题与排查状态指针错乱、AcceptFlag 失效与碎片化调试代码抄对了实验不一定一次过。我在复现过程中整理了三条最典型的踩坑记录每一条都对应一个具体的 debug 场景。4.1 生成成功但验证失败输入与预期转储信息不一致现象项目能生成、能启动但最后一步验证项目时提示源文件与目标文件内容不一致转储信息显示 NFA 状态数比预期多。原因排查下来发现是 | 操作符的代码里漏写了 fragment2.AcceptState-AcceptFlag 0。由于两个片段共用一个接受状态时前一个片段的接受状态被错误地保留了 AcceptFlag1导致 NFA 出现提前接受的分支状态图正确但语义错误。解决检查所有出栈片段的接受状态确保其 AcceptFlag 全部清零再对新构造的接受状态设置 AcceptFlag1。从那以后我每次写完一个 case 都会先扫一遍所有 AcceptFlag 赋值逻辑。4.2 空转换链死循环演示模式卡在某个观察点无法继续现象演示模式逐行执行到某个观察点函数时光标不再移动界面像死机一样。原因构造 NFA 时出现了环路而且环路上没有消费字符的转换导致 DFA 模拟时在空转换环上无限循环。多发生在 ? 操作符中NewStartState-Next2 和 fragment.AcceptState-Next1 都指向同一个状态时如果该状态又存在回边就会构成环路。解决检查所有 VoidTrans 的指向确保不会出现两个空转换首尾相接形成无意义环。常见做法是在写完每个操作符分支后在纸上画出状态图再对照代码检查状态数不超过五六个的时候这种检查非常快。4.3 修改了源代码但运行结果没变化增量编译的盲目信任现象改了 scan.txt 文件中的正则规则重新生成项目后运行统计结果和修改前一样完全没有生效。原因CP Lab 的增量编译只重建受影响的文件而 Lex 生成 C 代码的流程里scan.txt 被解析生成 main.c 的过程没有触发依赖更新导致一直在运行旧的 main.c。解决在生成菜单选择重新生成解决方案做全量重编或者手动删除生成的 main.c 再重新生成。我现在的习惯是每次改完规则文件都强制全量重建一次宁可比平时慢十几秒也不愿意被旧产物坑十分钟。5. Lex 自动生成扫描程序从规则文件到 yylex 函数的完整落地第二个实验的重头戏在 Lex 工具的使用上。Lex 的输入文件 scan.txt 采用三段式结构定义段、规则段、用户代码段CP Lab 会把这三种内容嵌入生成的 C 代码的不同位置。5.1 三段式文件结构定义段、规则段、用户代码段的映射关系scan.txt 的第一部分是定义段包含 C 头文件引入、宏定义、以及一些 Lex 专用的正则简写。第二部分是规则段核心内容是正则表达式 动作代码的配对Lex 会把这些规则编译成 DFA 驱动的状态转移表。第三部分是用户代码段会被原样拷贝到生成的 main.c 尾部。我在实验中写过的最简可运行规则的骨架如下%{ // 第一部分C 代码区包含 define.h 和其他头文件 #include define.h int num_no 0; int id_no 0; %} // 定义段正则简写 id [A-Za-z] num ([1-9][\d]*)|0 %% // 第二部分规则段 {num} { num_no; } {id} { return ID; } [ \t\n] ; . { return ERROR; } %% // 第三部分用户代码区会被原样拷贝 int main() { // 调用 yylex 的入口逻辑 }逻辑说明第一部分的 %{ %} 块中的内容会插入到生成的 C 代码文件头部这里用来包含 define.h 头文件。规则段里 {num} 和 {id} 是定义段的宏引用本质是把正则模板展开后再匹配。每条规则后面的花括号里是对应的动作可以是计数、返回 token 类型、或者直接忽略。参数说明[ \t\n] 这条规则匹配空白字符并跳过. 匹配任意其他单字符返回 ERROR这样能把非法输入显式暴露出来。5.2 标识符与关键字统计线性搜索与 key_table 的配合添加标识符和正整数统计是第一个练习。规则层的做法已经在上面代码里{num} 匹配数字文本{id} 匹配字母串然后 num_no 或返回 ID。但这里有一个容易踩的规则顺序问题Lex 的匹配原则是最长匹配优先如果两个规则匹配同一文本则取更长的那个。因此关键字需要通过额外手段识别。关键字的处理手段是 id2keyword 函数。这个函数用线性搜索方式遍历 key_table 表格把 identifier 的字符串逐个和关键字表项对比。实验要求不要直接使用字符串逐个匹配关键字的原因在于规则复用直接用字符串匹配会破坏 DFA 的最小化效果也会让规则表变得冗余。用一个统一的 id2keyword 函数既保持了规则的简洁也方便后续改用二分查找优化。// id2keyword 的参考实现线性搜索 key_table typedef struct { char *name; int type; } KeyWord; KeyWord key_table[] { {if, IF}, {then, THEN}, {else, ELSE}, {end, END}, // 其他关键字依次排列 }; int id2keyword(char *id) { int i; for (i 0; i sizeof(key_table) / sizeof(KeyWord); i) { if (strcmp(key_table[i].name, id) 0) { return key_table[i].type; } } return ID; // 非关键字返回标识符类型 }逻辑说明这个函数先遍历 key_table用 strcmp 逐一比较如果找到了就返回对应的 token 类型找不到则说明是普通标识符。参数说明key_table 的长度没有在代码里硬编码而是用 sizeof 除以单条记录大小动态计算这样改表结构不会影响遍历逻辑。思考练习要求改成二分法做法是把 key_table 按字母序排列然后用中点取值比较时间复杂度从 O(n) 降到 O(log n)对关键字表很大的场景有意义。5.3 添加 C 语言注释匹配/* */ 与 // 两种模式的正则表达第三个练习是让 Lex 正确匹配两种注释并统计数量。这个练习的核心在于 Lex 规则的上下文敏感匹配能力。/* { /* 进入块注释状态 */ } */ { /* 结束块注释状态 */ } // { /* 跳过直到行尾 */ }实践里更可落地的做法是直接用完整正则描述注释结构。// 单行注释的正则为//.*点号匹配任意非换行字符星号表示零个或多个。块注释的正则是/*([^*]|\*[^*/])*\*/这个表达式看起来复杂但拆开理解就是允许普通字符存在允许星号存在但必须保证后面不是单斜杠导致过早结束。写完这个规则后我做过一个验证把带注释的 TINY 程序输入进去统计个数和预期一致才算通过。可能遇到的坑是换行处理//.*不会跨行但如果输入文件用了 Windows 换行符 CRLF点号默认不会匹配 \r导致注释内的回车被当作下一个 token 的起始统计结果莫名多出一个半截符号。解决方法是规则里显式写成//.*\n?或者用[^\n]*替代.*。6. 从转储信息到图形化验证检查 NFA 正确性的一个直接技巧写完四个操作符分支并跑通验证后真正考验理解深度的是思考练习里画出例 7 和例 8 的 NFA 状态图这道题。例 7 是 (aa|b)a(a|bb)例 8 是 (a|b)*a(a|b)?如果只依赖转储信息里的数字状态去想象图形很容易画错。我一般会用一种很土但很有效的办法先把转储信息里的每次压栈出栈操作记录成一张表再按照片段合并的顺序逆向画出状态图。具体做法分三步。第一步观察观察点进入和离开时的转储信息差异记录哪几个状态被新建、哪几个状态的 Transform 字段被修改。第二步对照代码里操作符的分支逻辑把每一步涉及的片段边界在草稿上标出来片段边界就是 StartState 和 AcceptState。第三步把所有片段按栈操作顺序拼接检查每个状态的入边和出边是否完整有没有孤立状态或者指向未定义状态的悬空指针。// 转储信息查看格式参考伪代码逻辑 ObservationPoint 观察点: post2nfa 栈状态: 片段1: StartState1, AcceptState2, Transforma 片段2: StartState3, AcceptState4, Transformb 操作符: | 结果: 新栈顶片段: StartState5, AcceptState6 状态5: TransformVoidTrans, Next11, Next23 状态2: TransformVoidTrans, Next16 状态4: TransformVoidTrans, Next16配合这个过程你会发现 NFA 的构造确实是从最小的单字符片段开始每处理一个操作符就消耗栈里若干片段、产出一个更大的片段最后栈里剩下的唯一片段就是整体 NFA。这个小片段组合成大片段的思路和二叉树后序遍历的递归结构完全一致理解了这一层哪怕脱离 CP Lab 平台自己用纯 C 写一个 post2nfa 也不会发怵。在完成例 7 和例 8 的图形验证时我习惯额外做一次边界输入测试例 7 的正则表达式包含两个闭包分别测试空字符串、纯 a 串、纯 b 串以及混合串四种情况确保 NFA 的接受路径出现在预期分支上。例 8 因为有 ? 操作符重点测一个字符和两个字符的输入。这些测试做完确认所有输入都得到正确接受或拒绝的结果再画状态图就不会心虚了。至于 FreeNFA 的思考练习实现核心是对每个 NFA 状态做一次深度遍历释放。需要注意的是状态之间可能存在共享边所以释放前要给每个状态打上访问标记避免重复 free 引发野指针。我在这道题上翻过车第一次没做访问标记栈里两个片段共用了同一个接受状态free 了两次直接导致运行时崩溃。从那以后我每次写状态释放代码都会强制先画一遍状态图标记出所有共享节点再做释放顺序设计。希望这份拆解能帮你在 CP Lab 上少走几个来回把时间留给真正值得深挖的构造逻辑。本文还有配套的精品资源点击获取