简介本资源为编译原理课程实验报告文档适用于计算机科学与技术专业本科生也适合正在学习编译器前端知识、需要参考正则表达式到NFA转换实现及Lex词法分析器设计的学习者。实验依托Engintime CP Lab平台完成报告详细梳理了从领取任务、熟悉平台界面到阅读源码、生成项目、调试观察点的完整过程并重点解析了re2post、post2nfa、CreateNFAState、MakeNFAFragment等核心函数及NFA片段栈的作用。文档还包含第二个实验“使用Lex自动生成扫描程序”的规则编写与生成思路帮助读者建立从文本形式到抽象语法树的整体认识。资源为1个doc文件压缩包约1.75MB已有1471人浏览学习。对于希望深入理解词法分析、自动机理论并快速把握实验要点的读者这份报告能提供清晰的操作复盘与代码级讲解节省自行摸索的时间。1. 编译原理 CP Lab 实验报告把正则表达式到 NFA 和 Lex 扫描器一次跑通这份编译原理 CP Lab 实验报告藏着两个能直接复现的设计型实验一个在 Engintime CP Lab 里把正则表达式转换成 NFA一个用 Lex 自动生成 TINY 语言的扫描程序。第一次跑的时候我以为跟普通作业一样、填完代码看个结果就算完实际打开 CP Lab 才发现转储信息窗口能把 NFA 的构造过程一步一步摊开连空转移 ε 都标得清清楚楚。对正在补编译原理实验的学生来说这份报告的价值不是标准答案而是把 re2post、post2nfa、NFA 片段栈以及 Lex 规则文件的关键实现和验证流程都留了底。适合拿到 CodeCode.net 任务后不知道从哪下手的人也适合想搞懂正则引擎内部构造的自学者。2. 把正则表达式转成 NFAre2post 与 post2nfa 的流水线设计实验一的项目按模块拆得比较干净RegexpToNFA.h定义 NFA 状态和片段RegexpToPost.c负责中缀转后缀NFAFragmentStack.c提供一个装 NFA 片段的栈main.c把它们串起来。整体流程就是正则表达式 →re2post→ 后缀序列 →post2nfa→ NFA。这套设计不是报告作者临时发明的它是 Thompson 构造法的经典工程化写法先把中缀带括号的正则拍成后缀序列再用一个栈不断拼装小片段最后合成一个完整的 NFA。2.1 中缀转后缀re2post 先把优先级和括号拍平正则表达式直接构造 NFA 最大的麻烦是优先级和括号。比如a(a|1)**作用于括号里的a|1而不是作用于整个表达式|的优先级又是最低的。如果拿到一个字符就决定要不要开新状态你手里得同时维护一摞运算符状态括号一深就会乱。re2post做的事情就是把这些信息全部揉进后缀序列里普通字符原样输出运算符按优先级决定出栈时机这样后面的post2nfa只需要顺序扫描一次不需要再判断优先级。在 CP Lab 给的代码里main.c的开头会包含三个头文件然后初始化栈、调用re2post、再调用post2nfa。我照着报告把调用链重新写了一遍方便看清参数#include RegexpToNFA.h #include RegexpToPost.h #include NFAFragmentStack.h int main(void) { NFAFragmentStack stack; InitNFAFragmentStack(stack); // 栈用来放构造中的 NFA 片段 char *postfix re2post(a(a|1)*); // 转成后缀序列 NFAFragment full post2nfa(postfix, stack); // 后缀序列转 NFA // 此时的 full.StartState 是整个 NFA 的入口状态 return 0; }这段代码里InitNFAFragmentStack先把栈清空re2post的返回值是解析树的后序序列不是一棵真正的树post2nfa从后序序列开始每遇到一个运算符就从栈里弹出对应的片段拼好后再把新片段压回去。为什么要多绕一步后缀表达式因为|、连接、*的优先级和结合性在后缀序列里已经被转成了确定的弹出顺序后面不需要再递归下降也不用维护括号层级。提示报告里的代码注释很少初次读的时候容易把re2post当黑匣子。其实你只要记住它输出的是后序序列后面的栈式构造就顺了。2.2 片段栈每个 NFAFragment 只关心开始状态和接受状态post2nfa的关键数据结构是两个NFAState和NFAFragment。一个状态有状态名、转换标志、最多两个后继状态以及是否接受一个片段只记录开始状态和接受状态。我一般会先把这两个结构定下来再去看 switch-case否则四个运算符的实现会看晕。实验报告给出的状态定义可以归纳成这样typedef struct NFAState { int StateName; // 状态编号从 1 开始 int Transform; // VoidTrans 表示 ε 转移其他值表示字符 struct NFAState *Next1; // 第一个后继 struct NFAState *Next2; // 第二个后继可能为 NULL int AcceptFlag; // 1 为接受状态0 不是 } NFAState; typedef struct { NFAState *StartState; NFAState *AcceptState; } NFAFragment;NFAFragmentStack就是这个结构体的栈。为什么栈里放片段而不是单个状态因为构造是自底向上的单个字符先变成一个两状态的小片段遇到|或*再把栈顶的一个或两个片段拿出来外面包一层新状态变成一个更大的片段。栈里始终只留尚未合并的“半成品”最后栈顶就是完整 NFA 的片段。看|的构造这是最容易写错的一个case |: { NFAFragment fragment2 PopNFAFragment(FragmentStack); NFAFragment fragment1 PopNFAFragment(FragmentStack); NFAState *newStart CreateNFAState(); NFAState *newAccept CreateNFAState(); newStart-Transform VoidTrans; // ε 转移 newStart-Next1 fragment1.StartState; // 走分支 1 newStart-Next2 fragment2.StartState; // 走分支 2 newAccept-AcceptFlag 1; // 新的共同接受状态 fragment1.AcceptState-AcceptFlag 0; // 旧接受状态让位 fragment1.AcceptState-Transform VoidTrans; fragment1.AcceptState-Next1 newAccept; fragment2.AcceptState-AcceptFlag 0; fragment2.AcceptState-Transform VoidTrans; fragment2.AcceptState-Next1 newAccept; PushNFAFragment(FragmentStack, MakeNFAFragment(newStart, newAccept)); break; }这里最容易被忽略的是弹出顺序后缀序列里a b |到|时栈顶是 b 的片段下面才是 a 的片段。所以代码先fragment2 Pop...再fragment1 Pop...。如果顺序反了newStart的两条 ε 边就接反了NFA 的语义直接错掉。旧接受状态的AcceptFlag也要清掉否则这个自动机会在进入公共接受状态之前就莫名其妙地“接受”。*、?、三个一元运算符的代码也是同一套路区别只在“回边”和“跳过边”怎么接case *: { NFAFragment fragment PopNFAFragment(FragmentStack); NFAState *newStart CreateNFAState(); NFAState *newAccept CreateNFAState(); newStart-Transform VoidTrans; newStart-Next1 fragment.StartState; newStart-Next2 newAccept; // 零次直接跳到结束 newAccept-AcceptFlag 1; fragment.AcceptState-AcceptFlag 0; fragment.AcceptState-Transform VoidTrans; fragment.AcceptState-Next1 fragment.StartState; // 一次后可以回头 fragment.AcceptState-Next2 newAccept; // 也可以直接结束 PushNFAFragment(FragmentStack, MakeNFAFragment(newStart, newAccept)); break; } case ?: { NFAFragment fragment PopNFAFragment(FragmentStack); NFAState *newStart CreateNFAState(); NFAState *newAccept CreateNFAState(); newStart-Transform VoidTrans; newStart-Next1 fragment.StartState; newStart-Next2 newAccept; // 直接跳过子片段 newAccept-AcceptFlag 1; fragment.AcceptState-AcceptFlag 0; fragment.AcceptState-Transform VoidTrans; fragment.AcceptState-Next1 newAccept; PushNFAFragment(FragmentStack, MakeNFAFragment(newStart, newAccept)); break; } case : { NFAFragment fragment PopNFAFragment(FragmentStack); NFAState *newAccept CreateNFAState(); newAccept-AcceptFlag 1; fragment.AcceptState-AcceptFlag 0; fragment.AcceptState-Transform VoidTrans; fragment.AcceptState-Next1 newAccept; newAccept-Transform VoidTrans; newAccept-Next1 fragment.StartState; // 跑完一次还能回开头 PushNFAFragment(FragmentStack, MakeNFAFragment(fragment.StartState, newAccept)); break; }*和?都要新建开始状态因为“零次”是合法路径必须有一条 ε 边直接绕到新接受状态。不需要新建开始状态因为至少执行一次原来的 fragment.StartState 仍然作为整个片段的入口它要新建的是接受状态让旧接受状态通过 ε 边连到新接受状态再由新接受状态发一条 ε 回边到原来的开始状态实现“一次之后还能再来”。2.3 单字符原子和连接片段缺了它们四个 case 跑不起来报告附录只贴了|、*、?、四个 case但post2nfa的default分支才是地基遇到普通字符时要新建两个状态开始状态用字符转移指向接受状态。连接运算符对应的 case 在附录里没有贴但它的逻辑很固定从栈里弹出左右两个片段把左边片段的接受状态改为非接受加一条 ε 边到右边片段的开始状态新片段的开始状态取左边接受状态取右边。这四个一元/二元 case 加上单字符原子就已经能处理实验里的例 6 到例 8。比如a(a|1)*re2post会先把它处理成类似a a 1 | * .的后缀序列扫描到a时构造单字符片段扫描到1时再构造单字符片段扫描到|时合并成a|1的片段扫描到*时给整个片段包一个 ε 回边最后一个连接操作把开头的a和闭包片段串起来。整个过程中栈始终只保存片段而不是散乱状态这就是它能在单遍扫描里稳定工作的重要原因。3. 用 Lex 自动生成扫描程序从 scan.txt 到 main.c 的完整链路实验二比实验一更接近编译器前端的真实工作流你写的是 Lex 规则文件编译器工具链替你生成 C 代码。CP Lab 里这一整套已经内置好了你只需要在scan.txt里改规则然后在main.c里看生成的yylex函数。整个实验的核心不是 C 代码本身而是 Lex 输入文件的三段式结构。3.1 Lex 输入文件的三段式定义区、规则区、用户代码区Lex 输入文件天然分成三段用%%隔开。报告里写得很清楚define.h放 token 枚举scan.txt是 Lex 输入文件main.c默认是空文件Lex 根据scan.txt生成的 C 源码会输出到main.c中。一开始容易搞混的是“源代码在 scan.txt生成的代码也在 main.c”这不是复制粘贴而是 Lex 工具自动把三段内容搬到生成的 C 文件里。段放什么生成后去哪定义区%{ %}里的 C 代码、正则名字定义原样复制到生成代码规则区模式 动作每条规则一个入口编译成yylex的分支逻辑用户代码区自定义函数、main 等原样复制到main.c末尾我在看报告时最关注的是define.h里的枚举它把 TINY 语言的各种符号编号并且把“文件结束”定义在 0 的位置因为yylex遇到文件结束默认返回 0。这个细节很重要如果你自己写词法分析器把 EOF 的 token 定义成 0 是一个约定俗成的做法后续 parser 判断正常结束会非常方便。3.2 规则区实战标识符、整数的统计和关键字查表报告 3.5 节要求在scan.txt里加入标识符和正整数的统计功能。正则定义可以写成这样id [A-Za-z] num ([1-9][\d]*)|0这两条定义不是规则规则区里的{id}和{num}才会触发动作。num的写法有个细节它只允许“非零数字开头”的十进制串和单独一个0这样012不会被误认成整数也符合多数语言里整数字面量的规则。规则区对应的动作是计数%% {num} { num_no; } {id} { return ID; } %%这里num_no要在定义区的%{ %}里声明成全局变量否则动作里引用不到。{id}这一步直接返回ID后续的 parser 会根据ID这个 token 类型去查它到底是什么单词。报告特别强调了一句话标识符的正则表达式也用来匹配所有的关键字不要直接使用字符串来逐个匹配关键字。这个做法的道理是Lex 匹配规则是按最长匹配再按规则顺序决定调用哪个动作如果关键字规则写在{id}前面每个关键字都得单独维护一条规则如果写在后面则会被{id}截住。统一走{id}再查表能少写一套规则也不用担心顺序。id2keyword是实验 3.6 节要求补的函数使用前面的key_table做线性查找int id2keyword(char *id, KeywordPair *table, int count) { for (int i 0; i count; i) { if (strcmp(id, table[i].key) 0) { return table[i].type; } } return ID; // 不是关键字按普通标识符返回 }这段代码的逻辑很简单key_table 里每一项是“字符串 - token 类型”的映射用strcmp逐个比比到就返回类型比不到就返回 ID。报告 3.8 思考题要求改成二分法我会在最后一章给出实现但前提是把 key_table 按字母序排好否则二分出来的结果全是错的。C 风格注释的统计也是一样道理。多行注释和行尾注释在 Lex 里可以分别用两个正则识别/*([^*]|\*[^*/])*\*/ { comment_no; } //[^\n]* { comment_no; }第一个正则容易踩坑/* ... */中间可以跨行、可以出现任意非*字符也可以出现*但不允许是紧跟/的闭口。写成([^*]|\*[^*/])*是最常见的 C 注释匹配写法它能保证/* a /* b */这种嵌套注释不被拆散。第二个正则直接匹配//到行尾简单可靠。提示规则区里最好再补一条[ \t\n] { /* 忽略空白 */ }否则空格和换行会被送进默认的规则导致程序在真正读 token 前先匹配到一堆空白字符。实验报告虽然没有专门强调但实际运行时这条规则几乎是必须的。3.3 生成与运行F7 构建、CtrlF5 启动后的三个检查点在 CP Lab 里修改完scan.txt按 F7 生成项目。这时候“输出”窗口会实时显示生成进度如果有语法错误双击错误信息就能跳到出错位置。生成成功之后我一般会打开main.c做三个检查第一找scan.txt定义区那段 C 代码是否被原样搬到生成代码里第二找input函数和yylex函数的定义第三找yyin和yytext这两个变量到底在哪里被使用。yylex是 Lex 自动生成的函数它内部是一个基于 DFA 的表驱动扫描器yytext保存当前匹配到的字符串yyin指定输入来源。默认情况下yyin指向标准输入所以 sample.txt 里那个 TINY 小程序能从键盘读一个整数、算阶乘再输出。运行用 CtrlF5 启动程序会走一遍词法分析统计结果会停留在输出窗口。如果统计不对第一步不是改 C 代码而是看自己的规则写没写对id是不是把关键字吞了num是不是没挡住前导零注释正则有没有跨行问题。4. CP Lab 避坑记录我从这两个实验里踩过的五个坑这两个实验我前后做了两遍第二遍是拿这份报告对着复现仍然遇到几个问题。把它们记下来是为了让你少走这些弯路。4.1 转储信息不刷新不是构造失败是没进观察点现象F7 生成成功F5 启动调试“转储信息”窗口却一片空白完全看不到 NFA 片段信息。原因CP Lab 的转储信息不是实时刷新的它只在观察点函数进入和返回的位置输出关键状态。如果工具栏上的“演示模式”按钮没有高亮或者观察点没有落在post2nfa这样的函数上程序会直接跑完窗口当然空着。解决先确认“演示模式”高亮再从“调试”菜单选“启动调试”程序停在观察点入口后反复按 F5 让“演示流程”窗口逐行执行。每执行一行回看转储信息里的状态名称和 AcceptFlag 变化。这个“功能没生效”其实是操作顺序问题不是代码问题。4.2 验证失败但代码没语法错误先查 AcceptFlag 和弹出顺序现象post2nfa写完生成项目没有报错但点击验证项目之后提示源文件与目标文件内容不一致。原因最常见的两种情况是构造|时弹出的两个片段顺序反了或者旧接受状态的AcceptFlag没有清零。顺序反了会让两个分支互换AcceptFlag不清会让 NFA 在到达公共结束状态之前就认为已经接受状态图能画出来但语义是错的。解决对照附录的四个 case 逐条检查。|必须先fragment2 Pop...再fragment1 Pop...所有旧接受状态都要先AcceptFlag 0再补 ε 边到新接受状态。验证项目会拿你的结果和 CP Lab 内置的目标文件逐项比对所以任何语义差异都会被揪出来。4.3 关键字全被标识符吞掉规则顺序不是万能的现象加了关键字统计之后if、then、repeat 全被统计成普通标识符关键字数量永远是 0。原因这是我第一次写 Lex 最容易翻车的点。[A-Za-z]既能匹配if也能匹配普通变量名。Lex 采用最长匹配长度相同时按规则区从上到下的顺序选规则如果{id}写在关键字规则前面关键字就永远到不了关键字规则。解决不要试图把每个关键字都写一条规则用{id}统一匹配字母串并返回 ID再在id2keyword里查表。这样规则区只需要一条规则关键字表交给 C 代码处理既简单又不容易踩顺序坑。4.4 生成的 main.c 里找不到 yylex多半是删掉了生成结果现象打开 main.c里面是空文件或者只有自己手写的代码找不到yylex、input和yyin。原因CP Lab 是每次点击“生成项目”才把 Lex 规则编译成 C 代码并写入 main.c 的。如果你手动编辑过 main.c生成失败过一次或者改过输出路径生成结果可能被覆盖掉。Lex 输入的第三部分和定义区是原样粘贴到生成代码里的并不是系统帮你额外生成的。解决不要手动往 main.c 里补 yylex。回到scan.txt检查三段式保存后重新 F7。生成成功后在 main.c 里用搜索功能找yylex和input先确认生成内容完整再改规则也不迟。4.5 实验里看不出的内存泄漏换到工程里就是事故现象实验程序运行完直接退出没有报错自己把代码搬到本地用内存检查工具跑报告一堆 malloc 没有释放。原因post2nfa每调用一次CreateNFAState就动态分配一个状态实验代码默认没有写释放过程。CP Lab 是教学环境进程退出后内存由系统回收所以表面看起来没毛病。解决写一个 FreeNFA并且要处理*、产生的环。裸递归在a*这种结构里会无限循环必须用 visited 标记。我给出的实现放在最后一章可以直接抄到 main.c 里调用。5. 验证实验结果转储信息窗口与 NFA 状态图的对照方法实验做完不是跑通就完CP Lab 的验证项目会把你的实现和内置目标文件比较只有“源文件与目标文件的内容相同”才算通过。想通过验证你得学会读转储信息窗口。5.1 观察点与演示模式转储信息里到底在看什么演示模式下的调试其实是在“观察点函数”里逐行走演示流程。CP Lab 会忽略函数体原有的 C 代码改用预置的演示步骤代替每执行一步“转储信息”窗口就会更新一次数据。所以你不需要自己单步跟踪指针只要看懂窗口里的三类信息就行。转储信息项对应结构判断要点函数调用信息观察点函数入口说明当前要看的是哪个函数比如 post2nfa函数返回信息观察点函数出口显示最终 fragment 的开始状态和接受状态状态名称NFAState.StateName从 1 开始每次 CreateNFAState 递增转换标志TransformVoidTrans 就是 ε 转移转换到的状态Next1 / Next2检查边是否指向正确片段是否接受AcceptFlag1 为接受0 为不接受刚开始可能觉得这些字段很多但它的变化是有规律的。构造单字符 NFA 片段时你会看到一个开始状态和一个接受状态中间有一条字符转移构造连接 NFA 片段时左边片段的接受状态变成内部状态新加一条 ε 边连到右边片段的开始状态构造|时新增开始状态和接受状态两条 ε 边分别通到两个子片段构造*时新增开始和接受状态并且旧接受状态会多出一条 ε 回边。把演示流程从上到下走完转储信息窗口里最后一个状态图就是整个正则表达式的 NFA。这个过程比看任何书上的示意图都直观因为它把“小片段拼大片段”的每一步都摆在眼前。5.2 例 6、例 7、例 8用手画状态图之前先整理状态清单报告 3.12 的思考题要求验证例 6、例 7、例 8并画出后两个的 NFA 状态图。我复现后的验证结论如下例子正则验证结果画图重点例6a(a1)*通过例7(aab)*a(abb)*例8(ab)*a(ab)?我画状态图的方法是这样的先把转储信息里所有状态按编号列出来写清每个状态的 Transform、Next1、Next2 和 AcceptFlag然后从 StartState 出发凡是 Transform 为 VoidTrans 的边标 ε其余边标对应的字符遇到*或的片段重点检查有没有形成环最后数一遍所有 AcceptFlag1 的状态确认最终只有一个公共接受状态。这个步骤能帮你做两件事一是验证 CP Lab 给出的结果二是在验证失败时快速定位是哪个片段拼错了。比如例 7(aa|b)*a(a|bb)*如果转储信息里|的两个分支接反后面闭包的 ε 回边也会跟着错画出来的状态图会明显不对称但单独看每一段又会觉得“好像对”。这时候不要猜直接查case |的 pop 顺序和 AcceptFlag问题通常很快浮出来。6. 把这套实验代码搬到自己的工程里FreeNFA 与二分查找的进阶改造实验报告里的思考题其实比必做实验更实用。一个是处理内存泄露一个是把线性查找改成二分查找。这两处代码量不大但能体现你真正理解了这份代码。先看 FreeNFA。最直觉的写法是递归释放但正则转出来的 NFA 有环a*的一个旧接受状态同时有 ε 边回到开始状态裸递归会无限循环。我一般用状态编访问标记static int *visited; static int visited_size; void FreeNFA(NFAState *state) { if (state NULL) return; if (state-StateName visited_size || visited[state-StateName]) { return; // 已经释放过避免环导致死循环 } visited[state-StateName] 1; FreeNFA(state-Next1); FreeNFA(state-Next2); free(state); }调用时先按状态总数分配 visited状态总数可以用一个全局计数器统计每次CreateNFAState自增visited_size GetStateCount() 1; // StateName 从 1 开始 visited calloc(visited_size, sizeof(int)); FreeNFA(nfa.StartState); free(visited);因为CreateNFAState生成的状态名是从 1 开始递增的所以用状态名当下标最稳。注意visited要在每次调用前清空或者每次 FreeNFA 前重新分配否则第二次释放会误判。另一个改造是id2keyword的二分查找。先把 key_table 按字母序排好然后int id2keyword_binary(char *id, const KeywordPair *table, int left, int right) { while (left right) { int mid left (right - left) / 2; int cmp strcmp(id, table[mid].key); if (cmp 0) { return table[mid].type; } if (cmp 0) { right mid - 1; } else { left mid 1; } } return ID; // 没查到就是普通标识符 }二分查找只适合已经排好序的表。如果你把 key_table 按原顺序放着直接二分结果会全错。线性查找在小语言里够用但关键字一多这里就是热点函数能省就省。从那以后我每次把这份实验代码拿出去复用之前都会强制走一遍 FreeNFA 二分查找顺便把转储信息里的每个状态核对一遍这套流程已经成了我的习惯希望帮到你。本文还有配套的精品资源点击获取