【编译原理】DFA的生成与字符串的识别.doc

实 验 报 告实验项目列表序号实验项目名称成绩01DFA的生成与字符串的识别020304050607080910111213141516总评成绩： 教员签字：一、 实验名称DFA的生成与字符串的识别二、实验目的1.掌握正规文法与FA之间的转换；2.掌握通过DFA识别字符串的具体操作过程。三、实验内容和要求程序A(1)输入输出输入：正规文法输出：FA(2)具体功能本程序的具体功能包括以下两项：1）输入正规文法，并构造其等价的FA；2）对构造出的FA进行判断：是NFA晒是DFA。程序B(1)输入输出输入：DFA，字符串输出：字符串的DFA识别过程(状态转换轨迹)及错误信息或成功识别信息。(2)具体功能本程序的具体功能包括以下4项：1）输入DFA；2）输入一个字符串；3）对输入的字符串用DFA进行识别，并输出识别的过程(DFA状态转换轨迹);4）若DFA成功识别(输入串结束时到达某终态)，则给出成功识别的信息。若字符串不能为DFA所识别(在某状态下遇某输入符不能进行正常的状态转换)，则给出错误信息并结束程序的运行。四、实验环境1硬件环境：PC机2软件环境：Windows操作系统，VC+集成开发环境五、算法设计思想对于程序A，首先考虑的是正规文法的存储。根据情况可以将左右部分开存储，也可采用结构体的方式，将一个文法存储在一个结构体节点里。本程序采用了前者。将每个正规文法的左部存储在x字符组里，右部的终结符存储在y中。在用户输入了正规文法之后，分别考虑两种情况：1.右部只有一个终结符；2.右部有一个终结符和一个非终结符。根据两种情况分别对文法做如下存储：情况一在z里存入默认的终态Z；情况二在z里存储右部的非终结符。然后，为了使结果一目了然，设计者采用简易表格输出了对应FA的初态，终态，状态集，字母表等主要信息。在最后将文法的格式转化成状态矩阵的格式，并输出相应表格。最后，对输入文法本身进行了判断：若存在某一产生式左部和右部终结符均相同，但右部非终结符不同的情况，则输入文法所对应的FA为NFA；反之，若不存在这样的情况则为DFA。对于程序B，根据需要采用了结构体的存储方式。DAF.A用于存储当前状态，DAF.B用于存储输入符，DAF.C用于存储后继状态。变量start用于存储当前状态量，outstr存储已识别通过的状态。开始识别时，读入一个字符，采用顺序查找的方法找到与当前状态和输入符均符合的结点，将此时的DAF.C赋值给start，并存入输出字串outstr。然后循环。若某次查找无法找到对应的后继状态，报错。当查找到终态时，若此时字串也读取完毕则识别成功，若不然则继续。若字串读取完毕而未到终态，报错。六、主要问题与解决方法问题一：对于程序A，当输出状态集和字母表时会出现重复的元素，因此重新使用了字符数组xx，yy，zz来重新存储需要输出的元素，使输出的字符不重复。问题二：对于表格的制作与输出，采用了光标控制的方法。运用gotoxy函数解决了按行和按字符位从左到右的输入局限性，能灵活的控制输入的位置，界面更加友好。七、实验结果按照实验的要求，程序A实现了正规文法到有穷自动机的转换，输出的FA信息较为详细，表格化的输出方式能够让用户清晰的得到自己需要的信息。最后能够准确给出有穷自动机类型的判断，且整个用户界面友好美观。程序B实现了输入DFA的存储以及字符串的识别功能，并能够给出识别的状态转换轨迹。程序使用方法较为简便。以下是程序的用户运行界面截图：程序A运行界面：程序B运行界面： 八、体会、质疑、建议本次实验帮助编写者巩固了关于状态集、初态、终态字母表等基本术语的概念，对实验者熟练掌握正规文法与FA的相互转换、词法分析的基本流程等课堂知识起到了很好的实践作用。对于整个程序的编写也锻炼了程序编写者将算法思想转化为程序代码的能力。本次实验是编译原理课程的第一次实验。课程本身是具有一定难度的，实验的过程使得实验者对课堂上一些晦涩难懂的知识点得到了更好的理解，并且锻炼了编程能力，积累了一定的实践经验，希望编译原理课程能够安排更多的实验课程。九、源代码 程序A代码：#include#include#include#include#include/用以删除多余的中间文件#define M 10void gotoxy(int x,int y) COORD coord; coord.X=x; coord.Y=y; SetConsoleCursorPosition( GetStdHandle( STD_OUTPUT_HANDLE ), coord );void print()/简易画线代码，呵呵,画行直线int i,j;for(i=0;i10;i+)printf();printf();for(i=0;i25;i+)printf();putchar(10);for(i=0;i10;i+)printf( );printf();putchar(10);for(j=0;j3;j+)/画5行直线for(i=0;i10;i+)printf();printf();for(i=0;i25;i+)printf();putchar(10);for(i=0;i10;i+)printf( );printf();putchar(10);for(i=0;i10;i+)printf();printf();for(i=0;i25;i+)printf();putchar(10);void print2(int x)/简易画线代码，呵呵,画行直线int i,j;for(i=0;i12;i+)printf();printf();for(i=0;i12;i+)printf();printf();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+)printf();printf();for(i=0;i12;i+)printf();printf();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(i=0;i12;i+)printf();printf();for(i=0;i12;i+)printf();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(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;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);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);gotoxy(27,n+17+i*2);printf(%c,yi);gotoxy(52,n+17+i*2);printf(%c,zi);putchar(10);putchar(10);for(i=0;in;i+)/判断是DFA还是NFAfor(j=i+1;jn;j+)if(xi=xj&yi=yj&zi!=zj)sign=1;if(sign=1)printf(该FA是NFA。n);else printf(该FA是DFA。n);程序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_HANDLE ), coord );void main()int cnt,len,i=0,j=0,z=0,m=0;char start,endget,strN,outstrN;node DFAM;printf(请输入DFA,字符间用空格分隔:n);docinDFAi.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(start=DFAcnt-1.C&i