DFA的编程实现(含源代码、实验报告)要点

实验一（一）程序设计语言及其编译器实现概览（2小时）
实验目的：学习一门简单的程序设计语言的定义及其编译器实现
实验任务：针对一门简单的程序设计语言，阅读其定义文档，初步了解其编译器的源代码。
实验内容：
（1）选择一门语言：TINY或其它语言也可（需自备其编译器的源代码）。
（2）阅读其定义文档，了解语言定义的方法，包括：词法、语法、语义、运行时环境、目
标机器、目标语言等内容。
（3）了解其编译器源代码。
 对TINY语言编译器，其源代码由多个文件组成，请弄清楚每个文件的作用是什么。
详情请见《编译原理及实践》第1.7节。请做一个C++工程文件（Win32 Console
Application, tiny.dsp），把它们组织起来，然后编译成可执行文件(tiny.exe)，即为TINY
语言编译器。然后用它编译TINY语言示例源代码(sample.tny)。看看编译生成的目标
文件(sample.tm)是怎样的。要运行目标程序，还需要一个虚拟机，名为TM机。TM
机是以软件形式存在的，其源代码为tm.c，需要编译生成可执行文件tm.exe。然后将
目标程序作为TM机的输入运行TM机即可得到所期待的结果。要求读懂main.c、
globals.h、util.h、scan.h和util.c、scan.c等文件，三人一组进行讨论，给每一行加上
注释，总结你们各自对程序的理解和阅读程序的收获，每组提交1份加了注释的文件
和心得。有能力的同学可加上tm.c。

实验一（二）DFA的编程实现（2小时）
实验目的：通过本次实验，加深对DFA及其识别的语言的理解，学习对一般的DFA的表达
方法与编程实现方法。

实验任务：编写一个C语言程序，模拟实现DFA识别字符串的过程。
实验内容：（1）DFA的输入；（2）DFA的存储与读写；（3）DFA的正确性检查；（4）DFA
的语言集列表显示；（5）DFA的规则字符串判定；

内容说明：
（1）DFA的输入：
分别输入DFA的“字符集”、“状态集”、“开始状态”、“接受状态集”、“状态转换表”
等内容，并保存在设定的变量中。
（2）DFA的存储与读写：
将上述DFA的五元组保存在一个文本文件中，扩展名指定为.dfa。请自行设计DFA文
件的存储格式，并说明其含义。能将保存在内存变量中的DFA写入DFA文件，也能将DFA
文件读入内存中。（思考：对稀疏DFA（转换表中为空的地方较多）或用“或”表达转换的
DFA（如下的测试用例三），如何改进DFA转换表的表达。）
（3）DFA的正确性检查：
检查所有集合的元素的唯一性。
检查“开始状态”是否唯一，并是否包含在“状态集”中。
检查“接受状态集”是否为空，并是否包含在“状态集”中。
检查“状态转换表”是否满足DFA的要求。
检查“状态转换表”并非填满时的处理是否得当…
（4）DFA的语言集列表显示：
输入待显示的字符串的最大长度N，输出以上定义的DFA的语言集中长度≤N的所有
规则字符串。（提示：注意算法中while循环的次数）
（5）DFA的规则字符串判定：
输入（或用字符集随机生成）一个字符串，模拟DFA识别字符串的过程判定该字符串
是否是规则字符串（属于DFA的语言集）。

测试用例：

DFA（一）

DFA（二）
DFA（三）
实验要求：
按照《编译原理及实践》参考书第二章中描述的“while循环+双层case选择”的算法
编程实现一般的DFA。
要求能通过以上三个测试用例的测试。
完成内容中（1）（5）部分，可得C。
完成内容中（1）（2）（5）部分，可得B。
完成内容中（1）（2）（4）（5）部分，可得A。
完成全部内容，可得奖励。

判定算法概要：
准备：开始状态s0, 接受状态集F, 状态转换表T(s, c), sS, c
c = getchar();
s = 开始状态s0;
while ( c != EOF ) // 输入未结束则循环…
{
s = T(s, c);
if (s == NULL)
error();
c = getchar();
}
if (s  接受状态集F)
accept ();
else
error ();

通用DFA存储格式的建议：（用以上的第三个测试DFA为例）
3 // 字符集中的字符个数 (以下两行也可合并成一行)
/ * o // 以空格分隔的字符集。O代表任意非/和*的字符
5 // 状态个数 (以下两行也可合并成一行)
1 2 3 4 5 // 状态编号。若约定总是用从1开始的连续数字表示，则此行可省略
1 // 开始状态的编号。若约定为1，则此行可省略
1 // 结束状态个数。若约定为1，则此行可省略
5 // 结束状态的编号
2 -1 -1 // 状态1的所有出去的转换。按字符集中的字符顺序给出。-1表示出错状态
-1 3 -1
3 4 3
5 4 3
-1 -1 -1

实验报告：
同时上交纸质报告与电子版报告。纸质报告以实验分析、实验中遇到的问题及解决方
法、实验测试（含屏幕截图）、实验心得等为主，不得大量引用源程序（引用源程序总行数
不得超过100行）。电子版报告以源程序、测试用例、输出文件等为主，包括纸质报告的电
子版，须确保提并的源程序能编译运行，否则不要上交。电子版请发送到248133074@qq.com，
邮件标题请写明学号、姓名与实验编号，形如：<实验一> <学号> <姓名>。不得抄袭实验报
告与源程序，否则后果自负！
提高内容：
（1）图形化的用户界面；
（2）任意DFA的状态转换图、状态转换表的图形绘制；

附实验报告 源码
实验一DFA的编程实现
实验目的：
通过本次实验，加深对DFA及其识别的语言的理解，学习对一般的DFA的表
达方法与编程实现方法。

实验任务：
编写一个C语言程序，模拟实现DFA识别字符串的过程。

实验内容：
（1）DFA的输入；（2）DFA的存储与读写；（3）DFA的正确性检查；（4）
DFA的语言集列表显示；（5）DFA的规则字符串判定；

实验分析：
DFA的初始化
一个DFA的基本信息 状态集、字符集、开始状态、结束状态集、状态转换
表；
在程序中状态集、字符集、开始状态、结束状态集都用string类型来表示，
即可不用考虑用户输入内容的长度。但缺点是字符集只能是字符而不可以是字符
串。
状态转换表：为三个字符的字符串，第一个为当前状态，第二个为输入字符，
第三个为下一状态。 用vector容器存放转换函数的内容

字符串判断
初始化一个DFA，后可以通过一下算法判断一个字符串是否符合该DFA。
判定算法概要：
准备：开始状态s0, 接受状态集F, 状态转换表T(s, c), sS, c
c = getchar();
s = 开始状态s0;
while ( c != EOF ) // 输入未结束则循环…
{
s = T(s, c);
if (s == NULL)
error();
c = getchar();
}
if (s  接受状态集F)
accept ();
else
error ();

在实际编写代码中的体现为
void identify() //判断字符串
{
cout<<"请输入字符串"<string str;
cin>>str;
int i=0;
char present=StartStates;
while(i{
present=move(present,str[i]);//move函数即去遍历转换表，返
回下个状态
if(present=='N') // N 即为move返回错误的状态，
{
break;
}
i++;
}
if(FinalStates.find(present)!=FinalStates.npos)//如果返回
的状态用find函数 属于最终状态集则表示识别
cout<<"该自动机识别此字符串"<else
cout<<"该自动机不识别此字符串"<}

对DFA的存储与读写
将DNF的信息写入文件中，
第一行：字符集；
第二行：状态集;
第三行：开始状态；
第四行：结束状态集；
以下行写入状态转换表

按照既定的规定读取文件
中的数据将其赋值，然后
初始化DFA即可；

DFA的语言集列表显示：
这一个模块应该是这个实验中比较难的一部分了。我并没有使用while循环的
这个做法。而是用函数递归，通过所有字符集的路径去遍历整个DFA。最后将符
合条件的字符串输出；
void Traversal(char present, int N,string strass="")//遍历DFA的语
言集列表
{
if(present=='N'||N<0)//若路径已经大于N或者当前状态错误，停止递归
return;
N--;
if(FinalStates.find(present)!=FinalStates.npos)
{
cout<<"该自动机识别字符串:"<}
for(int i=0;i{
string temp;
temp=strass;
strass+=Alphabet[i];
Traversal(move(present,Alphabet[i]),N,strass);
strass=temp;
}
}
递归终止条件的判断。
当N-- 时， N小于0，或者遍历到无路可走是便终止

遇到的问题:
对于递归的终止条件写得不够明确。 递归前对字符串赋值strass赋值，递归后应该还
原，这一点没有想到。调试了很久。 总结，对递归的具体编写 还是不熟悉。
目前的代码，字符集和状态只能是一个字符，若要优化可以用vector容器
存储即可；
实验用例：