DFA的生成与字符串的识别

1、实验报告实验项目列表序号实验项目名称成绩01DFA的生成与字符串的识别020304050607080910111213141516总评成绩：教员签字：一、实验名称DFA的生成与字符串的识别二、实验目的1. 掌握正规文法与FA之间的转换；2. 掌握通过DFA识别字符串的具体操作过程。三、实验内容和要求程序 A(1) 输入输出输入：正规文法输出：FA(2) 具体功能本程序的具体功能包括以下两项：1 )输入正规文法，并构造其等价的 FA；2) 对构造出的FA进行判断：是NFAB是DFA程序 B(1) 输入输出输入：DFA字符串输出：字符串的DFA识别过程（状态转换轨迹）及错误信息或成功识别信息。（2

2、） 具体功能本程序的具体功能包括以下 4 项：1）输入 DFA；2）输入一个字符串；3）对输入的字符串用 DFA进行识别，并输出识别的过程（DFA状态转换 轨迹）;4）若DFA成功识别（输入串结束时到达某终态），则给出成功识别的信息。 若字符串不能为DFA所识别（在某状态下遇某输入符不能进行正常的状 态转换），则给出错误信息并结束程序的运行。四、实验环境1硬件环境：PC机2.软件环境：Windows操作系统，VC+集成开发环境五、算法设计思想对于程序A,首先考虑的是正规文法的存储。根据情况可以将左右 部分开存储，也可采用结构体的方式，将一个文法存储在一个结构体节 点里。本程序采用了前者。将每个

3、正规文法的左部存储在 x 字符组里，右部的终结符存储在 y 中。在用户输入了正规文法之后，分别考虑两种情况：1. 右部只有一个终结符； 2. 右部有一个终结符和一个非终结符。 根据两种情况分别对文法做如下存储：情况一在 z 里存入默认的终态Z情况二在z里存储右部的非终结符。然后，为了使结果一目了然，设计者采用简易表格输出了对应 FA 的初态，终态，状态集，字母表等主要信息。在最后将文法的格式转化 成状态矩阵的格式，并输出相应表格。最后，对输入文法本身进行了判断：若存在某一产生式左部和右部 终结符均相同，但右部非终结符不同的情况，则输入文法所对应的 FA 为NFA反之，若不存在这样的情况则为 D

4、FA对于程序B,根据需要采用了结构体的存储方式。 DAF.A用于存 储当前状态， DAF.B 用于存储输入符， DAF.C 用于存储后继状态。 变 量 start 用于存储当前状态量， outstr 存储已识别通过的状态。开始 识别时，读入一个字符，采用顺序查找的方法找到与当前状态和输入符 均符合的结点，将此时的 DAF.C 赋值给 start ，并存入输出字串 outstr 。然后循环。若某次查找无法找到对应的后继状态，报错。当 查找到终态时，若此时字串也读取完毕则识别成功，若不然则继续。若 字串读取完毕而未到终态，报错。六、主要问题与解决方法问题一：对于程序A,当输出状态集和字母表时会出现

5、重复的元素， 因此重新使用了字符数组 xx ，yy ，zz 来重新存储需要输出的元素， 使输出的字符不重复。问题二：对于表格的制作与输出，采用了光标控制的方法。运用 gotoxy 函数解决了按行和按字符位从左到右的输入局限性， 能灵活的控 制输入的位置，界面更加友好。七、实验结果按照实验的要求，程序A实现了正规文法到有穷自动机的转换，输 出的FA信息较为详细，表格化的输出方式能够让用户清晰的得到自己需 要的信息。最后能够准确给出有穷自动机类型的判断，且整个用户界面 友好美观。程序B实现了输入DFA的存储以及字符串的识别功能，并能够给出 识别的状态转换轨迹。程序使用方法较为简便。以下是程序的用户

6、运行界面截图：程序A运行界面：*C：!1U&er&Admini5-tratorDe：lctcBpS1 Debug LDFAexe*请输入正规文社;S_aflS hRS _aB_aS程序B运行界面:障输入硕，字符间用空格分隔,S a. AS a BA a A请输入IWm-字符间用空格分隔: a角A b Bi青输入须识別的宇符串*识别成功！ 狀态转離轨迹知S A ft A Bfress ny ket/ to continueG b BA a A请输入须识别的字符串=a.aLa-3-hib识别错误，再见！Press anv hey to continueA_aD八、体会、质疑、建议本次实验帮助编写者

7、巩固了关于状态集、初态、终态字母表等基本 术语的概念，对实验者熟练掌握正规文法与 FA的相互转换、词法分析的 基本流程等课堂知识起到了很好的实践作用。对于整个程序的编写也锻 炼了程序编写者将算法思想转化为程序代码的能力。本次实验是编译原理课程的第一次实验。课程本身是具有一定难度 的，实验的过程使得实验者对课堂上一些晦涩难懂的知识点得到了更好 的理解，并且锻炼了编程能力，积累了一定的实践经验，希望编译原理 课程能够安排更多的实验课程。九、源代码程序A代码：#include#include#include#include#include/ 用以删除多余的中间文件#define M 10 void

8、gotoxy(int x,int y)COORD coord;coord.X=x;coord.Y=y;SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HAND)L, E coord );void print()/ 简易画线代码，呵呵 , 画行直线int i,j;for(i=0;i10;i+)prin tf();prin tf();for(i=0;i25;i+)printf( );putchar(10); for(i=0;i10;i+)printf( );printf(| );putchar(10);for(j=0;j3;j+)/画 5 行直

9、线for(i=0;i10;i+)prin tf(); prin tf( +); for(i=0;i25;i+)printf();putchar(10); for(i=0;i10;i+)printf( ); printf( | ); putchar(10);for(i=0;i10;i+)printf();prin tf(丄); for(i=0;i25;i+)printf();putchar(10);void print2(int x)/简易画线代码，呵呵 , 画行直线int i,j;for(i=0;i12;i+)prin tf(); prin tf(); for(i=0;i12;i+)print

10、f( ); prin tf(); for(i=0;i13;i+)printf( ); putchar(10); for(i=0;i12;i+)printf( );printf(| );for(i=0;i12;i+)printf( );printf( | );putchar(10);for(j=0;jx;j+)/画 5 行直线for(i=0;i12;i+)prin tf(); prin tf(+);for(i=0;i12;i+)printf( ); prin tf(+);for(i=0;i13;i+)printf( ); putchar(10); for(i=0;i12;i+)printf( )

11、; printf(| );for(i=0;i12;i+)printf( ); printf( | ); putchar(10); for(i=0;i12;i+)printf( );prin tf(丄);for(i=0;i12;i+)prin tf(); printf( 丄); for(i=0;istr;if(strlen(str)=3)/*输入产生式为 S_a 型*/xi=str0;yi=str2;zi+=Z;else if(strlen(str)=4)/*输入产生式为 S_aB型*/xi=str0;yi=str2;zi+=str3;else printf( 输入错误，再见！ n),exit(

12、0);for(j=0;jendget;gotoxy(0,n+1);printf();gotoxy(0,n+1);while(endget!=Y); printf(nn 对应的 FA:n);print();/* 制表函数 */gotoxy(0,n+5);printf( 状态集 Q);gotoxy(22,n+5);for(i=0;in;i+)for(j=0;jcnt;j+) if(xi=xxj)break;if(j=cnt)xxcnt+=xi;for(i=0;icnt;i+)printf(%c ,xxi);printf(Znn字母表刀);gotoxy(22,n+7); cnt=0;for(i=0;

13、in;i+)for(j=0;jcnt;j+) if(yi=yyj)break; if(j=cnt)yycnt+=yi;for(i=0;icnt;i+)printf(%c ,yyi);putchar(10);putchar(10);printf( 初态 q0);gotoxy(22,n+9);printf(%c,x0);putchar(10);putchar(10);printf( 终态 Z); gotoxy(22,n+11); printf(Z);putchar(10);putchar(10);printf( 状态转换矩阵 n);print2(n);/* 制表函数 */gotoxy(8,n+15

14、);printf( 现态 ); gotoxy(35,n+15);printf( 输入符 ); gotoxy(60,n+15);printf( 后继态 );for(i=0;in;i+)gotoxy(2,n+17+i*2);printf(%c,xi);VzINSVZICI&=(+uvo上)_(OL)eu9nd_(OL)eu9nd 宀rBNo%=)t3d*+L+U79MXOO6二二 A=o%=)匕 d 命*+L+u20)AXOo6厂三 H-n-丄菸 .fcuE SQ 厂三ZIN ?H-菸 =)壬一d(LHUQSM 宀 UQSSZ 丄二 z 鸽曰 AH二拐豊 XH二 X)七 (+ruvr L+HE04

15、程序 B 代码：#include#include#include#include#include/ 用以删除多余的中间文件#define M 30/DFA 最多的 delta 函数个数#define N 40/ 能识别的最大字符串长度typedef struct schar A;char B;char C;node;void gotoxy(int x,int y)COORD coord;coord.X=x;coord.Y=y;SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HAND)L, Ecoord );void main()int cn

16、t,len,i=0,j=0,z=0,m=0;char start,endget,strN,outstrN;node DFAM;printf(请输入DFA字符间用空格分隔：n);doci nDFAi. A;cinDFAi.B;cinDFAi.C;i+;printf( 是否结束输入？ (Y/N)：);cinendget;gotoxy(0,i+1);printf();gotoxy(0,i+1);while(endget!=Y);cnt=i;printf( 请输入须识别的字符串 :n); cinstr;outstrm+=start=DFA0.A;len=strlen(str);for(i=0;i=len;i+)if(star