编译原理实验：正则表达式到NFA转换与Lex扫描程序生成

简介这份实验报告面向高校编译原理课程的学习者聚焦从正则表达式到NFA的转换以及使用Lex自动生成扫描程序两个核心实验依托Engintime CP Lab平台完成适合正在做课程实验或需要复盘编译器前端流程的学生参考。资源包内共1个doc文件约1.75MB为暨南大学本科实验报告格式涵盖实验环境使用、正则表达式与NFA含义、re2post与post2nfa等关键函数的实现思路以及Lex规则文件编写与词法分析器生成方法。报告详细记录了从CodeCode.net领取任务、克隆项目、阅读源代码到生成项目、解决语法错误、观察点调试的完整过程并配有实验主题、内容与步骤说明。目前已有1472人学习下载可帮助读者理解正则运算符到NFA状态转移的映射、ε转移的作用以及词法分析自动化生成机制强化对编译原理理论知识的掌握。1. 从一份实验报告说起正则表达式到 NFA 到底怎么落地很多人学编译原理正则表达式到 NFA 的转换在纸上画一画觉得懂了真到写代码就卡壳——状态怎么存、片段怎么拼、ε 转移什么时候加全是糊涂账。这份实验报告围绕两个核心实验展开一是用 C 语言实现从正则表达式到 NFA 的转换二是用 Lex 自动生成扫描程序。它把理论课上那些抽象概念落到了可编译、可调试的代码上适合正在上编译原理课、需要动手完成实验的本科生也适合想重新捡起编译器前端基础的开发者。报告里涉及的 CP Lab 集成环境、CodeCode.net 平台任务领取、观察点调试模式都是实打实的操作流程不是纸上谈兵。如果你正对着“正则表达式怎么变成状态图”发愁这份材料能帮你把链条打通。2. 正则表达式到 NFA核心数据结构与转换骨架2.1 为什么需要 NFAFragment 和栈正则表达式到 NFA 的构造常见做法是 Thompson 算法。它的核心思路是每个基本正则单元单个字符、连接、选择、闭包等都构造一个小 NFA 片段然后用栈把这些片段按运算符优先级拼起来。实验里的NFAFragment结构体就是干这个的——它保存一个片段的起始状态和接受状态。NFAFragmentStack则是一个存放这些片段的栈遇到操作符就弹出若干片段拼成新片段再压回去。为什么非得用栈因为正则表达式的后缀序列也叫逆波兰表示天然适合栈式求值。re2post函数先把中缀的正则表达式转成后缀序列比如a|b变成ab|a*变成a*。然后post2nfa从左到右扫描后缀序列遇到字符就造一个单字符片段压栈遇到操作符就弹出对应数量的片段进行组合。这个流程和计算器求后缀表达式几乎一样只是“运算”变成了 NFA 片段拼接。NFAState结构体里几个关键字段需要留意Transform表示转移字符VoidTrans代表 ε 转移Next1和Next2是两个后继状态指针AcceptFlag标记是否为接受状态。NFA 之所以“非确定”就是因为一个状态可以有两个后继或者可以在不读入任何字符的情况下跳转ε 转移。2.2 re2post中缀转后缀的优先级处理re2post函数负责把用户写的正则表达式中缀形式转成后缀序列。这一步容易被低估实际上它要处理运算符优先级、括号、隐式连接等细节。实验报告里没有展开re2post的全部代码但从思考题“详细阅读 re2post 函数中的源代码并尝试在源代码中添加注释”可以看出它是理解整个流程的关键入口。常见做法是维护一个操作符栈遇到操作数直接输出到后缀序列遇到操作符则根据优先级决定是压栈还是弹出。这里有一个容易翻车的点连接操作符比如ab中的连接通常是隐式的没有显式符号。re2post需要自己判断什么时候该插入一个连接符。一般规则是如果当前字符是操作数或左括号而前一个输出是操作数或右括号或星号则隐含一个连接操作。下面是一个简化的re2post逻辑示意帮助理解它的工作方式// 简化的 re2post 核心逻辑示意 // 输入: 正则表达式字符串 regexp // 输出: 后缀序列字符串 post void re2post(char *regexp, char *post) { char stack[100]; // 操作符栈 int top -1; // 栈顶指针 int j 0; // 后缀序列写入位置 int parenCount 0; // 括号计数 for (int i 0; regexp[i] ! \0; i) { char c regexp[i]; switch (c) { case (: // 左括号直接压栈同时增加括号计数 stack[top] c; parenCount; break; case ): // 弹出直到遇到左括号 while (top 0 stack[top] ! () { post[j] stack[top--]; } if (top 0) top--; // 弹出左括号 parenCount--; break; case |: // 优先级最低弹出所有优先级不低于它的操作符 while (top 0 stack[top] ! () { post[j] stack[top--]; } stack[top] c; break; case *: case : case ?: // 单目运算符优先级最高直接输出到后缀序列 post[j] c; break; default: // 普通字符直接输出 post[j] c; break; } } // 弹出栈中剩余操作符 while (top 0) { post[j] stack[top--]; } post[j] \0; }这段代码里stack是操作符栈post是输出的后缀序列。参数regexp是输入的中缀正则表达式post是转换结果。注意*、、?这三个单目运算符直接输出因为它们作用于前一个操作数在后缀序列中紧跟在操作数后面即可。|是双目运算符需要等右边的操作数也输出后才能输出。括号用来改变优先级遇到右括号就弹出到左括号为止。实际实验中的re2post还要处理隐式连接逻辑会更复杂一些。但抓住“操作符栈 优先级比较”这个骨架读源码就不会迷路。2.3 post2nfa四种运算符的片段拼接post2nfa是实验的核心实现部分报告里给出了|、*、?、四种运算符的完整代码。每种运算符的处理方式不同但套路一致弹出片段、创建新状态、设置转移、压回新片段。先看|选择的实现。它弹出两个片段fragment1和fragment2然后创建一个新的开始状态和一个新的接受状态。新开始状态通过两条 ε 转移分别指向两个片段的起始状态两个片段原来的接受状态取消接受标记各自通过 ε 转移指向新的接受状态。这样从新开始状态出发可以走任意一个分支到达新接受状态。case |: // 弹出栈顶两个片段 fragment2 PopNFAFragment(FragmentStack); fragment1 PopNFAFragment(FragmentStack); // 创建新的开始和接受状态 NewStartState CreateNFAState(); NewAcceptState CreateNFAState(); // 新开始状态通过 ε 转移指向两个片段的起始状态 NewStartState-Transform VoidTrans; NewStartState-Next1 fragment1.StartState; NewStartState-Next2 fragment2.StartState; // 新接受状态标记为接受 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;*闭包的处理略有不同。它只弹出一个片段然后创建新开始和新接受状态。新开始状态通过 ε 转移分别指向原片段起始状态和新接受状态这意味着可以跳过整个片段原片段的接受状态取消标记通过 ε 转移指回原片段起始状态实现循环和新接受状态实现退出。case *: 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 fragment.StartState; fragment.AcceptState-Next2 NewAcceptState; fm MakeNFAFragment(NewStartState, NewAcceptState); PushNFAFragment(FragmentStack, fm); break;?可选和正闭包的实现思路类似区别在于 ε 转移的指向。?相当于|的简化版新开始状态一条 ε 转移进入片段一条直接到新接受状态片段接受状态通过 ε 转移到新接受状态。则相当于*去掉“跳过”那条路径新开始状态直接就是原片段的起始状态原接受状态通过 ε 转移回起始状态和新接受状态。这四种运算符的代码结构高度一致理解了其中一个其余三个就是改几条Next1、Next2的指向。实验报告里把四段代码都列出来了对照着看能很快抓住规律。3. 用 Lex 自动生成扫描程序从规则文件到可执行词法分析器3.1 Lex 输入文件的三段式结构Lex 是经典的词法分析器生成工具它的输入文件实验里叫scan.txt分成三个部分用%%分隔。第一部分是定义段放 C 代码和正则表达式宏定义第二部分是规则段每行写“正则表达式 匹配后的动作”第三部分是用户代码段放辅助函数和main函数。实验里sample.txt是一个用 TINY 语言写的小程序功能是读入一个整数并计算阶乘。define.h定义了 TINY 语言的符号枚举其中“文件结束”放在最前面因为yylex遇到文件结束默认返回 0这样枚举值刚好对上。main.c初始为空Lex 会根据scan.txt生成 C 源代码输出到这里里面包含yylex函数的定义——这个函数就是词法分析器的核心基于 DFA 表驱动。生成项目后可以在main.c里找到input函数、yylex函数、yyin和yytext变量的定义。yyin是输入文件指针yytext指向当前匹配到的字符串。这些是 Lex 运行时的标准接口理解它们的位置有助于后续调试。3.2 添加标识符和正整数的统计实验要求在第一部分添加标识符和正整数的正则表达式在第二部分添加对应的统计代码。标识符的正则表达式是[A-Za-z]正整数的正则表达式是([1-9][\d]*)|0。注意正整数的写法要么是 1 到 9 开头后跟任意数字要么就是单个 0。这样写是为了避免匹配到0123这种前导零的情况。%{ #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; } %%这段规则里{num}匹配到正整数时执行num_no但不返回 token继续扫描下一个{id}匹配到标识符时返回ID。注意标识符的正则表达式也会匹配到关键字所以不能直接用字符串逐个匹配关键字而是先统一按标识符处理再通过id2keyword函数查表判断具体是哪个关键字。id2keyword函数需要自己编写要求使用key_table表格中的数据通过线性搜索根据标识符字符串确定关键字类型。key_table是一个结构体数组每项包含关键字字符串和对应的枚举值。线性搜索就是遍历数组用strcmp比较匹配到就返回对应类型没匹配到就返回ID表示普通标识符。3.3 处理 C 语言风格注释实验还要求处理两种 C 语言风格注释/* */多行注释和//单行注释。这需要在scan.txt中添加对应的正则表达式和统计代码。多行注释的正则表达式要能跨行匹配通常写成\/\*([^*]|\*[^/])*\*\/这种形式单行注释则是\/\/[^\n]*。%{ int comment_no 0; // 注释计数器 %} %% /*([^*]|\*[^/])**/ { comment_no; } //[^\n]* { comment_no; } %%多行注释的正则表达式\/\*([^*]|\*[^/])*\*\/的含义是以/*开头中间可以是任意非*字符或者*后面跟非/字符最后以*/结尾。这样能正确匹配跨行注释同时避免提前在*/处结束。单行注释\/\/[^\n]*匹配//到行尾的所有字符。修改完scan.txt后重新生成项目按 CtrlF5 运行检查统计的注释数量是否正确。如果生成失败根据“输出”窗口的提示修改语法错误。这一步的坑在于正则表达式的转义/和*在 Lex 规则里需要适当转义否则可能被解释成正则运算符。4. 避坑与排查那些实验报告里没细说的翻车点4.1 生成项目报错但找不到错误行现象按 F7 生成项目输出窗口提示有语法错误但双击错误信息定位不到具体代码行。原因通常是 Lex 生成的main.c文件太大或者错误出在scan.txt的规则段而非生成的 C 代码里。解决方法是先检查scan.txt的规则段是否有拼写错误特别是正则表达式里的括号和转义字符如果确认规则文件没问题再在生成的main.c里搜索错误提示的关键词手动定位。4.2 验证项目时源文件与目标文件内容不一致现象实验步骤 3.10 要求验证项目但比较文件内容时发现不一致验证失败。原因可能是post2nfa函数实现有误导致生成的 NFA 状态转移与预期不符。解决方法是回到演示模式在观察点函数结束位置中断查看“转储信息”窗口中的状态转移信息逐个核对Next1、Next2的指向是否正确。特别留意 ε 转移的Transform是否设成了VoidTrans以及接受状态的AcceptFlag是否在正确的位置置 1 或清 0。4.3 标识符统计把关键字也算进去了现象添加标识符统计功能后发现关键字也被计入标识符数量。原因是在规则段里{id}直接返回了ID但没有区分关键字和普通标识符。解决方法是在{id}的动作里调用id2keyword函数根据返回值决定是返回具体关键字类型还是ID。id2keyword内部用key_table做线性搜索匹配到关键字就返回对应枚举值否则返回ID。4.4 多行注释匹配不完整或提前结束现象/* ... */注释统计数量不对有时一个注释被拆成两个有时跨行注释没被识别。原因是正则表达式写得太简单比如用\/\*.*\*\/这种贪婪匹配遇到多个注释时会从第一个/*一直匹配到最后一个*/。解决方法是改用\/\*([^*]|\*[^/])*\*\/确保中间不会误吞*/。另外注意 Lex 默认是贪婪匹配如果规则写得不够精确很容易出现这种问题。4.5 演示模式下观察点函数不按预期中断现象在演示模式下调试观察点函数按 F5 继续后没有在函数结束位置中断或者“转储信息”窗口内容没有更新。原因是演示模式按钮没有高亮或者当前选中的不是观察点函数。解决方法是先确认工具栏上的“演示模式”按钮处于高亮状态然后在“调试”菜单里选择“启动调试”确保程序停在观察点函数入口。如果“演示流程”窗口没自动打开可以从“调试”菜单的“窗口”子菜单里手动打开。5. 进阶技巧从能跑到跑对再到跑明白实验做到最后代码能生成、能运行只是及格线。真正拉开差距的是两件事一是验证的完备性二是对内存和边界情况的处理。验证方面实验报告里列了例 2 到例 8 共七个正则表达式要求逐一验证并画出例 7、例 8 的 NFA 状态图。例 6 是a(a|1)*例 7 是(aa|b)*a(a|bb)*例 8 是(a|b)*a(a|b)?。这三个例子覆盖了连接、选择、闭包、可选等组合场景能全部通过说明post2nfa的实现基本正确。画状态图时建议从起始状态开始按Next1、Next2逐层展开ε 转移用虚线表示接受状态用双圈标记。画完对照“转储信息”窗口里的状态转移表能发现肉眼容易忽略的指向错误。内存方面思考题第一题要求编写FreeNFA函数在main函数最后调用释放整个 NFA 的内存。这个函数需要遍历所有 NFA 状态并逐个free。难点在于 NFA 状态之间通过Next1、Next2相互引用直接递归释放可能重复释放或漏放。常见做法是先用一个数组收集所有状态指针再统一释放。或者用一个访问标记数组递归时跳过已访问的状态。// FreeNFA 的参考实现思路 void FreeNFA(NFAState *start) { if (start NULL) return; // 用递归释放但需要防止重复访问 // 实际实现中建议用 visited 数组标记已释放状态 NFAState *next1 start-Next1; NFAState *next2 start-Next2; free(start); FreeNFA(next1); FreeNFA(next2); }上面这个递归版本在 NFA 状态有环的情况下会无限递归所以实际使用时必须加访问标记。更稳妥的做法是维护一个全局的状态指针数组在构造 NFA 时每创建一个状态就存入数组最后遍历数组统一释放。这样既避免了重复释放也避免了递归深度过大的问题。另一个进阶点是id2keyword的二分查找优化。思考题要求把key_table按字母顺序排列然后用二分法替代线性搜索。二分查找的代码不难写但要注意key_table必须严格有序否则查找结果会出错。改完之后可以用几个边界关键字测试比如字母顺序最前和最后的关键字确认都能正确匹配。从那以后我每次做这类状态机构造的实验都会先把状态转移表打印出来对照输入串手动走一遍确认无误再跑自动化验证。这个习惯帮我省下了大量调试时间。希望帮到你。本文还有配套的精品资源点击获取