词法分析程序报告及用例.doc

题目：词法分析器设计 实验类别： 设计性实验 实验目的： （1）掌握词法分析器的构造过程以及基本方法。 （2）理解正规式、NFA、DFA及最小化DFA的转换过程和方法。 实验内容： 给定一个正规式R=XY*|YX*Y|XYX，请先在练习本上将此正规式转变为NFA、DFA、最小化DFA；对你所完成的最小化DFA进行编程，完成词法分析器工作。 实验原理： 对于正规式 R= XY*|YX*Y|XYX 最小化DFA如下图： 设计分析： 对于给定的正规式的每一个产生式进行编码，可以将正规式分成三个部分进行编码，R=XY*，R=YX*Y和R=XYX。 对于产生式R=XY*，通过统计输入式子字符的个数与字符中Y的个数进行比较，可以判断出输入式是否为正规式R的产生式。 对于产生式R=YX*Y，首先通过判断输入式的第一个字符和最后一个字符是否为Y，是Y就再通过统计输入式子字符的个数与字符中Y的个数进行比较，可以判断出输入式是否为正规式R的产生式。 还要考虑到输入有空格的情况，当输入有空格的时候，从空格后面开始重新算作一个式子。 其他情况输出不属于正规式R。 程序代码： 头文件：search.h包含函数search1()，search2()用于查找输入字符串中X或Y的个数，而函数text()用于检测输入字符串是否属于正规式。 #include iostream.h int m; char s[128],h[128]; //字符数组s是判断输入串中有无空格后的字符串，字符数组h是开始输入的字符串 int count,count2; int search1(char p[],int a) { count=0; for(int d=a;dm;d++) { if(p[d]==Y) count++; } return count; } int search2(char o[],int b) { count2=0; for(int f=b;fm;f++) { if(o[f]==X) count2++; } return count2; } void text(char k[]) { if(k[0]==X) //第一层头字符为X的 { if(m1) {if(k[1]==Y) {if(k[2]==Y) { search1(k,3); //查找字符中Y的个数 if(count==m-3) coutk属于正规式 R = XY* !endl; //符合正规式XY*的字符串 else coutk不属于正规式 R !endl; } else if(k[2]==X) { if(m3) coutk不属于正规式 R !endl; else coutk属于正规式 R = XYX !endl; //符合正规式XYX的字符串 } else coutk不属于正规式 R !endl; } else coutk不属于正规式 R !endl; } else if(m=1) //符合正规式X的字符串 coutk属于正规式 R = X !endl; } else if(k[0]==Y) //第二层头字符为Y的 { if(k[1]==X) { if(k[m-1]==Y) { search2(k,2); //查找字符中X的个数 if(count2==m-3) coutk属于正规式 R = YX*Y !endl; //符合正规式YX*Y的字符串 else coutk不属于正规式 R !endl; } else coutk不属于正规式 R !endl; } else if(k[1]==Y) { if(m2) coutk不属于正规式 R !endl; else coutk属于正规式 R = YY !endl; //符合正规式YY的字符串 }} else coutk不属于正规式 R !endl; //第三层头字符随意的 }