CP Lab 编译原理实验指导

1

北京英真时代科技有限公司●●●●●●●●●●●●●

CP Lab编译原理实验指导

版本 1.1

北京英真时代科技有限公司

地址: 北京市房山区拱辰大街98号7层0825

邮编: 102488

电话: 010-********

QQ: 964515564

邮箱: support@https://www.wendangku.net/doc/4116531941.html,

网址: https://www.wendangku.net/doc/4116531941.html,

目录

CP LAB简介 (4)

实验1 实验环境的使用 (7)

实验2 NFA 到DFA (18)

实验3 使用LEX自动生成扫描程序 (22)

实验4 消除左递归（无替换） (27)

实验5 消除左递归（有替换） (31)

实验6 提取左因子 (36)

实验7 FIRST 集合 (40)

实验8 FOLLOW 集合 (44)

实验9 YACC分析程序生成器 (49)

实验10 符号表的构建和使用 (52)

实验11 三地址码转换为P-代码 (55)

实验12 GCC编译器案例综合研究 (59)

附录TINY编译器和TM机 (67)

CP Lab简介

获得人生中的成功需要的专注与坚持不懈多过天才与机会。

——C.W.Wendte

一、概述

CP Lab是一款专用于高等院校编译原理实验教学的集成环境，具有可视化程度高、操作简便、扩展性强等特点。CP Lab主要由两部分组成：

●一个功能强大的IDE环境。

●一套精心设计的编译原理实验题目和配套源代码。

CP Lab所提供的IDE环境可以在Windows操作系统上快速安装、卸载，其用户界面和操作方式与Microsoft Visual Studio完全类似，有经验的读者可以迅速掌握其基本用法。该IDE环境提供的强大功能可以帮助读者顺利的完成编译原理实验，主要功能包括对实验源代码的演示功能、编辑功能、编译功能、调试功能和验证功能。

CP Lab提供了一套精心设计的编译原理实验题目和配套源代码。实验题目涵盖了从词法分析、语法分析、语义分析、代码生成等所有重要的编译原理和算法。完成这些实验题目后，读者可以学习到通过手工编码是如何一步步实现一个编译器的，还可以使用Lex、Yacc工具完成简单的词法分析程序和语法分析程序，甚至还可以深入分析一个小型的开源编译器的实现方法。所有的源代码文件都使用C语言编写，可以与主流编译原理教材配套使用。这些源代码以模块化的方式进行组织，并配有完善的中文注释，可读性好，完全符合商业级的编码规范。

使用CP Lab进行编译原理实验的过程可以参见图0-1。

图0-1：使用CP Lab进行编译原理实验

二、实验题目清单

下面的实验题目适合在学习编译原理课程的过程中逐个完成。

三、开始使用

读者迅速掌握CP Lab的基本使用方法，是顺利完成编译原理实验的重要前提。虽然CP Lab提供了非常人性化的操作界面，而且读者只需要掌握很少的几个核心功能，就可以顺利完成实验。但是，为了达到“做中学”的目的，在向读者介绍CP Lab的核心功能时，不会使用堆砌大量枯燥文字的方法，而是在后面的“实验1”中，引导读者在使用CP Lab的过程中逐步掌握其基本使用方法，这样达到的效果最好。

实验1 实验环境的使用

实验难度：★★☆☆☆

建议学时：2学时

一、实验目的

●熟悉编译原理集成实验环境CP Lab的基本使用方法。

●掌握正则表达式和NFA的含义。

●实现正则表达式到NFA的转换。

二、预备知识

●在这个实验中NFA状态结构体使用了类似于二叉树的数据结构，还包括了单链表插入操作以及栈

的一些基本操作。如果读者对这一部分知识有遗忘，可以复习一下数据结构中的相关内容。

●实验中需要把正则表达式转换为NFA，所以要对正则表达式和NFA（非确定有穷自动机）有初步

的理解。读者可以参考配套的《编译原理》教材，预习这一部分内容。

三、实验内容

请读者按照下面的步骤完成实验内容，同时，仔细体会CP Lab的基本使用方法。在本实验题目中，操作步骤会编写的尽量详细，并会对CP Lab的核心功能进行具体说明。但是，在后面的实验题目中会尽量省略这些内容，而将重点放在实验相关的源代码上。如有必要，读者可以回到本实验题目中，参考CP Lab 的基本使用方法。

3.1 启动CP Lab

在安装有CP Lab的计算机上，可以使用两种不同的方法来启动CP Lab：

●在桌面上双击“Engintime CP Lab”图标。

或者

●点击“开始”菜单，在“程序”中的“Engintime CP Lab”中选择“Engintime CP Lab”。

3.2 用户注册

CP Lab每次启动后都会弹出一个“用户信息”对话框。在此对话框中填入“学号”和“姓名”后，点击“确定”按钮完成本次注册。

提示：完成注册后，CP Lab便会开始记录实验数据，这些数据可能会作为实验课的考评依据，所以请认真填写学号和姓名，并保证学号和姓名的一致性。

3.3 主窗口布局

CP Lab的主窗口布局由下面的若干元素组成：

●顶部的菜单栏、工具栏。

●停靠在左侧和底部的各种工具窗口。

●余下的区域用来放置“起始页”和“源代码编辑器”窗口。

提示：菜单栏、工具栏和各种工具窗口的位置可以随意拖动。如果想恢复窗口的默认布局，选择“窗口”菜单中的“重置窗口布局”即可。

3.4 新建实验项目

新建一个实验项目的步骤如下：

1.在“文件”菜单中选择“新建”，然后单击“项目”，打开“新建项目”对话框。

2.在“新建项目”对话框中，选择项目模板“001 正则表达式到 NFA”。注意，其他模板会在后面

的实验题目中使用。

3.在“名称”中输入新项目使用的文件夹名称“lab1”。

4.在“位置”中输入新项目保存在磁盘上的位置“C:\cplab”。

5.点击“确定”按钮。

新建完毕后， CP Lab 会自动打开这个新建的项目。在“项目管理器”窗口中（如图1-1所示），根节点是项目节点，各个子节点是项目包含的文件夹或者文件。读者也可以使用“Windows资源管理器”打开磁盘上的“C:\cplab\lab1”文件夹，查看项目中包含的源代码文件。

提示：右键点击“项目管理器”窗口中的项目节点，选择快捷菜单中的“打开所在的文件夹”，即可使用“Windows资源管理器”打开项目所在的文件夹。

图1-1：打开项目后的“项目管理器”窗口

3.5 阅读实验源代码

该实验包含了三个头文件“RegexpToNFA.h”、“RegexpToPost.h”、“NFAFragmentStack.h”和三个C 源文件“main.c”、“RegexpToPost.c”、“NFAFragmentStack.c”。下面对这些文件的主要内容、结构和作用进行说明：

main.c文件

在“项目管理器”窗口中双击“main.c”打开此文件。此文件主要包含了以下内容：

1.在文件的开始位置，使用预处理命令包含了RegexpToNFA.h、RegexpToPost.h和

NFAFragmentStack.h文件。

2.定义了main函数。在其中实现了栈的初始化。然后，调用了re2post函数，将正则表达式转换

到解析树的后序序列。最后，调用post2nfa函数，将解析树的后序序列转换到NFA。

3.在main函数的后面，定义了函数CreateNFAState和MakeNFAFragment，这两个函数分别是用来

创建一个新的NFA状态和构造一个新的Fragment。接着定义了函数post2nfa，关于此函数的功能、参数和返回值，可以参见其注释。在这个函数中用‘$’表示空转换，此函数的函数体还不完整，留给读者完成。

RegexpToPost.c文件

在“项目管理器”窗口中双击“RegexpToNFA.c”打开此文件。此文件主要包含了以下内容：

1.在文件的开始位置，使用预处理命令包含了RegexpToPost.h文件。

2.定义了re2post函数，此函数主要功能是将正则表达式转换成为解析树的后序序列形式。NFAFragmentStack.c文件

在“项目管理器”窗口中双击“NFAFragmentStack.c”打开此文件。此文件主要包含了以下内容：

1.在文件的开始位置，使用预处理命令包含了NFAFragmentStack.h文件。

2.定义了与栈相关的操作函数。在构造NFA的过程中，这个栈主要用来放置NFA片段。RegexpToNFA.h文件

在“项目管理器”窗口中双击“RegexpToNFA.h”打开此文件。此文件主要包含了以下内容：

1.包含用到的C标准库头文件。目前只包含了标准输入输出头文件“stdio.h”。

2.包含其他模块的头文件。目前没有其他模块的头文件需要被包含。

3.定义了与NFA相关的数据结构，包括NFA状态NFAState和NFA片段NFAFragment。具体内容可参

4.声明函数和全局变量。

RegexpToPost.h文件

在“项目管理器”窗口中双击“RegexpToPost.h”打开此文件。此文件主要包含了以下内容：

1.包含其他模块的头文件。目前只包含了头文件“RegexpToNFA.h”。

2.声明函数。为了使程序模块化，所以将re2post函数声明包含在一个头文件中再将此头文件包含

到“main.c”中。

NFAFragmentStack.h文件

在“项目管理器”窗口中双击“NFAFragmentStack.h”打开此文件。此文件主要包含了以下内容：

1.包含其他模块的头文件。目前只包含了头文件“RegexpToNFA.h”。

2.定义重要的数据结构。定义了与栈相关的数据结构。

3.声明函数。声明了与栈相关的操作函数。

提示：请读者认真理解这部分内容，其他实验题目中的源代码文件也严格遵守这些约定，如无特殊情况将不再进行如此详细的说明。

3.6 生成项目

使用“生成项目”功能可以将程序的源代码文件编译为可执行的二进制文件，操作如下：

1.在“生成”菜单中选择“生成项目”（快捷键是F7）。

在项目生成过程中，“输出”窗口会实时显示生成的进度和结果。如果源代码中不包含语法错误，会在生成的最后阶段提示生成成功，如图1-2所示。

生成项目的过程，就是将项目所包含的每个C源代码文件（.c文件）编译为一个对象文件（.o文件），然后再将多个对象文件链接为一个目标文件（.exe文件）的过程。以本实验为例，成功生成项目后，默认会在“C:\cplab\lab1\Debug" 目录下生成“main.o”文件“RegexpToPost.o”文件“NFAFragmentStack.o”文件和 “RegexpToNFA.exe”文件。

提示：读者可以通过修改项目名称的方法来修改生成的.exe文件的名称。方法是在“项目管理器”窗口中右键点击项目节点，选择快捷菜单中的“重命名”。待项目名称修改后，需要再次生成项目才能得到新的.exe文件。

图1-2：生成项目成功后的“输出”窗口

3.7 解决语法错误

如果在源代码中存在语法错误，在生成项目的过程中，“输出”窗口会显示相应的错误信息（包括错误所在文件的路径，错误在文件中的位置，以及错误原因），并在生成的最后阶段提示生成失败。此时，在“输出”窗口中双击错误信息所在的行，CP Lab会使用源代码编辑器自动打开错误所在的文件，并定位到错误所在的代码行。

可以按照下面的步骤进行练习：

1.在源代码文件中故意输入一些错误的代码（例如删除一个代码行结尾的分号）。

2.生成项目。

3.在“输出”窗口中双击错误信息来定位存在错误的代码行，并将代码修改正确。

4.重复步骤2、3，直到项目生成成功。

3.8观察点和演示模式

这里介绍CP Lab提供的两个重要功能：观察点和演示模式。

观察点

一个观察点对应一个函数的起始位置和结束位置（称这个函数为观察点函数）。在调试过程中，当程序执行到观察点函数的起始位置和结束位置时就会发生中断，就好像在这两个位置上添加了断点一样。并且，只要在观察点函数内部发生中断（包括命中断点、单步调试等），就会在“转储信息”窗口中显示观察点函数正在操作的数据信息，如果在“演示模式”下，还会在“演示流程”窗口中显示观察点函数的流程信息。

以本实验为例，“观察点”窗口如图1-3所示（在“调试”菜单的“窗口”中选择“观察点”，可以打开“观察点”窗口），说明post2nfa函数是一个观察点函数。启动调试后，在main.c文件post2nfa函数的开始位置和结束位置的左侧空白处，会显示观察点图标（与“观察点”窗口中左侧的图标一致），当程序执行到post2nfa函数的开始位置和结束位置时会发生中断。启动调试后，观察点窗口如图1-4所示，可以显示出观察点所在的“文件”和“地址”。

图1-3：观察点窗口（未启动调试）

图1-4：观察点窗口（启动调试）

演示模式

当CP Lab工具栏上的“演示模式”按钮高亮显示时（如图1-5所示），CP Lab处于演示模式。当在演示模式下调试观察点函数时，会忽略掉其函数体中的所有代码和断点，取而代之的是使用CP Lab提供的演示功能对观察点函数的执行过程和返回值进行演示。此特性可使观察点函数在还未完整实现的情况下，让读者了解到其应该具有的功能和执行过程，从而帮助读者正确实现此函数。

当工具栏上的“演示模式”按钮没有高亮显示时（鼠标点击工具栏上的“演示模式”按钮可以使其切换状态），CP Lab处于非演示模式。在非演示模式下调试观察点函数时，会使用其函数体中的代码和断点。

高亮

图1-5：工具栏上的“演示模式”按钮。

3.9在演示模式下调试项目

读者可以按照下面的步骤，练习在演示模式下调试项目（主要是调试观察点函数）：

1.保证工具栏上的“演示模式”按钮高亮显示。

2.在“调试”菜单中选择“启动调试”（快捷键是F5）。

启动调试后，程序会在观察点函数的开始位置处中断，如图1-6所示。源代码编辑器左侧空白处显示了相应的图标，分别标识了观察点函数的起始位置和结束位置，以及下一行要执行的代码（黄色箭头）。

图1-6：启动调试后，在观察点函数的开始位置中断。

同时，在“转储信息”窗口中（可以选择“调试”菜单“窗口”中的“转储信息”打开此窗口）显示了观察点函数正在操作的数据信息，如图1-7所示。主要包含了如下内容：

1.函数调用信息。对本次观察点函数的调用信息进行了描述。

2.函数返回信息。由于此时刚刚进入观察点函数，所以还无法显示其返回信息。当在观察点函数结

束位置中断时，即可显示其返回信息。主要对观察点函数的返回值或者操作结果进行描述。

3.重要的数据信息。包含了正则表达式和解析树的后序序列的描述，以及对栈中保存的NFA片段的

信息进行了描述，包括：状态名称（用数字表示从1开始）转换标志以及转换到的状态。当程序运行到观察点结尾的位置时还会显示返回结果用以验证项目（验证项目会在后面详细描述）

图1-7：在观察点函数开始位置中断时的“转储信息”窗口。

按照下面的步骤继续调试：

1.在“调试”菜单中选择“继续”（快捷键是F5）。

由于是在“演示模式”下调试观察点函数，CP Lab会忽略掉函数体中的所有代码，取而代之的是使用CP Lab提供的演示功能对观察点函数的执行过程进行演示。所以CP Lab会自动打开“演示流程”窗口（可以选择“调试”菜单“窗口”中的“演示流程”打开此窗口），在其中显示观察点函数的演示流程，如图1-8所示。

观察点函数的演示流程通常采用简洁、直观的语言进行描述（一行描述可能会对应多行C源代码），偶尔也会在读者理解起来比较困难的地方提供C源代码的提示或者直接使用C源代码，目的就是为了方便读者将演示流程快速转换为C源代码。在“演示流程”窗口左侧的空白处，同样使用黄色箭头标识出了下一行要执行的代码（流程）。

按照下面的步骤继续调试：

2.在“调试”菜单中重复选择“继续”，直到在观察点函数的结束位置中断。CP Lab会单步执行“演

示流程”窗口中的每一行（包括循环）。

在调试的过程中，每执行“演示流程”窗口中的一行后，仔细观察“转储信息”窗口内容所发生的变化，例如构造单字符 NFA 片段，构造连接NFA片段等，理解NFA片段构造的执行过程。当在观察点函数的结束位置中断时，“转储信息”窗口中将显示函数的返回信息。

按照下面的步骤结束此次调试：

1.在“调试”菜单中重复选择“继续”，直到调试结束。或者，在“调试”菜单中选择“停止调试”。

读者可以在演示模式下重新启动调试，再次执行以上的步骤，仔细体会在“演示模式”下调试观察点函数的过程。

图1-8：“演示流程”窗口。

3.10 验证项目（失败）

这里介绍CP Lab提供的另外一个重要功能：验证功能。

之前提到了main.c文件中的post2nfa函数还不完整，是留给读者完成的。而当读者完成此函数后，往往需要使用调试功能、或者执行功能，来判断所完成的函数是否能够达到预期的效果，即是否与演示时函数的执行过程和返回值完全一致。CP Lab提供的验证功能可以自动化的、精确的完成这个验证过程。

验证功能分为下面三个阶段：

1.在“演示模式”下执行观察点函数（与工具栏上的“演示模式”按钮是否高亮无关），将产生的

转储信息自动保存在文本文件ValidateSource.txt中。

2.在“非演示模式”下执行观察点函数，将产生的转储信息自动保存在文本文件ValidateTarget.txt

中。

3.自动使用CP Lab提供的文本文件比较工具来比较这两个文件。当这两个文件中的转储信息完全

一致时，报告“验证成功”；否则，报告“验证失败”。

当读者完成的函数与演示时函数的执行过程和返回值完全一致时，就会产生完全一致的转储信息，验证功能就会报告“验证成功”；否则，验证功能就会报告“验证失败”，并且允许读者使用CP Lab提供的文本文件比较工具，来查看这两个转储信息文件中的不同之处，从而帮助读者迅速、准确的找到验证失败的原因，进而继续修改源代码，直到验证成功。

按照下面的步骤启动验证功能：

1.在“调试”菜单中选择“开始验证”（快捷键是Alt+F5）。在验证过程中，“输出”窗口会实时显

示验证各个阶段的执行过程（如清单1-1所示），包括转储信息文件的路径、观察点函数的调用信息和返回信息、以及验证结果。由于post2nfa函数还不完整，所以验证失败。

2.使用“输出”窗口工具条上的“比较”按钮（如图1-9所示）查看两个转储信息文件中的内容，

即它们之间的不同之处。

提示：

● 在转储信息文件中，只保存了观察点函数开始位置和结束位置的转储信息，并使用单线进行分隔。

观察点函数多次被调用的转储信息之间，使用双线进行分隔。

● 在转储信息文件中，为了确保验证功能的准确性，某些信息会被忽略掉（不再显示或使用“N/A ”

替代），例如内存中的随机值等。

------ 已启动验证: 项目: RegexpToNFA, 配置: Debug ------

验证第一阶段：正在使用“演示模式”生成转储信息，并写入源文件... 源文件路径：G:\Documents and Settings\Engintime\My Documents\CP Lab\Projects\lab1\Debug\ValidateSource.txt

post2nfa 函数的调用信息：正则表达式到 NFA 。

post2nfa 函数的返回信息：返回 NFA 的开始状态地址。

===========================================================================

验证第二阶段：正在使用“非演示模式”生成转储信息，并写入目标文件...

目标文件路径：G:\Documents and Settings\Engintime\My Documents\CP Lab\Projects\lab1\Debug\ValidateTarget.txt

post2nfa 函数的调用信息：正则表达式到 NFA 。

post2nfa 函数的返回信息：返回 NFA 的开始状态地址。

===========================================================================

验证第三阶段：正在比较转储信息源文件与目标文件的内容

... 比较结果：转储信息源文件与目标文件的内容不同

==================== 验证结果：失败 ====================

清单1-1：在“输出”窗口中显示的验证信息。

图1-9：“输出”窗口工具栏上的“比较”按钮。

3.11 实现post2nfa 函数

文件main.c 中的post2nfa 的函数体还不完整，需要读者补充完整。

提示：

● 在“观察点”窗口中，可以在函数名称上点击右键，选择快捷菜单中的“查看演示流程”，CP Lab

会打开“演示流程”窗口，并显示观察点函数的演示流程。这样，即使在没有启动调试的情况下，读者也可以方便的查看观察点函数的演示流程。 ● 参考演示流程中构造NFA 片段的描述，其中给出了构造单字符NFA 片段和连接NFA

片段的源代码，

这两步操作可以完成对例1正则表达式到NFA 的转换（转换后的NFA 如图1-12所示），读者可以

在“演示模式”下一边调试一边理解源代码的执行过程，在此基础上完成其他形式NFA片段的构造。

对于问号的NFA片段的构造（如图1-15所示），原则上也可以将状态1作为开始状态，状态2作为接受状态，并通过ε-转换来表达接受状态为空的情况。但是如果存在一个或多个NFA片段与问号NFA片段相连接的情况，对于上述的情况就不适用了。因为在本程序中使用的是类似于二叉树的存储结构，一个状态最多只有两个转换指针，所以，必须在原来的基础上再添加两个状态作为开始状态和接受状态。

图1-10：NFA状态图例。

图1-11：表示单字符的NFA片段。

图1-12：表示连接的NFA片段（对应例1）。

图1-13：表示选择的NFA片段（对应例2）。

图1-14：表示星号的NFA片段（对应例3）。

图1-15：表示问号的NFA片段（对应例4）。

图1-16：表示加号的NFA片段（对应例5）

3.12 在非演示模式下调试项目

读者在实现了post2nfa函数后，可以按照下面的步骤，练习在非演示模式下调试项目（主要是调试由读者实现的观察点函数）：

1.在“生成”菜单中选择“生成项目”。如果读者编写的源代码中存在语法错误，修改这些错误，

直到可以成功生成项目。

2.鼠标点击工具栏上的“演示模式”按钮，使其切换到非高亮显示状态。

3.在“调试”菜单中选择“启动调试”。程序会在观察点函数的开始位置处中断。

4.在“调试”菜单中重复选择“逐过程”（快捷键是F10），直到在观察点函数的结束位置中断。CP Lab

会单步执行观察点函数中的每一行源代码。在调试的过程中，每执行一行源代码后，仔细观察“转储信息”窗口内容所发生的变化，例如游标的移动、构造单字符的NFA片段等，理解NFA片段的构造过程。当在观察点函数的结束位置中断时，“转储信息”窗口中将显示函数的返回信息。

以上的练习说明，CP Lab可以让读者在非演示模式下调试项目，并观察“转储信息”窗口内容所发生的变化，从而理解每一行源代码对内存数据的操作结果。如果读者发现所编写的源代码存在异常行为（例如死循环、数组越界访问或者验证失败），可以在非演示模式下单步调试项目，来查找异常产生的原因。

3.13 验证项目（成功）

按照下面的步骤启动验证功能：

1.在“调试”菜单中选择“开始验证”。

如果验证失败，读者可以参考之前的内容来查找原因并修改源代码中的错误，直到验证成功。

3.14 退出CP Lab

按照下面的步骤退出CP Lab：

1.在“文件”菜单中选择“退出”。

2.在CP Lab关闭前会弹出一个保存数据对话框，核对学号和姓名无误后点击“保存”按钮，CP Lab

关闭。

3.在CP Lab关闭后，默认会自动使用Windows资源管理器打开数据文件所在的文件夹，并且选中

刚刚保存的数据文件（OUD文件）。读者可以按照教师的要求，将数据文件备份（例如拷贝到U 盘中或者发送到服务器上），作为本次实验的考评依据。

3.15 总结

读者使用CP Lab进行编译原理实验的步骤可以总结如下：

1.启动CP Lab。

2.用户注册。

3.新建实验项目。

4.在演示模式下调试项目，理解观察点函数的执行过程（通常观察点函数还未完整实现)。

5.结合观察点函数的演示流程，修改观察点函数的源代码，实现其功能。

6.生成项目（排除所有的语法错误）。

7.验证观察点函数。如果验证失败，可以使用“比较”功能，或者在非演示模式下调试项目，从而

定位错误的位置，然后回到步骤5。

8.退出CP Lab并保存数据文件（OUD文件）。

3.16 获得帮助

如果读者在使用CP Lab的过程中遇到问题需要专业的解答，或者有一些心得体会想和其他CP Lab用户分享，欢迎加入CP Lab网上论坛：

●选择CP Lab“帮助”菜单中的“论坛”。

或者

●直接访问https://www.wendangku.net/doc/4116531941.html,/forum

这里列出了读者在使用CP Lab的过程中可能遇到的一些问题和使用技巧，用于帮助读者更好的使用CP Lab，获得最佳的实验效果。

1.读者时常会遇到在自己编写的源代码中存在死循环的情况，这就会造成CP Lab的调试功能，特

别是验证功能无法自行结束。此时，读者可以选择“调试”菜单中的“停止调试”（快捷键是Shift+F5）来强制结束这些功能。随后，读者可以检查自己编写的源代码，或者在“非演示模式”

下单步调试项目，从而找到造成死循环的原因。

2.读者时常会遇到的另外一个情况是“数组越界访问”。此时，CP Lab会弹出一个调试异常对话框，

读者只要选择对话框中的“是”按钮，就可以立即定位到异常所在的代码行。

3.CP Lab作为一个IDE环境，提供了强大的调试功能，包括单步调试、添加断点、查看变量的值、

查看调用堆栈等。读者在调试过程中可以灵活使用这些功能，提高调试效率。注意，在“演示模式”下，观察点函数中的断点会被忽略。

4.在“演示模式”下，对观察点函数只能进行单步调试（无论是按快捷键F5，还是F10），如果观

察点函数中存在多次循环，会造成调试过程比较缓慢。此时，读者可以选择“调试”菜单中的“结束观察”（快捷键是Shift+Alt+F5），直接跳转到观察点函数的结束位置中断。

5.“输出”窗口、“演示流程”窗口、以及“转储信息”窗口中的文本信息可以被选中并复制（但

是不能修改），读者可以很方便的将这些信息保存下来，用于完成实验报告等工作。

6.CP Lab提供的实验项目通常不会在Windows控制台窗口中打印输出任何信息，因为在“转储信息”

窗口、“输出”窗口中已经为读者提供了足够多的信息。当然，读者也可以根据自己的喜好，使用printf函数，在Windows控制台窗口中打印输出一些信息（这些信息不会对“验证”结果产生任何影响）。如果读者想快速查看程序在Windows控制台窗口中打印输出的信息，可以使用“调试”菜单中的“开始执行”功能（快捷键是Ctrl+F5）。

四、思考与练习

1.编写一个FreeNFA函数，当在main函数的最后调用此函数时，可以将整个NFA的内存释放掉，

从而避免内存泄露。

2.读者编写完代码之后可以对main.c中main函数之前的例2到例5进行一一验证，确保程序可以

将所有形式的正则表达式转换为正确的NFA，并验证通过。

3.对例6、例7、例8的正则表达式进行验证，并画出例7和例8的NFA状态图。

4.详细阅读re2post函数中的源代码，并尝试在源代码中添加注释。然后尝试为本实验中所有的例

子绘制解析树（类似二叉树）。

实验2 NFA 到DFA

实验难度：★★★★☆

建议学时：4学时

一、实验目的

●掌握 NFA 和 DFA 的概念。

●掌握ε-闭包的求法和子集的构造方法。

●实现 NFA 到 DFA 的转换。

二、预备知识

●完成从正则表达式到NFA的转换过程是完成本实验的先决条件。虽然DFA和NFA都是典型的有向

图，但是基于NFA自身的特点，在之前使用了类似二叉树的数据结构来存储NFA，达到了简化的目的。但是，DFA的结构相对复杂，所以在这个实验中使用了图的邻接链表来表示DFA。如果读者对有向图的概念和邻接链表表示法有一些遗忘，可以复习一下数据结构中相关的章节。

●对DFA的含义有初步的理解，了解ε-闭包的求法和子集的构造方法。读者可以参考配套的《编

译原理》教材，预习这一部分内容。

三、实验内容

3.1 准备实验

按照下面的步骤准备实验：

1.启动CP Lab。

2.在“文件”菜单中选择“新建”，然后单击“项目”，打开“新建项目”对话框。

3.使用模板“002 NFA 到 DFA”新建一个项目。

3.2 阅读实验源代码

NFAToDFA.h文件

主要定义了与NFA和DFA相关的数据结构，其中有关NFA的数据结构在前一个实验中有详细说明，所以这里主要说明一下有关DFA的三个数据结构，这些数据结构定义了DFA的邻接链表，其中DFAState结构体用于定义有向图中的顶点（即DFA状态），Transform结构体用于定义有向图中的弧（即转换）。具体内容可参见下面的表格。

main.c文件

定义了main函数。在main函数中首先初始化了栈，然后调用了re2post函数，将正则表达式转换到解析树的后序序列，最后调用了post2dfa函数将解析树的后序序列转换到DFA。

在main函数的后面，定义了一系列函数，有关函数的具体内容参见下面的表格。关于这些函数的参数和返回值，可以参见其注释。

RegexpToPost.c文件

定义了re2post函数，此函数主要功能是将正则表达式转换成为解析树的后序序列形式。PostToNFA.c文件

定义了post2nfa函数，此函数主要功能是将解析树的后序序列形式转换成为 NFA。关于此函数的功能、参数和返回值，可以参见其注释。注意，此函数的函数体还不完整，读者可以直接使用之前实验中编写的代码。

NFAFragmentStack.c文件

定义了与栈相关的操作函数。注意，这个栈是用来保存 NFA片段的。

NFAStateStack.c文件

定义了与栈相关的操作函数。注意，这个栈是用来保存 NFA状态的。

RegexpToPost.h文件

声明了相关的操作函数。为了使程序模块化，所以将re2post函数声明包含在一个头文件中再将此头

文件包含到“main.c”中。

PostToNFA.h文件

声明了相关的操作函数。为了使程序模块化，所以将 post2nfa函数声明包含在一个头文件中再将此头文件包含到“main.c”中

NFAFragmentStack.h文件

定义了与栈相关的数据结构并声明了相关的操作函数。

NFAStateStack.h文件

定义了与栈相关的数据结构并声明了相关的操作函数。

3.3 在演示模式下调试项目

按照下面的步骤调试项目：

1.按F7生成项目。

2.在演示模式下，按F5启动调试项目。程序会在观察点函数的开始位置中断。

3.重复按F5，直到调试过程结束。

在调试的过程中，每执行“演示流程”窗口中的一行后，仔细观察“转储信息”窗口内容所发生的变化，理解NFA到DFA的转换过程。正则表达式a(a|1)* 对应的NFA状态图可以参见图2-1，DFA状态图可以参见图2-2。“转储信息”窗口显示的数据信息包括：

●正则表达式。

●解析树的后序序列。

●NFA向DFA转换过程中构造的ε-闭包。包括元素个数和闭包中的元素。

●DFA 邻接表。包括DFA状态在线性表中的下标，DFA 状态中的 NFA 状态集合以及DFA 状态的转

换链表。在调试的最后，DFA的接受状态会包含在中括号中。

●调用post2nfa函数返回的NFA。详细的内容可以参看之前实验中的相关说明。

图2-1：调用post2nfa函数后返回的NFA

图2-2：NFA对应的DFA