企业官网建设流程全解析

简介：面向编译原理课程的实验报告，完整记录了在 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。由于两个片段共用一个接受状态时，前一个片段的接受状态被错误地保留了 AcceptFlag=1，导致 NFA 出现"提前接受"的分支，状态图正确但语义错误。

解决：检查所有出栈片段的接受状态，确保其 AcceptFlag 全部清零，再对新构造的接受状态设置 AcceptFlag=1。从那以后我每次写完一个 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: StartState=1, AcceptState=2, Transform='a' 片段2: StartState=3, AcceptState=4, Transform='b' 操作符: '|' 结果: 新栈顶片段: StartState=5, AcceptState=6 状态5: Transform=VoidTrans, Next1=1, Next2=3 状态2: Transform=VoidTrans, Next1=6 状态4: Transform=VoidTrans, Next1=6

配合这个过程，你会发现 NFA 的构造确实是从最小的单字符片段开始，每处理一个操作符就消耗栈里若干片段、产出一个更大的片段，最后栈里剩下的唯一片段就是整体 NFA。这个"小片段组合成大片段"的思路和二叉树后序遍历的递归结构完全一致，理解了这一层，哪怕脱离 CP Lab 平台，自己用纯 C 写一个 post2nfa 也不会发怵。

在完成例 7 和例 8 的图形验证时，我习惯额外做一次边界输入测试：例 7 的正则表达式包含两个闭包，分别测试空字符串、纯 a 串、纯 b 串以及混合串四种情况，确保 NFA 的接受路径出现在预期分支上。例 8 因为有 '?' 操作符，重点测一个字符和两个字符的输入。这些测试做完，确认所有输入都得到正确接受或拒绝的结果，再画状态图就不会心虚了。

至于 FreeNFA 的思考练习，实现核心是对每个 NFA 状态做一次深度遍历释放。需要注意的是状态之间可能存在共享边，所以释放前要给每个状态打上访问标记，避免重复 free 引发野指针。我在这道题上翻过车，第一次没做访问标记，栈里两个片段共用了同一个接受状态，free 了两次直接导致运行时崩溃。从那以后我每次写状态释放代码都会强制先画一遍状态图标记出所有共享节点，再做释放顺序设计。希望这份拆解能帮你在 CP Lab 上少走几个来回，把时间留给真正值得深挖的构造逻辑。

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